# 迷宮生成的取樣偏差：隨機 Kruskal 與 Wilson 的生成樹分布 > 隨機 Kruskal 對生成樹的取樣有偏差，Wilson 能均勻取樣。在 2×3 格線列舉 7! 種邊順序，15 棵樹各出現 360 次或 300 次，死路比例與直徑則用來挑適合關卡的迷宮。 原文：https://sheng.page/posts/maze-generation-sampling-bias-kruskal-vs-wilson/ · 發布：2026-10-25 · 作者：Sheng 完美迷宮就是格線圖的一棵生成樹，但隨機生成一棵樹，沒有保證每棵樹等機率出現。把 Kruskal 的邊順序隨機打亂，在 2×3 格線上列舉全部 5,040 種順序，會得到 15 棵樹，其中 9 棵各出現 360 次，另外 6 棵各出現 300 次。Wilson 的 loop-erased random walk 則能均勻抽出生成樹。 在 20×20 格線的比較裡，backtracker 的死路較少、直徑較長，適合先拿來試需要長路徑的關卡；要求每棵生成樹等機率出現，就用 Wilson。 ## 完美迷宮就是生成樹 把每個格子當成頂點，相鄰格子之間的牆當成候選邊，拆掉一面牆，就在圖上留下一條通道。完美迷宮要求任兩格之間恰好有一條路，所有格子都連得起來，也沒有迴圈，正好是一棵生成樹。 有 n 格就會留下 `n−1` 條通道。20×20 格線有 400 格，760 條候選邊最後留下 399 條；縮到 2×3 時只有 6 格、7 條候選邊，共有 15 棵生成樹。 ## 三個生成器 Recursive backtracker 用深度優先搜尋（DFS），從一格出發，隨機走向還沒去過的相鄰格，沒有地方可走就沿原路退回，繼續找未訪格。這種走法傾向留下長而彎的走廊，分叉較少（[迷宮生成文件](https://yog-ex.hexdocs.pm/maze_generation.md)）。 隨機 Kruskal 把所有候選邊打亂，再依序檢查每條邊。union-find 記住哪些格子已經連在一起，邊的兩端還沒連通就拆牆，已經連通就略過，避免形成迴圈。 Wilson 先選一格放進樹，再從樹外任一格出發做隨機漫步，每一步都從相鄰格等機率選一格。走回這次路徑已經經過的格子，就刪掉剛形成的迴圈，這就是 loop-erased random walk；碰到既有的樹時，把剩下的整條路接上去，再選一個樹外的格子繼續，直到所有格子都進入樹裡。初始格固定在左上角也能均勻取樣，均勻性有 [Wilson 1996 年的證明](https://www.cs.cmu.edu/~15859n/RelatedWork/RandomTrees-Wilson.pdf)保證。 ## 2×3 全列舉：Kruskal 不均勻 7 條邊只有 `7! = 5040` 種排列，可以每種都跑過，不必靠抽樣估計 Kruskal 的分布。`kruskal_enum.py` 把結果存成邊的集合，計算每棵樹出現幾次，再用 Wilson 在同一張圖抽 504,000 次作比較： ```python # Does "random spanning tree" mean "every spanning tree equally likely"? # On a 2x3 grid (6 cells, 7 edges) we can feed Kruskal every one of the 7! = 5040 edge # orderings and count how often each tree appears. Wilson's algorithm on the same grid is # sampled 504,000 times for comparison; it is known to sample spanning trees uniformly. from itertools import permutations from collections import Counter import random random.seed(42) W, H = 3, 2 cells = [(x, y) for y in range(H) for x in range(W)] edges = [((x, y), (x + 1, y)) for y in range(H) for x in range(W - 1)] + \ [((x, y), (x, y + 1)) for y in range(H - 1) for x in range(W)] nb = {c: [b if a == c else a for a, b in edges if c in (a, b)] for c in cells} def kruskal(order): parent = {c: c for c in cells} def find(c): while parent[c] != c: c = parent[c] return c tree = [] for a, b in order: ra, rb = find(a), find(b) if ra != rb: parent[ra] = rb tree.append((a, b)) return frozenset(tree) def wilson(): in_tree = {cells[0]} tree = [] while len(in_tree) < len(cells): c = random.choice([x for x in cells if x not in in_tree]) path = [c] while c not in in_tree: # loop-erased random walk c = random.choice(nb[c]) if c in path: path = path[:path.index(c) + 1] else: path.append(c) for a, b in zip(path, path[1:]): tree.append(tuple(sorted((a, b)))) in_tree.add(a) return frozenset(tree) orders = list(permutations(edges)) kc = Counter(kruskal(o) for o in orders) print(f"2x3 grid: {len(edges)} edges, {len(orders)} edge orderings, {len(kc)} distinct spanning trees, uniform would be {len(orders) // len(kc)} each") print("Kruskal: trees per multiplicity ->", dict(sorted(Counter(kc.values()).items()))) samples = 504_000 wc = Counter(wilson() for _ in range(samples)) print(f"Wilson ({samples} samples): {len(wc)} trees, counts from {min(wc.values())} to {max(wc.values())}, uniform would be {samples // len(wc)}") ``` ```text 2x3 grid: 7 edges, 5040 edge orderings, 15 distinct spanning trees, uniform would be 336 each Kruskal: trees per multiplicity -> {300: 6, 360: 9} Wilson (504000 samples): 15 trees, counts from 33360 to 34007, uniform would be 33600 ``` 如果每棵樹等機率，每棵應該各分到 5,040 種順序裡的 336 種。實際結果分成兩群，9 棵各有 360 種順序，另外 6 棵各有 300 種。 兩群可以用格線中間那條直邊區分。這條邊同時屬於左右兩個長度為 4 的迴圈，含它的 9 棵樹各出現 360 次，不含它的 6 棵各出現 300 次。Kruskal 產出的樹包含中間邊的機率是 `3240/5040`，約 64.3%；均勻取樣時應該是 `9/15`，也就是 60%。 Wilson 這次抽到的 15 棵樹，各出現 33,360 到 34,007 次，均勻分布下每棵的期望次數是 33,600。以每棵樹命中機率 `1/15` 的二項分布計算，次數的標準差約 177，最大偏差約 2.3σ，在同時觀察 15 棵樹時，這樣的波動不奇怪。 只抽少量 Kruskal 迷宮，360 與 300 的差距可能混在波動裡，這張小格線的全列舉直接算出了差距。 ## 20×20 的紋理指標 死路是只有一條通道的格子，[死路比例](https://educative.io/courses/mazes-for-programmers/counting-dead-ends)就是這種格子占全部格子的比例。直徑則是任兩格之間最短路徑的最大值，單位用邊數。樹的直徑可以做兩次 BFS：先從任一格找最遠格，再從那一格找最遠格，第二次得到的距離就是直徑。入口與出口已經固定時，要另外算這兩格之間的距離；把直徑兩端當成入口與出口，通關路徑才會等於直徑。 把程式存成 `maze_metrics.py` 執行，會在 20×20 格線上每種生成器各跑 200 張，開頭只設一次 `seed 42`，後面的生成器接續使用同一個亂數狀態，要重現結果就得保留執行順序： ```python # Texture of 20x20 mazes from three generators: share of dead ends, diameter (longest shortest # path, counted in edges) and wall-clock time. Numbers describe this grid size and sample # size only; they are not fixed properties of the algorithms. import random, time random.seed(42) W = H = 20 CELLS = [(x, y) for x in range(W) for y in range(H)] def nbrs(c): x, y = c return [(x + dx, y + dy) for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)) if 0 <= x + dx < W and 0 <= y + dy < H] def link(adj, a, b): adj[a].add(b); adj[b].add(a) def backtracker(): adj = {c: set() for c in CELLS} stack, seen = [(0, 0)], {(0, 0)} while stack: c = stack[-1] options = [n for n in nbrs(c) if n not in seen] if not options: stack.pop(); continue n = random.choice(options) link(adj, c, n); seen.add(n); stack.append(n) return adj def kruskal(): adj = {c: set() for c in CELLS} parent = {c: c for c in CELLS} def find(c): while parent[c] != c: parent[c] = parent[parent[c]]; c = parent[c] return c edges = [(a, b) for a in CELLS for b in nbrs(a) if a < b] random.shuffle(edges) for a, b in edges: ra, rb = find(a), find(b) if ra != rb: parent[ra] = rb; link(adj, a, b) return adj def wilson(): adj = {c: set() for c in CELLS} in_tree = {(0, 0)} while len(in_tree) < len(CELLS): c = random.choice([x for x in CELLS if x not in in_tree]) path = [c] while c not in in_tree: c = random.choice(nbrs(c)) if c in path: path = path[:path.index(c) + 1] else: path.append(c) for a, b in zip(path, path[1:]): link(adj, a, b); in_tree.add(a) return adj def farthest(adj, start): dist = {start: 0} queue = [start] for c in queue: for n in adj[c]: if n not in dist: dist[n] = dist[c] + 1; queue.append(n) far = max(dist, key=dist.get) return far, dist[far] RUNS = 200 print(f"20x20, {RUNS} mazes each") for name, gen in (("recursive backtracker", backtracker), ("Kruskal", kruskal), ("Wilson", wilson)): dead = diameter = 0.0 t0 = time.perf_counter() mazes = [gen() for _ in range(RUNS)] elapsed = (time.perf_counter() - t0) / RUNS * 1000 for adj in mazes: dead += sum(len(v) == 1 for v in adj.values()) / len(CELLS) a, _ = farthest(adj, (0, 0)) diameter += farthest(adj, a)[1] print(f"{name:22s} dead ends={dead / RUNS * 100:5.1f}% mean diameter={diameter / RUNS:6.1f} edges ({elapsed:5.1f} ms per maze)") ``` ```text 20x20, 200 mazes each recursive backtracker dead ends= 10.6% mean diameter= 228.6 edges ( 0.6 ms per maze) Kruskal dead ends= 30.3% mean diameter= 81.8 edges ( 0.7 ms per maze) Wilson dead ends= 29.3% mean diameter= 91.5 edges ( 5.1 ms per maze) ``` Backtracker 的平均死路比例是 10.6%，平均直徑 228.6 邊，死路較少，最長路徑也比另外兩種長。Kruskal 與 Wilson 的死路比例接近，分別是 30.3% 與 29.3%，平均直徑則是 81.8 與 91.5 邊。 生成耗時不含指標計算，backtracker 每張約 0.6 ms，Kruskal 約 0.7 ms，Wilson 約 5.1 ms，這是 Mac 上 Python 單執行緒的單次量測，只適合比較這組實作。關卡若換了格線尺寸，就重新量測耗時與死路比例，別直接沿用這裡的 10.6%。 ## 均勻對玩家有什麼意義 Wilson 讓格線圖的每棵生成樹等機率出現，但同一個死路比例可能對應很多棵樹，對應的樹越多，玩家遇到這個比例的機會就越高，路徑長度也一樣。 每日關卡要能重現，先保存各關的 seed，連同生成器與 Python 版本一起記錄，讓每關使用獨立的亂數狀態，就不用重跑前面關卡消耗過的亂數。這個做法也適用於 Kruskal 與 backtracker。 需要所有生成樹等機率時，用 Wilson，生成後就不再按紋理淘汰結果。能接受取樣偏差、想要接近 Wilson 的死路比例，又希望減少生成耗時，可以先試 Kruskal；需求偏向死路少、最長路徑長，就先試 backtracker。要控制關卡的死路與路程，可以把量測程式接成篩選步驟：生成器回傳的 `adj` 列出每格可通行的鄰格，逐張計算死路比例與入口到出口的距離，符合需求才依連線拆牆，不合的就丟棄重抽。 ## 補充筆記 - 驗收完美迷宮時，先確認所有格子連通且沒有迴圈，再檢查取樣分布。 - 能列舉的小圖就直接數完：2×3 格線的 `7!` 種邊順序讓 Kruskal 的 9 棵樹各出現 360 次、6 棵各出現 300 次，偏差可以精確算出來。 - 核對 Wilson 實作時，用小圖比較各棵樹的出現次數；504,000 次抽樣接近均勻期望，可作為對照。 - 20×20、每種 200 張的比較可當選型起點：要死路少、路徑長，可先試 backtracker（死路約 10.6%、直徑約 229 邊）；Kruskal 與 Wilson 的死路約 30%、直徑約 82 到 92 邊。 - 關卡篩選要量每張迷宮的死路比例與入口到出口的距離，整批平均值不能代替逐張檢查。 ## 延伸閱讀 - David Bruce Wilson〈[Generating Random Spanning Trees More Quickly than the Cover Time](https://www.cs.cmu.edu/~15859n/RelatedWork/RandomTrees-Wilson.pdf)〉，1996：用 loop-erased random walk 生成均勻生成樹的論文。 - YogEx〈[Maze generation](https://yog-ex.hexdocs.pm/maze_generation.md)〉：Elixir 迷宮函式庫文件，以走廊紋理描述不同生成器，適合對照質性描述。 - Jamis Buck《Mazes for Programmers》〈[Counting dead ends](https://educative.io/courses/mazes-for-programmers/counting-dead-ends)〉：線上課程章節，示範用程式統計死路數並比較演算法。 > 想法與技術判斷出自 Sheng，和 Claude 一起起草 · 範例在 Mac 上以 Python 3.15.0 實測。