元胞自动机在数学建模中的应用示例课件

元胞自动机是离散动力学系统CA之所以是离散系统，是因为元胞是定义在有限的时间和空间上的，并且元胞的状态是有限。CA被认为是动力学模型，是因为它的举止行为具有动力学特征元胞简介（Introduction）什么是元胞（CA）自动机第1页/共19页元胞（Cell）

元胞自动机最基本的单元.元胞有记忆贮存状态的功能.所有元胞状态都按照元胞规则不断更新格子(Lattice)元胞的网格空间.元胞构成（Components）第2页/共19页元胞自动机的规则(Rule)某元胞下时刻的状态只决定于邻居的状态以及自身的初始状态．元胞行为(Behavior)局部变化引起全局变化可以简单认为元胞自动机在运动上类似于波.元胞的状态变化依赖于自身状态和邻居的状态第3页/共19页元胞自动机在数学建模中的应用生命游戏森林火灾模型传染病模型2005年美赛公路收费站问题2007年美赛飞机就座问题2010年东三省封闭系统的货币分布问题2011年全国赛污染源问题2012年国际赛旅游方案制定第4页/共19页简单示例1、有1×L个格子；2、每个格有2种状态：01；3、任一时刻若0旁边有1，则下一时刻变成1；若1旁边有0，则下一时刻变成0。第5页/共19页森林火灾元胞自动机模型一片森林由于人为或自然原因，有一处着火，火情将由此处扩散至整个森林。1、用L×L个格子表示整个森林，一格代表一棵树；2、每个格有三种状态：

0：已经燃烧完了，空地；

1：正常一颗树；

5：正在燃烧的树；第6页/共19页3、某一时刻只要一棵树的邻居有一个正在燃烧，则下一时刻它也会燃烧；4、一棵树燃烧t2个时刻后成为空地；5、一个空地t0个时刻后长出新的树木；6、每颗树自然着火的概率为P

。第7页/共19页SARS特征1、具有明显的局部性与潜伏性；2、具有显著的个体传播特点。元胞自动机特点1、时间、空间离散；2、以局部性规则为基础以同步更新为前提来讨论整体性质。SARS传播模型第8页/共19页用元胞自动机模拟SARS传播的优点：通过局部规则的设定而使其更接近于实际情况。第9页/共19页模型构造考虑一L×L

的网格，每一格点(i,j)

处有一人，记为t时刻处的人的状态。易感者潜伏期者病发者免疫者第10页/共19页本模型采用VonNeumann邻居，即每个元胞的上下左右四个元胞作为它的邻居，病菌在邻居间相互传播。传播规则一初始化，生成n个潜伏期者第11页/共19页演化过程4、3、1、2、第12页/共19页主要程序实现元胞邻居：

ne=A(1:L,[L,1:L-1])+A(1:L,[2:L1])+...A([L1:L-1],1:L)+A([2:L1],1:L);矩阵可视化：利用matlab中的image(A)函数第13页/共19页传播规则二

：t

时刻(i,j)

处的人对SARS

病菌的抵抗概率；：t

时刻(i,j)

处的人为SARS

潜伏期状态时对易感者的传染概率；

：t

时刻(i,j)

处的人为SARS患者时对易感者的传染概率；：t时刻(i,j)

处的人为易感者时,(i-1,j),(i,j-1),(i+1,j),(i,j+1)

四处对(i,j)

处总的传染概率；第14页/共19页

：从病发期进入免疫状态所需时间步；

：t时刻(i,j)

处的人已经感染上病菌的时间步长;

：t时刻(i,j)

处的人为潜伏状态时,其转为SARS患者的概率。令第15页/共19页初始化:在t=0时，给定n个潜伏者作为初值，则对任一(i,j)

，状态从t到t+1的演化规则