1

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

我的要求是生成一个图表，而不是解决一个解决方案。

我正在寻找一种算法来生成一个只有 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 网格并首先在图表上放置随机死节点。在此之后，我放置随机的特殊节点。然后我运行一个遍历整个网格的 dfs 搜索，以查看是否存在满足特殊节点条件的有效循环，并且只访问每个节点一次（起始节点除外）并在起始节点处结束，使其成为一个完整的循环。

我的问题：

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

你会如何理想地解决这个问题？

4

2 回答 2

0

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

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

这个检查可以表述为以下问题：“如果你知道一个给定的平面图，你如何检查一个给定的平面图是否包含一个以上的汉密尔顿循环？”。

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

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

如果你取两个平面哈密顿循环并取所有不匹配的边，这些边会形成一个循环（可能会多次访问节点）。这个循环具有边缘在一个哈密顿循环和另一个循环之间交替的特性。我找不到扭转这个过程的方法。

于 2017-08-09T15:10:50.417 回答
0

为什么不将外部节点连接成一个圆圈，并将所有内部节点标记为“死节点”？

例如，从上面借用你的符号......

3x3 图表

@@@
@$@
@@@

4x4 图表

@@@@
@$$@
@$$@
@@@@

5x5 图表

@@@@@
@$$$@
@$$$@
@$$$@
@@@@@

总会有一个解决方案，并且很容易生成任意大小的图形。

于 2017-08-09T15:18:40.660 回答