知识卡片
近邻路线不保证全局最短
近似或启发式方法在精确求最优代价过高时,先寻找可接受的可行结果。旅行商的目标是每城访问一次并回到起点的最短闭合路线;最近邻策略从当前城市选尚未访问的最近城市,全部访问后再闭合。
每次最短边只是一种局部规则,不保证整条路线最短;起点和早期选择也会影响结果。本节没有给质量误差界,因此“足够好”须由实际目标评估,不能冒充已证明接近最优的比例保证。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
只计算出“足够好”的解。通常利用近似法解决那些计算成本很高又因为其本身十分有价值而不愿放弃的问题。推销员问题(见第16章)是一个通常会用近似法去解决的问题。 设想一位推销员需要设计一条去往好几个城市工作的路线。推销员问题的目的是找到最短的可能路径,以便推销员能够在回到出发点前恰好每座城市都只去过一次
参考来源
- 位置:《算法精解:C语言描述》第1章《算法设计的一般方法》(spine1180;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1148.html;u016-ch01-009)。
- 结论依据:16近似段给旅行商闭合目标和从当前点选最近未访问点的完整过程,未给误差界;卡片按此区分可行启发式与最优保证。
- 原始内容:只计算出“足够好”的解。通常利用近似法解决那些计算成本很高又因为其本身十分有价值而不愿放弃的问题。推销员问题(见第16章)是一个通常会用近似法去解决的问题。 设想一位推销员需要设计一条去往好几个城市工作的路线。推销员问题的目的是找到最短的可能路径,以便推销员能够在回到出发点前恰好每座城市都只去过一次