每日算法 — 使用java实现Wilson随机游走：均匀随机生成树与无偏迷宫生成

引言

均匀随机生成树（Uniform Spanning Tree, UST）是从图中所有可能的生成树中均匀随机选取一棵的算法。与Prim或Kruskal等确定性最小生成树算法不同，UST追求的不是最优性，而是随机性中的均匀性。

Wilson算法由David Wilson于1996年提出，利用循环擦除随机游走（Loop-Erased Random Walk, LERW）来高效生成UST。这一算法不仅具有理论上的优雅性，更是无偏迷宫生成的绝佳工具——生成的迷宫没有Prim算法常见的长走廊偏见，通道分布更加自然。

本文将用Java实现Wilson算法，并展示如何将其应用于迷宫生成。

算法原理

循环擦除随机游走（LERW）

标准随机游走的路径中会包含许多循环（访问同一节点多次）。LERW在游走过程中实时检测并擦除这些循环：

1. 从起点 $u$ 开始随机游走
2. 每到达一个新节点，记录访问路径
3. 如果到达一个已访问过的节点 $v$，则擦除从 $v$ 到当前路径末尾的循环部分
4. 继续游走直到到达目标集合

Wilson算法的核心步骤

给定连通图 $G=(V, E)$：

1. 任选根节点 $r$，将其标记为”已在树中”
2. 当还有未加入树的节点时：
   a. 任选一个未加入树的节点 $u$ 作为起点
   b. 从 $u$ 执行LERW，直到到达”已在树中”的节点
   c. 将LERW的路径加入生成树
3. 最终得到的边集即为均匀随机生成树

Wilson证明了这一算法生成的每棵生成树的概率恰好为 $1/\tau(G)$，其中 $\tau(G)$ 是图的生成树总数（由Kirchhoff矩阵树定理计算）。

Java实现

import java.util.*;

/**
 * Wilson算法实现：均匀随机生成树与无偏迷宫生成
 */
public class WilsonAlgorithm {

    // 迷宫方向：上、下、左、右
    private static final int[][] DIRS = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private static final String[] DIR_NAMES = {"UP", "DOWN", "LEFT", "RIGHT"};

    /**
     * 图的节点类
     */
    static class Node {
        int id;
        List<Edge> edges = new ArrayList<>();

        Node(int id) { this.id = id; }

        void addEdge(Node to, int weight) {
            edges.add(new Edge(this, to, weight));
        }

        Node getRandomNeighbor(Random rand) {
            if (edges.isEmpty()) return null;
            return edges.get(rand.nextInt(edges.size())).to;
        }
    }

    static class Edge {
        Node from, to;
        int weight;

        Edge(Node from, Node to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }
    }

    /**
     * Wilson算法：生成均匀随机生成树
     * @param nodes 图的所有节点
     * @param root 根节点
     * @return 生成树的边集合
     */
    public static Set<Edge> generateUST(List<Node> nodes, Node root) {
        Random rand = new Random();
        Set<Edge> treeEdges = new HashSet<>();
        Set<Node> inTree = new HashSet<>();
        inTree.add(root);

        while (inTree.size() < nodes.size()) {
            // 选择一个不在树中的节点作为起点
            Node start = null;
            for (Node node : nodes) {
                if (!inTree.contains(node)) {
                    start = node;
                    break;
                }
            }
            if (start == null) break;

            // 执行循环擦除随机游走
            List<Node> path = loopErasedRandomWalk(start, inTree, rand);

            // 将路径加入生成树
            for (int i = 0; i < path.size() - 1; i++) {
                Node from = path.get(i);
                Node to = path.get(i + 1);
                // 找到对应的边并加入树
                for (Edge e : from.edges) {
                    if (e.to == to) {
                        treeEdges.add(e);
                        break;
                    }
                }
                inTree.add(from);
            }
        }

        return treeEdges;
    }

    /**
     * 循环擦除随机游走（LERW）
     * 从start出发，随机游走直到到达inTree集合中的节点
     * 过程中擦除所有循环
     */
    private static List<Node> loopErasedRandomWalk(Node start, Set<Node> inTree, Random rand) {
        Map<Node, Integer> firstVisitIndex = new HashMap<>();
        List<Node> path = new ArrayList<>();
        Node current = start;

        while (!inTree.contains(current)) {
            // 如果当前节点已在路径中，说明形成了循环，擦除它
            if (firstVisitIndex.containsKey(current)) {
                int loopStart = firstVisitIndex.get(current);
                // 移除循环部分（从loopStart之后的所有节点）
                for (int i = loopStart + 1; i < path.size(); i++) {
                    firstVisitIndex.remove(path.get(i));
                }
                path = new ArrayList<>(path.subList(0, loopStart + 1));
            } else {
                firstVisitIndex.put(current, path.size());
            }

            path.add(current);
            current = current.getRandomNeighbor(rand);
        }

        // 最后加入目标节点（已在树中的节点）
        path.add(current);
        return path;
    }

    // ==================== 迷宫生成专用实现 ====================

    /**
     * 使用Wilson算法生成迷宫
     * 迷宫表示为网格，墙和通道交替排列
     */
    public static char[][] generateMaze(int width, int height) {
        Random rand = new Random();
        // 迷宫单元格（奇数坐标是墙，偶数坐标是通道）
        int cellW = (width - 1) / 2;
        int cellH = (height - 1) / 2;

        // 用并查集或简单标记来跟踪已访问的单元格
        boolean[][] inMaze = new boolean[cellH][cellW];
        char[][] maze = new char[height][width];

        // 初始化全部为墙
        for (int i = 0; i < height; i++) {
            Arrays.fill(maze[i], '#');
        }

        //  Wilson算法在网格图上执行
        // 随机选择一个起始单元格
        int startR = rand.nextInt(cellH);
        int startC = rand.nextInt(cellW);
        inMaze[startR][startC] = true;
        maze[startR * 2 + 1][startC * 2 + 1] = ' ';

        // 对剩余单元格执行LERW
        for (int r = 0; r < cellH; r++) {
            for (int c = 0; c < cellW; c++) {
                if (inMaze[r][c]) continue;

                // 从这个单元格开始LERW
                List<int[]> path = gridLERW(r, c, inMaze, cellH, cellW, rand);

                // 打通路径上的墙
                for (int i = 0; i < path.size() - 1; i++) {
                    int[] from = path.get(i);
                    int[] to = path.get(i + 1);

                    // 标记单元格为通道
                    maze[from[0] * 2 + 1][from[1] * 2 + 1] = ' ';

                    // 打通两个单元格之间的墙
                    int wallR = from[0] + to[0] + 1;
                    int wallC = from[1] + to[1] + 1;
                    maze[wallR][wallC] = ' ';

                    inMaze[from[0]][from[1]] = true;
                }
                // 标记终点
                int[] last = path.get(path.size() - 1);
                maze[last[0] * 2 + 1][last[1] * 2 + 1] = ' ';
            }
        }

        // 设置入口和出口
        maze[1][0] = 'S';
        maze[height - 2][width - 1] = 'E';

        return maze;
    }

    /**
     * 网格上的循环擦除随机游走
     */
    private static List<int[]> gridLERW(int startR, int startC, 
                                         boolean[][] inMaze, 
                                         int rows, int cols, Random rand) {
        Map<String, Integer> visitIndex = new HashMap<>();
        List<int[]> path = new ArrayList<>();
        int r = startR, c = startC;

        while (!inMaze[r][c]) {
            String key = r + "," + c;

            if (visitIndex.containsKey(key)) {
                int loopStart = visitIndex.get(key);
                for (int i = loopStart + 1; i < path.size(); i++) {
                    visitIndex.remove(path.get(i)[0] + "," + path.get(i)[1]);
                }
                path = new ArrayList<>(path.subList(0, loopStart + 1));
            } else {
                visitIndex.put(key, path.size());
            }

            path.add(new int[]{r, c});

            // 随机选择邻居
            List<int[]> neighbors = new ArrayList<>();
            for (int[] d : DIRS) {
                int nr = r + d[0];
                int nc = c + d[1];
                if (nr >= 0 && nr < rows && nc >= 0 && nc < cols) {
                    neighbors.add(new int[]{nr, nc});
                }
            }
            int[] next = neighbors.get(rand.nextInt(neighbors.size()));
            r = next[0];
            c = next[1];
        }

        path.add(new int[]{r, c}); // 添加已访问的终点
        return path;
    }

    /**
     * 打印迷宫
     */
    public static void printMaze(char[][] maze) {
        for (char[] row : maze) {
            System.out.println(new String(row));
        }
    }

    /**
     * 创建简单网格图用于UST演示
     */
    public static List<Node> createGridGraph(int rows, int cols) {
        List<Node> nodes = new ArrayList<>();
        Node[][] grid = new Node[rows][cols];

        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                grid[i][j] = new Node(i * cols + j);
                nodes.add(grid[i][j]);
            }
        }

        // 添加四邻域边
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (i > 0) grid[i][j].addEdge(grid[i-1][j], 1);
                if (j > 0) grid[i][j].addEdge(grid[i][j-1], 1);
            }
        }

        return nodes;
    }

    public static void main(String[] args) {
        // 测试1：简单网格图的UST
        System.out.println("=== Wilson算法：3x3网格图的均匀随机生成树 ===");
        List<Node> gridGraph = createGridGraph(3, 3);
        Set<Edge> ust = generateUST(gridGraph, gridGraph.get(0));
        System.out.println("生成树边数: " + ust.size());
        for (Edge e : ust) {
            System.out.printf("边: %d -> %d%n", e.from.id, e.to.id);
        }

        // 测试2：迷宫生成
        System.out.println("\n=== Wilson算法生成迷宫（21x11）===");
        char[][] maze = generateMaze(21, 11);
        printMaze(maze);

        // 测试3：多次生成，观察随机性
        System.out.println("\n=== 迷宫多样性测试（3个不同迷宫）===");
        for (int i = 0; i < 3; i++) {
            System.out.println("迷宫 " + (i + 1) + ":");
            char[][] m = generateMaze(15, 9);
            printMaze(m);
            System.out.println();
        }
    }
}

算法分析

时间复杂度

Wilson算法的时间复杂度取决于LERW的期望长度。对于 $n \times n$ 的网格图，LERW的期望覆盖时间为 $O(n^2 \log n)$，而Wilson算法的总期望时间为 $O(n^2 \log n)$，与图的大小成近乎线性关系。

对比其他迷宫生成算法：
– DFS递归回溯：$O(n^2)$，但有明显长走廊偏见
– Prim算法：$O(n^2 \log n)$，有短通道聚集偏见
– Wilson算法：$O(n^2 \log n)$，无偏均匀

空间复杂度

需要存储图结构和LERW的当前路径，空间复杂度为 $O(V + E)$。对于网格迷宫，$E \approx 2V$，因此为 $O(V)$。

均匀性证明的关键

Wilson算法的均匀性依赖于两个深层数学结果：
1. 循环擦除随机游走的轨迹分布与图的生成树分布通过Kirchhoff定理关联
2. 路径拼接时，各LERW之间的独立性保证了全局均匀性

扩展应用

有偏Wilson算法

通过修改随机游走的转移概率，可以生成具有特定统计特性的迷宫：
– 偏好直走：提高继续沿当前方向前进的概率，生成更”蜿蜒”的迷宫
– 偏好转弯：降低继续直走的概率，生成更多交叉路口的迷宫

这些变体牺牲了严格均匀性，但在游戏设计中更受欢迎。

与其他算法的比较

高维推广

Wilson算法可以自然地推广到三维甚至更高维网格，生成三维迷宫或洞穴系统。在三维情况下，通道和墙壁的拓扑结构更加复杂，适合开放世界游戏中的地下城生成。

总结

Wilson算法是随机图论中的一颗明珠，它将循环擦除随机游走与均匀随机生成树巧妙结合，既具有深厚的数学理论基础，又在实践中展现出优雅的简洁性。相比于传统的DFS或Prim迷宫生成算法，Wilson算法生成的迷宫没有任何系统性偏见，通道和死胡同的分布完全符合统计均匀性。在游戏开发、统计物理和组合数学中，掌握这一算法将为你提供一种全新的、无偏的随机结构生成工具。