问题定义
TSP问题： 无向图 $ G = (V,E)$，其中，$d:E\rightarrow \mathbb{Z}^+$ 表示每条边的权重，求费用最小的哈密尔顿回路。
TSP问题近似比
TSP问题是一个NP-hard 问题。而普通的 TSP 问题甚至没有很好的近似比的多项式时间算法。下面证：当定点数为 $n$ ，输入规模为 $n$ 的多项式，TSP 问题不存在近似比为 $O(2^{\mathrm{ploy}(n)})$ 的多项式时间算法，其中， $\mathrm{ploy}(n)$表示 $n$ 的多项式：
对无向图 $ G = (V,E)$，若存在近似比为 $O(2^{\mathrm{ploy}(n)})$ 的多项式时间算法，构造新的无向图 $ G’ = (V,E’)$，新图的输入规模仍是 $n$ 的多项式，其中边的权重定义为：
$$
w(e’) = \begin{cases} 1 & e’ \in E \\ 2^{\mathrm{poly}(n)}n & e’ \not\in E \end{cases}
$$
对新的图使用假设的多项式时间算法，算法不会选取 $e’ \not\in E$ 的边（否则不是权重最小）因此，算法找到了原图 $G$ 中的哈密尔顿回路。然而，找无向图的哈密尔顿回路是一个 NPC 问题，矛盾。
因此，普通无向图上 TSP 问题的近似算法无法取得较好的解。因此我们给问题一些限制。
满足三角不等式的TSP问题
设无向图的权重满足： $$ d(i,j) \le d(i,k)+d(k,j) ,\ \forall i,j,k \in V$$
近似比为 2 的近似算法
计算无向图的最小生成树 $T^*$ 【图 (b)】
$$ d(T^*)\le d(OPT)$$ : 哈密尔顿回路是一个圈，因此权重一定大于最小生成树。
将最小生成树每条边重复一次，可以得到一个欧拉回路 【图 (c)】
$$ d(\widetilde{G})=2 d(T^*)$$
沿着欧拉回路，如果一个顶点已被访问，则跳过直接访问下一个顶点，由于满足三角不等式，新访问的边权重一定小于等于欧拉图中的多条边权重之和。得到哈密尔顿回路 【图 (d)】
$$ d(H)\le d(\widetilde{G})=2 d(T^*)\le2d(OPT)$$
图 (e) 为最优解
近似比为 1.5 的近似算法
- 计算无向图的最小生成树 $T^*$
- 找出 $T^*$ 的奇度点（偶数个），找到权重最⼩的完美匹配 $M$
- $T^*\cup M$ 是⼀个欧拉回路
- 延着欧拉回路，如果一个顶点已被访问，则直接访问下一个顶点，得到哈密尔顿回路
记奇度点为 $u_1,u_2,…,u_{2k}$ 。由于无向图满足三角不等式，一定可以得到一个奇度点组成的圈，使得，圈的权重小于权重最小的哈密尔顿回路：奇度点的数量一定少于哈密尔顿回路中点的数量，将哈密尔顿回路中的偶度点去掉，权重将减小。
由奇度点组成的圈对于两个匹配，因此，权重最⼩的完美匹配 $M$ 满足 $ d(M)\le\frac{1}{2}d(OPT)$$
$$
d(H)\le d(T^*)+ d(M)\le 1.5d(OPT)
$$
最短哈密尔顿路
没有满足三角不等式条件的最短哈密尔顿路问题同样无法用多项式时间算法得到较好的近似。对于满足三角不等式条件的有 0、1、2 个固定顶点的最短哈密尔顿路问题，可以向最小生成树中加入匹配，使固定点为奇度点，非固定点为偶度点，从而得到一个满足条件的欧拉路，通过欧拉路进行 short-cutting 得到哈密尔顿路。
可以用近似算法求解：
- 计算无向图的最小生成树 $T^*$
- 记点集 $S$ 为：固定点中的偶度点，非固定点中的奇度点；
- 求 $S$ 的最小匹配 $M$，使得恰有 2 个奇度点，且固定点在这 2 个点里；
- $T^* \cup M$ 可以得到欧拉路，从而得到哈密尔顿路。
证明
这里的主要证明是的最小匹配 $M$ 的权重，需要注意的是这里需要和最短哈密尔顿路进行比较，而不能和哈密尔顿回路比较。
- 有 0、1 个固定点时，可以得到近似比为1.5的多项式时间算法
- 有 2 个固定点时，可以得到近似比为 5/3 的多项式时间算法
