algorithm - 生成只有 1 个有效哈密顿循环的图

Question

我正在寻找一些正确方向的建议/指导。

我的要求是生成一个图表而不是解决一个问题。

我希望实现一种算法来生成只有 1 个哈密顿循环的图(NxN 网格)。请注意，只有一个独特的解决方案是至关重要的。该图将是一个 NxN 节点网格，每个节点只有 4 个相邻节点，即顶部、右侧、底部、左侧。节点只能被访问一次。除此之外，还可以有一些特殊的节点。

1. 死节点，即它们没有边缘连接
2. 固定入口和导出节点，即入口和导出节点已经定义，没有其他节点可以连接到给定节点。它可以是一个。相邻节点 b.直节点

一些例子:

@ - means that nodes can be connected with adjacent nodes (top,right,bottom,left)
$ - indicated dead end (no connections with adjacent nodes)

Graph 1 =>
@-@-@
@-$-@
@-@-@

Solution 1 =>
1-2-3
8-$-4
7-6-5

here the solution of the graph is 1->2->3->4->5->6->7->8->1. Notice how the $ node was not included in the final solution.

---

我的方法:

我采用 n*n 网格，并首先在图形上放置随机死节点。在此之后，我放置随机的特殊节点。然后我运行遍历整个网格的 dfs 搜索以查看是否存在满足特殊节点条件的有效循环并仅访问每个节点一次(起始节点除外)并在起始节点结束，使其成为一个完整的循环。

我的问题:

我在这里问的是如何确保图形只有 1 个有效循环。我可以做的一件事是通过在每个循环之后添加更多死节点和特殊节点来递归地迭代级别，直到有效哈密顿循环的数量减少到一个。这就是我计划实现的。

理想情况下，您将如何解决这个问题？

Answer 1

首先我想说明一下，我还没有找到完整的解决方案。

我会做的是在网格中生成一个循环并存储这个“解决方案”，然后在所有遗漏的方 block 上添加一个死胡同，这使得生成的循环哈密尔顿。然后我会通过迭代添加“强制边缘”并检查是否存在第二个(读作:“多个”)哈密顿循环来遵循您的做法。

此检查可以表述为以下问题:“如果您知道一个给定的平面图是否包含多个哈密顿循环，您将如何检查？”。

我使用“平面”的原因很容易解释。您的起始网格是平面的，删除节点或强制边缘不会使其成为非平面的。这是因为强制边 A-B 可以在 A-X-B 中转换，其中 X 是一个新节点，因此需要通过任何哈密顿循环访问，从而导致强制边被访问。

下面列出了我尝试将一个哈密尔顿循环转换为另一个的方法:

如果您采用两个平面哈密尔顿循环并采用它们不匹配的所有边，则这些边会形成一个循环(可能会多次访问节点)。该循环具有边缘在一个哈密顿循环和另一个哈密顿循环之间交替的特性。我找不到逆转此过程的方法。