克里斯托菲德斯算法

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

算法

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

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

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

近似比

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

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

因為兩個邊集是 C 的劃分,二者中的某一個至多有 C 總邊權的一半,因而其對應匹配的總邊權不超過 C 總邊權的一半。因為沒有比最小完美匹配更小的匹配,所以 w(M) ≤ w(C)/2。 TM 的權重總和也就是歐拉迴路的權重總和,也就是至多 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[3]

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

參考文獻

  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) .

外部連結