java - 有人可以向我介绍哈密顿循环吗？

Question

我有这个项目，我必须提出实现哈密顿循环的 Java 源代码。我在谷歌上搜索，至少现在我知道哈密顿循环是什么，除了起始顶点之外只通过所有顶点一次的路径，因为它也是最后一个顶点（告诉我我是否错了）。问题是我不知道如何实现它。基本上，我的问题是：

1. 如何，在哪里实现哈密顿循环？
2. 哈密​​顿循环的应用是什么（有助于理解为什么它如此重要）

Answer 1

1. 您没有实现哈密顿循环，而是找到了它（或发现给定图不存在）。由于这是一个 NP 完全问题，这意味着这可能不是有效的解决方案，我只需实现一个简单的回溯算法。由于您正在寻找一个循环，因此您从哪个节点开始并不重要。
2. 哈密​​顿循环可用于零知识证明的密码学。我不确定这是否仍然只是研究，或者它是否正在任何加密协议中被积极使用。

Answer 2

(B) 实际应用

• 为电话系统确定最有效的交换网络
• 最佳公交路线、邮政路线、抄表路线

Answer 3

这是作业吗？如果是这样，请将其标记为这样。

如果您可以使用递归，则很容易实现它（如果图形变得太大则不是这种情况）。您所做的是编写一个函数，该函数将图形作为参数（对此有不同的表示形式），该函数检查图形是否仅包含起点，如果是，则返回，如果没有返回，则递归调用自身仍然在图中的每个节点 N 并给出图减去节点 N 作为参数。

Answer 4

最简单的方法是从一个节点开始，“标记它”，选择下一个可到达的“未标记”节点，“标记它”，然后继续直到：

• 你到达起始节点，因此你找到了哈密顿循环。对每个节点重复循环以找到该图中的每个哈密顿循环。
• 您不能选择另一个“未标记”节点，这意味着该起始节点没有哈密顿循环（但无论如何您找到了哈密顿路径）。

该算法可以通过多种方式进行优化，但我让你告诉你。您找到的任何解决方案都是 NP 完全的。

至于它们的用途，我只在图论和 AI 课程中看到过它们（这是一个特殊的旅行者问题，每条边的成本为 1），而且他们从未告诉过我在现实生活中的用途。