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

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

  •  
  •   mathzhaoliang · 67 天前 · 741 次点击
    这是一个创建于 67 天前的主题,其中的信息可能已经有所发展或是发生改变。

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

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

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

    2 回复  |  直到 2017-09-17 07:56:18 +08:00
        1
    withrock   67 天前
    这个厉害
        2
    zddhub   63 天前 via iPhone
    已 follow
    DigitalOcean
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   鸣谢   ·   1831 人在线   最高记录 3541   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.0 · 55ms · UTC 13:49 · PVG 21:49 · LAX 05:49 · JFK 08:49
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1