為什麼 TSP 需要一個特殊假設
旅行推銷員問題要找一條最便宜的路線，恰好造訪每座城市一次再回到出發點。從困難性那一階你已經知道它的近親有多兇狠：判定一張圖是否「存在」漢米爾頓迴圈就是 NP 完全的，所以要找「最便宜的」漢米爾頓迴圈至少同樣難。正是在這一刻，近似的思維方式派上用場：我們不再求一個精確答案，而是退而求一條長度可被證明落在最佳解某個固定倍數之內的路線，也就是你在本階第一篇遇到的近似比。
但先有個刺。對「一般的」TSP，邊的成本可以是任何值，那麼除非 P = NP，否則不可能存在任何常數倍的近似。理由是一個歸約：拿任意一張圖，問它是否有漢米爾頓迴圈。建一張完全圖，原本的邊成本為 1、缺失的邊成本為某個巨大的 M。一條短路線存在，恰好等價於原圖是漢米爾頓的；而把 M 任意抬高，就能讓「是」與「否」之間的差距要多寬有多寬。任何具備常數比的演算法都得落在那道差距的正確一側，於是它就偷偷地在多項式時間內解出了漢米爾頓迴圈的判定問題。
於是我們加上一個誠實而溫和的限制。在度量 TSP 中，距離構成一個度量：每個成本非負、從 a 到 b 的成本等於從 b 到 a 的成本，而且對任意三座城市都滿足三角不等式，cost(a,c) <= cost(a,b) + cost(b,c)。直走永遠不會比繞路更糟。這符合大多數真實距離——行車時間、歐氏幾何——而且關鍵在於，它給了我們一根一般問題所不給的槓桿：我們可以「跳過」一座已造訪過的城市，而帳單絕不會上升。
倍樹 2 倍近似
這是第一個想法，它很美，因為它重用了你早已信任的東西：最小生成樹。建出城市的最小生成樹 T（用普林演算法或克魯斯卡爾演算法，隨你）。一棵生成樹用最便宜的方式把所有人連起來且不形成迴圈，所以它「幾乎」就是一條路線——只是它不是單一的環。計畫如下：沿樹走一遍，再把這趟走法捷徑化成一條真正的路線。這就是倍樹演算法。
- 建出最小生成樹 T。它的總成本為 cost(T)。
- 把 T 的每條邊都複製一份。現在每個頂點的度數都是偶數，所以這個多重圖有一條尤拉迴路——一條把每條（被複製的）邊恰好用一次的封閉走法。沿著它走；它的長度恰好是 2 * cost(T)。
- 捷徑化：沿著尤拉迴路走，但跳過任何已造訪過的城市，直接跳到下一個新城市。由三角不等式，每次跳過都只會讓行程更短。剩下的走法造訪每座城市恰一次再回到出發點——一條合法的路線。
現在來分析，而且很短。首先，cost(T) <= OPT，其中 OPT 是最佳路線長度。為什麼？從最佳路線上刪掉任一條邊，你就得到一條穿過所有城市的路徑，而那是一棵生成樹；最小生成樹是最便宜的生成樹，所以它不會比那條路徑更貴，而那條路徑又不會比整條路線更貴。其次，我們的路線成本至多等於那趟尤拉走法，也就是 2 * cost(T)。串起來：tour <= 2 * cost(T) <= 2 * OPT。這是一個乾淨的 2 倍近似——絕不超過最佳解的兩倍——而且每一步都是先前各階的東西。
那個 2 倍從哪裡漏掉
仔細看我們是在哪裡失分的。我們把路線拿來和 OPT 比較，卻在一個草率的動作裡白白丟掉了 2 倍：把每條樹邊都複製一份。我們複製是因為需要每個頂點都有偶數度數——那正是尤拉迴路存在的條件。但複製是一把大鐵鎚。我們其實不需要把整棵樹都複製一遍；我們只需要修正度數的「奇偶性」。
在任何圖中，奇數度數的頂點數量永遠是偶數（一個經典的握手事實）。所以在最小生成樹 T 裡，度數為奇的頂點構成一個大小為偶數的集合；稱它為 O。如果我們能加上一小組額外的邊，恰好把那些奇頂點翻成偶、又不動已經是偶的頂點，我們就會得到一個尤拉多重圖，卻不必為整棵樹付第二份的錢。把這些奇頂點兩兩配對、再把每一對連起來，最便宜的做法就是 O 上的一個最小權完美匹配。
克里斯托菲德斯：1.5 倍
把這個修正擺進來，就得到克里斯托菲德斯演算法，它其實就是倍樹演算法，只是把浪費的複製換成一個省錢的匹配。整個方法是四個動作。
- 建出所有城市的最小生成樹 T。
- 令 O 為 T 中奇數度數頂點的集合（數量為偶）。在 O 上算出一個最小權完美匹配 M。
- 把 T 與 M 合併成一個多重圖。加入 M 恰好翻轉了那些奇頂點的奇偶性，於是現在每個頂點都是偶數度數，尤拉迴路存在。把它走一遍。
- 和先前一樣，用三角不等式把重複的城市捷徑化，得到一條合法的路線。
比值是 1.5，而這個界有兩項材料。第一項和先前一樣：cost(T) <= OPT。第二項是新而巧妙的：cost(M) <= OPT / 2。圖像是這樣的。把最佳路線只限制在 O 中的城市上，並把其餘的捷徑跳過；由三角不等式，這條在 O 上縮小後的路線成本至多為 OPT。而一條穿過偶數個頂點的環會拆成兩個完美匹配（隔一條取一條，紅與藍）。這兩個匹配中有一個成本至多是該環的一半，因而至多為 OPT / 2。我們的 M 是 O 上的「最小」匹配，所以它不會比那一個更貴：cost(M) <= OPT / 2。
把兩塊加起來。尤拉多重圖的成本為 cost(T) + cost(M) <= OPT + OPT/2 = 1.5 * OPT，而捷徑化只會更好，所以最終路線至多為 1.5 * OPT。那個額外的想法——用匹配修正奇偶性而非複製整棵樹——讓你從 2 倍一躍而下到 1.5 倍。
誠實的界線與該記住的事
要對 1.5 的意思講究。它是一個最壞情況的保證：在度量實例上，克里斯托菲德斯絕不會回傳長度超過最佳解 1.5 倍的路線。它並不是對典型情況的主張——在真實地圖上它通常做得好得多，常常落在幾個百分點之內——但證明只承諾那個天花板，而非平均。而且，三角不等式一旦失效，這個保證就在那一瞬間蒸發；在非度量的 TSP 上，如我們所見，除非 P = NP，否則根本不可能有任何常數倍。
我們究竟能寄望做到多好？度量 TSP 是 APX 困難的：存在一個常數，除非 P = NP，否則沒有任何多項式時間的近似能低於它，所以一般度量 TSP 的 PTAS 被排除了。這正是本階稍後不可近似性的味道——困難性不只擋住精確答案，還能為你能近似到多接近設下上限。克里斯托菲德斯自 1976 年起，作為已知最佳比值屹立了四十多年；直到很近期 1.5 才被以毫釐之差略微壓低，而真正的最佳常數至今仍是開放問題。