← 返回刚才阅读的位置

知识卡片

普通读书笔记卡 · 3770

旅行商问题寻找最短城市回路

理解等级:初级

旅行商问题(TSP)把城市看作完全图的顶点(完全图指任意两个顶点之间都有一条边,即任意两城可直达),城市 i、j 间的距离 dᵢⱼ 是边权;目标是从一个城市出发,每座城市恰好访问一次,返回起点,并使整条回路的边权和最小。

这个模型规定了可行路线与优化目标,和某个求解算法不同:最近邻法只按当前最近的未访问城市逐步构造候选,用“未访问城市集合”排除重复访问,它本身不能证明所得回路是全局最短。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • 1 2 . 3 . 2 基 于 贪 心 算 法 的 旅 行 商 问 题 · 查看原书依据

      G的环路会经过V中所有顶点且每个顶点只通过一次,TSP就是求出权值最小的一条环路。 应用贪心算法求解TSP问题时,常用的贪心策略是最近邻算法(nearest-neighbor algorithm):选择任意一个顶点作为起点v,之后每次选择与当前顶点距离最近且没有经过的顶点作为下一个访问目标,直至遍历V中所有顶点,算法停止。

    参考来源

    - 位置:《智能算法导论》第 127 项《12.3.2 基于贪心算法的旅行商问题》(源文件:`_epub-src/EPUB/xhtml/chapter12_0007.xhtml`) - 结论依据:原文将 TSP 定义为带距离权值的完全图上,每个顶点经过一次且回到起点的最短回路;随后另行介绍最近邻启发式。 - 原始内容:G的环路会经过V中所有顶点且每个顶点只通过一次,TSP就是求出权值最小的一条环路。