巡回セールスマン問題

巡回セールスマン問題 †

このページは競技プログラミングに興味のある方向けに巡回セールスマン問題を簡単に説明するページです

巡回セールスマン問題って何？ †

TSP(Traveling Salesman Problem)とも表記される有名な問題です。
内容としては

・いくつかの都市があり、各都市感の距離が与えられている
・全ての都市をたどる経路の内、最も短い経路を求める

というものです。

画期的な解き方を見つけたぞ！ †

論文にして出してください。もれなく1億円と世界中の好きな大学で教授待遇で働ける環境がついてきます。

全探索ぐらいしか思いつかないです・・・ †

実は巡回セールスマン問題は"現時点で"効率的な解き方(＝多項式時間で解くアルゴリズム)が見つかっていない問題です
全探索であれば O(N!), もうすこし頭のいい解き方でもO(2^N × N^2)程度かかります(Nは都市の数)
つまりNが10ぐらいまでならまだ何とかなりますが、20ぐらいだと(少なくとも競技プロコンで要求される制限時間内では)もうダメです

効率的な解き方が無いなら競技プロコンだと他の人と差が出ないよね？ †

TSPは大体の場合において他の問題との複合問題である場合が多いです
典型的なのは「都市の位置だけ与えられていて距離は与えられていない」という問題です
これは「各都市間の距離を調べる」→「TSPで最短経路を探索する」という複合問題です
全探索すると確実に解けて、要素数が10程度なら「あ、これはTSPだな」と発見できるかどうかが鍵です

頭のいい解き方を教えて †

競技プロコンにおいては「TSPであることに気付く」ということが大事であって「それを効率的に処理できるか」は基本的にどうでもいいことです
(なぜなら、効率のいい解き方が見つかっていないのですから)
ですから別に知らなくても特に問題はないです
(N＝10が解けてN＝100000が解けないとかならともかく、N＝10が解けてN＝15が解けないということにおいてそこに本質的な差があるでしょうか？)

それでも知りたい †

ざっくりいうとBitDPを使います
部分的な都市の集合Sの最適巡回手順をメモ化して、それを上回る距離の巡回手順を含む経路を省くことでO(2^N × N^2)程度にまで落としこめます