千禧难题已解决？！

• 下载源代码 - 238.1 KB

更新信息

代码已更新。

• 现在该应用程序允许测试路径是否为当前图的哈密顿圈的有效性。当前图是从文件打开或手动创建的图。请参阅类CycleTester及其用法。
• 路径可以从*.path-file或*.txt-file读取（请参见“打开Ham路径”按钮）。该文件必须包含图节点编号的逗号分隔（或空格分隔）的序列。节点编号从零开始。
• 添加了一种视图模式（多次点击“切换视图”按钮）。

引言

你们大多数人都听说过由（克莱数学研究所）设立的七大千禧年大奖难题，每个难题的解决方案奖金为100万美元。看起来，其中一个难题可能已经被中国武汉科技大学的（杜礼志）教授解决了。

背景

一年前我读了他的文章，但无法解读算法的逻辑（当然，我也怀疑是否真的成功了）。后来，我尝试实现该算法，但经过一番努力后放弃了。不幸的是，作者没有公开他的C++代码。

身为教师有一个很大的优势——你可以给学生布置任务，如果他恰好拥有非凡的头脑（此外，还有极大的耐心，对自己能力的信念，相信老师不会怀疑成功），那么你就能赢得胜利。对我来说，这种事就发生在了我和我的学生Ivan Fedorov身上。他非常努力了一个月（或更长时间），搁置了所有其他事务，最终取得了成功。他设法理解了文字描述的算法逻辑（您可以通过上面的链接找到该算法的描述），并将其转化为可工作的代码。但首先，你应该确信解决方案是可能的。

主要思想

杜礼志教授方法的核心思想是将任何无向图表示为节点环（见图1），并尝试修复节点连续链中的“断裂”。“断裂”（或作者术语中的“断点”）是指两个相邻节点（沿环链）之间不存在边。

如果你成功修复了所有断裂，就找到了哈密顿圈。它就是沿着环的节点序列。很久以前，我开发了一个应用程序，可以以RingView方式重绘任何图并拖动其节点。如果你尝试（使用本文随附的应用程序）直观地拖动某个图的节点以修复所有“断裂”，你通常可以成功。

参见图2，其中通过向下拖动节点#8修复了一个“断裂”（比较图1和图2）。

图3. 显示了通过拖动几个节点修复所有“断裂”后的最终结果。比较图3和图1。注意节点的编号。考虑到在拖动过程中，你不会改变图的结构（或邻接矩阵）。正如你所见，所有“断裂”都已修复，现在我们有了一个哈密顿圈（它是沿着椭圆环的节点序列）。

这种练习让我相信杜礼志教授的方法是相当合理的。我将这个技巧展示给Ivan Fedorov，让他相信解决方案近在眼前。你所要做的就是将直观的拖动操作转化为严格的编程逻辑。哦，别忘了参考PDF文档中关于杜礼志算法的几页说明。

受此逻辑启发，Ivan开始工作。最终的代码结果令人印象深刻，因为它奏效了！但它并不那么好，因为它被压缩成两个大函数，存在大量重复和非常难以理解的逻辑。经过两天对问题的思考和与代码的搏斗，我认为代码变得更易读、更易管理了。现在它被封装在一个类中，该类有八个方法（每个方法实现算法的一个独立步骤）。代码运行速度比原始版本（两个函数的方法）稍快。

关注点

即使到现在，我也不能确定自己能清楚地解释所有的神奇之处（特别是TrySecond、TryThird和CutAndInsert等方法的逻辑）。我认为我理解并能解释用于改变图结构的“旋转技术”，但即便如此，我也不能100%确定我能解释所有的操作。Ivan说他也有同样的看法，尽管是他将代码从诚实但相当冗长的杜礼志文档中复活出来的（参见上面他文章的链接）。

代码使用

数据文件扩展名为‘*.gv’（GraphView文件）。这是最简单的格式（每个图节点的邻接节点列表）。如果你将OpenFileDialog中的过滤器更改为‘*.hcp’，你可以打开网络上许多现有的图文件。这种文件的格式非常简单——边（连接节点对）的列表。我在项目的Data文件夹中只放了两个这样的文件。名为‘TestGraph_11_4.hcp’的文件不包含哈密顿圈，但杜礼志教授在该图上找到了一个哈密顿路径。请注意，我们的实现不搜索哈密顿路径（只关注圈）。

在玩应用程序时，首先打开带有小数字前缀的文件（Ctrl+O），然后尝试使用旧的已知算法（Posa、Roberts and Flores、Recursive Backtracking）。这些算法是我几年前实现的。顺便说一下，Posa算法并不总能找到解，因为它随机选择节点（算法描述在此）。在简单的图上尝试几次，它有时会找到一个解（每次可能不同）。更强大但速度较慢的是Roberts and Flores创建的算法（您可以在网上找到其描述）。它肯定会找到一个哈密顿圈，或者会给出一个不存在的消息。

您可以通过按右箭头键循环切换当前选定的算法。按空格键开始搜索。您还可以通过设置动画延迟来查看搜索算法的内部过程（详细信息）（使用带有工具提示的工具栏按钮：更改动画延迟）。在打开一些较大的图（09 Knight.gv之后的文件）时，不要忘记将延迟时间设置为零。这个图对应于维基百科中提到的著名的骑士游程问题。为了看到杜礼志算法的本质（以及本文的目的），请执行以下步骤

• 打开文件09 Knight.gv，
• 选择RobertsFlores算法
• 清除延迟（使用按钮更改动画延迟）。
• 按空格键，然后去喝杯咖啡。计算机将花费数小时寻找解决方案，因为它需要数十亿次回溯。
• 如果您不想等待，请停止算法（使用工具栏按钮停止搜索）。
• 选择LizhiDu算法，然后按空格键。

解决方案将立即找到（如果您没有忘记清除延迟）。该算法只需要234步。这太棒了！

结论

如果数学界采纳杜礼志教授的解决方案证明，那么正如（权威人士）警告我们的那样，所有公钥RSA密码系统都将崩溃。这对我们来说是坏消息吗？我不知道，我总是忽视安全问题。数学家们将不得不发明新的东西。

历史

• 2017年5月21日：初始版本