博士家园

发表于 2016-11-20 18:18:24 | 显示全部楼层 |阅读模式
下面的动态图演示的是概率论中的 Wilson uniform spanning tree 算法,你相信吗,它包含 3580 帧,但是只有 274 KB !




Wilson 算法做的是这么一个事情:给定一个有限连通图 $G$,怎样在 $G$ 的所有生成树里面以完全相同的概率随机地任选一个?

在 $G$ 是平面上的网格图的情形,任何生成树都是一个完美迷宫(任何两个房间之间有且仅有唯一的路径相连),上面的动画演示的就是算法的执行过程:

1. 任选一个点 $v$,维护一个树 $T$,初始时刻 $T=\{v\}$。
2.  从任何一个不属于 $T$ 的顶点 $w$ 出发,作简单随机游动,每次随机地走到与当前位置相邻的一个顶点上去,但是一旦走的路径中出现了回路,则立刻将这个回路擦去。直到这个随机游动撞到 $T$ 为止,这时把这个路径加入 $T$。
3. 重复步骤 2 直到所有顶点都属于 $T$ 为止,这时得到的 $T$ 就是一个生成树,而且 $T$ 服从一致分布。

Wilson 算法的证明其实就挺难的(虽然没有什么高深的理论,然而技巧性很强)。我是五六年前接触到的这个算法,后来看到了别人有用 Javascript 做的动画演示:

https://bl.ocks.org/mbostock/11357811

非常羡慕,萌发了自己做一个 gif 版本的动画的想法。然而那时水平不行,根本不知从何下手。对 Python 有一定了解以后本来打算用 pygame 或者 pyglet 做一个的,但是偶然地看到了  gif 编码协议,受到了启发,决定直接从字节流入手来实现。在排除了无数 bug,翻阅了 N 多遍  gif 编码协议之后,终于成功的做出了想要的效果。

脚本不使用任何第三方库/软件,不使用任何图形/图像库,没有任何绘图/染色命令,就是把整个动态的过程编码为字节流然后写入文件,压缩的效率是很高的,接近 8000 帧的 1000x800 的动态图也只有不到 2M,这个动态图你可以看到有 200K 左右,也很不错了。

程序运行时间不等,一般只有几秒,考虑到做的是一个几千帧的 gif 图,这还是很棒的。

如果是在某个图形界面里面画好每一帧,然后再合成的话,得到的图片会非常臃肿,这是因为每一帧图片的大小都是窗口大小,这没有考虑到实际上帧和帧之间只有部分像素在变化。

代码比较长,加注释的话得  >500 行(我还没写注释),目前代码写的还很乱,再修改一下以后会放到 github 上去。


这个方法还可以做 langton 蚂蚁,或者 conway's game of life,它们的特点都是网格图,而且只用到较少的颜色,所以可以有很好的效率和压缩比。

本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2016-11-21 09:45:37 | 显示全部楼层
厉害了,看得电脑都卡住了。。。
发表于 2016-11-22 01:04:10 | 显示全部楼层
66666,看来要好好学习了!
发表于 2016-11-26 05:15:07 | 显示全部楼层
看别人的好像简单,但自己做起来就非常困难了,楼主厉害
 楼主| 发表于 2017-3-3 19:24:51 | 显示全部楼层
wilson 算法的代码见附件,运行
  1. python main.py
复制代码
即可。



本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?注册

x
发表于 2017-10-15 10:54:27 | 显示全部楼层
楼主真厉害。

关于我们|手机版|博士家园 ( 沪ICP备15045866号 )(沪公网安备沪公网安备 31011702001868号) 

GMT+8, 2018-10-22 14:10 , Processed in 1.078125 second(s), 20 queries , Gzip On.

Powered by Discuz! X3.2

© 2004-2018 Comsenz Inc.

快速回复 返回顶部 返回列表