巡回セールスマン問題
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/08/02 08:29 UTC 版)
|
この記事は英語版の対応するページを翻訳することにより充実させることができます。（2024年9月）
翻訳前に重要な指示を読むには右にある[表示]をクリックしてください。
|
巡回セールスマン問題（じゅんかいセールスマンもんだい、英: traveling salesman problem、TSP）は、都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題である。
詳細
問題例の大きさは、都市の数で表される。この問題は、計算複雑性理論においてNP困難と呼ばれる問題のクラスに属する。すなわち、問題例の大きさに関する決定性の多項式時間アルゴリズムが見つかりそうにない、計算量的に困難な問題である。なお、この問題の特殊ケースとして考えられるハミルトン閉路問題は、NP困難であると共にNP完全と呼ばれるクラスにも属するので、扱いが異なる。
都市間の移動コストが三角不等式を満たす、すなわち移動コストを距離と呼べる部分問題（あるいは制約つき問題）も、NP困難である。都市を平面上の点、都市間の距離を平面上のユークリッド距離とする部分問題は最も直感的で理解しやすいが、これも NP困難である。この部分問題は平面TSPなどと呼ばれ、実用上の応用も多く、またベンチマークの問題例としても距離関数の定義が自明なため頻繁に現れる。 都市の間の移動コストを 1 または 2 に制限しても、この問題もNP困難である。ハミルトン閉路問題は、移動コストを 1 または無限大に制限した TSP とみなすことができる。
一方で制約のない巡回セールスマン問題の直接の応用事例は無いと言ってもよい。逆に実際の応用事例では、より複雑な定義で配送計画や表面実装ロボットの動作計画などに適用される。
整数線形計画問題による定式化
巡回セールスマン問題は整数線形計画問題として定式化することができる[1][2][3]。定式化の方法としてはいくつか知られており、そのうち Miller–Tucker–Zemlin (MTZ) 定式化と Dantzig–Fulkerson–Johnson (DFJ) 定式化の2種類が著名な定式化として知られている。DFJ定式化はMTZ定式化と比べて制約によって構成される多面体が厳密に小さいという意味で強い定式化とされているが、MTZ定式化についても特定の状況下では使用される[4][5]。
両者の定式化に共通して与えられる定数は都市 
- 『巡回セールスマン問題の意味と2近似アルゴリズム』 - 高校数学の美しい物語
- Traveling Salesman Problem - TSPのベンチマーク問題集その2 (World TSP，National TSPs, VLSI)
 |
この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。 |
| 典拠管理データベース: 国立図書館 |
|---|
Weblioに収録されているすべての辞書から巡回セールスマン問題を検索する場合は、下記のリンクをクリックしてください。
全ての辞書から巡回セールスマン問題
を検索
- 巡回セールスマン問題のページへのリンク
