【じゅんかいせーるすまんもんだい】
巡回セールスマン問題 とは？
💡 すべての街を回って帰る最短ルートは？コンピュータでも頭を抱える難問
📌 このページのポイント
ひよこ セールスマンが街を回る問題って、カーナビのルート検索と同じこと？
ペンギン先生 似てるけどもっと難しいんだ。カーナビは「A地点からB地点への最短経路」だけど、巡回セールスマン問題は「すべての街を1回ずつ回って出発地に戻る最短ルート」を求めるんだよ。回る順番の組み合わせが爆発的に多いのがポイントだね
ひよこ 10個の街なら何通りくらいあるの？
ペンギン先生 10都市だと約18万通り。これならまだコンピュータで全部調べられる。でも20都市だと約6京通り、30都市だと天文学的な数になって、スーパーコンピュータでも全探索は無理なんだよ
ひよこ じゃあ実際の宅配便のルートってどうやって決めてるの？
ペンギン先生 ひよこ IT以外でも使われるの？
ペンギン先生 工場のロボットアームが基板に穴を開ける順序の最適化、ゲノム解析でのDNA断片の並べ替え、ドローンの巡回経路など、「複数地点を効率よく回る」問題はすべてTSPの仲間だよ
ひよこ いつか完璧に速く解けるようになるのかな？
ペンギン先生 TSPは「P≠NP問題」という数学の未解決問題と深く関わっていて、もし高速に解けるアルゴリズムが見つかったらコンピュータ科学の歴史が変わるレベル。100万ドルの懸賞金がかかっているミレニアム懸賞問題の一つでもあるんだよ
まとめ：ざっくりこれだけ覚えればOK！
「巡回セールスマン問題」って出てきたら「全地点を最短で回るルート探し、でも都市が増えると超大変」と思えればだいたいOK！
📖 おまけ：英語の意味
「Traveling Salesman Problem（TSP）」 ＝ 巡回セールスマン問題
💬 セールスマンが複数の街を営業で回るとき、一番効率のいいルートはどれ？という場面がそのまま問題名になったんだよ