巡回セールスマン問題

旅商人問題とも言う。 もともとは米ランド社が提出した懸賞問題である。 巡回セールスマン問題をコンピュータで特には、任意のnに対して最適解を求める解法のうち、最も短い時間で最適解が得られる解法でも、実行時間が2の二乗に比例する。 それゆえ、現在の主流であるノイマン型デジタル計算機では、最適解を求めることが難しいといわれている。 このため、ニューラルネットワーク、進化論的（遺伝的アルゴリズム）アルゴリズムを利用した方法やアニーリング法といった生物を模倣した新しい計算手法の有効性を示す方法として、巡回セールスマン問題をいかに短時間で解けるかが試金石として利用されている。 なお、今日では運送会社の配送ルートの計画から、VLSIの設計など、その解法は様々な場面で応用されている。