CSCI3160 L18 旅行商问题的树遍历近似

课程：CSCI3160 Design and Analysis of Algorithms 本讲：L18 旅行商问题的树遍历近似 · 原件 L18-Approximation-02-Traveling-Salesma-未核-隐藏.pdf（本地课件） p.1–12 定位：用 MST 下界、加倍树边和三角不等式串起二倍保证。

p.1–3：三个输入条件都要记住【新】

p.1 为标题。p.2 输入为完全无向图、非负边权、满足三角不等式；Hamiltonian cycle 访问每个顶点恰一次并回到起点。p.3 说明即使有这些条件仍是 NP-hard。

p.2 $w(x,z)\le w(x,y)+w(y,z).$

图（p.2）：五点完全图，讲义最优环 a→c→d→b→e→a。元素：边权分别1、3、4、2、4，总14。看什么：绕过中间点时有直达边，而且直达不更贵，这分别使用完全图与三角不等式。

原图 10 条无向边完整权重为 ab=6、ac=1、ad=4、ae=4、bc=5、bd=4、be=2、cd=3、ce=4、de=6。任意方向走同一条边，权重相同。

p.4–6：先造一个容易控制成本的闭合走法

p.4 近似比指返回环长度至多 $\rho OPT$ 。p.5 先求 MST。图中树边 ca=1、cd=3、ce=4、eb=2，总10。p.6 每条树边来回各一次，DFS 下行和回溯即能在线性时间得到闭合走法 c,a,c,d,c,e,b,e,c，长20。

它还不是 Hamiltonian cycle，因为 c、e 重复，但长度已经准确等于两倍树权。

p.7–9：跳过重复点

p.7 “If v has not been seen before, append v to σ.”

顺着闭合走法保留第一次出现的顶点，最后补回起点。p.8 从 c,a,c,d,c,e,b,e,c 得 c,a,d,e,b,c。其权重1+4+6+2+5=18；p.9 声称这个算法具有二倍保证。18不是原例最优14，但不超过保证28，甚至不超过两倍MST的20。

跳过并不是删掉一段后把两端当作同一点；必须用原完全图中两端的直接边连接。

补充：把第一次出现列表与闭合回路区别开。 扫描原例走法 c,a,c,d,c,e,b,e,c，维护已见集合：第一次见 c、a、d、e、b 时依次写入，重复的 c、e 跳过。此时只有开放列表 c,a,d,e,b，尚未返回起点；还必须加边 b→c，才是合法环。最后返回 c 不受“每点只出现一次”的字面阻止，因为环的起终点重复是表示法所必需。

自测：没有三角不等式，shortcut 仍然不会变贵吗？

自取三点，ab=1、bc=1、ac=100。绕过 b 将 a→b→c 的长度 2 换成直边 ac 的 100，费用暴增。MST 仍可照常求，双倍树遍历仍等于两倍树权，但从重复走法到 Hamilton 环的那一步失去了成本保证。图若不完全，直边甚至可能不存在。

近似证书应按不同对象写：输出环、树的双倍闭合走法、MST、未知最优环。不能把一个具体可行环的 14 或 18 当作未经证明的全局下界。原例已知最优 14来自原材料；算法一般分析则依靠 MST 下界，不需要先知道 OPT 的数值。

p.10–12：三段不等式分别用什么

p.10 从最优环删一条边得到生成树，非负边保证删后不更贵，MST又不比这棵树贵，所以 $w(T)\le OPT$ 。p.11 每树边恰走两遍，所以 $w(\pi)=2w(T)$ 。p.12 对每次 shortcut，反复应用三角不等式，直达边不超过被跳过那段路径；分段相加得 $w(\sigma)\le w(\pi)$ 。因此

w(\sigma)\le w(\pi)=2w(T)\le2OPT.

p.12 的求和证明可以保留全部索引而不靠图理解。设原走法为 $u_1,\ldots,u_t$ ，保留位置为

1=i_1<i_2<\cdots<i_{|V|}<i_{|V|+1}=t.

对第 j 段反复使用三角不等式，有

w(u_{i_j},u_{i_{j+1}})\le\sum_{k=i_j}^{i_{j+1}-1}w(u_k,u_{k+1}).

这些区间首尾相接而不重叠，覆盖原走法的全部边，所以对 j 从 1 加到 |V|，右侧恰是原走法总长，没有漏算或重复计算。算法时间由 MST 主导；树遍历与已见标记扫描均 O(|V|)，例如稠密图 Prim 可使整体 O(|V|²)。

图中的 c→a→c→d 段变为 c→a→d，a→d 权4恰等于 a→c→d 的1+3；b→e→c 变 b→c，权5不超过2+4=6。每次局部比较都有依据。讲义末行 wk+1 应按上下文读作顶点 uk+1。

只需访问指定点的期末题见附录 A1。

本讲核心考点

（C 级通识）三角不等式用在 shortcut，不用在 MST 算法本身。
（C 级通识）写出 MST 下界→加倍→shortcut 的完整证明。
（A 级：Final-2024T1 Q8）用最短路度量闭包推广到指定顶点的往返访问。

附录

A1 作业/往年题演练（非讲义内容）：Final-2024T1 第 8 题

题面（Final-2024T1-缺判断-题目.pdf · Problem 8 · p.5；扫描件，视觉读取；公式按原题重排）

p.5 “Problem 8 (10 marks). Consider an undirected simple graph G = (V,E), where each edge is associated with a positive weight, referred to as the length of the edge.”

“Let S be a subset of V, which includes a source vertex denoted as s, and k other destination vertices, where k is an integer satisfying $1\le k\le\lvert V\rvert-1$ . Define an S-round-trip walk as a walk that starts from s, visits every destination vertex of S at least once (the order by which those vertices are visited does not matter), and then ends at s. Recall that a walk is a vertex sequence $u_0,u_1,u_2,\ldots,u_\ell$ , where $\{u_i,u_{i+1}\}$ is an edge in E for all $i\in[0,\ell-1]$ . The length of the walk equals the total length of all the edges traversed. For example, consider G to be the following graph. If S has source vertex d and k = 2 destination vertices a and g, then an S-round-trip walk is dabcdgfed, whose length is 6 + 1 + 1 + 2 + 1 + 2 + 1 + 5 = 19.”

“Design an algorithm to find an S-round-trip walk with length at most 2 · OPT, where OPT is the minimum length of all round-trip walks. Your algorithm's running time must be polynomial in $\lvert V\rvert$ . You do not need to prove your algorithm's correctness, but you do need to analyze its running time.”

图（题面，p.5）：九点正权无向图。元素：边ab=1、ad=6、bc=1、cd=2、ce=10、de=5、ef=1、fg=2、dg=1、dh=3、gh=1、gi=1、fi=2。看什么：只有a、d、g是本例必须访问的终端；其他点允许作为最短路中转。

题源：Final-2024T1-缺判断-题目.pdf（本地课件） p.5 Q8。正权无向图，给定源点 s 和 k 个须访问的点；要求从 s 出发、访问它们并返回 s 的多项式时间二倍近似，允许重复顶点和边。

对终端集合 R（含 s）计算两两最短距离，构成完全图。最短距离满足三角不等式；若终端不可达，先报告无可行往返。求这个完全图的 MST，双向遍历其边，再把每条虚拟边展开为原图最短路径，即得到可行往返，成本为2MST。任意原图最优往返按终端访问次序投影到度量闭包，成本不会增大；删边得到终端生成树，所以MST≤原OPT，二倍保证成立。允许重复时不必额外 shortcut。

原题图 s=d、须到 a,g。d 到 a 的最短路 d→c→b→a 长2+1+1=4，d 到 g 长1，a 到 g 长5。终端 MST 权5，加倍得原图路线 d→c→b→a→b→c→d→g→d，长10。题中长19的走法只是可行示例，不能当作OPT。

以二叉堆 Dijkstra 计算距离需要 $O((k+1)(V+E)\log V)$ ，终端完全图 MST 还需至多 $O((k+1)^2\log(k+1))$ ，均为多项式。

回到正文：二倍保证

来源与证据

本次逐页复核：2026-10-13，依据上述本地课件；保留已发布深化内容，页码指 PDF 物理页。历史考试演练保留其原有出处，本次不将旧记录冒充重新阅卷。
原件：L18-Approximation-02-Traveling-Salesma-未核-隐藏.pdf（本地课件）；页码均为 PDF 页号。
版本记录（2026-09-17）：当时从教师官网下载并逐字节核对，与本地原件一致；此日期不是本次重新联网核验。原始学期未核，不据网页学期补猜。
发布状态（2026-09-17 核验时）：官网链接所在行隐藏，当时按预习参考处理；不据此推断后续发布或考试范围。
既有考试证据记录（2026-09-17）：当时读取了教师官网、Midterm-2021T1-题目.pdf、Midterm-2021T1-题解.pdf、Review-Quiz-2020T2-题目.pdf、Review-Quiz-2020T2-题解.pdf、Quiz-01-2025T1-题解.pdf、Midterm-A-2025T1-缺题干-解答.pdf、Quiz-02-2025T1-缺题干-解答.pdf、Quiz-03-2025T1-缺题干-解答.pdf、Final-2021T1-题解.pdf、Final-2024T1-缺判断-题目.pdf、Final-2025T1-题目.pdf、Final-2025T1-缺题干-解答.pdf；未识别用途的 PDF：无
缺题干解答卷仅用于核对已取得的题面，不由答案反推题目。