新作了一个 GIF 动图，演示 Wilson 算法和宽度优先算法
mathzhaoliang · neozhaoliang · 2017-09-13 16:33:14 +08:00 · 2860 次点击这是一个创建于 2628 天前的主题，其中的信息可能已经有所发展或是发生改变。
以前写的一个脚本，今天拿来改了下，做了一个彩色的 GIF 图。动图见 github 项目主页
演示的是概率论中的一个算法，叫做 Wilson 一致生成树算法，这个算法的目的是在一个有限图的所有的生成树（此处是网格图，其生成树可以理解为完美迷宫）中以等概率完全随机地取样。这个算法关键的概念是擦圈的随机游动，它维护一个树 T，然后从一个顶点出发，不停的作随机游动，每当遇到回路就擦掉这个回路继续走，直到撞到 T 为止，然后把得到的路径加入 T。重复这个步骤直到所有顶点都在 T 中为止，这时得到的就是一个完全随机的生成树。然后用宽度优先搜索解这个迷宫。染色方案是根据每个顶点到起点的距离染色。
程序用纯 python 写成，不使用任何第三方库／软件，是将整个过程编码为字节流一次输出。生成例子中的图一般几秒十几秒就可以。用 python2 或者 3 都可以运行，大家不妨试一下。
Select Language