知识卡片
最近邻路线是贪心启发式
从起点出发,反复选当前点距离最近的未访问点,直到访问完所有点,再回起点。本例距离由平面坐标的欧氏距离计算,比较局部边并不比较整个剩余回路。
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提到交换路线中的边并重新计算长度,若严格接受更短的可行回路,可逐步改进当前解;它依赖定义具体交换邻域与终止条件,原文没有给出完整算法或全局最优证明。
- 原始内容:交换启发法就是不断地使用其他更好的边交换路线中已经存在的边。每次交换结束后,都会重要计算路线的长度,来判断路径是否改进。