五子连珠问题模型研究报告

1、参赛队号：16018选题题号：A五子连珠问题模型研究摘要本文针对“五子连珠问题在二维网格和三维网格的最优方案进展建模与求 解.对于六行七列网格的情况进展分析, 先考虑一维情况下的模型,并将一维情 况下模型的周期性性质推广至二维,据此建立 0-1规划模型,进展求解得最优方 案为最少取出8个棋子.并对结果的准确性进展理论证实, 对此给出两种证实方 法.第一中可以通过软件求解过程中的输出信息来给与证实, 第二种通过反证法 进展理论证实.对上述结果对应的方案进展研究,得到二维网格中最优方案的变化存在一定 的周期性,据此周期性建立递推模型,并得到实用于一般二维网格中最优方案的 数学模型,对13行17列的

2、网格进展求解,的到最少取出 44个棋子.对此二维 网格最优方案的周期性进一步研究并推广到三维网格中,通过二维网格叠加形成 三维网格的方式,从而建立了三维网格中的最优方案的数学模型,并对 6*7*6的 网格进展求解的到少取出50个棋子.关键字：0-1规划,递推模型,网格叠加.word.zl.1问题重述问题1:在6X7的长方形棋盘放满棋子.从这 42个棋子中取出一些棋子, 使得棋盘上剩下的棋子,没有五个在一条直线横、竖、斜方向上依次相连, 最少取出多少个棋子才能满足要求？同时给出一种去掉棋子的方式.问题2:问题1中使用数学证实的方法,只能解决规模很小的问题.现在从 一般性的问题考虑,一利用数学建模

3、的方法建立一般模型, 然后设计算或利用软 件求解.基于此,请针对任意规模的棋盘,满足的条件与问题1 一样.问至少去掉多少个棋子.问题3:三维问题将该二维平面网格扩展到三维空间,得到一个的空间长方 体网格.在这些格子中同样都填满了棋子,现要从中抽取一局部,使得每种平面, 包括横向所截的m个平面,纵向所截的n个平面,竖直方向所截的p个平面, 在每个平面上在横向、纵向、斜方向上都不出现5子连珠.并且要求在空间斜线上也不出现5子连珠.问最少去掉多少个棋子可以满足要求.请建立一般问 题的数学模型.并给出具体的解结果.2问题分析2.1 问题1分析由题意可知,要求解一个取出的数量最少的取棋子方案.此问题中可

4、以通过0-1变量来表示每个位置上的棋子是否被取出,假设取出,那么用 1表示,否那么用0表示.那么就可以用一个0-1矩阵来表示方案,那么含有1的个数最少,.word.zl. 且满足题目中三个条件的矩阵就表示的是最优方案. 因此可以建立0-1规划模型, 对问题进展求解.模型的目标函数即为矩阵的行列变量总和.模型的约束条件可 以通过题目中的三个条件来给定.而对于这三个条件,先考虑一维情况下的模型, 并将一维情况下的模型的性质推广至二维,并由此性质来建立对应的约束条件.对于结果准确性,可以通过软件求解过程中的输出信息来给与证实,也可以通过反证法来进展理论证实.2.2 问题2分析此题目要求将问题一的模型

5、推广至一般情况.先对问题1的结论进展分析, 得出结论所具有的性质,并加以理论证实,然后将其性质推广至一般情况. 先将 问题一中的模型的行数推广至一般情况, 并在此根底上,将列数也推广至一般情 况,从而建立一般情况下的模型.的模型还需要考虑特殊情况：行数小于5或者列数小于5.对此,很容易能得到在行数和列数都小于 5的情况下,不需要取出 任何点,即结果为零；对于只有列数小于 5或者行数小于5的情况,规定每行或 者每列的最优结果的累加,即是最终结果.而对于每行或者每列的最优结果,可 以通过一般一维模型下的最优结果的算法给出.2.3 问题3分析此题目要求将平面网格推广至三维空间,建立一般模型,并计算

6、6x6x7情况下的 最优结果.在问题二模型的根底上将结果的性质经一部推广至三维网格,这样, 就可以直接应用结果的性质,通过二维到三维网格的二维网格扩大的方式对三维 模型进展建立.word.zl.3模型假设假设二维网格中的每个格子都是1x1的小正方形,在三维网格中,每个格子是1x1x1的小正方体.假设格子之间共顶点或者共边时,两个字相连.假设在相连的格子中的棋子的距离是1.假设每个小方格或者小正方体中只能放一个棋子.4符号说明Xi表示0-1变量G,Q,Q,C4,Cn表示方案矩阵的列向量口/2产3产4,Xn表示方案矩阵的行向量落表示n对m向上取整n4表示n对m向下取整VAL2(m,n)表示二维网格

7、最少可取棋子的数量VAL3(m,n)表示三维网格最少可取棋子的数量m% n表示n对m取余数.word.zl.5模型建立和求解5.1 问题1的模型建立与求解5.1.1 模型建立前提理论为了在二维片面上建立模型,先来研究模型在一维情况下的性质,要在 n个方格中取棋子,那么可以用一个n元素只有0和1的n维向量a来表示最取棋子方案.那么为了使得取棋子总数最少,及方案最优,就有结论：aa(i 5)(i 5 n,a(D)表示a向量的第i个分量n5 a n5其中, % 表示%向下取整,% 表示向上取整.将此性质推广至二维网格,那么对于 m n二维网格的取棋子方案矩阵.w C1 C2 C3 C4 Cn3(2)

8、rn其中G C2 c3Cn为矩阵W的列向量,123m为W的行向量那么有如下结论：Ci C 5(3)i i 5(4)且在各行各列性质在 W各行,各列以及各对角线上仍然成立.这个结论很容易便可从一维的情况得到,只要证实 n不代中的每个分量都和5及0 5的对应分量相等即可,这从一维的情况中很容易就能得到.wod.zl.5.1.2模型建立(5)对于6X7网格的问题,先设取棋子方案矩阵位:XiX12XI3X14X15X16XI7x21X22X23X24X25X26X27x31 wX32X33X34X35X36X37X41X42X43X44X45X46X47X51X52X53%4X55X56X57X61X

9、62X63X54X65X6647根据上述性质式3、4可得:TX11T X61X11X16X12X17X12X62X21X26X22X27X13X63X31X36X32X37X14X64X41X46X42X47X15X65X51X56%2X57X16%6X61X66X62X67X17%7将其带入取棋子方案矩阵,并对位置变量进展重新编号,那么可对取棋子方X1X2X3X4X5X1X2X6X7X8XX10X6X7wX11X12X13X14X15X11X12X16X17X18X19X20X16X17X21X22X23X24X25X21X22X1X2X3X4X5X1X26那么可得式所示2,可得式8案矩阵进

10、展简化,且简化后取棋子方案矩阵为:为使方案各行满足条件,可对此矩阵各行使用性质式 2, 约束条件；为使方案各列满足条件,可对此矩阵各列使用性质式.word.zl.所示约束条件；为使方案的各条对角线满足条件,我们仅对长度大于4的对角线使用式2,可得式9、10所示8条约束条件1 2x12 x2x3x4 x521 2x62x7x8x9x1021 2x112 x12x13x14x15212x162 x17x18x19x2021 2x212 x22x23x24x2521 2x12 x6x11x16x2121 2x22 x7x12x17x2221 2x32x8x13x18x23212x42 x9x14x1

11、9x2421 2x52x10x5x20x2521 2x1x7x13x19x2521 2x2x8x14x20x2121 2x1x10为4x18x2221 2x2x7x11x20x242x3 xx15x16x221x5x6x12x18x24124(10)x3为x11x20x241x5x9x13x17x211(8)(9)联立以上各约束条件,并通过 W矩阵建立模型如下:min Z 4X| 4x2 2x3 2x4 2x52x6 2x7x8x9x102x112 x12x13x14x15(11)2x162 x17x18x19x202x212 x22x23x24x25求解模型,那么可得最少的取棋子个数及最优方

12、案矩阵,其中Z的值就是最少可取走的棋子的数量.将Xi, X2, X3带入W那么可得到最优方案矩阵.word.zl.5.1.3模型求解对于上述0-1规划模型,我们可直接通过MATLAB软件求解.我们得到的所有解如下：图1最优方案示意图通过求解模型得到最少取棋子数量为 8个,一方面,通过软件求解过程当中的输出的最优解得类型来判定此结果就是最少的取棋子个数；另一方面,可通过反证法来证实8就是最少取棋子个数.反证法证实：假设七个棋子可以满足条件,那么有W矩阵的7个列向量中都只能有一个非零的分量,且有 J Ce, C2 C7不妨设G (1 0 0 0 0 0) , C (0 1 0 0 0 0) , C

13、3 (0 0 1 0 0 0),c4 (0 0 0 1 0 0) , C5 (0 0 0 0 1 0)T T T T T T T那么 W C1 ,C2,C3 ,C4 ,C5 ,C1 ,C此时,W矩阵的最后一行全为零,此取棋子方案表示在 6x7网格的第6行中不取走任何棋子,显然,在第6行中出现7个棋子连续的情况.由此我们可以知 道取走7个棋子是无法.即8个棋子为最少的取棋子数量.word.zl.5.2问题2的模型建立和求解5.2.1 模型建立理论准备根据问题一中一维模型最优方案的性质到二维网格中最优性质的推广结论式3卜4,将其作适当推广可得如下12、13两条性质：对于m行n列的网格,其最优方案矩

14、阵 W的行向量7=和列向量满足以下 性质：cj cj 5 cj 10cj 5n 12其中,1 Cj5n 5；rj rj 5 h 10口 5n 13其中,1 rj 5n 5.此性质说明的是：在二维网格中,随着行和列的扩大,最优方案和最优取棋子矩阵的变化具有一定的周期性,且周期为5,即行数每增加5,或者列数每增加5,最优方案矩阵将在矩阵的后边拼接一个特定的矩阵.最优方案对应的取棋 子个数也将以特定的值增加.据此,便可将二维网格中最优方案的模型推广至一 般情况.5.2.2 模型建立在以上理论根底上,通过最优方案的行周期性,可将二维网格的行数推广到 一般情况.word.zl.以5X5网格为初始的网格状

15、态,可建立网格扩大5Xn时的最少取棋子个数模型如下：VAL2(5,n) ( n51) 5 VAL(5,n%5) 5(n5 ) 5 VAL(5,n%5)其中,VAL2(m,n)表示在(m,n)网格中最优方案所对应的取棋子个数,办唏5表 示n和5的求余数运算.在此根底上,建立将网格扩大成为(m,n)时,最优取棋子个数的模型：VAL2(m,n) m5 VAL2(5,n) VAL2(m%5,n)m5 n55 VAL2(5,n%5)VAL2(m%5, n)m5 n5 5 m5 VAL2(5,n%5) VAL2(m%5,n)以上模型都是建立在 m, n大于5的情况下,为保证模型的一般性,还需考虑m, n小

16、于5的情况,当m, n都小于5时,显然有最优方案为不去出任何棋 子,即最优取棋个数为0,最优取棋矩阵为全零矩阵.而对于 m, n中仅有一个 小于5的情况,由式(2)可知kn5VAL(k,n)kn5(n 5,k 5)km5VAL(m, k)k/(m 5,k 5)为使到达最优,故规定：VAL2(k,n) k n5 (n 5,k 5)VAL2(m,k) k m5(m 5,k 5)带入上述VAL2(5, n) , VAL2(m,n)模型,那么可得到完整的一般情况下的模.word.zl.型为:VAL2(m,n)5 mS m nS n mS 0n%5 m%5m 5, n 5m 5,n 5m, n 5nSm

17、, n 55.2.3模型求解对上述模型的求解,通过MATLAB软件编写函数fhanshum, n来实现函 数具体代码在附件二中,其返回值为最少的可取出的棋子数量,并且会根据结 果的数量进展二维示意图绘制,如果返回值为零那么不进展绘图且输出不用取出 任何棋子的说明,否那么,那么绘制相应的最优取棋子方案示意图.将m=13, n=17,带入函数可得最少可取棋子数量为：44,其绘制出的最优方案示意图有多个,其中一个示意图如下列图,五干理融出!*:0Q1Q+aQQfQQ电0o*口0+qgaq*.QQ十0QQOO00,-4at.000+0o0o*Qoa7a占*0 -aok-=-GO0m一 -&：od+EO

18、白+aoad白+*o+白白心白D+oo4J&*oo台bo+0O：O+O：Oi1 =0+QQO?oQ*.a00OQ*q4O口!=-Ad ! 一 士: 32Q口*+0Q中a0*oooo.*0Q*.&口oQ*：O0oia+O0o*Ooe*口4o+心ooo*.og白*口D0o ： ooQ+口口 OQ0 *1口口16图2 13x17最优方案示意图.word.zl.5.3问题3模型建立和求解5.3.1 模型建立前的理论准备1对问题二中,二维网格最优解的周期性性质可推广至三维情况,即在三 维网格中,随着层数的扩大,最优方案和最优取棋子矩阵的变化具有一定的周期 性,且周期为5.此性质在三维情况下可以通过面周期

19、性加以证实.2分析问题二的结果,可得到如下结论,11G C2 c3 c4 C5111r1 r2 r3 r4 r511111其中,+ 为0-1向量的加法运算,可参看符号说明.将此性质推广至三维,即1,1(X1 X2 X3 X4 X5): :1 1其中X,X2,%,.见某一三维网格最优方案的连续叠加在一起的五个二维网 格的取棋子方案,那么可保证空间斜线上不出现五颗棋子连续的情况. 对此性质, 可考虑可通过反证法进展证实.假设对于某三维网格最优方案上述性质不满足,即在此最优方案中有(X1 X2 X3 X4 X5).word.zl.那么不妨设(XiX3X4X5)那么可由0-1变量+运算方法知:Xi(1

20、,1) 0X2(1,1) X3(1,1) X4(1,1)X5(1,1)；由此可知此方案中有五个连续的棋子, 那么这种方案就不是最优解.由此,也就的到上述性质在三维网格中成立.5.3.2模型建立对三维情况下模型的建立,只需要将问题二中的模型在层数上进展扩大.以(m,n,5)维初始网格状态对网格进展扩大,并记此 5x5x5网格的最少可取t个棋子,那么可建立网格扩大为(m, n, p)时最少取棋子个数的模型：VAL3(m, n, p) p5VAL3(m,n,5) VAL3(m,n, p%5) q5 m n q%5 VAL2(m,n)其中VAL3(m, n, p)表示在(m, n, p)空间网格中最少

21、可取的棋子数量.同样的我们规定：VAL3(m, n, p) p VAL 2(m, n) p 5那么可得到在三维空间网格中最少可取棋子个数的模型为：VAL3(m, n, p)P5 m n p%5 VAL2(m,n) p 5VAL3(m,n, p) P VAL2(m, n) p 55.3.3模型求解对上述模型的求解,通过 MATLAB软件编写函数3dimension Cm, n, p来.word.zl. 实现函数具体代码在附件三中,其返回值为最少的可取出的棋子数量,并且 会根据结果的数量进展二维示意图绘制,如果返回值为零那么不进展绘图且输出 不用取出任何棋子的说明,否那么,那么绘制相应的最优取棋子

22、方案示意图.将m=6, n=7, p=6,带入函数可得最少可取棋子数量为：50. 得到最优方案对应,x,y,z坐标在附加的程序3;6模型的评价及改进6.1 问题一的模型评价及改进问题立的模型是0-1规划模型,通过了简单的方法去解决复杂的问题,简单 明了,容易理解.模型的建立在一维模型的根底上, 十分有利于模型向更高维数 的推广.解决了 6x7二维网格的最少取旗子数量问题. 但是由于只能解决具体的 问题,模型不具有一般性,网格行列数不同的问题不能进展求解. 问题二中针对 这一缺点给出了解决一般问题的模型.6.2 问题二的模型评价及改进问题二模型是基于问题一以及一维情况下的模型性质的,并由此得到了

23、二维网格在扩大过程当中周期性规律,并由此建立了相应的最优去棋子个数的模型. 这样就使得程序模型的求解在程序实现等过程就变得相当简单.将复杂的问题, 通过其规律性简化.但模型的缺点就是通过结果的规律性直接对问题进展了建模 求解,从模型当中看不出问题结果的实际推导过程, 是一个相比照拟高度集中的 模型.word.zl.6.3 问题三的模型评价及改进问题三的模型是基于问题二的模型的. 通过二维模型的周期性性质相三位情 况的推广,发现了三位情况下最优方案仍然具有周期性,这对这一问题模型的建立起到了极其重要的作用.和问题二中的模型一样,该模型通过的求解在程序实 现时是相当简单的.同样,由于模型只给出了最

24、终结果的计算方式,是一个相比 照拟集中的模型,在模型中看不出结果的实际转换过程.7参考文献1启源,叶其孝,数学建模,：机械工业,2021.8.2马莉,MATLAB语言实用教程,：清华大学,2021.1.3薛定宇,高等数学问题的MATLAB求解,：清华大学,2021.4汪晓银,周保平,数学建模与数学实验第二版,：科学出版式,2021.8.5同济大学数学系,高等数学第二版上册,：同济大学,2021.10.6占军,倩,MATLAB函数查询手册,：机械工业,2021.1.word.zl.8附录程序1a=zeros(4,25);a(1,3)=1;a(1,9)=1;a(1,15)=1;a(1,16)=1;

25、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;

26、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(

27、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);程序2.word.zl.function 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=5S=floor(m/5)*n;h=f

28、loor(m/5);k=mod(m,5);c=p(1:n,1:5);for i=1:hC=C,c;endC=C,c(1:n,1:k)f=size(C,1);k=size(C,2);for i=1:ffor j=1:kif abs(C(i,j)-1)1e-5axis(1 max(f,k)+1 1 max(k,f)+1);plot(j+0.5,i+0.5,r*);.word.zl.endelseendt田e五子连珠图2grid on;hold onaxis(1 max(k,f)+1 1 max(k,f)+1);plot(j+0.5,i+0.5,ko);grid on;hold onendenden

29、d% N5,M5 时if n5if m=5,M=5if m5.word.zl.if n5l=floor(m/5);k=mod(m,5);c=p(1:5,1:5);for i=1:lB=B,c;endB=B,p(1:5,1:k);x=floor(n/5);y=mod(n,5);for i=1:xD=D;B;endD=D;B(1:y,1:length(B);s=size(D,1)f=size(D,2)figure(1)for i=1:sfor j=1:fif abs(D(i,j)-1)1e-5axis(1 max(s,f)+1 1 max(s,f)+1);%axis(1 s+1 1 f+1).word.zl.plot(j+0.5,i+0.5,r*);t田e(五子连珠图2)grid on;hold onelseaxis(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 onendendendS=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