1、生命游戏逆问题回溯模型摘要本文围绕生命游戏逆问题进行探索分析，以题中所给的大量游戏终局数据为基础，利用回溯算法、元胞自动机，递归迭代为理论基础进行完整的建模工作，然后利用Matlab实现对问题的求解。针对问题一，本文建立了回溯模型。结合题中所给游戏规则，得出细胞进化过程中需满足的基本约束条件，考虑到位于网格边界处细胞与非边界处细胞的邻居数不同，边界处细胞邻居数为3或5，其余非边界处细胞邻居数为8。为了简化运算，本文在调用已知矩阵时还加上了上下两行及左右两列零向量，将原位于边界处细胞转化为非边界处细胞一同处理，从而运用Matlab构建整体的回溯模型，由不同的终局得出其相应的初始状态。针对问题二，
2、本文在问题一的基础上进一步深入探讨，得到回溯一步后只有一种初始状态时原初局应为稳定状态，或者原终局回溯一步后只能为一种情况。而在生命游戏中达到稳定状态时仅有生者恒生的5种情形,分别为蜂窝、面包、砖块、小船及大船。不断在两种情形下变动的只有震荡中的眨眼者以及灯塔。因此，本文以这些特殊情况为基础设定终局回溯一步后只有唯一结果需满足的约束条件，结合第一问的回溯模型对该约束条件在Matlab中进行检验。针对问题三，由问题一对各终局的回溯结果可得知，不同的终局所对应的初始状态可能有多种，根据问题一中已建立的回溯模型，以及问题二中的约束条件，得出当回溯后的初始状态唯一时原终局需满足的约束条件。关键词：回溯
3、算法 迭代 Matlab 稀疏矩阵一：问题重述生命游戏（Life Game）是由数学家John Conway于1970年发明的。是一类特殊的细胞自动机。在简单的规则下，不同初始状态将演变出五彩缤纷的画面。 游戏背景： 生命游戏在一个方形网格中进行，类似于棋盘，每个网格代表一个细胞。 细胞分为“活细胞”和“死细胞”。细胞的“邻居”是指它周围的 8 个网格中的细胞。游戏规则： 1.一个死细胞恰好有3个活邻居的话，就成为一个活的细胞（诞生）；2.一个活细胞有2个或3个活邻居的话，就继续活下去（生存）；3.其他情况下，细胞死去或是保持死的状态（孤独或拥挤）。 4.方形网格以外的细胞，总是死细胞。在如此
4、简单的进化规则下，却可以演化出许多非常奇妙的结果（参见爱课程网，视频公开课数学建模从自然走向理性之路第8讲“计算机仿真与数学建模”），正如维基百科的评价：自从Conway的游戏发明以来，由于其丰富多彩的进化演变模式，以及在社会自组织机制方面出人意料的结果，引起了研究工作者门广泛的关注，其中包括计算机学者、物理学家、生物学家、经济学家、社会学家、数学家以及哲学家。但是，这个有趣的游戏也引出了另一个有趣的问题：如果将顺序倒过来，能否由当前的进化状态推测出其以前的状态？请建立回溯模型或算法，来推测当前游戏状态往前回溯（5）步的初始状态。附件B-test.csv给出了测试数据集，包含了50000个当前
5、的游戏状态以及回溯步数，其中“1”表示活细胞。要求建立模型求出它们往前回溯步的初始状态。需要注意的是，初始状态可能不唯一，求出其中之一即可。作为进一步考虑，能否给出回溯1步有唯一结果所要求满足的条件？测试数据集中有哪些游戏的回溯初始状态是唯一的？结果输出格式同附件B-test.csv格式，只需将“stop.k”改为“start.k”. 二：问题分析本题主要研究生命游戏逆问题的回溯算法。问题一要求建立回溯模型，由题中所给的已知终局回溯得到相应的初局。问题二及问题三要求更深层次的探讨，给出回溯一步有唯一结果时原终局应满足的条件，并判别所给数据中回溯后具有唯一初始状态的终局。问题一要求建立回溯模型。
6、首先结合游戏规则对已知终局进行分析，得出由初局到下一步的转变需满足的基本约束条件，逆推出转换为当前状态的前一个状态应满足的约束条件，从而构建回溯算法。在调用已知矩阵时，先对其进行处理，即在该矩阵基础上加上下两行，左右两列的零向量，代表网格外的死细胞，将原位于网格边界处细胞化为非边界处细胞，简化运算，建立一步回溯模型。最后利用迭代法在一步回溯模型基础上进行反复迭代，得出不同终局经不同回溯次数后相应的初局。问题二要求给出原终局经回溯一步后仅有唯一结果需满足的条件。经分析得出，终局回溯一步后情形唯一只有两种情况：原初局处于稳定状态、原终局回溯情况只有一种即它处于两种变化状态之间，终局与回溯一步后的状
7、态。根据生命游戏中满足这两种情况的七种情况，对已知终局设定相应的约束条件，结合第一问得出的回溯模型对该终局及其约束条件进行检验，最终得出结果。 问题三要求给出原终局经回溯后初局唯一需满足的条件。由问题一的回溯模型及问题二的回溯一步后结果唯一时原终局需满足的约束条件，分析得出当回溯后初局唯一时，原终局需满足的条件。三：符号说明与模型假设3.1 符号说明m行数n列数已知终局矩阵原终局加上左右两列零向量后形成的新矩阵原终局加上左右两列及上下两行零向量后形成的新矩阵随机生成矩阵（矩阵元素为0或1）随机矩阵加上左右两列零向量后形成的新矩阵随机矩阵加上左右两列及上下两行零向量后形成的新矩阵用于存放初局的矩
8、阵s计数3.2 模型假设稳定状态仅为生者恒生的五种情况；变化情况仅在终局和回溯一步后状态之间变化的状态仅有震荡中的两种情况。四：模型的建立与求解4.1模型一：终局回溯根据生命游戏规则，一个死细胞周围恰有三个活细胞，则该细胞成为一个活细胞；一个活细胞周围恰有两个或三个活细胞，则该细胞可继续存活；其它情况下，细胞死去或保持死的状态。方形网格外的细胞为死细胞。（用0,1表示细胞所处状态，0代表死细胞；1代表活细胞。）则细胞存活只能为以下三种情况：010111000010101 000010110000记初局时某个小方格内细胞状态为b(x,y)，s为其周围所有邻居细胞状态之和，如下所示：则应有如下约束
9、表达式： 即若已知细胞为死细胞，前一状态可能为死细胞，则它周围活邻居数目相加不能为3；前一状态也可能为活细胞，则它周围活邻居数目相加不能为2也不能为3。 即若已知细胞为活细胞，前一状态可能为死细胞，则它周围活邻居数目相加一定为3；前一状态也可能为活细胞，则它周围活邻居数目可以为2也可以为3。基于以上回溯基本约束条件，利用Matlab编程进行回溯，得出结果。下图为第一个游戏终局：4.2 模型二：终局回溯一步后结果唯一由前面问题分析得出，终局回溯一步后结果唯一的情况只能是处于稳定状态及仅在两种状态之间变化。共有七种情况，包括生者恒生的五种情况以及震荡中的两种情况。生者恒生的五种情况：砖块、蜂窝、面
10、包、小船、大船震荡中的两种情况：眨眼者、灯塔稀疏矩阵是指那些零元素数目远远多于非零元素数目，并且非零元素的分布没有规律的矩阵。题中所给的生命游戏终局矩阵很符合稀疏矩阵的特点，因此，可利用Matlab中sparse语句返回出终局矩阵中非零元素的下标。 A8(x,y)，第8个游戏终局在Matlab 中利用该语句返回出非零元素的下标，显然，该终局即为生者恒生中的砖块，若要使其回溯一步后只有唯一结果，则回溯一步后的状态也应为稳定状态。假设回溯一步后的初局已达到稳定状态砖块，设定在该初局中c(x,y)为该砖块模型的左上角处方块，则其余非零元素应为如下四点：、。同理，对于其它的六种特殊情况，也可以设定左上
11、角方块为c(x,y)，依次可得出其余非零元素所在的点。结合第一问中已建立的回溯模型可得出回溯一步后的矩阵，然后利用sparse语句可找出非零元素所在的点，若这些点所在位置符合前七种特殊情况，则说明回溯一步后的状态已达到稳定或其变化情况只有两种，即回溯一步后的结果唯一。五：模型评价与改进模型评价：1.模型一中对已有终局矩阵进行预处理，将位于网格边缘处细胞转化为网格内的细胞一同处理，极大地简化了运算；2.模型中借助稀疏矩阵的运用，简易地得出了矩阵中非零元素所在的位置；3.迭代法的运用，简便了模型的运算。模型改进：1.模型一中随机生成的矩阵具有很大的随机性，得到正确结果需运行很多次；2.模型二中的判
12、定情况有七种，运算较为复杂；3.模型构建不完整。参考文献：【1】湖南人文科技学院，生命游戏逆问题，2014年8月15日 【2】feike2008,稀疏矩阵，2014年8月17日 【3】百度百科，生命游戏，2014年8月15日 附录模型一中第一个游戏终局画图程序：for x=1:20 for y=1:20 if a1(x,y)=1 fx=x-1,x-1,x,x;fy=y-1,y,y,y-1;fill(fx,fy,g),hold on axis(0 20 0 20) else end endend模型二中第八个游戏终局画图程序：for x=1:20 for y=1:20 if a8(x,y)=1
13、fx=x-1,x-1,x,x;fy=y-1,y,y,y-1;fill(fx,fy,g),hold on axis(0 20 0 20) else end endend模型一中回溯模型：m=22;n=22;a1= 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0
14、0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
15、0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
16、0 0 0;for k=1:10000 b1=randint(20,20); a2=zeros(20,1),a1,zeros(20,1); a=zeros(1,22);a2;zeros(1,22); b2=zeros(20,1),b1,zeros(20,1); b=zeros(1,22);b2;zeros(1,22); for x=2:m-1; for y=2:n-1; s=b(x-1,y-1)+b(x-1,y)+b(x-1,y+1)+b(x,y-1)+b(x,y+1)+b(x+1,y-1)+b(x+1,y)+b(x+1,y+1); if s = 1 b(x,y) = (rand(1)0.5)
17、; else b(x,y) = 0; end if a(x,y)=0 if b(x,y)=0 if s=3 c(x,y)=b(x,y); else flag=1; break; end elseif s=2|s=3; c(x,y)=1; else flag=1; break; end elseif b(x,y)=0; if s=3 c(x,y)=b(x,y); elseif s=2|s=3; c(x,y)=1; else flag =1; break; end end end if flag = 1 break; end end flag = 0;endfor x=2:m-1 for y=2:n-1 if c(x,y)=1 fx=x-1,x-1,x,x;fy=y-1,y,y,y-1;fill(fx,fy,g),hold on else fx=x-1,x-1,x,x;fy=y-1,y,y,y-1;fill(fx,fy,w),hold on end endendend
