« 長井ツアーの締め切りは | トップページ | ペットボトルのリサイクルについて考える »

巡回セールスマン問題

巡回セールスマン問題の解法について
 M05UC525 やまだはるひろ

 巡回セールスマン問題(Traveling Salesman Problem TSPと略記)とは、多くの町と各町間の移動コストが与えられたとき、全ての町を一度だけ回って戻ってくるルートのうちコスト最小のものを求める問題である。この問題は、NP困難であることが知られている。
 解は確実に存在し、総当りをすれば必ずとける組合せ最適化問題の代表問題である。
 要素数(町の数)分の総当りでなければ、一部の特殊例を除き、最適解かどうか検証は困難である。しかし最適解を求める総当りの厳密解法では、要素数(町の数)が増加した場合はその処理時間が問題となるため、近似解を近似アルゴリズムやヒューリスティクスにより求めること現実的である。

厳密解法
 最適解を求めることが出来る。
 総当り法(しらみ潰し法)
  = 全要素を総当りで検証し、得られた解の中でもっとも最適なものを得る方法。 プログラム的にはデータ構造やループの方法などで処理時間に差が出るため。実装方法において多くの手法が検討されている。
 分枝限定法(厳密解法)
 = 総当り法を行うにあたり明らかに処理の無駄と考えられる部分を除外し、演算回数の削減を図る方法。
 「明らかに処理の無駄」な部分のみを演算しないため 総当り法同様 厳密な 最適解が得られる。
 「明らかに処理の無駄」であることをより効率的に判断するために、多種な解法が存在する。

近似解法
 処理時間を実用的とするために、近似解を求める方法。近似率と処理時間で評価されるが、その評価法にも所見がある。
 分岐限定法にあたり、なんらかの理由で無駄と考えられる部分を除外し演算回数の削減を図る方法。
 何らかの理由があるため 求められる解の精度に(何らかの)保証がある。

ヒューリスティック 発見的解法
= 良いと思われる解を探索する解法。解の精度に保証は無い。問題によっては、発散してしまう場合がある。TSPにおいては、限定した範囲の最適化を行う改善法 のバリエーションで解かれることが多い。
  構築法
  改善法
  近傍改善法(山登り法)
  逐次改善法
  焼きなまし法(アニーリング法)
  禁断探索法 (タブーサーチ)
  遺伝解法

« 長井ツアーの締め切りは | トップページ | ペットボトルのリサイクルについて考える »

大学院通院生活」カテゴリの記事

コメント

コメントを書く

(ウェブ上には掲載しません)

トラックバック


この記事へのトラックバック一覧です: 巡回セールスマン問題:

« 長井ツアーの締め切りは | トップページ | ペットボトルのリサイクルについて考える »

特選サイト


  • Kinki students Biped-robot League
    近畿学生2足ロボリーグ

  • 大阪市広報twitter

  • Phenix-03

  • 北海道は不景気だけど。

    ばんえい競馬を観に行きたい!


  • はりまロボットスクールプロジェクト

2020年5月
          1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31            
無料ブログはココログ