知识卡片

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

旅行商优化的是完整回路

理解等级:中级

给定带权图,旅行商优化问题寻找访问每个顶点一次并回到起点的最小权回路。书例限定完全无向图,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条边。 解决旅行商问题的其中一