知识卡片

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

最近邻路线是贪心启发式

理解等级:中级

从起点出发,反复选当前点距离最近的未访问点,直到访问完所有点,再回起点。本例距离由平面坐标的欧氏距离计算,比较局部边并不比较整个剩余回路。

03093图例得到约15.95,所示更优路线约14.71,差约1.24,按较长路线作分母约7.8%;这是单个示例而非所有输入的性能保证。原文“通常两倍以内”没有提供适用分布或证明,不能作为最近邻的通用2近似保证;度量TSP确有其他具备2倍保证的方法,但不等同本最近邻过程。

点数较多时,本实现每次扫描所有顶点,O(V²),结果依起点和距离相等时的选择而变化。

306提到交换路线中的边并重新计算长度,若严格接受更短的可行回路,可逐步改进当前解;它依赖定义具体交换邻域与终止条件,原文没有给出完整算法或全局最优证明。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 2 处

    • · 查看原书依据

      最近邻点法的应用 一种近似地计算旅行商路线的方法就是使用最近邻点法。其运算过程如下。从一条仅包含起始点的路线开始,将此顶点涂黑。其他顶点为白色,在将其他顶点加入此路线中后,再将相应顶点涂黑。接着,对于每个不在路线中的顶点v,要为最后加入路线的顶点u与v之间的边计算权值。回想一下,在旅行商问题中u与v

    • · 查看原书依据

      交换启发法就是不断地使用其他更好的边交换路线中已经存在的边。每次交换结束后,都会重要计算路线的长度,来判断路径是否改进。

    参考来源

    - 位置:《算法精解:C语言描述》第16章《最近邻点法的应用》(spine1416;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1382.html;u302-ch16-013)。 - 结论依据:302全文、03092欧氏距离公式和03093全部选点与对比图实读;MIT近似讲义区分生成树2近似与最近邻。 - 原始内容:最近邻点法的应用 一种近似地计算旅行商路线的方法就是使用最近邻点法。其运算过程如下。从一条仅包含起始点的路线开始,将此顶点涂黑。其他顶点为白色,在将其他顶点加入此路线中后,再将相应顶点涂黑。接着,对于每个不在路线中的顶点v,要为最后加入路线的顶点u与v之间的边计算权值。回想一下,在旅行商问题中u与v - 位置:《算法精解:C语言描述》第16章《相关主题》(spine1420;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1386.html;u306-ch16-013)。 - 结论依据:306提到交换路线中的边并重新计算长度,若严格接受更短的可行回路,可逐步改进当前解;它依赖定义具体交换邻域与终止条件,原文没有给出完整算法或全局最优证明。 - 原始内容:交换启发法就是不断地使用其他更好的边交换路线中已经存在的边。每次交换结束后,都会重要计算路线的长度,来判断路径是否改进。