学习常用模型及算法4.元胞自动机

一维元胞自动机。给出任意一个状态，都能知道下一时刻的状态。规则已给出，总共有2^3 = 8种可能。

二维元胞自动机——生命游戏

元胞的状态是有限的——不是有车就是无车，不是死就是活。
可以用简单的规则来模拟复杂的问题。

1.元胞自动机的构成要素

左图可用来模拟疾病传播情况

最常用的就是正方型网格，其次是六边型网格。三角型网格几乎不出现。

最常用的为左数两种邻居，但具体按照题目要求决定。

边界处理总共有四种类型。其中汽车交通就采取的是吸收型（汽车经过以后就会消失不见）
右侧采取的是周期型，相当于将相同的网格拼在一起。

总和型是合法型的一种特殊情况

2.例森林火灾模型

火灾在森林中蔓延的模型。元胞总共有三种状态：空格、树、火。
其中如果树的任一邻居是火（或者树遭雷劈），它的下一阶段就会变成火。再下一阶段就变成了空格。会以极小概率再次变成树。

系统稳定条件：着火的密度和由空格转化而成的树的密度应该是相等的。
时间尺度分离条件：遭雷劈的概率<<空格转化成树的概率<<树被火烧完的时间尺度

用切片重拼的方法表示上下左右邻居。

这里用RGB分别表示着火、树和空格。

% simulate forest fire with cellular automata
% zhou lvwen: zhou.lv.wen@gmail.com
% August 15 2010
n = 300;
Plight = 5e-6;
Pgrowth = 1e-2;
UL = [n 1:n-1];
DR = [2:n 1];
veg=zeros(n,n);
imh = image(cat(3,veg,veg,veg));
% veg = empty=0 burning=1 green=2
for i=1:3000
    %nearby fires?
    sum =            (veg(UL,:)==1) + ...
        (veg(:,UL)==1)     +      (veg(:,DR)==1) + ...
                     (veg(DR,:)==1);
    veg = 2*(veg==2) - ...
          ( (veg==2) & (sum>0 | (rand(n,n)<Plight)) ) + ...
          2*((veg==0) & rand(n,n)<Pgrowth) ;
    set(imh, 'cdata', cat(3,(veg==1),(veg==2),zeros(n)) )
    drawnow
end