CSCI3160 Regular 11：TSP 近似、绕行与困难性

原件：题目（本地课件）；官方答案（本地课件） p.1–3。 定位：分清 MST 的下界、加倍遍历的代价和三角不等式对捷径的作用。

图形已按 PDF 渲染核对，以下明确列出边权，避免仅凭文字提取猜图。近似算法为：求 MST，沿树边往返形成闭游走，再跳过已访问顶点得到哈密顿环。

Problem 1：没有三角不等式，捷径可能特别贵（答案 p.1）

原图四点 A、B、C、D 的六边为 AB=1、BC=1、BD=1、AC=2、CD=2、AD=10。MST 选以 B 为中心的三条权重 1 的边，代价 3。沿树走 A,B,C,B,D,B,A，代价 6。保留首次访问顶点并返回起点，得到 A,B,C,D,A，权重为 1+1+2+10=14。

另一个环 A,B,D,C,A 只花 1+1+2+2=6。固定从 A 出发并忽略反向重复，三种环代价分别为 14、6、14，所以 OPT=6，14/6>2。

失败点在从 D 绕 B 回 A 原本仅需 2，却被直接边 DA 的 10 代替。三角不等式要求直接边不超过绕行长度，这里恰好违反。MST 下界与树遍历加倍仍然正确，出错的是“跳过中间顶点不会更贵”。

Problem 2：即便是度量图，也不能保证 1.6（答案 p.1–2）

官方六点反例可明确描述为：完整图 A,B,C,D,E,F；五条 F 到其他点的边均重 1；外圈 AB、BC、CD、DE、EA 重 1；其他边重 2。边权仅为 1 或 2，所以任一直接边≤2，而任意两边和≥2，三角不等式成立。

以 F 为中心的星形树边权和 5，是 MST，因为任何六点树有五条边且每边至少 1。选树遍历 F,A,F,C,F,E,F,B,F,D,F，去掉中间重复点后为 F,A,C,E,B,D,F，代价 1+2+2+2+2+1=10。

环 A,B,C,D,E,F,A 全用权重 1 的边，代价 6；任何六边环至少 6，所以它最优。比值 10/6=5/3>1.6。这里存在多种 MST 和遍历次序；展示这套算法允许的一个执行超过 1.6，就否定不加额外规则的普遍 1.6 保证，不等于每种执行都差。

Problem 3：非完全图上的覆盖游走二倍近似（答案 p.2）

题目只要求一条访问所有顶点的游走，允许重复边，也不要求首尾不同或相同。先求 MST，沿每条树边来回走一次，得到闭游走，也是合法覆盖游走，代价为 2w(T)。不做捷径，因此不要求图完整，也不需要三角不等式。

任意覆盖游走用到的不同边组成连通生成子图。因为边权非负，从中选生成树不会比游走总权更重，MST又不比这棵树更重，所以 $w(T)\le OPT$。于是输出代价≤2OPT。

自取三点路径，两边权为 2、3，最优开放游走从一个端点走到另一个花 5，算法来回花 10，恰为两倍。不能把开放最优误说成一定是哈密顿环。求 MST 多项式，树遍历 O(n)，输出顶点序列长度 2n−1。

Problem 4：没有三角不等式时任意常数近似都会解难题（答案 p.2–3）

假设有保证常数比率 ρ≥1 的多项式 TSP 算法。对任意 n 点哈密顿环判定实例 G，构造完整图 G′：原图边重 1，原图没有的边重 $\rho n+1$。这种“大罚款”制造两类解之间的间隔。

若 G 有哈密顿环，它在 G′ 中总代价 n，且每个 n 边环至少 n，所以 OPT=n。ρ 近似输出至多 ρn。只要使用一条罚款边，输出至少 $(n-1)+(\rho n+1)=\rho n+n>\rho n$，不合法。因此算法只能全用原边，返回代价 n 的环。

反过来，若输出环代价 n，因为每边至少 1，全部边只能是重 1 的原边，所以它本身就是 G 的哈密顿环。故检查输出是否恰好 n 即可判定原难题。

构图 O(n²)，罚款数位数在固定 ρ 下为 O(log n)；若需整数且 ρ 不便编码，可选一个固定整数 R≥ρ，用 Rn+1 作罚款，同样形成严格间隔。之后只调用一次假设算法，总体多项式，与哈密顿环 NP 难性冲突（除非 P=NP）。证明不是说 TSP 没有任何算法，而是不存在这种多项式且保证常数比率的算法。

补充：把困难性里的成本间隔做一个数值核对。 自取n=5、假设近似比ρ=2，罚款边权为11。若原图有Hamilton环，最优成本5，保证算法输出≤10；任何用一条罚款边的五边环至少为11+4=15，因此不可能被输出。若原图无Hamilton环，每个环至少用一条罚款边，成本都≥15。这给了清楚的yes/no间隔，而不是凭算法返回某个“大数”猜原图是否有环。

来源与证据

官方答案 p.1–3，Q1、Q2 图形已视觉核对。自取路径例子仅用于说明开放游走边界。本文不据练习推断考试范围。