text: 克里斯托菲德斯演算法 (Christofides algorithm) 是旅行商問題在度量空間上的一個近似演算法。 該演算法可以保證相對最優哈密爾頓迴路長度有3/2的近似比。尼科斯·克里斯托菲德斯 (Nicos Christofides) 於1976年首次發表了這個演算法，故以他的名字命名之。 截至2017年 (2017)[ [update]]，這一演算法仍然是一般性旅行商問題的演算法中近似比最好的結果。演算法.令 "G" = ("V","w") 是旅行商問題的一個例項。 即， G 是一頂點集V 上的一個完全圖，函式 w 給 G 的每條邊指定了一個非負實邊權。依三角不等式，對每三個頂點 u, v 和 x 都有關係 "w"("uv") + "w"("vx") ≥ "w"("ux").演算法可以被描述為如下虛擬碼。近似比.演算法所生成的解相對最優解有3/2的近似比。下給出簡要證明。令 C 為圖上的最優旅行商迴路。注意到，刪除 C 上的一條邊將產生原圖上的一棵生成樹，其總權重至少為最小生成樹的總權重，亦即 "w"("T") ≤ "w"("C")。接下來，給O中的頂點編號，編號順序依據迴路C 上的頂點順序。再將 C 做劃分，得到兩個邊集：其一包含所有起始點為奇數編號的邊，另一個則包含所有起始點為偶數編號的邊。這兩個邊集各對應於 O 上的一個完美匹配，且匹配的總邊權不超過邊集的總邊權。因為兩個邊集是 C 的劃分，二者中的某一個至多有 C 總邊權的一半，因而其對應匹配的總邊權不超過 C 總邊權的一半。因為沒有比最小完美匹配更小的匹配，所以 "w"("M") ≤ "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。
metadata: erhwenkuo/wikipedia-zhtw
metadata: 克里斯托菲德斯演算法
metadata: https://zh.wikipedia.org/wiki?curid=5996253