度量 TSP 的 2 近似（2-approximation for metric TSP）

旅行推銷員問題（TSP）要找出一條最短旅程，恰好造訪每座城市一次再回到出發點。一般而言它極難，但在「度量」版本中距離滿足三角不等式——從 A 直接到 C 永遠不會比繞經 B 還長。這個非常自然的單一假設（直線距離與道路距離都成立）就足以解鎖一個建立在最小生成樹上的乾淨 2 近似。

四步驟配方。第一，建出城市的最小生成樹（MST）——把它們全部連起來的最便宜道路集合。第二，想像你把樹的每條邊都加倍來走它，這造出一條封閉走訪、每條邊走兩次並造訪每座城市；它的長度恰好是 2 * (MST 權重)。第三，這條走訪會重複城市，所以把它「抄捷徑」：當你沿走訪前進時，跳過任何已造訪過的城市，直接跳到下一個新城市。由三角不等式，每個捷徑只可能縮短旅程。結果是一條真正的旅程，長度最多是加倍走訪，即最多 2 * MST。最後一環是下界：任何旅程，包括最佳旅程，都含有一條造訪所有城市的路徑，而刪掉最佳旅程的一條邊就留下一棵生成樹，所以 MST <= OPT。串起來：旅程長度 <= 2 * MST <= 2 * OPT。

所以 MST 身兼兩職：既建出解，又認證了界，這正是反覆出現的「OPT 替身」模式。這是 TSP 近似的教科書入門，因為每一步都很基本——MST、加倍、抄捷徑、三角不等式。誠實的提醒：三角不等式是關鍵（對一般非度量 TSP，除非 P = NP，根本不存在任何常數因子近似），而因子 2 不是已知最佳——Christofides 用更聰明的匹配取代浪費的邊加倍，把它改進到 1.5。儘管如此，這個 2 近似是人人最先學到的概念基石。