巡回セールスマン問題

緑色の● A, B, C, D, E, F, G, H --- 「都市」または「顧客」を表す

各都市をちょうど一回ずつ通るルートのうち， 移動距離が一番短くなるようなルートは?
（各都市間の距離は直線距離で測る）


ルートの案(1)


ルートの案(2)

明らかに下のルートの案(2)の方が移動距離がより小さい （実は移動距離が最小）

「巡回セールスマン問題」 ―― 移動距離最小となる巡回ルートを求める問題

応用

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