巡回セールスマン問題
【英】traveling salesman problem
巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことである。旅商人問題とも言う。もともとは米ランド社が提出した懸賞問題である。
巡回セールスマン問題をコンピュータで特には、任意のnに対して最適解を求める解法のうち、最も短い時間で最適解が得られる解法でも、実行時間が2の二乗に比例する。それゆえ、現在の主流であるノイマン型デジタル計算機では、最適解を求めることが難しいといわれている。
このため、ニューラルネットワーク、進化論的（遺伝的アルゴリズム）アルゴリズムを利用した方法やアニーリング法といった生物を模倣した新しい計算手法の有効性を示す方法として、巡回セールスマン問題をいかに短時間で解けるかが試金石として利用されている。
TSP多面体
が巡回セールスマン問題
【英】：traveling salesman problem (TSP)
概要
枝に重みを与えたグラフ
において, すべての点を丁度1度ずつ訪問して元に戻る巡回路(ハミルトン閉路)のうち, 総重みを最小にするものを求める問題. グラフの枝が有向であるか無向であるかで大別する. 平面上(あるいは空間内)の
点と各点の間の距離が与えられたとき, すべての点を訪問する順回路のうち最短のものを求める問題, と定義されることもある. 代表的な組合せ最適化問題の1つ.
詳説
点集合 
，枝集合 
から構成されるグラフ 
, 枝 
上の距離 
が与えられたとき，点集合 のすべての点をちょうど1回ずつ経由する巡回路（ハミルトン閉路）で，枝の距離の合計を最小にするものを求める問題を巡回セールスマン問題 (traveling salesman problem) （行商人問題）とよぶ．
特に，距離の対称性（
）を満たすものを対称巡回セールスマン問題，三角不等式（
）を満たすものを三角不等式を満たす巡回セールスマン問題，点集合が 
次元超立方体 ![[0,1]^d\,](http://weblio.hs.llnwd.net/e7/img/dict/orjtn/80fe30c74ba98e326e73076e8a2f4ef5.png)
内に分布しており，
点間の距離が点間のユークリッド距離で定義されたものをユークリッド巡回セールスマン問題 (Euclidean (Euclidian) traveling salesman problem) とよぶ．
巡回セールスマン問題に対する応用は，数百点を扱う基盤配線，運搬経路計画，スケジューリング，数万点を扱う基盤穿孔，X線結晶構造解析 (タンパク質の構造解析)，数百万点を扱うVLSI設計など，さまざまである．また，次世代のVLSI設計においては，数千万点の問題を解く必要があると言われている．
巡回セールスマン問題は，NP困難 (NP-hard) であり, 多項式時間の厳密解法が絶望視されているばかりでなく，近似比が 一定値
で抑えられる多項式時間の近似解法さえ
のもとでは存在しないことが示されている．
三角不等式を満たす対称巡回セールスマン問題に対しては，近似比が 
以下の保証をもつ多項式時間の近似解法が知られている．また， を定数としたときの 次元ユークリッド巡回セールスマン問題に対しては，固定された 
を与えたときに，近似比が 
以下に抑えられる多項式時間の近似解法（近似スキーム）が存在する．
実用的な近似解法としては，最近近傍法 (nearest neighbor method) やセービング法 (saving method) によって構築された巡回路をk-opt法 (
-opt)で改善する方法が一般的である．厳密解法としては，巡回セールスマン問題の多面体構造（TSP多面体(TSP polytope)）を利用した分枝カット法 (branch and cut method) が有効であり，実務的な大規模問題の求解に成功している．
[1] 山本芳嗣, 久保幹雄,『巡回セールスマン問題への招待』, 朝倉書店，1997.
[2] D. L. Applegate, R. E. Bixby, V. Chvatal and W. J. Cook, The Traveling Salesman Problem, Princeton, 2006.
[3] アルゴリズムデータベース http://www-or.amp.i.kyoto-u.ac.jp/algo-eng/db/
| グラフ･ネットワーク： | 完全グラフ 局所点連結度 局所辺連結度 巡回セールスマン問題 平面グラフ 循環フロー 最大フローアルゴリズム |
| 組合せ最適化： | 動的計画 多面体理論 多項式時間アルゴリズム 巡回セールスマン問題 整数計画 施設配置問題 最大クリーク問題 |
「traveling salesman problem」の例文・使い方・用例・文例
- traveling-salesman problemのページへのリンク
