【じゅんかいせーるすまんもんだい】
巡回セールスマン問題 とは？
最終更新:
💡 すべての地点を回って戻る、最小費用の順番探し
各地点を一度ずつ訪問して出発点へ戻る巡回路のうち、距離や費用の合計が最小のものを求める問題。一般にはNP困難ですが、全候補の列挙しか解法がないわけではなく、個別の大規模問題が最適に解ける場合もあります。
📌 このページのポイント
ひよこ 2地点の最短ルート探しと同じ？
ペンギン先生 基本TSPでは、すべての地点を一度ずつ訪れ、出発点へ戻る順番を選ぶんだ。各地点間の移動費用が決まっていて、その合計を最小にする。ある2地点間だけの最短経路を探す問題とは、選ぶ対象が違うよ。
ひよこ 10地点なら何通り？
ペンギン先生 出発点を固定し、行きと帰りの費用が同じで、逆回りを同一とするなら9!÷2で181,440通り。20地点は19!÷2で60,822,550,204,416,000通りだよ。方向によって費用が違う場合には逆回りを同一にできず、同じ計算式ではないんだ。
ひよこ 全部調べるしかない？
ペンギン先生 そうではないよ。分枝限定や整数計画などを使って最適性を確認する厳密解法がある。よい経路を素早く探すヒューリスティックもあるけれど、一般にはそれだけで最短と証明できない。保証付きの近似も、距離の条件や方式を確認する必要があるんだ。
ひよこ 宅配便もこの問題？
ペンギン先生 訪問順を考える基礎として関係するよ。ただし実際の配送は複数車両、積載量、時間枠、道路の制約などがあり、基本TSPそのままとは限らない。実務の条件を省いて出した最短経路が、そのまま実行できるとは言えないんだ。
ひよこ NP困難なら大きな問題は全部無理？
ペンギン先生 一般の場合に効率よく最適解を得る方法が知られていないことと、個別の問題が解けることは別だよ。研究では大規模な事例の最適解も確認されている。よい経路を見つけることと、それよりよい経路が存在しないと確認することを区別しよう。
もっと詳しく知りたい人へ
P対NPの懸賞金はTSPの短いルートを見つけたらもらえる？
個別のTSPを解くことと、P対NPの数学的な問題を解決することは違います。一般の問題をどう効率よく解けるかという理論の話で、特定の配送ルートを改善しただけでは解決にはなりません。
まとめ：ざっくりこれだけ覚えればOK！
「巡回セールスマン問題」って出てきたら「全地点を回って戻る最小費用の順番探し」と思えばだいたいOK！
📖 おまけ：英語の意味
「Traveling Salesman Problem（TSP）」 ＝ 巡回セールスマン問題
💬 複数の街を営業で回って戻る順番を考える場面に対応する名前です。費用は距離以外でも定義でき、対称な問題と方向で費用が異なる問題があります。