Wilson 均匀生成树算法
问题: 给定一个有限、无向的连通图
常见的生成树算法如 DFS/BFS 算法、Prim 算法、Kruskal
算法等给出的生成树都不是完全随机的。例如,取
DFS 算法 ( 每次将新顶点的顺序打乱再入栈 ) 倾向于尽可能深地探索整个图,因此得到的迷宫往往包含长且蜿蜒的路径,死角 ( 即叶节点 ) 是很少的:
与之相反,Prim 算法由于每次是在当前树上随机添加一个叶节点,因此得到的迷宫往往包含很多死角:
总之从直观上就可以看出这两个算法得到的生成树都不是完全随机的。
目前最快的生成均匀生成树的算法是 Wilson 算法,它借助于擦圈的随机游动来实现。
Wilson
算法. 设
- 任取一个顶点
,维护一个树 ,初始时 。 - 任取一个不属于
的顶点 ,从 出发作图上的随机游动,一边走一边随时擦掉路径中出现的圈 ( 此谓之 loop erased random walk ) ,即每当走到一个以前访问过的顶点 ,则两次访问 之间的路径都被擦掉。按此规则持续行走直到与 相遇为止,这时得到一条从 到 的不含圈的路径 ,把 加入到 中,将 更新为 。 - 重复步骤 2 直到
包含 的所有顶点,这时 是一个服从均匀分布的生成树。
下面是 Wilson 算法的 Javascript 演示,你可以随时单击鼠标来重启动画。
注意 Wilson 算法的描述中有两个任意:
- 初始时可以任选一个初始根节点
。 - 每次可以任选一个不属于
的顶点出发作随机游动。
Wilson 的 论文 中给出的证明相当有技巧性,而且有一些晦涩的部分,我是花了很久才真正理解。本文就来介绍这个证明。
证明思路
先不管均匀分布的事情,我们来说明 Wilson 算法以概率 1 会在有限时间内结束。
命题 1.1. Wilson 算法以概率 1 在有限时间内返回一个生成树。
证明:由于
所以真正有挑战性的地方在于论证得到的生成树服从均匀分布。
证明的大致想法是这样的:我们构造概率空间
对几乎处处的 有定义 ( 不是所有的 都对应一个生成树,但这种例外发生的概率是 0 ) 。 是满射。 ( 不能漏掉任何树 )- 对任何树
,其在 中的原像 的测度是一个与 无关的常数。
一旦找到了这样的概率空间
构造
直接介绍 Wilson 算法背后的游戏可能有点难以理解。作为热身,我们先来看看大家都熟悉的 Tetris 游戏(俄罗斯方块)。我希望你能从中理解「系统随机性」与「玩家策略」的区别。
经典的 Tetris 游戏是这样的,系统每次会随机从屏幕顶端落下
Tetris 游戏的结果由两个因素决定:系统的随机性和玩家的操作。这里系统的随机性是指每次落下的方块的随机性。
系统的随机性可以用一个概率空间
例如,一个样本点
一旦给定了
现在我要告诉你,Wilson 算法背后是一个类似 Tetris 的游戏,但又和
Tetris 游戏有一个关键不同:Wilson
算法的结果只依赖于系统的随机性,不依赖于玩家的操作。换句话说:对给定的
下面来具体介绍这个游戏。
Wilson 算法作为游戏策略
我们来玩一个叫做回路弹出 ( cycle popping )
的游戏。我先介绍这个游戏背后的系统随机性
概率空间
- 固定一个顶点
。对每个 ,定义栈 。 的长度是无穷,其元素 都是来自 的邻居的均匀采样。所有栈元素都是独立的。顶点 的栈是空栈: 。 - 概率空间
是所有栈 的所有可能的状态组成的集合。这是一个无穷离散的概率空间,其上的测度 为乘积测度。
为了方便,我们称
在任何时刻,这些栈
回路弹出游戏. 给定栈的一个状态
在回路弹出游戏中,玩家能做的就是每次选择一个需要弹出的回路,别的什么也做不了。游戏开始之前,
Wilson
算法作为游戏策略.
每次任选一个不属于
树
我们前面剧透过,回路弹出游戏的结果不依赖于玩家的操作。我们把这个事实的证明放在后面,先承认它是正确的,于是我们可以定义映射
定理
2.1.
这个结论解释了为什么 Wilson 算法中的 两个任意 对最终结果是没有影响的。
证明:我们来计算如下事件的概率:依次弹出回路
设
为什么给定
现在
游戏结果与策略无关
最后我们证明最关键的部分:Wilson 算法的结果与每次选择弹出的回路无关。
假设有若干玩家分别玩回路弹出的游戏,每个人采取的策略是不同的。我们想知道,对给定的系统随机性
答案是:不管这些玩家采取怎样的策略,只有两种可能的结果出现:
- 所有人都不能获胜。
- 所有人都能获胜,而且每个人使用的操作次数也相同,最终得到的栈顶图
也相同。不仅如此,每个人弹出的回路组成的集合 也都是相同的。注意这里的回路 是带有颜色标记的,两个回路相同不仅要求包含的顶点相同,也要求对应顶点的颜色相同。仅仅弹出的顺序可能不同。
我们只要证明如下的结论即可:
引理.
对任一栈状态
证明:对玩家
设
如果
既然
接下来的论述是钻石引理 ( diamond lemma )
的典型操作:我们引入两个新玩家
和 第一步操作相同,因此由归纳假设 可以经过 步后获胜; 和 前两步操作后到达相同的状态,而已知 可以在 步后获胜,所以由归纳假设 也可以在 步后获胜; 和 第一步操作相同,而已知 可以在 步后获胜,所以由归纳假设 也可以在 步后获胜。
至此我们就说明了
对没有接触过钻石引理的读者,我这个论述比 Wilson 的原证明的论述要繁琐,但是这个角度更本质地揭示了为什么游戏的结果不依赖于具体的策略。