补充资料：细胞自动机

细胞自动机
cellular automata

　　x ibao zidongji细胞自动机(ceUular auto]川Iata)并行计算机的一种理论模型。细胞自动机可视为由若干小单元构成的动态阵列，其中每一单元具有有限个状态，在离散步序中，每一小单元按一致的法则，由其原状态及其邻域单元的状态决定新的状态。在任一时刻，诸小单元状态的总体构成细胞自动机的格局。从初始格局到最后格局的演化过程为计算处理过程，最后格局被视为计算结果。实际上，细胞自动机的每一小单元均为一有限态自动机，细胞自动机即为有限态自动机的动态阵列，细胞自动机格局的演化过程即为并行计算过程。细胞自动机的主要功能在于:可由局部特性及简单的一致性法则模拟、处理总体上具有高复杂性的离散过程和现象。所以，细胞自动机除了在计算机科学中的重要意义外，它还是描述现实世界中大型复杂离散系统的数学工具。细胞自动机的“小单元”在细胞自动机结构中称为细胞。一个细胞自动机定义为有规律地分布于n维空间中的一个细胞空间或细胞集合。n二1是最简单情形，细胞分布在一条直线上，每一细胞为一方格，每一细胞有两个邻域细胞(简称邻域)，每一细胞仅有两个不同状态，可由0和1值表示。在每一时刻，全部细胞状态值构成的序列为细胞自动机在该时刻的格局。在n=2的情形，细胞在二维平面上分布，它们可为连续的方格，等边三角形，蜂房形式或其他形式。一个简例是，细胞空间为扩，其中z为整数。每一细胞x二(xl，xZ)直接连接它的8个邻域，每一细胞的状态值q任10，1}。局部性法则为局部传递函数占: 占(g。，91，92，…，g，)=1，若。。=o且艺。‘=3或、。一i且2(艺。、(3， 心其他情形其中q0为所考虑的细胞的状态。可知，细胞在离散步序中的新值由该细胞的当前值及其8个邻域细胞的当前值按法则占确定。在每一时间步序，占以并行方式同步地作用于每一细胞状态，从而实现细胞自动机总体格局的并行计算。一般地，细胞自动机的基本模型具有五个主要特征: (1)它们由细胞的离散格局构成; (2)它们在离散时间步序中演化; (3)每一细胞的状态均在同一有限集中取值; (4)每一细胞的状态依同一确定的法则演化; (5)细胞状态的取值法则仅依赖于其自身及其周围局部领域细胞的状态值。 由于不同的目的和需要，出现了许多细胞自动机的变异模型。这些变异由以下因素产生:细胞相互联接形式的改变;细胞取值随机性的引人;细胞间信息交换(通信)机制;外部信息的输人及信息输出，等等。这使得在文献中也使用了其他一些术语。 细胞自动机提供了分布并行计算系统的数学模型，它在新一代计算机结构设计中有重要意义。细胞自动机在模式识别、图象处理及人工智能中有重要应用，在计算机视觉研究中是合宜的模型。

说明：补充资料仅用于学习参考，请勿用于其它任何用途。