巡回セールスマン問題

都市の集合と各2都市間の移動コスト（たとえば距離）が与えられたとき、全ての都市をちょうど一度ずつ巡り出発地に戻る巡回路のうちで総移動コストが最小のものを求める（セールスマンが所定の複数の都市を1回だけ巡回する場合の最短経路を求める）組合せ最適化問題

都市数の増加に対して時間計算量が急速に増加するため、都市数が20以上になると現実的でない

参考文献