数学中国培训(元胞自动机).pdfVIP

数学建模讲座：元胞自动机 aqua2001 数学中国超级版主 September4,2010 大家好，我是数学中国超级版主aqua2001。我们这次做元胞自动机的讲 座。 元胞自动机是一个在数学建模中有用的工具。在这里，我们打算通过一 些模型，来初步介绍元胞自动机的应用。使用计算机进行模拟往往在建模过 程中有很大的用途，但凭空说“模拟真实世界”往往让人觉得难以下手。而元 胞自动机则往往能给模拟方法提供一个容易思考的框架。 考虑到大家在建模中的实用性，所以在介绍当中，我会尽量多做直观的介 绍，尽量避免数学计算。详细的数学内容大家可以参照相关书籍。讲解中有 一些图片或说法来源于书籍或网络。 我们在讲解当中，除了一些直接用到元胞自动机的模型，也介绍了在元胞 自动机的发展过程当中一些比较有影响力的内容。它们不一定对建模有直 接的用途，但我希望大家对它的了解能够更广泛一些，这样可能对它进行更 灵活地运用。 元胞自动机（Cellular Automata 或Cellular Automaton, CA）是空间和时间 都离散，物理参量只取有限数值集的物理系统的理想化模型。 它的提出，最早是冯•诺依曼在研究能够自我复制的自动机时提出来的。 其特点是，空间被分成离散的格子（可以是方形、三角形或六边形等），称之为 元胞（Cell）。元胞处于若干可能的状态之一，而且随着时间，其状态可以演 化。每个元胞状态的演化，往往要受到临近元胞的状态的影响。而且，在传 统的元胞自动机中，每个元胞的变化都是同时进行的。 最著名的元胞自动机的例子，应属Conway 提出的“生命游戏”。它的提出 并不是为了具体的应用，但其蕴含的丰富内容引起了许多人的兴趣。假设二 维空间被划分成方形的格子，当然每个格子都是一个元胞。假设每个元胞只 处于两种状态之一：死的与活的。死的可以记为0，活的可以记为1。 现在我们来考察每个元胞周围的“邻居”。“邻居”的定义当然并不唯一， 1 Figure 1: 标准邻居 Figure2: 死亡，存活和重生的规则 有时考虑的是它的上下左右的邻居（如果是三维空间，则还有前后），这被称 为“冯•诺依曼邻居”；有时考虑的是包围在它周围的全部邻居，被称为Moore 邻居。在更高维的空间也可以有类似的定义。当然，也完全可以考虑其它类 型的邻居，也可以包括更广的范围。 在生命游戏中，考察每个元胞的Moore 邻居。如果邻居中只有 1 个或者 没有活的元胞，或者有4 个以上活的元胞，那么这个元胞如果是活的，就变成 死的（由于孤独或拥挤），如果本来是死的就不用变了。若邻居中有2 或3 个 活的元胞，那么如果这个元胞是活的，可以继续存活。如果邻居中有3 个活 的元胞，而中间的元胞现在是死的，那么可以再生。 整个空间的初始的状态可以人为设计，也可以随机设定。随着时间的推 移，每个元胞都或死或生，然而空间的整体却出现了非常复杂的状态演化。 有一些活元胞组成的形状会稳定不动（例如四个活元胞排成田字形），而 有一些则会周期性变化（例如三个活元胞排成一字形）。有一些活的元胞可 2 Figure 3: 滑翔机的运动 Figure 4: 滑翔机发射器 以排列成能够整体运动的形态（称之为Slider，我们暂时翻译成滑翔机。） 有一些元胞的组合可以在自己的周期变化当中不断地发射出滑翔机，有 一些可以在自己的周期当中“吃掉”滑翔机。更多的则是体现出复杂而难以 捉摸的演化状态。活元胞的总数随时间的变化，总的来说也无规律可循。 很奇妙的事情是，有一些组合的形状，可以不停地发射出滑翔机，而发射 的滑翔机之间的间隔，竟然是非周期的，呈现出貌似随机的样子。 我们来看看常见的一些样子，见图5： Conway 证明，生命游戏事实上等价于一个通用图灵机。通过选择不同的 初始条件，可以完成一切计算机能够完成的