2015/05/29

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

分野: グラフ理論  レベル: マニアック

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

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

問題

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

TSPの具体例

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

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

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

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

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

近似アルゴリズム

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

「最悪でも $c$ 倍」のような近似解が得られるとき,つまり,
近似アルゴリズムの出力解の値 $\leq$ $c\times$ 本当の最適値
を満たすような解を出力してくれる近似アルゴリズムを $c$ 近似解法,$c$ -opt法などと言います。

三角不等式を満たすTSP

近似アルゴリズムを設計するために,問題に「移動時間が三角不等式を満たす」という仮定を加えます。
つまり,任意の $i,j,k$ に対して $d_{ij}+d_{jk}\geq d_{ik}$ とします。

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

TSPの2近似解法

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

1.最小全域木 $T$ を求める
2. $T$ の枝をコピーしたグラフを一筆書きで一周する。
3.一回通ったとこはショートカットすることで,全都市をちょうど一回巡る閉路にする。

tspの2近似解法

注:最小全域木を求めるのは簡単(例えばクラスカルのアルゴリズムという多項式時間解法がある)です。
注2:$T$ の枝をコピーしたグラフは全ての頂点の次数が偶数なので一筆書きで一周できます。→オイラーグラフの定理とその証明

2近似解法であることの証明

  • $T$ の重み $\leq$ 真の最適値
  • 2で得られる閉路の長さ= $2\times T$ の重み
  • 3で得られる閉路の長さ $\leq $2で得られる閉路の長さ

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

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

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