巡回セールスマン問題(TSP)とは
巡回セールスマン問題はとても有名で、NP困難の話をするときによく出てくる問題の一つです。多少のバリエーションはあるかもしれませんが、基本的には、「グラフが与えられたときに、全ての頂点を1度ずつ通り、帰ってくる経路のうち、最もコストの低い経路を求める」という問題です。
この巡回セールスマン問題ですが、一言に巡回セールスマン問題と言っても様々なグラフについてのものが現代まで考えられてきました。以下に3つほど紹介します。
TSP
任意のグラフについての巡回セールスマン問題です。
この問題は当然NP困難で、さらには近似すら多項式近似ではできないということが知られています。
この話は後述して深堀りしたいと思います。
Metric TSP
Metric TSPはグラフの辺の重みが三角不等式を満たす場合の巡回セールスマン問題です。寄り道をするよりもまっすぐ向かう方がコストが小さいという自然な仮定です。Δ-TSPと呼ぶこともあります。
Metric TSP問題はNP困難ですが、近似については多項式時間で可能です。最小全域木(MST)の深さ優先探索を使った近似率2のアルゴリズムや、それに最小重み完全マッチングを加えて少し改良した近似率1.5のクリストフィードのアルゴリズムが有名です。
実は巡回セールスマン問題の話をするときにこのクラスの話を仮定しているということもあります。
最近、巡回セールスマン問題の最良の近似解を求めるアルゴリズムが更新されたという話が少し話題になったことは記憶に新しいかもしれません。
[2007.01409] A (Slightly) Improved Approximation Algorithm for Metric TSP
https://arxiv.org/abs/2007.01409
しかし、前述したように任意のグラフについての巡回セールスマン問題の近似は多項式時間ではできません。つまり、論文のタイトルにもあるように、これはMetric TSPの話です。
Euclidean TSP
Euclidean TSPは、Metric TSPをさらに条件づけたもので、グラフの頂点に座標を割り当て、その頂点間のユークリッド距離を辺の重みにしたものです。これはつまり、ある都市からある都市へ行くときに、直線でまっすぐ行くことができるという仮定になるので、現実的な仮定でないことも多いです。
そして、ここまで厳しい条件をつけても巡回セールスマン問題はNP困難です。しかし、近似についてはとても正確に近似できるアルゴリズムが知られており、近似率$1+\epsilon$の多項式時間アルゴリズムが知られています。$\epsilon$としてとても小さな数を選択してアルゴリズムを実行することで、とても正確な近似解が得られます。
近似アルゴリズム
さて、ここまで特に定義せず近似アルゴリズムの話をしてきましたが、もう少しきちんと近似アルゴリズムについて見ていきたいと思います。
近似率
近似率は、近似アルゴリズムがどれほどいい精度で解を近似できるかの指標です。本来は最大化問題と最小化問題について定義する必要がありますが、巡回セールスマン問題は最小化問題なので、最小化問題についての定義に沿います。ここでの近似率とは、「最適解のコストの何倍以内のコストで収まる許容解を出力できるか」ということです。形式的に書くと、最適解(セールスマンが通るベストな経路)を$\mathbf{o}$、許容解(セールスマンが通るベターな経路)を$\mathbf{a}$、解のコスト(その経路の重みの和)を求める関数を$\mathrm{cost}$とすると、近似率$\delta$のアルゴリズムが求める許容解$\mathbf{a}$について、次が成立します。
$$
\mathrm{cost}(\mathbf{o}) \le \mathrm{cost}(\mathbf{a}) \le \delta \mathrm{cost}(\mathbf{o})
$$
というのも、許容解が最適解よりもいい解(コストが小さい解)になるはずがなく、またそのコストが悪すぎてもだめなので、最適解のコストのせいぜい$\delta$倍で抑えられるような許容解を求めるアルゴリズムについて考えましょうと言うことです。
上で少し触れた、Metric TSPの2近似アルゴリズムというのは、最適な経路に比べてせいぜいコスト2倍で済むような経路を求めるアルゴリズムということになります。
任意のグラフでは、TSPは定数近似すら多項式時間ではできない
では、今回の本題です。任意のグラフでのTSPでは、最適解の定数倍以下のコストで済むような経路を、多項式時間で求めるアルゴリズムは存在しないということをなぞっていきます。
証明の概要としては、もしそのようなアルゴリズムが存在すると、任意のグラフについてのハミルトン閉路問題(すべての頂点をちょうど1度ずつ通って返ってくる経路があるかどうかを判定する問題)を多項式時間で解けることになってしまうが、ハミルトン閉路問題はNP完全なので、P≠NPである限り多項式時間で解けることはおかしい、という流れです。
つまりは背理法です。早速「任意のグラフのTSP問題を多項式時間で近似する、近似率が定数$\delta$のアルゴリズム」$\mathcal{A}$が存在すると仮定しましょう。
まずは、ハミルトン閉路問題を考えたい$n$頂点のグラフ$G_\mathrm{hamilton}$を考えます。次に、そのグラフ$G_\mathrm{hamilton}$を完全グラフ(すべての頂点間に辺があるグラフ)にしたグラフ$G_\mathrm{tsp}$を考えます。このグラフ$G_\mathrm{tsp}$の辺の重みは、元のグラフ$G_\mathrm{hamilton}$で辺があった場合は1、なかった場合は$(\delta-1)n+2$と(恣意的に)設定します。
さて、このようにして作ったグラフ$G_\mathrm{tsp}$で、先ほど存在を仮定した定数近似アルゴリズム$\mathcal{A}$を動作させてみます。
まず、もとのグラフ$G_\mathrm{hamilton}$でハミルトン閉路が存在した場合、作られたグラフ$G_\mathrm{tsp}$での巡回セールスマン問題の最適解は、もとのグラフ$G_\mathrm{hamilton}$のハミルトン閉路で、そのコストは$n$です(辺のコストは1で、頂点数$n$と同じ数の辺を通るため)。そのため、存在を仮定した定数近似アルゴリズムが求める経路のコストは$\delta n$以内ということになります。
次に、もとのグラフ$G_\mathrm{hamilton}$でハミルトン閉路が存在しなかった場合、作られたグラフ$G_\mathrm{tsp}$での巡回セールスマン問題の最適解は、少なくとも1つの新たに作った重み$(\delta-1)n+2$の辺を少なくとも1度は通ることになります。つまり、そのコストは、$n-1 + (\delta-1)n+2 = \delta n + 1$以上になります。そして、存在を仮定した近似アルゴリズムが求める許容解は、最適解よりもよいコストの経路を求めることはできないことから、そのまま$\delta n + 1$以上となります。
さて、整理しましょう。元のグラフ$G_\mathrm{hamilton}$にハミルトン閉路があった場合、存在を仮定したアルゴリズム$\mathcal{A}$は、多項式時間で、コスト$\delta n$以下の経路を求めました。そして、元のグラフ$G_\mathrm{hamilton}$にハミルトン閉路がなかった場合、存在を仮定したアルゴリズム$\mathcal{A}$は、多項式時間で、コスト$\delta n + 1$以上の経路を求めました。つまり、求めた経路のコストが$\delta n$以下であれば元のグラフはハミルトン閉路を持ち、$\delta n + 1$以上であれば、元のグラフはハミルトン閉路を持たないということになります。つまり、存在を仮定したアルゴリズム$\mathcal{A}$を使うことで多項式時間でハミルトン閉路問題を解くことができるということになります。
しかし、前述の通り、ハミルトン閉路問題はNP完全です。多項式時間で解くことはできないと予想されています。では、何がおかしかったかというと、背理法の仮定、「任意のグラフのTSP問題を多項式時間で近似する、近似率が定数$\delta$のアルゴリズム」$\mathcal{A}$が存在するということが誤りということになります。
以上から、任意のグラフでのTSPの定数近似は、多項式時間で行うことはできないということが確認できました。近似すら多項式時間でできないというのはなかなか面白い話だと思います。