ジュンカイセールスマンモンダイ

デジタル大辞泉

じゅんかいセールスマン‐もんだい〔ジユンクワイ‐〕【巡回セールスマン問題】

読み方：じゅんかいせーるすまんもんだい

あるセールスマンが複数の都市を一度ずつ訪れるとき、どのような順番で巡回すれば総移動時間（移動距離または交通費）を最小にできるかを問う問題。グラフ理論の有名な問題の一つであり、都市（ノード）の数が大きくなると計算量が爆発的に増えることが知られている。同種の問題は、荷物の配送や集積回路の配線などに応用される。

IT用語辞典バイナリ

巡回セールスマン問題

読み方：ジュンカイセールスマンモンダイ
【英】traveling salesman problem

巡回セールスマン問題とは、組み合わせ最適化問題の一つで、「ある都市を出発したセールスマンの移動距離が最小値を取るように、すべての都市を一度ずつ必ず訪問して出発点に戻るための経路を求める」を求める問題のことである。旅商人問題とも言う。もともとは米ランド社が提出した懸賞問題である。

巡回セールスマン問題をコンピュータで特には、任意のnに対して最適解を求める解法のうち、最も短い時間で最適解が得られる解法でも、実行時間が2の二乗に比例する。それゆえ、現在の主流であるノイマン型デジタル計算機では、最適解を求めることが難しいといわれている。

このため、ニューラルネットワーク、進化論的（遺伝的アルゴリズム）アルゴリズムを利用した方法やアニーリング法といった生物を模倣した新しい計算手法の有効性を示す方法として、巡回セールスマン問題をいかに短時間で解けるかが試金石として利用されている。

なお、今日では運送会社の配送ルートの計画から、VLSIの設計など、その解法は様々な場面で応用されている。

情報処理のほかの用語一覧

アルゴリズム：

選択ソート  シェルソート  識別子  巡回セールスマン問題  昇順  シーケンシャルサーチ  挿入ソート

>>アルゴリズムカテゴリの他の用語