巡回セールスマン問題

[英] traveling salesman problem（TSP）
巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことで、最適化問題の代表例として知られている。
もともとはアメリカ合衆国のランド社が提出した懸賞問題である。
都市数が少ないうちは、最適解を求めるのは楽な問題だが、都市数が増えるにしたがって、計算量は2の2乗に比例して増えるため、コンピュータでも最適解を求めるのは難しくなっていき、効率よく厳密な解を求める手法は未だに確立されていない。
そのため、ニューラルネットワークや遺伝的アルゴリズムを利用した方法やアニーリング法などを用いて、近似解を求める方法が一般的である。
ただし、実際にこの問題の解を応用できる事例は多く、配送計画や表面実装ロボットの動作計画などに適用されている。