知识卡片

普通读书笔记卡 · 5654.d.1.f.3.b · 生成模型:未记录

哈密顿圈逐顶点访问并返回

理解等级:中级

哈密顿圈从一个顶点出发,经过其他每个顶点恰好一次,再回到起点;起点在序列首尾出现是闭合表示,不意味着允许任意重复中间顶点。它约束访问顶点,不是要求每条边恰好走一次。

本章把旅行商问题描述为在这些完整回路中选总代价最小者:存在某个可行回路与找到最便宜回路是不同任务。此处只说明模型,未给求解过程,也不能由“任意一点出发”理解为任意图都必然有哈密顿圈。

这张卡片看不懂?

已有反馈 · 0 条

    还没有人提交反馈。

    在整书笔记中的位置

    原书出处 · 1 处

    • · 查看原书依据

      每一个顶点恰好一次,最后返回初始顶点,则称该路径为哈密顿圈。旅行商问题(见第16章)是哈密顿圈问题的一个特殊形式。在旅行商问题中我们要以最小的代价找到哈密顿圈。 分团问题 在图的区域中,每个顶点都以某种方式与其他结点相连。拥有这种属性的区域称为团(clique)。一些分团问题旨在找出图中所包含的最大

    参考来源

    - 位置:《算法精解:C语言描述》第11章《第11章 图》(spine1321;extracted/OReilly精品图书系列共21册(《Javascript权威指南》、《机器学习:实用案例解析》、《编写可读代码的艺术》、《算法精解》等)/_epub-src/text/part1288.html;u185-ch11-003)。 - 结论依据:185哈密顿圈完整应用段实读,保留与TSP成本目标关系,具体算法留第16章。 - 原始内容:每一个顶点恰好一次,最后返回初始顶点,则称该路径为哈密顿圈。旅行商问题(见第16章)是哈密顿圈问题的一个特殊形式。在旅行商问题中我们要以最小的代价找到哈密顿圈。 分团问题 在图的区域中,每个顶点都以某种方式与其他结点相连。拥有这种属性的区域称为团(clique)。一些分团问题旨在找出图中所包含的最大