*满足三角不等式的货郎问题的最小生成树算法

货郎问题的最小生成树(MST)算法

1. 对货郎问题实例的赋权完全图，调用最小生成树算法，得到最小生成树。
2. 复制最小生成树的每条边，即沿生成树每条边来回走两次，形成欧拉(Eulerien)图。
3. 在这个欧拉图中寻找其欧拉回路。
4. 利用“抄近路”方法将欧拉回路变成货郎旅游回路。

近似性能比证明

抄近路即在欧拉回路的顶点序列中，删除重复顶点，得到每个顶点仅出现一次的序列，即得到了货郎旅游。

令最小生成树为 $T$，其长度表示为 $d(T)$。定义最优货郎回路长度为 $OPT(I)$。将货郎回路任意去掉一条边，可得一条树 $T'$（可以叫做货郎树？），因为 $T$ 的长度是最小的，所以可得 $d(T)<=d(T')<OPT(I)$。

OPT 可以看做是 optimal 的简写。

令最小生成树得到的欧拉回路为 $E$，其长度为 $d(E)$，因为 $E$ 是由 $T$ 将所有边完全复制一份得到的，所以 $d(E)=2d(T)$

令由抄近路得到的货郎回路（该回路非最优解）的长度为 $MST(I)$，因为该回路为基于欧拉回路删除边得到的，所以 $MST(I)<d(E)$

由上述三点可得比较链:

$MST(I)<d(E)=2d(T)<=2d(T')<2OPT(I)$

即

$MST(I)<2OPT(I)$

满足三角不等式的货郎问题的最小对集算法

最小生成树算法生成货郎回路的核心想法是在原赋权完全图上生成的欧拉回路生成货郎回路，原图的欧拉回路则是通过最小生成树复制边生成的。而要将最小生成树通过补边的方式生成欧拉回路，实际上并不需要把所有边都复制一次。

根据欧拉回路的判定方式（所有点的度数为偶数），只需要把最小生成树中，度数为奇数的点之间的边复制一次即可，这样就可以用更少的复制操作，保证欧拉回路的生成。

货郎问题的最小生成树-最小对集(MM)算法

1. 对赋权完全图 $G=(F, E)$，调用最小生成树算法，求出 $G$ 的最小生成树 $T$。
2. 对最小生成树 $T$ 中顶点度为奇数的顶点子集 $V^{\prime}=\left\{a_{1}, a_{2}, \cdots, a_{2 k}\right\}$，调用最小对集算法，在图 $G$ 中求出奇数度顶点子集 $V'$ 的最小对集 $M$。
3. 将最小生成树 $T$ 添加上 $V'$ 中最小对集 $M$ 中的边，形成欧拉图 $G'$。
4. 在欧拉图 $G'$ 中求欧拉回路。
5. 采用“抄近路”方法，将 $G'$ 的欧拉回路变成关于 $G$ 的货郎旅游回路。

近似性能比证明

令在最小对集 $M$ 中的点表示为 $V_M$（即上文的 $V'$），其在赋权完全图 $G$ 上构成的子图表示为 $G_M$（当然也是一个赋权完全图），令在 $G_M$ 上的最优货郎回路表示为 $G_{M'}$，其长度表示为 $OPT(I_M)$。

因为（最小对集） $|V_M|<=|V|$，由三角不等式可得 $OPT(I_M)<=OPT(I)$（因为走了更少的点，所以肯定走了更少的边，多走一个点肯定会多两条边少一条边，这三条边可以构成一个三角形，而两边之和大于第三边）。

将对集子图上的货郎回路，隔一条选一条，可以构成两个对集 $M_1$ 和 $M_2$ （两个对集的边合起来即为原货郎回路），可得：

$d(M1)+d(M2)=OPT(I_M)$

易得：

$min\{d(M1), d(M2)\}<=OPT(I_M)/2$

因为 $M$ 是最小对集，可得

$d(M)<=min\{d(M_1),d(M_2)\}$

由上述比较链可得

$d(M)<=min\{d(M_1),d(M_2)\}<=OPT(I_M)/2<=OPT(I)/2$

令该算法生成货郎回路（非最优解）的长度表示为 $MM(I)$，因为该货郎回路由欧拉回路 $G'$ 抄近路求得，因此 $MM(I)<=d(G')=d(T)+d(M)$

在上一题中证明了 $d(T)<OPT(I)$

因此，$MM(I)<=d(T)+d(M)<3OPT(I)/2$