Christofidesアルゴリズムは、度量TSP（Metric Traveling Salesman Problem）に対して、最適解の総コストの 3/2倍以内 という保証付きで近似解を求める有名なアルゴリズムです。以下では、アルゴリズムの前提条件、手順、具体例を交えて、解説します。
1. 問題の背景
旅行セールスマン問題（TSP） は、与えられたすべての都市を一度ずつ訪問し、出発地点に戻る最短経路を求める問題です。しかし、TSPはNP困難であるため、最適解を求めるのは計算量的に現実的ではありません。
度量TSP は、以下の条件を満たすTSPです：
- 非負性：任意の都市間の距離は0以上（自己ループは0）。
- 対称性：( c(i, j) = c(j, i) )（都市間の移動コストは同じ）。
- 三角不等式：任意の3都市 (i, j, k) に対して、( c(i, k) \leq c(i, j) + c(j, k) ) が成り立つ。
これらの条件が成立することで、ある種の近似手法が理論的に保証できるようになります。
2. Christofidesアルゴリズムの手順
Christofidesアルゴリズムは大きく3つのステップに分かれます。
2.1 最小全域木（MST）の構築
- 目的：全都市を含むグラフから、全体の総移動コストが最小となる全域木（MST）を求めます。
- 性質：MSTの総コストは、最適なTSP解のコスト（OPT）以下であるため、基礎として利用可能です。
2.2 奇数次数頂点の最小完璧マッチング
-
奇数次数頂点の抽出：MSTの中で次数が奇数の頂点集合 (O) を求めます。
※グラフの性質上、奇数次数頂点は必ず偶数個存在します。 - 最小完璧マッチングの計算：頂点集合 (O) 上で、全ての頂点をペアに分ける完璧マッチングを求めます。このとき、各ペアの辺の総和が最小となるようにします。
- 目的：このマッチングをMSTに加えることで、すべての頂点の次数を偶数にし、オイラーグラフ（全辺を一度ずつ通る経路が存在するグラフ）を構成します。
2.3 オイラー路の構成とショートカット
- オイラー路の構成：MSTと最小完璧マッチングを合わせたグラフはすべての頂点の次数が偶数になるため、オイラー路が存在します。
-
ショートカット（Shortcutting）：オイラー路は同じ頂点を複数回訪れる可能性がありますが、TSPでは各都市を一度だけ訪問する必要があります。そこで、既に訪問した頂点が再び現れた場合は、直接次の新しい頂点へ移動（ショートカット）します。
※度量TSPでは三角不等式により、ショートカットをしても全体のコストは増加しません。
3. 具体例による説明
例えば、次のような都市と距離が与えられたとします：
| 都市 | A | B | C | D |
|---|---|---|---|---|
| A | 0 | 10 | 15 | 20 |
| B | 10 | 0 | 35 | 25 |
| C | 15 | 35 | 0 | 30 |
| D | 20 | 25 | 30 | 0 |
ステップ1：MSTの構築
- 例：辺 (A)–(B) (10)、(A)–(C) (15)、(A)–(D) (20) を選んだとします。
- MST総コスト：(10 + 15 + 20 = 45)
ステップ2：奇数次数頂点のマッチング
- 奇数次数の頂点：このMSTでは、頂点Aの次数は3（奇数）、B, C, Dの各頂点は次数1（奇数）となります。
- 最小完璧マッチング：例えば、頂点BとDをペアにすると、距離は25となり、これが最小となる組み合わせと仮定します。
ステップ3：オイラー路とショートカット
- グラフ合成：MSTに最小完璧マッチングの辺を加えると、すべての頂点の次数が偶数になり、オイラー路が構成可能です。
- ハミルトン閉路への変換：オイラー路上で、既に訪問済みの頂点が出現した際はショートカットを行い、各都市を一度だけ訪問する巡回路に変換します。
4. アルゴリズムの評価
Christofidesアルゴリズムでは、以下の保証が成り立ちます：
- MSTの性質：( \text{MSTのコスト} \leq \text{OPT} )
- マッチング部分：最小完璧マッチングのコストは ( \leq \frac{1}{2} \times \text{OPT} )
-
総コスト：したがって、最終的なハミルトン閉路のコストは
[
\text{MST} + \text{Matching} \leq \text{OPT} + \frac{1}{2},\text{OPT} = \frac{3}{2},\text{OPT}
]
つまり、Christofidesアルゴリズムによって得られる解は、最適解のコストの ( \frac{3}{2} ) 倍以内に収まることが保証されます。
5. まとめ
- 問題設定：TSPは各都市を一度だけ訪問して最短巡回路を求める問題で、NP困難です。
- 度量TSP：非負性、対称性、三角不等式が成立するTSPであり、近似アルゴリズムが適用可能です。
-
Christofidesアルゴリズムの手順：
- MSTを構築する
- MSTの奇数次数頂点に対して最小完璧マッチングを行う
- MSTとマッチングを合成し、オイラー路を構成 → ショートカットでハミルトン閉路に変換する
- 評価：最終解は最適解の ( \frac{3}{2} ) 倍以内のコストであることが保証される
このアルゴリズムは、複雑なTSP問題に対して、シンプルな手法（MSTとマッチング）を組み合わせることで、計算可能な近似解を提供する点で非常に有用です。