Christofides 演算法（Christofides' algorithm）
/ kris-TOFF-ih-dees /
Christofides 演算法是對度量 TSP 那個簡單的 MST 加倍 2 近似的著名改進。把每條樹邊都加倍是浪費的——它為整棵樹付了雙倍，只為了讓每個頂點都有偶數條邊（這才能讓你描出一條封閉走訪）。Christofides 的洞見是：你不必把一切都加倍；你只需要修補樹中那些「奇度」的頂點，而這件事用一個聰明的匹配可以便宜得多地完成。回報是更緊的 1.5 近似，而且四十多年來它一直是度量 TSP 已知的最佳比值。
演算法有三步。第一，建出城市的最小生成樹 T。第二，看那些在 T 中有奇數條邊的頂點——這種奇度頂點的個數永遠是偶數，是個基本的圖論事實——然後在「僅僅這些奇度頂點之間」算出一個最小權重完美匹配 M，盡可能便宜地把它們兩兩配對。把 M 的邊加進 T。現在每個頂點都是偶度，所以合併後的圖有歐拉迴路：一條恰好用到每條邊一次的封閉走訪。第三，描出這條迴路並抄掉已造訪的城市，與 MST 方法完全一樣；三角不等式保證抄捷徑絕不會讓結果變長。為何是 1.5？樹的成本一如既往 MST <= OPT。匹配可以被證明最多花 OPT / 2：把那些奇度頂點按最佳旅程的順序排，會分成兩個交錯的完美匹配，總和最多 OPT，所以較便宜的那個——進而最小匹配——最多 OPT / 2。加起來：旅程 <= MST + M <= OPT + OPT/2 = 1.5 * OPT。
為何重要與誠實的細節。Christofides 是「更聰明的下界論證換來更好比值」的典範結果，而且它確實被使用。代價：算最小權重完美匹配是昂貴的一步，雖是多項式但明顯比建 MST 慢得多，所以更好的比值不是免費的。兩個提醒：和 2 近似一樣它需要三角不等式，而那個 1.5 直到最近才被打破、且只改進了極小的量，即便如此也離我們夢寐以求的 1 還很遠——度量 TSP 在小常數以上仍然真的難以近似。
取五座城市。建出 MST；設其中四個頂點為奇度。Christofides 把這四個配成兩對便宜的對（最小權重完美匹配），加上那兩條邊，現在每個頂點都是偶度。它走出所得的歐拉迴路，抄掉重複，產生一條保證在最佳 1.5 倍以內的旅程。
MST 加上奇度頂點上的便宜匹配，使之歐拉化，再抄捷徑：1.5 * OPT。
匹配只在 MST 的奇度頂點之間計算，不是所有頂點，而且是「最小」權重完美匹配——正是這個最小性給出 OPT/2 的界。略過最小性或對所有人做匹配都會破壞 1.5 保證。