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

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

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. 让我们从东/北角开始，创建一个向西和向东的简单之字形：

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

Answer 2

本文描述了一种方法：

Oberdorf, R.；弗格森，A.；雅各布森，JL； Kondev, J. - 长致密聚合物中的二级结构 (arXiv.org)

该方法大致如下包含以下内容：从锯齿形图案（网格上的非随机哈密顿路径）开始，并对路径重复应用变换（称为“backbite”）。 Backbite 包括从端点 A 之一添加一条边到除 A 连接的顶点之外的相邻顶点 B（从而创建循环），然后删除从 B 开始的边，该边不是刚刚添加的边，导致循环（除了刚刚添加的循环之外，总是只有一个导致循环）。

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

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

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

Answer 3

您可以从您提到的方法开始寻找哈密顿路径。要进一步随机化解决方案，您可以开始旋转边缘，如

Answer 4

足够的随机性是非常普遍的，
你应该有一些基准，最著名的欧几里得 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，它更随机，但请参阅Markov Chain 以获得更好的性能和随机性。

Answer 5

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

欧拉路径也不像寻找环路那样是 NP 困难的。