在网格中找到一个随机的哈密顿路径的算法？

Question

我正在寻找一种高效算法，能够在双向的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

- Fejuto

---

闻起来像作业 - 谷歌是你的朋友。 - duffymo

Answer 1

首先，你所展示的图像中的算法并不是解决哈密顿路径问题的解决方案，而是迷宫生成的解决方案，因为最终路径有几个分支。

要查找迷宫生成算法，请参见： https://en.wikipedia.org/wiki/Maze_generation_algorithm 现在这里有一个简单的算法来在N*M 2D网格上生成哈密顿路径：

1. 让一个NM网格为（例如，4*5）：

    O-O-O-O-O
    | | | | |
    O-O-O-O-O
    | | | | |
    O-O-O-O-O
    | | | | |
    O-O-O-O-O

2. 让我们从东/北角开始，创建一个简单的之字形向西和向东：

    O-O-O-O-O
    |
    O-O-O-O-O
            |
    O-O-O-O-O
    |        
    O-O-O-O-O

现在我们有了一个哈密顿路径。

3. 让我们找到两个相邻的粘在一起的边缘。它们是一个环的起点和终点：

    O-O-O-O-O
    |        
    O-OXO-O-O
            |
    O-OXO-O-O
    |        
    O-O-O-O-O

4. 确保环内至少有一条边缘与环外的边缘相连，否则返回步骤3：

    O-O-O-O-O
    |        
    O-OXO-O-O
            |
    O-OXOxO-O
    |        
    O-O-OxO-O

5. 切断环：

    O-O-O-O-O
    |        
    O-O O-O-O
      | |   |
    O-O OxO-O
    |        
    O-O-OxO-O

6. 通过另外两个粘在一起的边缘重新连接环：

    O-O-O-O-O
    |        
    O-O O-O-O
      | |   |
    O-O O O-O
    |   | |  
    O-O-O O-O

7. 如果哈密顿路径不够随机，请返回第3步。

只有起点和终点不会移动。要使终点或起点随机化，可以用另一种算法替换初始的“之”字形：

1. 选择四个角中的一个
2. 搜索所有未访问的邻居
3. 如果没有邻居，则地图已填满，否则转到步骤4
4. 仅保留具有空白或已访问单元格之一的邻居（换句话说，是沿着未访问区域的边界行走的邻居）
5. 选择其中一个邻居，访问它并转到步骤2

结果可能看起来像这样：

O-O-O-O-O
        |
O-O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-O

使用这个算法，起点始终在一个角落，但终点可以在任何位置。要随机化起点和终点，您可以应用一个算法，在起点或终点上迭代多次。让我们以起点为例：

1. 定位起点：

``` | v O-O-O-O-O | O-O-O-O O | | | O O-O O O | | | | O-O-O O-O ```

2. 找到与起点没有直接连接的邻居（在2D网格中总能找到一个）：

``` O-O-O-O-O | ->O-O-O-O O | | | O O-O O O | | | | O-O-O O-O ```

3. 找到从起点（或从终点）到达它的位置：

``` O-O-O-O-O | OXO-O-O O | | | O O-O O O | | | | O-O-O O-O ```

4. 剪切此链接并在此点与起点之间创建链接：

O-O-O-O-O
|       |
O O-O-O O
|     | |
O O-O O O
|   | | |
O-O-O O-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()

- Fabrice TIERCELIN

Answer 2

本文描述了一种方法：

Oberdorf, R.；Ferguson, A.；Jacobsen, J.L.；Kondev, J. - 长紧致聚合物中的二级结构（arXiv.org）

该方法大致包括以下步骤：从一个锯齿形图案（网格上的非随机哈密顿路径）开始，反复应用一个变换（称为“倒咬”）到路径上。倒咬包括将一条边从一个端点A添加到与A相邻的另一个顶点B（从而创建一个环），然后删除从B开始的不是刚刚添加的那条边并导致环的边（除了刚刚添加的边之外，始终只会有一条导致环的边）。

作者们添加了一些条件以获得粗略的均匀性（包括对应用倒咬移动的次数进行估计）。详见论文。

作者们还通过实验证明，他们的方法生成相邻端点的概率大致与均匀随机哈密顿路径的理论概率相匹配。

这里有一个JavaScript实现该算法的链接：哈密尔顿路径生成器。

- Pedro Gimeno

Answer 3

足够的随机性是非常普遍的，你应该有一些基准。最著名的欧几里得TSP算法有3/2的近似度（Christofides算法），它使用MST（像你提到的算法一样，它是2-近似的）。正如你在维基百科中看到的，目前找到的最好的PTAS运行时间取决于(n log n)^f(c,2)对于c > 0（在二维空间中，就像你的样本一样），近似值为(1+1/c)。对于具有恒定因子的TSP，最佳近似值是3/2 - 1/500算法（最近发现），但它们都使用逻辑方法，有一些随机用法，但这并不会导致所有事情都留给随机选择。如果你只想使用随机，你可以使用随机游走，它更加随机，但是请参考马尔可夫链以获得更好的性能和随机性。

- Saeed Amiri

Answer 4

您可以从提到的途径开始查找哈密顿路径。为了进一步随机化解决方案，您可以像wiki中提到的那样开始旋转边缘。这样做得越频繁，解决方案就会变得更加随机。将一个随机边缘旋转N * M次可以使算法保持高效，并使找到的哈密顿路径更加随机。

- Fejuto

---

有人能解释一下为什么这个被踩的答案被接受了吗？ - James LT

Answer 5

你的问题是错误的。你正在寻找欧拉路径。按照定义，哈密顿路径始终是一个完整的循环（-1边）。

与寻找循环一样，欧拉路径也不是NP难题。

- Zimné