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

Question

我正在寻找一种能够尽可能随机地找到 Hamiltonian path 的高效算法在双向 N*M 网格中。

有人知道我在哪里可以找到或如何构建这样的算法吗？

---

我已经找到了一种有效的方法(见下图)。这里的最终结果是哈密顿循环。删除随机边将使其成为哈密顿路径。该算法是高效的，但没有提供足够的随机性。这种方法将始终使路径的起点和终点彼此相邻，而我希望它们位于随机位置。 Space-filling curve 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

Answer 1

首先，pdf 文件中显示在图像上的算法不是汉密尔顿路径问题的解决方案，而是迷宫生成的解决方案，因为最终路径有多个分支。

要查找迷宫生成算法，请参阅: https://en.wikipedia.org/wiki/Maze_generation_algorithm

下面是一个在 N*M 二维网格上生成哈密顿路径的简单算法:

1. 设 NM 个网格(例如，45):

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

2. Let's start from the East/North corner and let's create a simple zigzag to the West and to the East:

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

Now we have a Hamiltonian path.

3. Let's search two glued edges which one front of the other. They are the beginning and the end of a loop:

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

4. Ensure that there is at least one edge inside the loop that is glued to an edge outside the loop, otherwise, go to step 3:

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

5. Shortcut the loop:

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

6. Reattach the loop by the two other glued edges:

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

7. If the Hamiltonian path is not randomized enough, go to step 3.

Only the start and the end will not move. To randomize the end or the start, you can replace the initial zigzag by another algorithm:

1. Choose one of the four corners
2. Search all the non-visited neighbors
3. If there is no neighbor, the map is filled, otherwise go to step 4
4. Only keep the neighbors that have a void or a visited cell on one side, left or right (in other words, the neighbors that walk along the border of the non-visited area)
5. Choose one of those neighbors, visit it and go to step 2

The result may look like that:

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

使用此算法，起点仍然在拐角处，但终点可以在任何地方。要随机化开始和结束，您可以应用一种算法，您可以在开始或结束时根据需要迭代任意多次。让我们开始吧:

1. 找到起点:

|vO-O-O-O-O        |O-O-O-O O|     | |O O-O O O|   | | |O-O-O O-O

2. Locate a neighbor that is not directly connected to the start (you will always find one in a 2D grid):

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

3. Find from where you arrive to it from the start (respectively from the end):

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

4. Cut this link and create a link between this point and the start:

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

The start has moved two cells. The start and the end are as on a checkerboard and they only can move on a case with the same color.

Now your path is completely randomized.

Here is the whole algorithm in Python. You can run it here:http://www.compileonline.com/execute_python3_online.php

The result is stored in an array (self.gameGrid) that is logged twice (with arrows and with nodes and lines). The first two glued edges are called a permutation and the second ones are called an intersection.

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