新作了一个 GIF 动图,演示 Wilson 算法和宽度优先算法

2017-09-13 16:33:14 +08:00
 mathzhaoliang

以前写的一个脚本,今天拿来改了下,做了一个彩色的 GIF 图。动图见 github 项目主页

演示的是概率论中的一个算法,叫做 Wilson 一致生成树算法,这个算法的目的是在一个有限图的所有的生成树(此处是网格图,其生成树可以理解为完美迷宫)中以等概率完全随机地取样。这个算法关键的概念是擦圈的随机游动,它维护一个树 T,然后从一个顶点出发,不停的作随机游动,每当遇到回路就擦掉这个回路继续走,直到撞到 T 为止,然后把得到的路径加入 T。重复这个步骤直到所有顶点都在 T 中为止,这时得到的就是一个完全随机的生成树。然后用宽度优先搜索解这个迷宫。染色方案是根据每个顶点到起点的距离染色。

程序用纯 python 写成,不使用任何第三方库/软件,是将整个过程编码为字节流一次输出。生成例子中的图一般几秒十几秒就可以。用 python2 或者 3 都可以运行,大家不妨试一下。

2832 次点击
所在节点    分享创造
2 条回复
withrock
2017-09-13 17:26:14 +08:00
这个厉害
zddhub
2017-09-17 07:56:18 +08:00
已 follow

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/390422

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX