巡回セールスマン問題

例えば,次の絵の中で,緑色の●の A, B, C, D, E, F, G, H は「都市」または「顧客」を表すと思ってください.

ここで,次の問題を考えます. ただし,簡単のために,各都市間の距離は直線距離で 測るものとしましょう.

例えば,以下のような赤色のルートが全ての都市を一巡するルートの候補になります.


ルートの案(1)


ルートの案(2)

この場合,明らかに下のルートの案(2)の方が移動距離が小さくてすみます. 問題は,このようなルートのうち,移動距離が最小になるものを見つける ということになります.

このような移動距離最小となる巡回路を求める問題を「巡回セールスマン問題」 といい,古くから盛んに解法が研究されてきました.

それでは,9都市の場合の問題で遊んでみてください.

9都市の問題で遊ぼう!  最初のページに戻る