我正在寻找一种有效的算法，该算法能够在双向 N*M 网格中找到尽可能随机的哈密顿路径。
有谁知道我在哪里可以找到，或者如何构建这样的算法？
我已经找到了一种有效的方法（见下图）。这里的最终结果是哈密顿循环。删除随机边将使其成为哈密顿路径。该算法是有效的，但没有提供足够的随机性。这种方法将始终使路径的起点和终点彼此相邻，而我希望它们位于随机位置。 空间填充曲线 http://img593.imageshack.us/img593/8060/sfc.png 图片取自http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.35.3648&rep=rep1&type= pdf
首先，从 pdf 文件显示在图像上的算法不是解决哈密尔顿路径问题的方法，而是解决迷宫生成问题，因为最终路径有几个分支。
要查找迷宫生成算法，请参阅： https ://en.wikipedia.org/wiki/Maze_generation_algorithm
现在这是一个在 N*M 2D 网格上生成哈密顿路径的简单算法：
设一个 N M 网格为（例如，4 5）：
噢噢噢 | | | | 噢噢噢 | | | | 噢噢噢 | | | | 哦哦哦
让我们从东/北角开始，向西和向东创建一个简单的锯齿形：
噢噢噢 噢噢噢 噢噢噢
哦哦哦
现在我们有一条哈密顿路径。
让我们搜索两个粘合的边缘，一个在另一个前面。它们是循环的开始和结束：
噢噢噢
O-OXO-OO | O-OXO-OO |
哦哦哦
确保环内至少有一条边粘在环外的边上，否则转至步骤 3：
噢噢噢
O-OXO-OO | O-OXOxO-O |
OO-OxO-O
快捷循环：
噢噢噢
哦哦哦 | | | OO OxO-O |
OO-OxO-O
通过另外两个胶合边缘重新连接环：
噢噢噢
哦哦哦 | | | 哦哦哦 | | |
哦哦哦
如果哈密顿路径不够随机化，请转到步骤 3。
只有开始和结束不会移动。要随机化结束或开始，您可以用另一种算法替换初始之字形：
结果可能如下所示：
O-O-O-O-O
|
O-O-O-O O
| | |
O O-O O O
| | | |
O-O-O O-O
使用这种算法，起点仍然在一个角落，但终点可以在任何地方。要随机化开始和结束，您可以应用一种算法，您可以在开始或结束时根据需要进行多次迭代。让我们开始吧：
|
v
哦哦哦
|
哦哦哦
| | |
哦哦哦哦
| | | |
哦哦哦
哦哦哦
|
->哦哦哦
| | |
哦哦哦哦
| | | |
哦哦哦
哦哦哦
|
OXO-OO O
| | |
哦哦哦哦
| | | |
哦哦哦
哦哦哦 | | 哦哦哦哦 | | | 哦哦哦哦 | | | | 哦哦哦
开始移动了两个单元格。开始和结束就像在棋盘上一样，它们只能在相同颜色的情况下移动。
现在你的路径是完全随机的。
这是Python中的整个算法。你可以在这里运行它：http: //www.compileonline.com/execute_python3_online.php
结果存储在一个数组 ( self.gameGrid) 中，该数组记录了两次（带有箭头以及节点和线）。前两个粘合的边缘称为排列，第二个称为交集。
import random
import enum
class From(enum.Enum):
NOWHERE = 1
NORTH = 2
EAST = 3
SOUTH = 4
WEST = 5
class Hamiltonian:
def __init__(self, width: int, height: int, start: tuple = (0, 0)):
self.arcs = {From.NORTH: (0, -1), From.SOUTH: (0, 1), From.EAST: (1, 0), From.WEST: (-1, 0)}
self.width = width
self.height = height
self.start = start
self.grid = {(i, j): self._zig_zag(i, j) for i in range(width) for j in range(height)}
self.grid[start] = From.NOWHERE
self.curr_loop = []
def generate(self, count: int = 100):
for i in range(count):
sp = self._split_grid()
self._modify_path(sp)
tu = self._mend_grid(sp)
self._modify_path(tu)
def _modify_path(self, spl):
pt_a, pt_b = spl
pta, ptb = self.grid[pt_a], self.grid[pt_b]
orientation = pta
if orientation in [From.NORTH, From.SOUTH]:
if pt_a[0] < pt_b[0]:
pta, ptb = From.EAST, From.WEST
else:
pta, ptb = From.WEST, From.EAST
else:
if pt_a[1] < pt_b[1]:
pta, ptb = From.SOUTH, From.NORTH
else:
pta, ptb = From.NORTH, From.SOUTH
self.grid[pt_a] = pta
self.grid[pt_b] = ptb
def _move(self, pt) -> [tuple, None]:
if pt in self.grid and self.grid[pt] != From.NOWHERE:
(x, y), (dx, dy) = pt, self.arcs[self.grid[pt]]
if (x + dx, y + dy) in self.grid:
return x + dx, y + dy
return None
def _set_loop(self, start, stop):
self.curr_loop = []
point = start
while point and len(self.curr_loop) <= len(self.grid) and point != stop and self.grid[point] != From.NOWHERE:
point = self._move(point)
self.curr_loop.append(point)
return point == stop
def _split_grid(self) -> tuple:
candidates = []
for pt, dx in self.grid.items():
x, y = pt
if dx == From.NORTH:
cx = (x+1, y - 1)
if cx in self.grid and self.grid[cx] == From.SOUTH:
candidates.append((pt, cx))
elif dx == From.SOUTH:
cx = (x+1, y + 1)
if cx in self.grid and self.grid[cx] == From.NORTH:
candidates.append((pt, cx))
elif dx == From.EAST:
cx = (x + 1, y + 1)
if cx in self.grid and self.grid[cx] == From.WEST:
candidates.append((pt, cx))
elif dx == From.WEST:
cx = (x - 1, y + 1)
if cx in self.grid and self.grid[cx] == From.EAST:
candidates.append((pt, cx))
if len(candidates) > 0:
start, end = random.choice(candidates)
if self._set_loop(start, end):
return start, end
elif not self._set_loop(end, start):
raise Exception('Cannot split. Loop failed.')
return end, start
def _mend_grid(self, sp):
candidates = []
for pt, dx in self.grid.items():
(x, y), lx = pt, pt in self.curr_loop
if dx == From.NORTH:
cx = (x+1, y - 1)
rx = cx in self.curr_loop
if cx in self.grid and self.grid[cx] == From.SOUTH and rx != lx:
candidates.append((pt, cx))
elif dx == From.SOUTH:
cx = (x+1, y + 1)
rx = cx in self.curr_loop
if cx in self.grid and self.grid[cx] == From.NORTH and rx != lx:
candidates.append((pt, cx))
elif dx == From.EAST:
cx = (x + 1, y + 1)
rx = cx in self.curr_loop
if cx in self.grid and self.grid[cx] == From.WEST and rx != lx:
candidates.append((pt, cx))
elif dx == From.WEST:
cx = (x - 1, y + 1)
rx = cx in self.curr_loop
if cx in self.grid and self.grid[cx] == From.EAST and rx != lx:
candidates.append((pt, cx))
a, b = sp
if (a, b) in candidates:
candidates.remove((a, b))
elif (b, a) in candidates:
candidates.remove((b, a))
if len(candidates) > 0:
return random.choice(candidates)
else:
return sp
def _zig_zag(self, x: int, y: int) -> From:
even = y % 2 == 0
if (x == 0 and even) or (x == self.width - 1 and not even):
return From.NORTH
return From.WEST if even else From.EAST
def print_path(self):
result_str = ''
for y in range(self.height):
for x in range(self.width):
if (self.grid[x, y] == From.NORTH) or ((y > 0) and (self.grid[x, y - 1] == From.SOUTH)):
result_str = result_str + ' |'
else:
result_str = result_str + ' '
result_str = result_str + ' \n'
for x in range(self.width):
if (self.grid[x, y] == From.WEST) or ((x > 0) and (self.grid[x - 1, y] == From.EAST)):
result_str = result_str + '-O'
else:
result_str = result_str + ' O'
result_str = result_str + ' \n'
print(result_str)
if __name__ == '__main__':
h = Hamiltonian(5, 5)
h.generate(500)
h.print_path()
本文介绍了一种方法：
奥伯多夫，R。弗格森，A。雅各布森，JL；Kondev, J. -长密实聚合物中的二级结构(arXiv.org)
该方法大致包括以下内容：从锯齿形图案（网格上的非随机哈密顿路径）开始，并重复对路径应用变换（称为“backbite”）。backbite 包括将一条边从端点 A 添加到相邻顶点 B 而不是 A 连接到的那个（从而创建一个循环），然后删除从 B 开始的边，而不是刚刚添加的边，并且这会导致循环（除了刚刚添加的循环之外，总是只有一个导致循环）。
作者添加了一些条件以获得粗略的均匀性（包括估计应用背咬移动的次数）。论文中的详细信息。
作者还凭经验证明，他们的方法生成相邻端点的概率与均匀随机哈密顿路径中的理论概率近似匹配。
这里有一个 JavaScript 算法的实现：Hamiltonian Path Generator
足够的随机性是非常普遍的，你应该有一些基准，最著名的欧几里德 TSP 算法有 3/2 近似值（Christofides 算法），它使用 MST（就像你提到的算法是 2 近似值），正如你在wiki中看到的当前找到的最佳 PTAS 的运行时间取决于 (n log n)^f(c,2)，c > 0（在像您的样本一样的二维空间中），近似为 (1+1/c)，最佳近似为 TSP具有常数因子的是3/2 - 1/500算法（最近发现），但它们都使用逻辑方式，有一些随机用法，但不会导致所有事物都留给随机选择。如果你只是想使用随机你可以使用Random Walk，它更随机但看到Markove Chain以获得更好的性能和随机性。
您可以从您提到的方法开始找到哈密顿路径。要进一步随机化解决方案，您可以按照wiki中的说明开始旋转边缘。更频繁地执行此操作将使解决方案更加随机。将随机边旋转 N*M 次使算法保持在有效范围内，同时使找到的哈密顿路径更加随机。