元胞自动机---林天龙.pptx

CA(元胞自动机);元胞自动机的规则非常简单，甚至用一句话就可以描述，但是他却是万能的。 ----冯诺依曼 ;提要;元胞自动机的简介;元胞自动机的发展历史;20世纪90年代，元胞自动机发展百花齐放，以美国圣达菲为代表，提出了人工生命。 进入21世纪蒂芬·沃尔夫勒姆的A MEW KIND OF Science将元胞提升到更高一层。;元胞自动机的主要应用;元胞自动机基础;元胞自动机的概念;元胞自动机的组成;元胞;元胞空间;元胞网格(Lattice);;元胞边界;元胞邻居;;局部规则;元胞状态; 元胞自动机由元胞、元胞的状态空间、邻居及局部规则四部分组成,可用一个四元组表示: A = ( Ld , S , N , f ) 其中A 为一个元胞自动机; Ld 为元胞空间, d 为元胞空间的维数; S 为元胞的有限状态集; N 表示一个所有邻域内元胞的组合, 为包含n 个不同元胞的空间矢量, 表示为N =( s1 , s2 , ?, sn) , n 是邻居元胞个数, si ∈ Z (整数集) , i = 1 ,2 ,?, n ; f 表示将Sn 映射到S 上的一个状态转换函数;元胞自动机的分类;1维元胞; 考虑有等长的L个格子的线段;其中变量有三个，每个变量取两个状态值，那么就有2×2×2=8种组合，只要给出在这八个自变量组合上的值，f就完全确定了。例如以下映射便是其中的一个规则: ;以上八种组合分别对应0或1，因而这样的组合共有256种（2的8次方）;二维元胞;生命游戏的构成及规则: 元胞分布在规则划分的网格上； 元胞具有，两种状态，代表“死”，l代表“生”； 元胞以相邻的8个元胞为邻居。即Moore邻居形式； 一个元胞的生死由其在该时刻本身的生死状态和周围八个邻居的状态 (确切讲是状态的和)决定: 在当前时刻，如果一个元胞状态为“生”，且八个相邻元胞中有两个或三个的状态为“生”，则在下--时刻该元胞继续保持为“生”，否则“死”去； 在当前时刻。如果一个元胞状态为死。且八个相邻元胞中正好有三个为生。则该元胞在下一时刻 复活。否则保持为死。 ;生命游戏的设计中,我们将平面划分成方格棋盘,每个方格代表一个元胞,元胞状态为0 表示死亡,1 表示活着,邻域半径为1 ,邻域类型为Moore 型,演化规则为:;程序中,用户用鼠标通过图形界面输入元胞的初始状 态;给出邻居的定义和局部规则后,程序即可以自动运行,产 生丰富的各种演化模式。我们采用二维矩阵X ( m , m) 来定义 元胞在时刻t 的状态。具体算法如下: 1) 求相邻矩阵: 定义四个方向向量: n = [1 ,　1 : m - 1 ] ; 　/ / 表示上方(北方) 向量 e = [1 : m – 1, 　m] ; 　/ / 表示右方(东方) 向量 s = [ m ,　2 : m ] ; 　/ / 表示下方(南方) 向量 w = [2 : m ,　1 ] ; 　/ / 表示左方(西方) 向量 2) 求和: :根据Moore邻居模型和矩阵N 为东、南、西、北、 东南、西南、东北、西北八个邻居的和;用矩阵表示如下: N = X ( n , :) + X ( s , :) + X ( : , e) + X ( : , w) + X ( n , e) + X ( n , w) + X ( s , e) + X ( s , w) ; ; 元胞有3个不同的状态.状态为 0是空位,状态= 1是燃烧着的树木, 状态 = 2是树木. 如果4个邻居中有一个或一个以上的是燃烧着的并且自身是树木(状态 为2 ),那么该元胞下一时刻的状态是燃烧(状态为1). 森林元胞(状态为2 )以一个低概率(例如.5 )开始烧(因为闪电). 一个燃烧着的元胞(状态为1)在下一时时刻变成空位的(状态为0 ). 空元胞以一个低概率(例如. )变为森林以模拟生长. 出于矩阵边界连接的考虑,如果左边界开始着火,火势将向右蔓延,右边 界同???.同样适用于顶部和底部. ;三维元胞