巡回セールスマン問題
読み方：ジュンカイセールスマンモンダイ
【英】traveling salesman problem
巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことである。旅商人問題とも言う。もともとは米ランド社が提出した懸賞問題である。
巡回セールスマン問題をコンピュータで特には、任意のnに対して最適解を求める解法のうち、最も短い時間で最適解が得られる解法でも、実行時間が2の二乗に比例する。それゆえ、現在の主流であるノイマン型デジタル計算機では、最適解を求めることが難しいといわれている。
このため、ニューラルネットワーク、進化論的（遺伝的アルゴリズム）アルゴリズムを利用した方法やアニーリング法といった生物を模倣した新しい計算手法の有効性を示す方法として、巡回セールスマン問題をいかに短時間で解けるかが試金石として利用されている。
なお、今日では運送会社の配送ルートの計画から、VLSIの設計など、その解法は様々な場面で応用されている。
|
