基本介紹
- 中文名：克里斯托菲德斯算法
- 外文名：Christofides algorithm
- 提出者：Nicos Christofides
- 提出時間：1976
算法,近似比,下界,
算法
令G= (V,w)是旅行商問題的一個實例。 即，G是一頂點集V上的一個完全圖，函式w給G的每條邊指定了一個非負實邊權。 依三角不等式，對每三個頂點u,v和x都有關係w(uv) +w(vx) ≥w(ux).
算法可以被描述為如下偽代碼。
- 構造圖上的最小的生成樹T
- 令 O為原圖頂點集中在T上度數為奇數的頂點集。根據握手定理，O中有偶數個頂點
- 構造點集O在原完全圖上的最小完全匹配M
- 將 M 和 T 的邊集取並，構造重圖H ，滿足其每個頂點都是偶數度的
- H可以形成一個歐拉迴路
- 將前一步得到的圖改造為一個哈密爾頓迴路：只需要跳過前一步歐拉迴路中重複的頂點即可（這個步驟又稱作選取近道，"short-cutting"）。
近似比
算法所生成的解相對最優解有3/2的近似比。下給出簡要證明。
令C為圖上的最優旅行商迴路。注意到，刪除C上的一條邊將產生原圖上的一棵生成樹，其總權重必然不小於最小生成樹，亦即w(T) ≤w(C)。接下來，給O中的頂點編號，編號順序依據迴路C上的頂點順序。再將C做劃分，得到兩個邊集：其一包含所有起始點在生成樹上有奇數度的邊，另一個則包含所有起始點在生成樹上有偶數度的邊。這兩個邊集各對應於O上的一個完全匹配，且匹配的總邊權不超過邊集的總邊權。
因為兩個邊集是C的劃分，二者中的某一個至多有C總邊權的一半，因而其對應匹配的總邊權不超過C總邊權的一半。因為沒有比最小完全匹配更小的匹配，所以w(M) ≤w(C)/2。T和M的權重總和也就是歐拉迴路的權重總和，也就是至多3w(C)/2。由於做選取近道操作並不增加權重，所有最終輸出的總邊權也不超過3w(C)/2.
下界
存在使得克里斯托菲德斯算法近似比任意接近3/2的輸入。
一類滿足條件的輸入由n個頂點組成，滿足最優環路上邊的權重都為1，且在最優環路上相隔一條邊的邊都有權重1 +ε，其中ε是一個足夠小的正數。未由上述定義給出的權重由兩點間的最短路徑給出。
最小生成樹可以從最優環路中構造，總長n− 1。唯二的奇數度點是這棵樹（此時也是條路徑）的兩個端點，其完全完全匹配僅由一條權重近似為n/2的單邊構成。 生成樹和這條單邊的並集是一個迴路，沒有可能的近道 (short-cutting)，且其總邊權近似為3n/2。 而問題的最優解是使用所有權重為1或1 +ε的邊構造的環路，其總權重為n+ (n− 2)ε，對充分小的ε可以無限靠近於n。
