五子连珠问题模型研究

参赛队号： 16018 选题题号： A 五子连珠问题模型研究摘要本文针对“五子连珠”问题在二维网格和三维网格的最优方案进行建模与求解。对于六行七列网格的情况进行分析，先考虑一维情况下的模型，并将一维情况下模型的周期性性质推广至二维，据此建立0-1规划模型，进行求解得最优方案为最少取出8个棋子。并对结果的准确性进行理论证明，对此给出两种证明方法。第一中可以通过软件求解过程中的输出信息来给与证明，第二种通过反证法进行理论证明。对上述结果对应的方案进行研究，得到二维网格中最优方案的变化存在一定的周期性，据此周期性建立递推模型，并得到实用于一般二维网格中最优方案的数学模型，对13行17 列的网格进行求解，的到最少取出44个棋子。对此二维网格最优方案的周期性进一步研究并推广到三维网格中，通过二维网格叠加形成三维网格的方式，从而建立了三维网格中的最优方案的数学模型，并对6*7*6的网格进行求解的到少取出50个棋子。关键字：0-1规划，递推模型，网格叠加1问题重述问题1：在67 的长方形棋盘放满棋子。从这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各行，各列以及各对角线上仍然成立。这个结论很容易便可从一维的情况得到，只要证明ri和ci中的每个分量都和及的对应分量相等即可，这从一维的情况中很容易就能得到。5.1.2模型建立对于67网格的问题，先设取棋子方案矩阵位：(5)根据上述性质式(3)、(4)可得： 将其带入取棋子方案矩阵，并对位置变量进行重新编号，则可对取棋子方案矩阵进行简化，且简化后取棋子方案矩阵为：(6)为使方案各行满足条件，可对此矩阵各行使用性质式(2)，则可得式(7)所示约束条件；为使方案各列满足条件，可对此矩阵各列使用性质式(2)，可得式(8)所示约束条件；为使方案的各条对角线满足条件，我们仅对长度大于4的对角线使用式(2)，可得式(9)、(10)所示8条约束条件。(7)(8)(9)(10)联立以上各约束条件，并通过W矩阵建立模型如下：(11)求解模型，则可得最少的取棋子个数及最优方案矩阵，其中Z的值就是最少可取走的棋子的数量。将，带入W则可得到最优方案矩阵。5.1.3模型求解对于上述0-1规划模型，我们可直接通过MATLAB软件求解。我们得到的所有解如下:图 1 最优方案示意图通过求解模型得到最少取棋子数量为8个，一方面，通过软件求解过程当中的输出的最优解得类型来判定此结果就是最少的取棋子个数；另一方面，可通过反证法来证明8就是最少取棋子个数。反证法证明：假设七个棋子可以满足条件，则有W矩阵的7个列向量中都只能有一个非零的分量，且有，不妨设，则此时，W矩阵的最后一行全为零，此取棋子方案表示在6x7网格的第6行中不取走任何棋子，显然，在第6行中出现7个棋子连续的情况。由此我们可以知道取走7个棋子是无法。即8个棋子为最少的取棋子数量。5.2问题（2）的模型建立和求解5.2.1模型建立理论准备根据问题一中一维模型最优方案的性质到二维网格中最优性质的推广结论式(3)、(4)，将其作适当推广可得如下(12)、(13)两条性质：对于m行n列的网格，其最优方案矩阵W的行向量ri=和列向量cj满足以下性质：(12)其中， ；(13)其中， 。此性质说明的是：在二维网格中，随着行和列的扩充，最优方案和最优取棋子矩阵的变化具有一定的周期性，且周期为5，即行数每增加5，或者列数每增加5，最优方案矩阵将在矩阵的后边拼接一个特定的矩阵。最优方案对应的取棋子个数也将以特定的值增加。据此，便可将二维网格中最优方案的模型推广至一般情况。5.2.2模型建立在以上理论基础上，通过最优方案的行周期性，可将二维网格的行数推广到一般情况。以55网格为初始的网格状态，可建立网格扩充5n时的最少取棋子个数模型如下：其中，表示在网格中最优方案所对应的取棋子个数，n%5表示n和5的求余数运算。在此基础上，建立将网格扩充成为时，最优取棋子个数的模型：以上模型都是建立在m，n大于5的情况下，为保证模型的一般性，还需考虑m，n小于5的情况，当m，n都小于5时，显然有最优方案为不去出任何棋子，即最优取棋个数为0，最优取棋矩阵为全零矩阵。而对于m，n中仅有一个小于5的情况，由式(2)可知 为使达到最优，故规定：带入上述，模型，则可得到完整的一般情况下的模型为：5.2.3模型求解对上述模型的求解，通过MATLAB软件编写函数fhanshu（m，n）来实现（函数具体代码在附件二中），其返回值为最少的可取出的棋子数量，并且会根据结果的数量进行二维示意图绘制，如果返回值为零则不进行绘图且输出不用取出任何棋子的说明，否则，则绘制相应的最优取棋子方案示意图。将m=13，n=17，带入函数可得最少可取棋子数量为：44，其绘制出的最优方案示意图有多个，其中一个示意图如图所示，图 2 13x17最优方案示意图5.3问题（3）模型建立和求解5.3.1模型建立前的理论准备1）对问题二中，二维网格最优解的周期性性质可推广至三维情况，即在三维网格中，随着层数的扩充，最优方案和最优取棋子矩阵的变化具有一定的周期性，且周期为5。此性质在三维情况下可以通过面周期性加以证明。2）分析问题二的结果，可得到如下结论，其中，+为0-1向量的加法运算，可参看符号说明。将此性质推广至三维，即其中某一三维网格最优方案的连续叠加在一起的五个二维网格的取棋子方案，则可保证空间斜线上不出现五颗棋子连续的情况。对此性质，可考虑可通过反证法进行证明。假设对于某三维网格最优方案上述性质不满足，即在此最优方案中有则不妨设则可由0-1变量+运算方法知：；由此可知此方案中有五个连续的棋子，那么这种方案就不是最优解。由此，也就的到上述性质在三维网格中成立。5.3.2模型建立对三维情况下模型的建立，只需要将问题二中的模型在层数上进行扩充。以维初始网格状态对网格进行扩充，并记此5x5x5网格的最少可取t个棋子，则可建立网格扩充为时最少取棋子个数的模型：其中表示在空间网格中最少可取的棋子数量。同样的我们规定：则可得到在三维空间网格中最少可取棋子个数的模型为：5.3.3模型求解对上述模型的求解，通过MATLAB软件编写函数3dimension（m，n，p）来实现（函数具体代码在附件三中），其返回值为最少的可取出的棋子数量，并且会根据结果的数量进行二维示意图绘制，如果返回值为零则不进行绘图且输出不用取出任何棋子的说明，否则，则绘制相应的最优取棋子方案示意图。将m=6，n=7，p=6，带入函数可得最少可取棋子数量为：50。 得到最优方案对应，x,y,z坐标在附加的程序3；6模型的评价及改进6.1问题一的模型评价及改进问题一建立的模型是0-1规划模型，通过了简单的方法去解决复杂的问题，简单明了，容易理解。模型的建立在一维模型的基础上，十分有利于模型向更高维数的推广。解决了6x7二维网格的最少取旗子数量问题。但是由于只能解决具体的问题，模型不具有一般性，网格行列数不同的问题不能进行求解。问题二中针对这一缺点给出了解决一般问题的模型。6.2问题二的模型评价及改进问题二模型是基于问题一以及一维情况下的模型性质的，并由此得到了二维网格在扩充过程当中周期性规律，并由此建立了相应的最优去棋子个数的模型。这样就使得程序模型的求解在程序实现等过程就变得相当简单。将复杂的问题，通过其规律性简化。但模型的缺点就是通过结果的规律性直接对问题进行了建模求解，从模型当中看不出问题结果的实际推导过程，是一个相对比较高度集中的模型。6.3问题三的模型评价及改进问题三的模型是基于问题二的模型的。通过二维模型的周期性性质相三位情况的推广，发现了三位情况下最优方案仍然具有周期性，这对这一问题模型的建立起到了极其重要的作用。和问题二中的模型一样，该模型通过的求解在程序实现时是相当简单的。同样，由于模型只给出了最终结果的计算方式，是一个相对比较集中的模型，在模型中看不出结果的实际转换过程。7参考文献1 姜启源，叶其孝，数学建模，北京：机械工业出版社，2009.8.2 马莉，MATLAB语言实用教程，北京：清华大学出版社，2010.1.3 薛定宇，陈阳泉，高等数学问题的MATLAB求解，北京：清华大学出版社,2008.4 汪晓银，周保平，数学建模与数学实验（第二版），北京：科学出版式，2012.8.5 同济大学数学系，高等数学（第二版）上册，上海：同济大学出版社，2009.10.6 占军，张倩，MATLAB函数查询手册，北京：机械工业出版社，2011.1.8附录程序1a=zeros(4,25);a(1,3)=1;a(1,9)=1;a(1,15)=1;a(1,16)=1;a(1,22)=1;a(2,5)=1;a(2,6)=1;a(2,12)=1;a(2,18)=1;a(2,24)=1;a(3,3)=1;a(3,7)=1;a(3,11)=1;a(3,20)=1;a(3,24)=1;a(4,5)=1;a(4,9)=1;a(4,13)=1;a(4,17)=1;a(4,21)=1;c=2 2 1 1 1;b=zeros(14,25);b(1,1:5)=c;b(2,6:10)=c;b(3,11:15)=c;b(4,16:20)=c;b(5,21:25)=c;b(6,1)=2;b(6,7)=1;b(6,13)=1;b(6,19)=1;b(6,25)=1;b(7,2)=2;b(7,8)=1;b(7,14)=1;b(7,20)=1;b(7,21)=1;b(8,1)=2;b(8,10)=1;b(8,14)=1;b(8,18)=1;b(8,22)=1;b(9,2)=2;b(9,6)=1;b(9,15)=1;b(9,19)=1;b(9,23)=1;b(10,1)=2;b(10,6)=1;b(10,11)=1;b(10,16)=1;b(10,21)=1;b(11,:)=0,b(10,1:24);b(12,:)=0,0,b(10,1:23);b(13,:)=0,0,0,b(10,1:22);b(14,:)=0,0,0,0,b(10,1:21);f=ones(1,25);f(1:2)=4 4;f(3:7)=2 2 2 2 2f(11:12)=2 2;f(16:17)=2 2;f(21:22)=2 2;A=b;-bd=ones(14,1)*2;ones(14,1)*-1aeq=a;beq=ones(4,1);x,fv,exitflag,output=bintprog(f,A,d,aeq,beq);程序2function S A=fhanshu(n,m)p=zeros(5,5);p(1,5)=1;p(2,3)=1;p(3,1)=1;p(4,4)=1;p(5,2)=1;B=;C=;D=;% N5;if n5|m=5 S=floor(m/5)*n; h=floor(m/5); k=mod(m,5); c=p(1:n,1:5); for i=1:h C=C,c; end C=C,c(1:n,1:k) f=size(C,1); k=size(C,2); for i=1:f for j=1:k if abs(C(i,j)-1)1e-5 axis(1 max(f,k)+1 1 max(k,f)+1); plot(j+0.5,i+0.5,r*); title(五子连珠图2) grid on; hold on else axis(1 max(k,f)+1 1 max(k,f)+1); plot(j+0.5,i+0.5,ko); grid on; hold on end end end endend% N5,M5时if n5 if m=5,M=5if m5 if n5 l=floor(m/5); k=mod(m,5); c=p(1:5,1:5); for i=1:l B=B,c; end B=B,p(1:5,1:k); x=floor(n/5); y=mod(n,5); for i=1:x D=D;B; end D=D;B(1:y,1:length(B); s=size(D,1)f=size(D,2)figure(1)for i=1:s for j=1:f if abs(D(i,j)-1)1e-5 axis(1 max(s,f)+1 1 max(s,f)+1); %axis(1 s+1 1 f+1) plot(j+0.5,i+0.5,r*); title(五子连珠图2) grid on; hold on else axis(1 max(s,f)+1 1 max(s,f)+1); %axis(1 s+1 1 f+1) plot(j+0.5,i+0.5,ko); grid on; hold on end endendS=sum(sum(D);A=D; endend程序3c=zeros(6,6)x3=1 2 3 4 5 5 6 7 1 2 3 4 4 5 6 7 1 2 3 3 4 5 6 7 1 2 2 3 4 5 6 7 7 1 1 2 3 4 5 6 6 7 1 2 3 4 5 5 6 7y3=4 2 5 3 1 6 4 2 2 5 3 1 6 4 2 5 5 3 1 6 4 2 5 3 3 1 6 4 2 5 3 1 6 1 6 4 2 5 3 1 6 4 4 2 5 3 1 6 4 2z3=1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 4 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5