用1个有效的哈密尔顿周期生成图 [英] Generating graphs with only 1 valid Hamiltonian cycle

问题描述

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

我正在寻找一种算法来生成一个只有1个哈密尔顿循环的图（NxN网格）。请注意，只有一个独特的解决方案至关重要。该图将是N×N的节点网格，每个网格只有4个相邻节点，即顶部，右侧，底部，左侧。节点只能访问一次。除此之外，还可以有一些特殊的节点。

1. 死亡节点即它们没有边缘连接


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

一些例子：

 <$ c $表示节点可以与相邻节点连接（顶部，右侧，底部，左侧）
 $  - 表示终点（与相邻节点无连接）
 
图1 => ; 
 @  -  @  -  @ 
 @  -  $  -  @ 
 @  -  @  -  @ 
 
解决方案1 ​​=> 
 1-2-3 
 8  -  $  -  4 
 7-6-5 
 
这里图的解是1-> 2-> 3→4-将5-> 6-&将7-> 8-→1。注意最终解决方案中没有包含$节点。 
  

---

我的方法：

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

我的问题：

我在这里问的是如何确保图形只有1个有效周期。我可以做的一件事是在每个循环后面添加更多的死节点和特殊节点，直到有效哈密尔顿周期的数量减少到1，递归迭代该级别。这是我打算实施的。

您如何理想地解决此问题？

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

3x3图形

  @@@ 
 @ $ @ 
 @@@ 
  

4x4图形

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

<5x5图表

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

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

I am looking for some advice /guidance in the right direction.

My requirement is to generate a graph rather than solving one for solution.

I am looking to implement an algorithm to generates a graph(NxN grid) with only 1 hamiltonian cycle. Note that only one unique solution is of key importance. The graph will be a NxN grid of nodes with each having just 4 neighbouring nodes i.e top, right, bottom, left. Nodes can be visited only once. Apart of this, there can be some special nodes.

1. Dead nodes i.e. they have no edge connections
2. Fixed entry and exit node i.e entry and exit nodes are already defined and no other node can connect with the given node. It can be a. adjacent nodes b. straight nodes

Some examples:

@ - 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.

---

My Approach:

I take a n*n grid and start by placing random dead nodes on the graph. After this, I place random special nodes. I then run a dfs search that traverses the entire grid to see is a valid cycle presents that fulfills the special node criteria and visits every node only once (except for the start node) and end at the start node, making it a complete loop.

My Questions:

What I am asking here is how do I ensure that the graph has only 1 valid cycle. One thing I can do it iterate on the level recursively by adding more dead nodes and special nodes after every cycle, till the number of valid Hamiltonian cycle decreases to one. This is what I am planning to implement.

How would you ideally approach this problem?

解决方案

Why not just connect the outer nodes to form a circle, and label all inside nodes as "dead nodes"?

For example, borrowing your notation from above...

3x3 Graph

@@@
@$@
@@@

4x4 Graph

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

5x5 Graph

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

There will always be exactly one solution, and it's easy to generate graphs of arbitrary size.

这篇关于用1个有效的哈密尔顿周期生成图的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！