克里斯托菲德斯算法

克里斯托菲德斯算法（英語：Christofides algorithm）是旅行商問題在度量空間（即距離對稱且滿足三角不等式）上的一個近似算法。^[1] 該算法可以保證相對最優哈密爾頓迴路長度有3/2的近似比。尼科斯·克里斯托菲德斯（英語：Nicos Christofides）於1976年首次發表了這個算法，故以他的名字命名之。^[2] 截至2017年^[update]，這一算法仍然是一般性旅行商問題的算法中近似比最好的結果。

算法

令 $G = (V, w)$ 是旅行商問題的一個實例。即， $G$ 是一頂點集 $V$ 上的一個完全圖，函數 $w$ 給 $G$ 的每條邊指定了一個非負實邊權。依三角不等式，對每三個頂點 $u$ , $v$ 和 $x$ 都有關係 $w (uv) + w (vx) \geq w (ux)$ .

算法可以被描述為如下偽代碼。

構造圖上的最小的生成樹 T
令 O 為原圖頂點集中在 T 上度數為奇數的頂點集。根據握手定理，O 中有偶數個頂點
構造點集O在原完全圖上的最小完美匹配M
將 M 和 T 的邊集取並，構造重圖 H ，滿足其每個頂點都是偶數度的
H 可以形成一個歐拉迴路
將前一步得到的圖改造為一個哈密爾頓迴路：只需要跳過前一步歐拉迴路中重複的頂點即可（這個步驟又稱作選取近道，"short-cutting"）。

近似比

算法所生成的解相對最優解有3/2的近似比。下給出簡要證明。

令 $C$ 為圖上的最優旅行商迴路。注意到，刪除 $C$ 上的一條邊將產生原圖上的一棵生成樹，其總權重至少為最小生成樹的總權重，亦即 $w (T) \leq w (C)$ 。接下來，給 $O$ 中的頂點編號，編號順序依據迴路 $C$ 上的頂點順序。再將 $C$ 做劃分，得到兩個邊集：其一包含所有起始點為奇數編號的邊，另一個則包含所有起始點為偶數編號的邊。這兩個邊集各對應於 $O$ 上的一個完美匹配，且匹配的總邊權不超過邊集的總邊權。

因為兩個邊集是 $C$ 的劃分，二者中的某一個至多有 $C$ 總邊權的一半，因而其對應匹配的總邊權不超過 $C$ 總邊權的一半。因為沒有比最小完美匹配更小的匹配，所以 $w (M) \leq w (C)/2$ 。 $T$ 和 $M$ 的權重總和也就是歐拉迴路的權重總和，也就是至多 $3 w (C)/2$ 。由於做選取近道操作並不增加權重，所有最終輸出的總邊權也不超過 $3 w (C)/2$ .

下界

存在使得克里斯托菲德斯算法近似比任意接近3/2的輸入。

一類滿足條件的輸入由 $n$ 個頂點組成，滿足最優環路上邊的權重都為 $1$ ，且在最優環路上相隔一條邊的邊都有權重 $1 + ε$ ，其中 $ε$ 是一個足夠小的正數。未由上述定義給出的權重由兩點間的最短路徑給出。

最小生成樹可以從最優環路中構造，總長 $n - 1$ 。唯二的奇數度點是這棵樹（此時也是條路徑）的兩個端點，其完美匹配僅由一條權重近似為 $n /2$ 的單邊構成。生成樹和這條單邊的併集是一個迴路，沒有可能的近道 (short-cutting)，且其總邊權近似為 $3 n /2$ 。而問題的最優解是使用所有權重為1或 $1 + ε$ 的邊構造的環路，其總權重為 $n + (n - 2) ε$ ，對充分小的 $ε$ 可以無限靠近於 $n$ 。^[3]

例

	已知：一個邊權滿足三角不等式的完全圖
	計算最小生成樹T
	計算最小生成樹中奇數度的頂點集O
	用 O 中的點構造原完全圖上的一個完全子圖
	構造這個子圖上的最小完美匹配M
	將生成樹和匹配取並 $T \cup M$ 形成一個歐拉重圖
	計算歐拉迴路
	刪除重複頂點，選取近道 (short-cutting)，給出算法的輸出

參考文獻

^ Goodrich, Michael T.; Tamassia, Roberto, 18.1.2 The Christofides Approximation Algorithm, Algorithm Design and Applications, Wiley: 513–514, 2015 .
^ Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
^ Bläser, Markus, Metric TSP, Kao, Ming-Yang (編), Encyclopedia of Algorithms, Springer-Verlag: 517–519, 2008 [2017-12-26], ISBN 9780387307701, （原始內容存檔於2016-04-28） .

外部連結

NIST 克里斯托菲德斯算法定義（頁面存檔備份，存於互聯網檔案館）

[gt-1] Goodrich, Michael T.; Tamassia, Roberto, 18.1.2 The Christofides Approximation Algorithm, Algorithm Design and Applications, Wiley: 513–514, 2015 .

[2] Nicos Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.

[3] Bläser, Markus, Metric TSP, Kao, Ming-Yang (編), Encyclopedia of Algorithms, Springer-Verlag: 517–519, 2008 [2017-12-26], ISBN 9780387307701, （原始內容存檔於2016-04-28） .

[1]

[2]

[3]