使用循环擦除随机游走实现Wilson算法的无偏迷宫生成

Wilson算法是一种高效生成完美迷宫的方法，它通过构建图的均匀生成树（uniform spanning tree）确保迷宫路径无偏且唯一连接所有单元格。这种算法特别适用于网格图上的迷宫生成，避免了传统随机游走可能引入的循环和偏好问题。核心在于使用循环擦除随机游走（loop-erased random walk, LERW）来探索路径，该机制能自然产生无环路径，从而形成树状结构。

循环擦除随机游走是Wilson算法的关键组件。在标准随机游走中，从起点出发，每次随机选择相邻节点前进，但可能形成自环。LERW通过即时擦除这些环来修正：当游走路径再次访问已走过的节点时，删除从上次访问该节点到当前的循环部分，继续从该节点游走。这种擦除确保最终路径是简单的无环路径。根据Wilson的1997年论文，该方法能以概率1在有限时间内生成均匀分布的生成树，避免了穷举所有可能树结构的计算开销。

在网格图实现中，首先定义数据结构：使用二维数组表示网格，每个单元格记录访问状态和墙壁（上、下、左、右）。初始化时，选择一个随机单元格作为根节点，标记为已访问，并移除其不必要的墙壁。未访问单元格集合用列表或集合维护。算法循环直到所有单元格访问完毕：从未访问集合中随机挑选一个起点，进行LERW直到击中已访问区域。

具体步骤如下：1. 从起点开始记录路径列表。2. 在当前节点随机选择未访问邻居（四方向：上、下、左、右，边界检查）。3. 如果邻居已访问且在当前路径中，找到上次访问位置，擦除其后的路径段，继续从该位置游走。4. 如果邻居是已访问的树节点，停止游走，将擦除后的路径添加到树中，更新墙壁（移除路径间墙），并标记路径单元为已访问。5. 重复挑选新起点。

为确保效率，可落地参数包括：网格大小n×m，推荐20-50以平衡复杂度和性能；随机种子固定以复现测试；游走步数上限设为2n（防止无限游走），超时则重启该路径。代码清单（Python伪代码）：

import random

def lerw(grid, visited, unvisited, start):
    path = [start]
    current = start
    while current not in visited:
        neighbors = get_unvisited_neighbors(grid, current)
        if not neighbors:
            return None  # 孤立，罕见
        next_pos = random.choice(neighbors)
        if next_pos in path:
            # 擦除循环
            loop_start = path.index(next_pos)
            path = path[:loop_start + 1]
        else:
            path.append(next_pos)
        current = next_pos
    # 添加路径到树
    for i in range(len(path) - 1):
        remove_wall(grid, path[i], path[i+1])
        visited.add(path[i])
    return path

def generate_maze(rows, cols):
    grid = [[{'visited': False, 'walls': {'N': True, 'S': True, 'E': True, 'W': True}} for _ in range(cols)] for _ in range(rows)]
    visited = set()
    unvisited = [(i, j) for i in range(rows) for j in range(cols)]
    # 初始化根
    root = random.choice(unvisited)
    grid[root[0]][root[1]]['visited'] = True
    visited.add(root)
    unvisited.remove(root)
    while unvisited:
        start = random.choice(unvisited)
        path = lerw(grid, visited, unvisited, start)
        if path:
            for pos in path[:-1]:  # 最后一个已在visited
                unvisited.remove(pos)
    return grid

此实现中，get_unvisited_neighbors返回当前未访问的相邻位置，remove_wall根据方向移除墙壁。证据显示，在100×100网格上，平均游走长度约为O(n log n)，但最坏情况可达O(n^2)，故监控运行时间。

优化要点：1. 使用哈希集加速访问检查。2. 对于大网格，分块处理或并行多根初始化（但需调整以保持均匀性）。3. 回滚策略：若游走超过阈值，重选起点。风险包括随机性导致的性能波动，可通过多次运行取中位数评估。均匀性验证：生成多组迷宫，统计长走廊比例，应接近理论均匀分布（无明显偏好）。

在实际应用中，如游戏开发，此算法生成迷宫后，可添加入口出口（随机选边界单元），并集成A*求解器测试连通性。参数清单：- 网格分辨率：32×32起步。- 随机选择策略：均匀随机或顺序（为简单）。- 监控指标：生成时间<1s，路径长度方差<10%。通过这些工程化参数，Wilson算法可可靠用于生产环境，确保迷宫生成高效且无偏。