巡回セールスマン問題の意味と2近似アルゴリズム

図は6都市の場合の例です（移動時間は図に書くのが難しいので，例えば二点間の距離と見てください）。青い経路はそれなりに合理的に見えますが，もっとよい経路があるかもしれません。

なお，グラフ理論の言葉を使うと「重み付きグラフに対して，重み最小のハミルトン閉路を求めよ」と述べることができます。

巡回セールスマン問題は「難しい問題」の代表です。実際，都市の巡る順番として $\dfrac{(n-1)!}{2}$ 通り（逆向きに巡るのは同じとみなすので2で割った）の候補があり，総当りで確かめようとすると莫大な計算時間がかかります（階乗は指数関数より大きい＆指数はやばい）。

巡回セールスマン問題はNP-hardです（P≠NP予想が正しいという仮定のもと，多項式時間解法は存在しません）。

厳密な最適解を求めるのが難しいからと言ってそこで諦めてはいけません。厳密解が難しいので近似解を求めにいきましょう。

「最悪でも $c$ 倍」のような近似解が得られるとき，つまり，

近似アルゴリズムの出力解の値 $\leq$$c\times$ 本当の最適値

を満たすような解を出力してくれる近似アルゴリズムを $c$ 近似解法などと言います。

近似アルゴリズムを設計するために，問題に「移動時間が三角不等式を満たす」という仮定を加えます。

つまり，任意の $i,j,k$ に対して $d_{ij}+d_{jk}\geq d_{ik}$ とします。

「寄り道した方が早いことはない」というのは現実的な仮定でしょう。なお，三角不等式を満たすTSPもNP-hardであることが知られています。近似解法が設計できると嬉しいです。

三角不等式を満たすTSPに対する2近似解法を解説します。

注：最小全域木を求めるのは簡単です。例えばクラスカルのアルゴリズムという多項式時間解法があります。

注2： $T$ の枝をコピーしたグラフは全ての頂点の次数が偶数なので一筆書きで一周できます。→オイラーグラフの定理（一筆書きできる条件）とその証明

※2021/8/8追記：「2近似解法のことを2-opt法とも呼ぶ」という旨の誤った記載を消去しました。ご指摘いただきありがとうございました！

「移動時間が三角不等式を満たす」という条件をつけない場合は，P≠NPの仮定のもと，TSPに多項式時間の近似アルゴリズムがないことが証明できます。つまり，どのような定数 $c$ に対しても $c$ 近似解法は存在しません。

証明には，ハミルトン閉路があるかどうかを判定する問題「ハミルトン閉路問題」を使います。