知识卡片
旅行商优化的是完整回路
给定带权图,旅行商优化问题寻找访问每个顶点一次并回到起点的最小权回路。书例限定完全无向图,V个顶点有V(V−1)/2条边;现实建模还须核对方向、可达性、时间窗口等约束。
枚举排列是阶乘规模的直接方法,即使固定起点并排除反向重复也仍非多项式;每条路线求和成本要按实现计入,不能由一种枚举法慢就证明所有算法不存在多项式解。
严格区分:给定上限k问是否存在代价≤k的回路是决策形式,标准编码下它是NP完全;求最小代价的优化形式称NP难。NP完全含义是属于NP且所有NP问题可多项式归约至它,并非定义为“尚未找到多项式算法”。参考:MIT决策形式与证明。
这张卡片看不懂?
这张卡片已通过人工审查,不再接受失败反馈。
已有反馈 · 0 条
还没有人提交反馈。
在整书笔记中的位置
原书出处 · 1 处
- · 查看原书依据
哈密顿圈。要解决旅行商问题,需要用图G=(V,E)作为模型,寻找图中最短的哈密顿圈。G是一个完整的、无方向的带权图,其中V代表将要访问的顶点集合,E为连接这些顶点的边的集合。E中每条边的权值由顶点之间的距离决定。由于G是一个完整的、无方向的图,因此E包含V(V-1)/2条边。 解决旅行商问题的其中一
参考来源
- 位置:《算法精解:C语言描述》第16章《旅行商问题的描述》(spine1416;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1382.html;u301-ch16-012)。
- 结论依据:301全文、图规模和复杂度说明实读;MIT讲义决策问题定义及NP完全证明段补核。
- 原始内容:哈密顿圈。要解决旅行商问题,需要用图G=(V,E)作为模型,寻找图中最短的哈密顿圈。G是一个完整的、无方向的带权图,其中V代表将要访问的顶点集合,E为连接这些顶点的边的集合。E中每条边的权值由顶点之间的距离决定。由于G是一个完整的、无方向的图,因此E包含V(V-1)/2条边。 解决旅行商问题的其中一