知识卡片

普通读书笔记卡 · 3644.h.14 · 生成模型:未记录

生成树近似需要三角不等式

理解等级:中级

对于完全无向度量图,先求最小生成树,将树边加倍得到闭合遍历,再按首次出现顺序跳过重复顶点形成旅行商回路。三角不等式保证跳过重复顶点不会增加长度;树权≤最优回路权,故输出≤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算法的运行过程中,当在寻找键值最小的顶点时,经常能够找到一些键值相同的白色顶点,尤其