正則グラフの巡回セールスマン問題を解くアルゴリズムの時間計算量

概要

1. はじめに
巡回セールスマン問題 (Traveling Salesman Problem) は, グラフの辺に非負の重みが与えられたとき, すべての頂点を, ちょうど一度ずつ通るハミルトンサイクルのうち, 辺の重みの合計が最小となるものを求める組み合わせ最適化問題のひとつであり, TSP と略される [12].

2007 年に David Eppstein は, 3–正則グラフに対する TSP の時間計算量を O(1.260n) に改善する Forced TSP アルゴリズムと 4–正則グラフに対する TSP の時間計算量を O(1.890n) に改善する確率的アルゴリズムを発表した [8]. その後, 2008 年に Heidi Gebauer により, 4–正則グラフに対する TSP の時間計算量を O(1.733n) に改善する MinHC アルゴリズムが発表された [9], [10]. また, 2014 年に Maciej Li’skiewicz–Martin R. Schuster によって, 3–正則グラフに対する TSP の時間計算量は O(1.2553n) に改善された [13]. 本論文では, 次数が 3 以上の正則グラフに対する TSP の計算時間量を改善する各アルゴリズムを紹介するとともに, 最大次数が 4 である入力グラフのサイズを減らす変形を試みた自身の結果を述べる.

2. 用語の定義
グラフ (graph) G とは, 集合 V, E とひとつの関数 ψ の 3 つの組 (V, E, ψ) をいう. V の元を G の頂点 (vertex) とよび, G の頂点の個数をその位数 (order) という. E は V とは互いに素な集合であり, その元を Gの辺 (edge) という. 両端点が同じ辺をループ (loop) , 同じ 2 頂点を接続している複数の辺を平行辺 (parallel edges) という. ψ は接続関数 (incidence function) とよばれ, G の各辺に G の頂点の対を対応させる. G の各辺 e にひとつの非負の実数を対応させて, e の重み (weight) という.

頂点 v に接続している辺の本数を v の次数 (degree) という. ループが接続しているときは, 1 本あたり 2 と数える. また, すべての頂点の次数が k であるグラフを k–正則グラフ(k–regular graph) という. 頂点と辺が交互に並んだ列をウォーク (walk) という. ウォークに含まれている辺の本数をそのウォークの長さ (length)といい, 2 個の頂点を結ぶ最小のウォークの長さをそれら 2 点の距離 (distance) という. すべての頂点が異なるウォークをパス (path) という. また, 始点と終点とが一致するパスをサイクル (cycle) とよび, 長さが k のサイクルを k–サイクル (k–cycle) という. 特にグラフのすべての頂点をちょうど 1 回だけ通るサイクルはハミルトンサイクル(Hamilton cycle) という.

3. 最大次数が 3 のときの TSP の時間計算量
2007 年に Eppstein によって, 最大次数が 3 の重み付き n 頂点グラフがアルゴリズムに入力されたときの TSP の時間計算量を, O(2 n/3 ) ≈ O(1.260n) に改善する, Forced TSP アルゴリズムが発表された [8]. このアルゴリズムでは, forced edge とよばれる要素をもつ, グラフの辺集合の部分集合 F を考え, 重み付きグラフと F を入力したとき, F のすべての要素を含むようなハミルトンサイクルの最小の重みを出力する. はじめに図 1 のような変形を行って入力グラフのサイズを減らした後, 一回の再帰呼び出し時に問題を 2 つの subproblem に分割して再帰的に解くことで, 時間計算量の改善を図っている. その後, 2014 年にLi’skiewicz–Schuster によって, 問題の分割の際, 時間計算量に影響を及ぼす最悪のケースを減らすことで, 時間計算量は O(21219 n) ≈ O(1.2553n) に改善された [13].

4. Eppstein による最大次数が 4 のときの TSP の時間計算量の改善
2007 年に Eppstein によって, 最大次数が 4 の重み付き n 頂点グラフがアルゴリズムに入力されたときの TSP の時間計算量を, O(( 3 )n2 n ) ≈ O(1.890n) に改善する, モンテカルロ法による確率的アルゴリズムが発表された [8]. このアルゴリズムでは, 次数が 4 の頂点に対して分割処理を行い, 最大次数が 3 のグラフに変形した後, 表 1 の Forced TSP アルゴリズムに適用することで, 時間計算量の改善を図っている.

図 2 のように, 次数が 4 の頂点すべてに分割処理を行った後, 最適解を見つけられる確率を求めて時間計算量の改善を図っている. アルゴリズムを ( 3 )f 回繰り返せば, 最適解が見つかる回数の期待値は 1 となるので, f ≦ n より, 時間計算量は O(( 3 )n2 n ) ≈ O(1.890n) となる. さらに, Li’skiewicz–Schuster によって改良された Forced TSP アルゴリズムを適用することで, 時間計算量を O(( 3 )n2 1219 n) ≈ O(1.8829n) に改善できる.

5. 最大次数が 4 の入力グラフに対する変形
Forced TSP アルゴリズムでは最大次数が 3 の入力グラフに対する変形を行うが, 特定のパターンが含まれている最大次数が 4 の入力グラフに対しても変形を行うことができると考え, そのサイズを減らすことを試みた, 自身の結果について述べる.

6. Gebauer による最大次数が 4 のときの TSP の時間計算量の改善
2008 年に Gebauer によって, n が偶数である最大次数が 4 の重み付き n 頂点グラフがアルゴリズムに入力されたときの TSP の時間計算量を, O(3 n・poly(n)) ≈ O(1.733n) に改善する, MinHC アルゴリズムが発表された [9]. このアルゴリズムでは, 与えられた 2 個の頂点 v1, vm(2 ≦ m ≦ n) に対して, 最小の重み付きサイクルである (v1, vm)–サイクルを見つけることを考える.

アルゴリズムの最初の処理では, 頂点 v1 から出発して, まだ訪れていないすべての近傍の各頂点を再帰的に訪問していくことで, 長さ n のパスを得るためのアルゴリズムとして考えることができる. 2 頂点のペア (v1, vm) の組み合わせは n − 1 通りなので, (v1, vm)–パスの長さは n より, パスに含まれる頂点の個数は n + 1 個となる. そのため, n の多項式を poly(n) で表したとき, (v1, vm)–パスの本数は高々(n − 1)・4・3 n −1 ≈ 3 n・poly(n) 本であり, PL に納められる要素の最大の個数も同じ式で制限できる. したがって, Step 1 の時間計算量は O(3 2・poly(n)) である.

その後の処理では, PL に対するソートと探索の実行にとどまるため, アルゴリズム全体の時間計算量には影響が及ばない. したがって, アルゴリズム全体の時間計算量は, O(3 n・poly(n)) ≈ O(1.733n) である.

また, n が奇数のときは, 頂点 v1, vm が距離 n をもつ (v1, vm)–サイクルの代わりに, 頂点 vi と辺 e がひとつずつ与えられ, e の両端点から vi までの距離がどちらも n−1 をもつハミルトンサイクル, (vi, e)–サイクルを考えることで, n が偶数のときと同様にアルゴリズムを実行できるため, 時間計算量は変わらない.

7. 最大次数が 5 以上のときの TSP の時間計算量
Gebauer の MinHC アルゴリズムに入力するグラフを k–正則グラフとしても, アルゴリズム自体に変更が発生しないため, 4–正則グラフのときと同様に TSP の時間計算量を求めることができる. したがって, k–正則グラフの TSP の時間計算量は O((k − 1) n/2・poly(n)) ≈ O((k − 1) n/2 ) で求められる.