生命游戏逆问题回溯模型.doc

生命游戏逆问题回溯模型摘要本文围绕生命游戏逆问题进行探索分析，以题中所给的大量游戏终局数据为基础，利用回溯算法、元胞自动机，递归迭代为理论基础进行完整的建模工作，然后利用Matlab实现对问题的求解。针对问题一，本文建立了回溯模型。结合题中所给游戏规则，得出细胞进化过程中需满足的基本约束条件，考虑到位于网格边界处细胞与非边界处细胞的邻居数不同，边界处细胞邻居数为3或5，其余非边界处细胞邻居数为8。为了简化运算，本文在调用已知矩阵时还加上了上下两行及左右两列零向量，将原位于边界处细胞转化为非边界处细胞一同处理，从而运用Matlab构建整体的回溯模型，由不同的终局得出其相应的初始状态。针对问题二，本文在问题一的基础上进一步深入探讨，得到回溯一步后只有一种初始状态时原初局应为稳定状态，或者原终局回溯一步后只能为一种情况。而在生命游戏中达到稳定状态时仅有生者恒生的5种情形,分别为蜂窝、面包、砖块、小船及大船。不断在两种情形下变动的只有震荡中的眨眼者以及灯塔。因此，本文以这些特殊情况为基础设定终局回溯一步后只有唯一结果需满足的约束条件，结合第一问的回溯模型对该约束条件在Matlab中进行检验。针对问题三，由问题一对各终局的回溯结果可得知，不同的终局所对应的初始状态可能有多种，根据问题一中已建立的回溯模型，以及问题二中的约束条件，得出当回溯后的初始状态唯一时原终局需满足的约束条件。关键词：回溯算法 迭代 Matlab 稀疏矩阵一：问题重述生命游戏（Life Game）是由数学家John Conway于1970年发明的。是一类特殊的细胞自动机。在简单的规则下，不同初始状态将演变出五彩缤纷的画面。 游戏背景： 生命游戏在一个方形网格中进行，类似于棋盘，每个网格代表一个细胞。 细胞分为“活细胞”和“死细胞”。细胞的“邻居”是指它周围的 8 个网格中的细胞。游戏规则： 1.一个死细胞恰好有3个活邻居的话，就成为一个活的细胞（诞生）；2.一个活细胞有2个或3个活邻居的话，就继续活下去（生存）；3.其他情况下，细胞死去或是保持死的状态（孤独或拥挤）。 4.方形网格以外的细胞，总是死细胞。在如此简单的进化规则下，却可以演化出许多非常奇妙的结果（参见爱课程网，视频公开课数学建模从自然走向理性之路第8讲“计算机仿真与数学建模”），正如维基百科的评价：自从Conway的游戏发明以来，由于其丰富多彩的进化演变模式，以及在社会自组织机制方面出人意料的结果，引起了研究工作者门广泛的关注，其中包括计算机学者、物理学家、生物学家、经济学家、社会学家、数学家以及哲学家。但是，这个有趣的游戏也引出了另一个有趣的问题：如果将顺序倒过来，能否由当前的进化状态推测出其以前的状态？请建立回溯模型或算法，来推测当前游戏状态往前回溯（5）步的初始状态。附件B-test.csv给出了测试数据集，包含了50000个当前的游戏状态以及回溯步数，其中“1”表示活细胞。要求建立模型求出它们往前回溯步的初始状态。需要注意的是，初始状态可能不唯一，求出其中之一即可。作为进一步考虑，能否给出回溯1步有唯一结果所要求满足的条件？测试数据集中有哪些游戏的回溯初始状态是唯一的？结果输出格式同附件B-test.csv格式，只需将“stop.k”改为“start.k”. 二：问题分析本题主要研究生命游戏逆问题的回溯算法。问题一要求建立回溯模型，由题中所给的已知终局回溯得到相应的初局。问题二及问题三要求更深层次的探讨，给出回溯一步有唯一结果时原终局应满足的条件，并判别所给数据中回溯后具有唯一初始状态的终局。问题一要求建立回溯模型。首先结合游戏规则对已知终局进行分析，得出由初局到下一步的转变需满足的基本约束条件，逆推出转换为当前状态的前一个状态应满足的约束条件，从而构建回溯算法。在调用已知矩阵时，先对其进行处理，即在该矩阵基础上加上下两行，左右两列的零向量，代表网格外的死细胞，将原位于网格边界处细胞化为非边界处细胞，简化运算，建立一步回溯模型。最后利用迭代法在一步回溯模型基础上进行反复迭代，得出不同终局经不同回溯次数后相应的初局。问题二要求给出原终局经回溯一步后仅有唯一结果需满足的条件。经分析得出，终局回溯一步后情形唯一只有两种情况：原初局处于稳定状态、原终局回溯情况只有一种即它处于两种变化状态之间，终局与回溯一步后的状态。根据生命游戏中满足这两种情况的七种情况，对已知终局设定相应的约束条件，结合第一问得出的回溯模型对该终局及其约束条件进