| 搜索 | 节点 | 结果 |
|---|---|---|
| 普通回溯 | – | – |
| Warnsdorff 顺序 | – | – |
| 死路与连通性检查 | – | – |
| 三者齐用 | – | – |
哈密顿路径探索器
1857 年,威廉·罗万·哈密顿设计了一道谜题:沿十二面体的棱行走,恰好经过它的 20 个角各一次,并回到出发点。这样的路线如今称为哈密顿回路。它容易验证,却通常很难找到。您可以在哈密顿的十二面体、棋盘或自己画的图上描出一条,也可以看回溯搜索去寻找,数一数它走进的死路,看看几项简单检查能把搜索缩短多少。 选择一个图和一个目标:回到起点的回路,或者一条路径。描画:点击一个顶点开始,然后每次点击一个邻点;虚线圆环显示接下来可以走到哪里。点击最后一个顶点、点「后退」或「撤销」可退回一步,「提示」会给出一个仍能走完的下一步。搜索:用「运行」或「单步」运行回溯搜索,它不断添加顶点,直到走不通就回退;红色虚线标出回退的地方,柱状图按路径长度统计节点数。开始之前,点击某个顶点可选择从哪里出发。复选框开关剪枝,「对比」用同一个图分别运行带剪枝和不带剪枝的搜索,「全部计数」数出小图的每条回路或路径。编辑:点击空白处添加顶点,点击两个顶点可连接或断开,拖动可移动顶点,「删除」移除选中的顶点。
它是如何运作的
- 选择一个图,例如哈密顿的十二面体、彼得森图或马步巡游,或者在「编辑」中画自己的图,并选择回路或路径作为目标。
- 在「描画」中点击一个顶点开始,然后一个接一个地点击邻点。「后退」和「撤销」退回一步,「提示」给出一个仍能走完的下一步。
- 在「搜索」中按「运行」或「单步」观看回溯寻找路线,开关剪枝,再按「对比」看看每个版本各需要多少节点。
哈密顿与欧拉
欧拉路径把每条边走一次;哈密顿路径把每个顶点走一次。两者听着相似,表现却大不相同。一个连通图是否有欧拉路径,数一数奇数度顶点即可判定,这正是欧拉在 1736 年所证明的:当奇数度顶点为 0 个或 2 个时就有。对哈密顿路径则没有这样的规则。判断一个图是否有哈密顿回路是 NP 完全问题,属于理查德·卡普 1972 年所列 21 个问题之一,因此一旦有了快速方法,成千上万的其他难题也都能快速求解。现有的是一些能判定部分图的条件。狄拉克 1952 年的定理指出,若每个顶点的度数至少为 n/2,则必有哈密顿回路;奥尔 1960 年的定理则要求任意两个不相邻顶点的度数之和至少为 n。而度数为 1 的顶点、割点或大小不等的两个颜色类则会排除回路。
搜索是怎样工作的
回溯一次添加一个顶点来构造路径,走不通时撤回最后一步并改试下一个邻点。只要存在哈密顿回路,它总能找到,但部分路径的数量可能呈指数增长。在没有哈密顿回路的 5 × 5 网格上,普通回溯要探索 153,745 个节点才能确定。两项检查能及早砍掉没希望的路径:空闲邻点少于两个的未访问顶点已经无法嵌入回路;当未访问顶点分裂成互不相连的几块时,单条路径也无法覆盖它们。两项都用时,同一个证明只需 1,761 个节点。1823 年的 Warnsdorff 规则优先尝试后续走法最少的邻点,能从角上出发、用 64 步找出 8 × 8 的马步巡游,一次死路也不走。
常见问题
哈密顿路径与哈密顿回路有什么区别?
哈密顿路径恰好经过图中每个顶点一次。哈密顿回路做同样的事,然后再沿一条边回到出发点,因此它可以从自己的任何一个顶点开始。每个有哈密顿回路的图都有哈密顿路径(去掉回路中的一条边即可),反之则不然:彼得森图有哈密顿路径,却没有哈密顿回路。
十二面体有哈密顿回路吗?
有,共 30 条,这是把每条回路不论起点和方向都只算一次的结果。哈密顿在 1857 年把这个问题做成了二十面体游戏:一块棋盘,上面是压平的十二面体的 20 个角,用辅音字母标注。他把版权以 25 英镑卖给了伦敦玩具商 John Jaques and Son。应用中的「全部计数」约用 1,400 个节点就能找出这 30 条回路。
为什么 5 × 5 网格没有哈密顿回路?
把 25 个点按棋盘着色:13 个是一种颜色,12 个是另一种,而每走一步都换到另一种颜色。回路一圈下来颜色交替,因此两色必须一样多,而 13 与 12 做不到。同样的论证适用于任何点数为奇数的网格,适用于 5 × 5 或 7 × 7 棋盘上的马(马总是换格色),也适用于两类分别有 6 个和 5 个顶点的赫歇尔图。哈密顿路径仍然可能:它在数量较多的一色上起止。
Warnsdorff 规则怎样找到马步巡游?
H. C. 冯·Warnsdorff 在 1823 年提出,总是把马移到后续走法最少的那个格子。靠近边缘和角落、容易被切断的格子因此较早被走到,此时马还进得去。这条规则只是经验法则,并非保证,平局也得用某种方式打破,但在 8 × 8 棋盘上它通常能一路走完而不回头。像本应用这样与回溯结合使用时,它能找到 5 × 5 及以上的开放巡游,以及 6 × 6 和 8 × 8 棋盘上的闭合巡游。
完全图有多少条哈密顿回路?
当 n ≥ 3 时是 (n − 1)!/2。固定起点顶点,其余 n − 1 个可按任意次序排列,而每条回路会被数两次,两个方向各一次。K₆ 有 5!/2 = 60 条,K₁₀ 有 181,440 条。这些正是旅行商必须从中挑选的环路,也正因如此,逐一试遍很快就变得不可能。
准备好尝试了吗?
在浏览器中打开 PictorX — 无需安装,无需信用卡即可启动。
前往编辑器