最近在准备数学建模比赛，元胞自动机好像是比较有用的一个模型，或者说框架。

初见

从去年准备国赛考试就一直听说这个元胞自动机这个名词，但是一直不懂这是什么东西，据说还跟可计算理论息息相关，当时我就对它印象很差。。。这个寒假有了更多的时间来准备这个比赛，因此就专门看了看这个模型，或者说框架，有了一点浅显的了解，可以先通过下面的例子开始对这个模型的了解。

简单的例子–戴帽子问题

现在假设这样一个场景，很多学生排成一排，其中带着帽子的用true表示，不带帽子的用false表示，他们戴帽子与否遵从这样一个规则：

Hat rule: a student will wear the hat in the following class if one or the other—but not both—of the two classmates sitting immediately on her left and on her right has the hat in the current class (let us say that if nobody wears the hat, then a hat is out of fashion; but if both neighbors wear it, it is too popular to be trendy).

意思就是当某学生旁边的两个人都不带帽子，或者都带帽子的时候，这个学生就不带帽子，若是旁边的两个人有一个戴帽子，那么他就戴帽子。然后可以用代码模拟这个过程。写了一段简单的cpp代码模拟~

class CA
{
public:
	void addElement(bool);
	void changeElement(int, bool);
	void simulate();
private:
	vector<bool> v;
};

void CA::addElement(bool hat)
{
	v.push_back(hat);
}

void CA::changeElement(int index, bool hat)
{
	v[index] = hat;
}

void CA::simulate()
{
	int counter = 50;
	while (counter)
	{
		vector<bool> buf(v);

		if (buf[1] == 1)
			v[0] = 1;
		else
			v[0] = 0;

		for (int i = 1; i < buf.size() - 1; i++)
		{
			if (buf[i - 1] ^ buf[i + 1])
			{
				v[i] = 1;
			}
			else
			{
				v[i] = 0;
			}
		}
		if (buf[buf.size() - 2] == 1)
			v[buf.size() - 1] = 1;
		else
			v[buf.size() - 1] = 0;

		for (int i = 0; i < v.size() - 1; i++)
			if (v[i])
				cout << v[i] << " ";
			else
				cout << "  ";
		if (v[v.size() - 1])
			cout << v[v.size() - 1] << endl;
		else
			cout << endl;
		counter--;
	}
}

代码打印出来的图形很有意思，是一个分形结构，就像下图这样~其中每一行是每一个时间戳下所有元胞的状态，每一列是一个元胞随着时间戳的增大的状态的变换过程。

基本理论

四个特性

元胞自动机有以下四个特性。

1. Discrete n-dimensional lattice of cells: We can have one-dimensional, two-dimensional, … , n-dimensional CA. The atomic components of the lattice can be differently shaped: for example, a 2D lattice can be composed of triangles, squares, or hexagons. Usually homogeneity is assumed: all cells are qualitatively identical.

2. Discrete states: At each discrete time step, each cell is in one and only one state, σ ∈ Σ, Σ being a set of states having finite cardinality |Σ| = k.

3. Local interactions: Each cell’s behavior depends only on what happens within its local neighborhood of cells (which may or may not include the cell itself). Lattices with the same basic topology may have different definitions of neighborhood, as we will see below. It is crucial, however, that “actions at a distance” not be allowed.

4. Discrete dynamics: At each time step, each cell updates its current state according to a deterministic transition function φ: Σn → Σ mapping neighborhood configurations (n-tuples of states of Σ) to Σ. It is also usually, though not necessarily, assumed that (i) the update is synchronous, and (ii) φ takes as input at time step t the neighborhood states at the immediately previous time step t − 1.

首先，就是需要一个N维晶格的元胞，按照我的理解就是有一个N维的空间，每个空间里有一个元胞。

其次，就是每个元胞在每一时刻都有一个状态，而且这个状态属于一个有限的状态集合。

然后，是元胞之间交互的方式。元胞自动机有这样一个约束，就是说每个元胞的行为取决于他的邻居元胞。暂时理解来说邻居元胞并不一定纯粹是相邻的元胞。而且，自己邻居可以是自己，自己邻居可以是自己。因为很重要所以说两遍

最后，就是元胞状态的改变。随着时间戳增大，元胞状态的改变全部遵循一个函数。函数的参数是所有邻居的状态，输出是该元胞的状态。

针对上面的戴帽子问题，上面的规则可以表述为~

1. 1-dimensional lattice of square cells on a line.

2. Σ = {1, 0} (1 = black or hat on, 0 = white or hat off), so |Σ| = 2.

3. Each cell’s neighborhood is composed by the two nearest cells. If we index the cells by the integers, so that ci is cell number i, then the neighborhood of ci is N(ci) = <ci − 1, ci + 1>.

4. The transition rule φ is simply stated: At each time step t, a cell state is 1 if exactly one of the neighboring cells was 1 at t − 1, 0 otherwise.

就我感觉，元胞自动机很像是编译原理中讲的自动状态机。转换的发生与否取决于该元胞的邻居的状态，由一个函数决定。元胞的状态改变的过程可以看做从源节点走向汇节点的过程。而那个转换函数就相当于Dtran，不知道这样理解对不对，总感觉两者有些类似。

Wolfram的初等元胞自动机

Wolfram，这个人是谁我不太了解，不过有一个搜索引擎，叫做WolframAlpha，前段时间非常火，它跟元胞自动机有啥关系不知道，不过听说WolframAlpha的加载页面就是元胞自动机的样子。也不懂是什么意思。

不过Wolfram的初等元胞自动机，是比较容易理解的。他是指，当元胞维数是1，状态集合的势是2的情况下的自动机。这个时候，邻居有三个，所以转换函数可能的输入有2的3次方也就是8个，而每个输入对应的输出为0或者1两个，因此总共可能的转换函数为2的8次方也就是256个。不同规则会产生不同的奇奇怪怪的元胞状态转换的图形，上面那种分形图形是其中比较好看的。

转换函数分类

根据图形的样子，转换函数可以被分为四类。为什么我认为元胞自动机不是一个模型而是一个框架，就是因为此，每一个转换函数，都是一种完全不同于其他转换函数的规则，因此可以说他只是一个用来描述问题的框架，就像下面提到的交通流模型就是建立在第184条规则的基础上的。

第一类，所有的元胞收敛于相同的状态。

第二类，所有的元胞进入了一种稳定的状态，或者周期性出现的状态。

第三类，混沌状态，无序状态

第四类，复杂的图案和结构

第三类，第四类有啥区别，我也不知道_(:зゝ∠)_，希望有人能够解答。

第184号规则–车辆行驶规则

现在我们可以将元胞中状态true理解为有车占据此位，false代表无车占据此位。转换函数如下所示~

111->1
110->0
101->1
100->1
011->1
010->0
001->0
000->0

其中箭头左边为输入，分别是元胞左边，自己，右边的位置有无车。箭头右边为输出，是元胞下一个时间戳时候的状态。这个转换函数可以被理解为，如果当前前面有车，那就停下来等，如果前面没有车，就前进一格。好像玩大富翁的既视感=-=。

这就是最简单的车辆行驶的模型，后来比较著名的NaSch模型就是对于这个元胞自动机的扩展。这里暂且不论，以后再表。

收尾

总体而言，初等的元胞自动机就是这样，其实也没什么难懂的地方，还留了多维，状态集合大于2的元胞自动机以及NaSch模型等等的坑没填，这些明天再看咯。

参考资料

• Stanford Encyclopedia of Philosophy这是什么，斯坦福哲学百科全书~？