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

離散最適化の有名問題である,巡回セールスマン問題(Traveling salesman problem, TSP)について。問題の意味と簡単な近似アルゴリズムについて解説します。

巡回セールスマン問題とは

問題

都市の数 nn と,二つの都市 iijj の間を移動するのにかかる時間 dijd_{ij} が与えられる。このとき,全ての都市を巡ってもとの都市に戻ってくるような経路のうち,移動時間が最小なものを求めよ。

TSPの具体例

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

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

巡回セールスマン問題の難しさ

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

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

近似アルゴリズム

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

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

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

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

三角不等式を満たすTSP

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

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

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

TSPの2近似解法

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

  1. 最小全域木 TT を求める。

  2. TT の枝をコピーしたグラフを一筆書きで一周する。

  3. 一回通ったとこはショートカットすることで,全都市をちょうど一回巡る閉路にする。

tspの2近似解法

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

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

2近似解法であることの証明
  • TT の重み \leq 真の最適値
  • 2で得られる閉路の長さ= 2×T2\times T の重み
  • 3で得られる閉路の長さ 2\leq 2 で得られる閉路の長さ

より,3で得られる閉路の長さ 2×\leq 2\times 真の最適値

ただし,三つ目の不等式で三角不等式を使った。

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

一般的なTSPに多項式時間近似解法がないことの証明

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

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

証明

TSPの cc 近似解法が存在すると仮定して,矛盾を導く。概要は以下の1~3。

  1. 任意のグラフ GG に対して,下図のようにグラフ GG' を作る。
  2. TSP の多項式時間 cc 近似解法を GG' に適用すると,GG のハミルトン閉路問題が多項式時間で解ける。
  3. ハミルトン閉路はNP-completeなので矛盾。
  • 11 の詳細 ハミルトン閉路問題から巡回セールスマン問題への帰着 GG の頂点をそのままで,完全グラフにしたものを GG' とする。ただし,GG' の枝の長さは,もともと GG に枝があった場合 11,もともと GG には枝がなかった場合長さ cncn とする。ここで,nnGG の頂点数。

  • 2の詳細
    以下のように,TSPの答えから GG のハミルトン閉路の有無が確認できる。

    • もし,GG にハミルトン閉路があった場合,GG' をTSPでとくとその閉路が最短の経路になり,長さは nn になる。
    • 逆に,GG にハミルトン閉路がなかった場合,GG' をTSPでとくと,経路のうち必ず1本は長さ cncn のものが入るので,最短の経路の長さは (n1)+cn(n-1) + cn 以上になる。
  • 3について,ハミルトン閉路問題はNP-completeであることの証明は省略します。

ちなみに,三角不等式を満たすTSPに対してはマッチングを用いた1.5近似アルゴリズムもあります。マッチング素晴らしいですね。