五子连珠问题模型研究讲述.docx

参赛队号：16018选题题号：A五子连珠问题模型研究摘要本文针对“五子连珠”问题在二维网格和三维网格的最优方案进行建模与求解。对于六行七列网格的情况进行分析，先考虑一维情况下的模型，并将一维情况下模型的周期性性质推广至二维，据此建立0-1规划模型，进行求解得最优方案为最少取出8个棋子。并对结果的准确性进行理论证明，对此给出两种证明方法。第一中可以通过软件求解过程中的输出信息来给与证明，第二种通过反证法进行理论证明。对上述结果对应的方案进行研究，得到二维网格中最优方案的变化存在一定的周期性，据此周期性建立递推模型，并得到实用于一般二维网格中最优方案的数学模型，对13行17 列的网格进行求解，的到最少取出44个棋子。对此二维网格最优方案的周期性进一步研究并推广到三维网格中，通过二维网格叠加形成三维网格的方式，从而建立了三维网格中的最优方案的数学模型，并对6*7*6的网格进行求解的到少取出50个棋子。关键字：0-1规划，递推模型，网格叠加1问题重述问题1：在6×7 的长方形棋盘放满棋子。从这42 个棋子中取出一些棋子，使得棋盘上剩下的棋子，没有五个在一条直线（横、竖、斜方向）上依次相连，最少取出多少个棋子才能满足要求？同时给出一种去掉棋子的方式。问题2：问题1 中使用数学证明的方法，只能解决规模很小的问题。现在从一般性的问题考虑，一利用数学建模的方法建立一般模型，然后设计算或利用软件求解。基于此，请针对任意规模 的棋盘，满足的条件与问题 1 相同。问至少去掉多少个棋子。 问题3：三维问题将该二维平面网格扩展到三维空间，得到一个 的空间长方体网格。在这些格子中同样都填满了棋子，现要从中抽取一部分，使得每种平面，包括横向所截的m 个平面，纵向所截的n 个平面，竖直方向所截的p 个平面，在每个平面上在横向、纵向、斜方向上都不出现5 子连珠。并且要求在空间斜线上也不出现5 子连珠。问最少去掉多少个棋子可以满足要求。请建立一般问题的数学模型。并给出具体的解结果。2问题分析2.1问题（1）分析由题意可知，要求解一个取出的数量最少的取棋子方案。此问题中可以通过0-1变量来表示每个位置上的棋子是否被取出，若取出，则用1表示，否则用0表示。那么就可以用一个0-1矩阵来表示方案，则含有1的个数最少，且满足题目中三个条件的矩阵就表示的是最优方案。因此可以建立0-1规划模型，对问题进行求解。模型的目标函数即为矩阵的行列变量总和。模型的约束条件可以通过题目中的三个条件来给定。而对于这三个条件，先考虑一维情况下的模型，并将一维情况下的模型的性质推广至二维，并由此性质来建立对应的约束条件。对于结果准确性，可以通过软件求解过程中的输出信息来给与证明，也可以通过反证法来进行理论证明。2.2问题（2）分析本题目要求将问题一的模型推广至一般情况。先对问题（1）的结论进行分析，得出结论所具有的性质，并加以理论证明，然后将其性质推广至一般情况。先将问题一中的模型的行数推广至一般情况，并在此基础上，将列数也推广至一般情况，从而建立一般情况下的模型。的模型还需要考虑特殊情况：行数小于5或者列数小于5。对此，很容易能得到在行数和列数都小于5的情况下，不需要取出任何点，即结果为零；对于只有列数小于5或者行数小于5的情况，规定每行或者每列的最优结果的累加，即是最终结果。而对于每行或者每列的最优结果，可以通过一般一维模型下的最优结果的算法给出。2.3问题（3）分析本题目要求将平面网格推广至三维空间，建立一般模型，并计算6x6x7情况下的最优结果。在问题二模型的基础上将结果的性质经一部推广至三维网格，这样，就可以直接应用结果的性质，通过二维到三维网格的二维网格扩充的方式对三维模型进行建立。3模型假设假设二维网格中的每个格子都是1x1的小正方形，在三维网格中，每个格子是1x1x1的小正方体。 假设格子之间共顶点或者共边时，两个字相连。假设在相连的格子中的棋子的距离是1。假设每个小方格或者小正方体中只能放一个棋子。4符号说明表示0-1变量表示方案矩阵的列向量表示方案矩阵的行向量表示n对m向上取整表示n对m向下取整表示二维网格最少可取棋子的数量表示三维网格最少可取棋子的数量表示n对m取余数5模型建立和求解5.1问题1的模型建立与求解5.1.1模型建立前提理论为了在二维片面上建立模型，先来研究模型在一维情况下的性质，要在n个方格中取棋子，则可以用一个n元素只有0和1的n维向量a来表示最取棋子方案。则为了使得取棋子总数最少，及方案最优，就有结论：表示a向量的第i个分量）(1)其中，表示向下取整,表示向上取整。将此性质推广至二维网格，则对于二维网格的取棋子方案矩阵(2)其中为矩阵W的列向量，为W的行向量则有如下结论：(3)(4)且在各行各列性质在W各行，各列以及各对角线上仍然成立。这个结论很容易便可