V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
爱意满满的作品展示区。
mathzhaoliang
V2EX  ›  分享创造

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

  •  
  •   mathzhaoliang ·
    neozhaoliang · 2017-09-13 16:33:14 +08:00 · 2754 次点击
    这是一个创建于 2388 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    2 条回复    2017-09-17 07:56:18 +08:00
    withrock
        1
    withrock  
       2017-09-13 17:26:14 +08:00
    这个厉害
    zddhub
        2
    zddhub  
       2017-09-17 07:56:18 +08:00 via iPhone
    已 follow
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1112 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 22:49 · PVG 06:49 · LAX 15:49 · JFK 18:49
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.