知识卡片
生成树近似需要三角不等式
对于完全无向度量图,先求最小生成树,将树边加倍得到闭合遍历,再按首次出现顺序跳过重复顶点形成旅行商回路。三角不等式保证跳过重复顶点不会增加长度;树权≤最优回路权,故输出≤2倍最优。
原文把TAPP称为“任意计算出的任何近似路线”,并直接断言TAPP≤2TMST,缺少三角不等式及具体构造。任意路线不满足这个界;最近邻也不能仅因本法有保证就继承2倍保证。
参考:MIT度量TSP近似讲义,2026-11-06实读双树构造和证明。当前书中mst实现还有连通性与成本边界,不能把抽象算法保证直接套到未经修复的程序。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
2TOPT。总结起来如下: TMST≤TOPT,TAPP≤2TMST⇒TAPP≤2TOPT 问:当用Prim算法计算最小生成树时,对于相同的图,如果从不同的顶点开始运行算法,有可能获得一棵不同的树吗? 答:在Prim算法的运行过程中,当在寻找键值最小的顶点时,经常能够找到一些键值相同的白色顶点,尤其
参考来源
- 位置:《算法精解:C语言描述》第16章《问与答》(spine1419;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1385.html;u305-ch16-015)。
- 结论依据:305全部六组问答与不等式实读;MIT讲义相关证明补核,明确不等式的算法和前提。
- 原始内容:2TOPT。总结起来如下: TMST≤TOPT,TAPP≤2TMST⇒TAPP≤2TOPT 问:当用Prim算法计算最小生成树时,对于相同的图,如果从不同的顶点开始运行算法,有可能获得一棵不同的树吗? 答:在Prim算法的运行过程中,当在寻找键值最小的顶点时,经常能够找到一些键值相同的白色顶点,尤其