知识卡片

结构图卡 · 3769

最近邻逐城构造TSP近似回路

理解等级:中级

最近邻法从任一城市出发,每步转到尚未访问城市中距离最近者,访问完后闭合成回路。起点会影响贪心选择,因此可逐一尝试各起点并保留这些候选中的最短路线;这只是改善启发式结果,不能保证全局最短。它适合快速构造可行候选,仍需用更强的搜索或下界评估路线质量。问题模型见 [[旅行商问题寻找最短城市回路]]。

示例(补充教学示例,非书中数据):四城对称距离 A–B=1,B–C=1,C–D=1,D–A=10,A–C=100,B–D=1。

起点 最近邻构造 回路长
A A→B→D→C→A 1+1+1+10=13
C 且第二步选 D C→D→B→A→C 1+1+1+100=103

同一规则、不同起点(及并列最近邻的打破方式)可得到长度差很大的可行回路,故多起点比较只是在启发式候选里选短的。

结构图:

flowchart TD
  A[选择起点] --> B[前往最近的未访问城市]
  B --> C{还有未访问城市?}
  C -- 有 --> B
  C -- 无 --> D[闭合为回路]
  D --> E{尝试其他起点?}
  E -- 是 --> A
  E -- 否 --> F[选已生成路线中的最短者]
  F --> G[不等于全局最优]
这张卡片看不懂?

已有反馈 · 0 / 10 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    参考来源

    - 位置:《智能算法导论》第 12 章《1 2 . 3 . 2 基 于 贪 心 算 法 的 旅 行 商 问 题》(源文件:`_epub-src/EPUB/xhtml/chapter12_0007.xhtml`) - 结论依据:正文规定每步选距离最近且未访问的顶点,并说明不同起点可能产生不同回路,比较各起点所得路线仅选择其中最短者。四城距离表是补充教学示例,非书中数据。 - 原始内容:之后每次选择与当前顶点距离最近且没有经过的顶点作为下一个访问目标,直至遍历 V 中所有顶点,算法停止。最终,该方法构造了一个环路。