元 胞 自 动 机.ppt

文档介绍：元胞自动机

元胞自动机(Cellular Automata,简称CA,也有人译为细胞自动机、点格自动机、分子自动机或单元自动机)。
是一时间和空间都离散的动力系统。散布在规则格网(Lattice Grid)中的每一元胞(Cell)取有限的离散状态,遵循同样的作用规则,依据确定的局部规则作同步更新。大量元胞通过简单的相互作用而构成动态系统的演化。
构成: 元胞自动机最基本的组成:元胞、元胞空间、邻居及规则四部分。简单讲,元胞自动机可以视为由一个元胞空间和定义于该空间的变换函数所组成。

1. S. Wolfram和初等元胞自动机
初等元胞自动机(Elementary Cellular Automata,简称ECA)是状态集S只有两个元素{s1,s2},即状态个数k=2,邻居半径r=l的一维元胞自动机(谢惠民,1994、李才伟,1997、Wolfram,S,1986)。它几乎是最简单的元胞自动机模型。由于在S中具体采用什么符号并不重要,它可取{0,1},{-l,1},{静止,运动},{黑,白},{生,死}等等,这里重要的是S所含的符号个数,通常我们将其记为{0,1}。此时,邻居集N的个数2r=2,局部映射f:S3→S可记为:
其中变量有三个,每个变量取两个状态值,那么就有2×2×2=8种组合,只要给出在这八个自变量组合上的值,f就完全确定了。例如以下映射便是其中的一个规则:
通常这种规则也可表示为以下图形方式(黑色方块代表l,白色方块代表0):