游戏中的数学模型

数学模型与游戏2011年2月21日过河问题是世界名题，有很多种说法。最早引进中国的是中国数学会第一届理事，扬州中学的数学教师陈怀书先生。后我国数学科普作家、哈军工大教授薛鸿达先生曾写过一篇专文《渡河难题》，对此进行了全面介绍。我们将介绍三种不同的形式。过河问题例1商人们怎样安全过河问题(智力游戏)3名商人3名随从随从们密约,在河的任一岸,一旦随从的人数比商人多,就杀人越货.乘船渡河的方案由商人决定.商人们怎样才能安全过河?问题分析多步决策过程决策~每一步(此岸到彼岸或彼岸到此岸)船上的人员要求~在安全的前提下(两岸的随从数不比商人多),经有限步使全体人员过河.河小船(至多2人)模型构成xk~第k次渡河前此岸的商人数yk~第k次渡河前此岸的随从数xk,yk=0,1,2,3;k=1,2,sk=(xk,yk)~过程的状态S={(x,y)x=0,y=0,1,2,3;x=3,y=0,1,2,3;x=y=1,2}S~允许状态集合uk~第k次渡船上的商人数vk~第k次渡船上的随从数dk=(uk,vk)~过程的决策D~允许决策集合uk,vk=0,1,2;k=1,2,sk+1=skdk+(-1)k~状态转移律D={(u,v)u+v=1,2}状态因决策而改变xy3322110•穷举法~编程上机•图解法状态s=(x,y)~16个格点~10个点允许决策~移动1或2格;k奇,左下移;k偶,右上移.s1sn+1d1,d11给出安全渡河方案d1d11允许状态模型构成模型求解求dkD(k=1,2,n),使skS,并按转移律sk+1=sk+(-1)kdk由s1=(3,3)到达sn+1=(0,0).问题归结为由状态(3,3)经奇数次可取运算，即由可取状态到可取状态的转移，转化为(0,0)的转移问题。商人和随从人数增加或小船容量加大;商人们怎样安全过河智力游戏多步决策过程(数学模型)易于推广:规格化方法考虑4名商人各带一随从的情况.多步决策模型:恰当地设置状态和决策,确定状态转移律及目标(目标函数).便于求解(计算机编程等)例2.人、狗、鸡、米过河问题这是一个人所共知而又十分简单的智力游戏。某人要带狗、鸡、米过河，但小船除需要人划外，最多只能载一物过河，而当人不在场时，狗要咬鸡、鸡要吃米，问此人应如何过河。在本问题中，可采取如下方法：一物在此岸时相应分量为1，而在彼岸时则取为0，例如（1,0,1,0）表示人和鸡在此岸，而狗和米则在对岸。（i）可取状态：根据题意，并非所有状态都是允许的，例如（0,1,1,0）就是一个不可取的状态。本题中可取状态（即系统允许的状态）可以用穷举法列出来，它们是：人在此岸人在对岸(1，1，1，1)(0，0，0，0)(1，1，1，0)(0，0，0，1)(1，1，0，1)(0，0，1，0)(1，0，1，1)(0，1，0，0)(1，0，1，0)(0，1，0，1)总共有十个可取状态，对一般情况，应找出状态为可取的充要条件。（ii）可取运算：状态转移需经状态运算来实现。在实际问题中，摆一次渡即可改变现有状态。为此也引入一个四维向量（转移向量），用它来反映摆渡情况。例如（1，1，0，0）表示人带狗摆渡过河。根据题意，允许使用的转移向量只能有（1，0，0，0，）、（1，1，0，0）、（1，0，1，0）、（1，0，0，1）四个。规定一个状态向量与转移向量之间的运算。规定状态向量与转移向量之和为一新的状态向量，其运算为对应分量相加，且规定0+0=0，1+0=0+1=1，1+1=0。(解释)在具体转移时，只考虑由可取状态到可取状态的转移。问题化为：由初始状态（1，1，1，1）出发，经奇数次上述运算转化为（0，0，0，0）的转移过程。我们可以如下进行分析：（第一次渡河）(不可取)(不可取)(可取)(不可取)(0,1,1,1)(0,1,1,0)(0,1,0,1)(0,0,1,1)(1,0,0,0)(1,0,0,1)(1,0,1,0)(1,1,0,0)(1,1,1,1)（第二次渡河）(1,0,0,0)(1,0,0,1)(1,0,1,0)(1,1,0,0)(0,1,0,1)(可取)(不可取)过的状态)(循环,回到原先出现(不可取)(1,1,0,1)(1,1,0,0)(1,1,1,1)(1,0,0,1)＝以下可继续进行下去，直至转移目的实现。上述分析实际上采用的是穷举法，对于规模较大的问题是不宜采用的。人在此岸人在对岸(1，1，1，1)(0，0，0，0)(1，1，1，0)(0，0，0，1)(1，1，0，1)(0，0，1，0)(1，0，1，1)(0，1，0，0)(1，0，1，0)(0，1，0，1)图解法问题转化为求点(1,1,1,1)到点(0,0,0,0)的一条通路。1,1,1,00,1,0,11,1,0,10,0,0,10,1,0,01,0,1,11,1,1,10,0,1,01,0,1,00,0,0,0例3：高塔逃生：铁匠海乔90，公主安娜50，侍女40，铁链30原则：人下来时两个筐子必须都有人或铁链，并且重量相差10公斤。两个筐子装的总重量不超过170公斤。转化：用向量表示状态:如(9,5,4,3)表示四者均在上面，(9,4)表示海乔和侍女在上面，其余在下面。从(9,5,4,3)开始，到(3)结束。方案之一：开始铁链下去侍女下去铁链上来铁链拿到筐外公主在下面可把铁链拿到筐里(9,5,4,3)→(9,5,4)→(9,5,3)→(9,5)→(9,4)→(5,4,3)→(5,4)→(5,3)→(5)→(4)→(3)。注意不同于过河问题，此过程是不可逆的。共有八种不同的方案，可试着做一下。德国著名的艺术家AlbrechtDürer(1471-1521)于1514年曾铸造了一枚名为“MelencotiaI”的铜币。令人奇怪的是在这枚铜币的画面上充满了数学符号、数字及几何图形。这里，我们仅研究铜币右上角的数字问题Dürer魔方（或幻方）问题所谓的魔方是指由1~n2这n2个正整数按一定规则排列成的一个n行n列的正方形。n称为此魔方的阶。Dürer魔方：4阶，每一行之和为34，每一列之和为34，对角线（或反对角线）之和是34，每个小方块中的数字之和是34，四个角上的数字加起来也是34什么是Dürer魔方多么奇妙的魔方！铜币铸造时间：1514年构造魔方是一个古老的数学游戏，起初它还和神灵联系在一起，带有深厚的迷信色彩。传说三千二百多年前（公元前2200年），因治水出名皇帝大禹就构造了三阶魔方（被人们称“洛书”），至今还有人把它当作符咒用于某些迷信活动，大约在十五世纪时，魔方传到了西方，著名的科尼利厄斯·阿格里帕（1486-1535）先后构造出了3~9阶的魔方。如何构造魔方奇数（不妨n=5）阶的情况Step1:在第一行中间写1Step2:每次向右上方移一格依次填按由小到大排列的下一个数，向上移出界时填下一列最后一行的小方格；向右移出界时填第一列上一行的小方格。若下面想填的格已填过数或已达到魔方的右上角时，改填刚才填的格子正下方的小方格，继续Step2直到填完12345678910111213141516171819202122232425偶数阶的情况偶数阶的魔方可以利用奇数阶魔方拼接而成，拉尔夫·斯特雷奇给出了一种拼接的方法，这里不作详细介绍你想构造Durer魔方吗？如何构成所有的Durer魔方？Durer魔方有多少？五阶没人知道有多少个！！！三阶1个反射和中心旋转生成8个四阶880个反射和中心旋转生成7040个魔方数量随阶数n增长的速度实在是太惊人了！同阶魔方的个数06118910601509119960711891070160911997108010015014011050407020160901201303060定义：如果4×4数字方，它的每一行、每一列、每一对角线及每个小方块上的数字之和都为一确定的数，则称这个数字方为Durer魔方。R=C=D=S仍以4阶方阵为例其中：R为行和，C为列和，D为对角线和，S为小方块和设D为所有满足R=C=D=S的Durer魔方的集合。允许取相同的数字，并且允许数字在某个数域里任意取值。a11a12a13a14a21a22a23a24a31a32a33a34a41a42a43a44A=b11b12b13b14b21b22b23b24b31b32b33b34b41b42b43b44B=类似于矩阵的加法和数乘，定义魔方的加法和数乘。易验证，D对加法和数乘封闭，且构成一线性空间。记M={所有的4×4数字方}，则其维数为16。而D是M的子空间，则D是有限维的线性空间。根据线性空间的性质，如果能得到D的一组基，则任一个Durer方均可由这组基线性表示。1在第一行中共有4种取法，为保持上述性质的成立，第二行中的1还有两种取法。当第二行的1也取定后，第三行与第四行的1就完全定位了，故一共可作出8个不同的最简方阵，称之为基本魔方并记之为Q1，…，Q8R=C=D=S=1的方阵构成的线性空间具有什么样的性质？（这是非常必要的，因为我们一般取的是整数。）类似于构造n维欧氏空间的标准基，利用0和1我们来构造一些R=C=D=S=1的最简单的方阵。Durer魔方的维数和生成集由0,1数字组合，构造所有的R=C=D=S=1的魔方。共有8个，记为Qi,i=1,2,…,8。Q1=1000001000010100Q2=1000000101000010Q3=Q4=00011000001001000001010010000010Q5=0010100001000001Q6=0100001010000001Q7=0010010000011000Q8=0100000100101000可以证明，Dürer空间（简称D空间）中任何一个元素都可以用Q1，Q2，…，Q8来线性表示，但它们能否构成D空间的一组基呢？是否线性无关？821,,,QQQ容易看出：076328541QQQQQQQQQ1，…，Q8这8个基本方是线性相关的，即至少存在一个Qj，可以通过其它7个基本方的线性组合得到。这8个基本方的地位是等同的，故可不妨设j=8。下面验证Q1，Q2，…，Q7是否线性相关。071iiiQr令：，即6542317713526426174534375621rrrrrrrrrrrrrrrrrrrrrrrrrrrr0000000000000000=等号两边对应元素相比较，得r1=r2=…=r7=0，所以是线性无关721,,,QQQ721,,,QQQ是D空间的最小生成集。令D即解方程组：772211QdQdQd114155127698111051323166542317713526426174534375621dddddddddddddddddddddddddddd=解得D=8Q1＋8Q2＋7Q3＋6Q4－2Q5＋3Q6＋4Q7研究AlbrechtDürer铸造的铜币D空间的子空间和D空间的扩展（1）要求数字方的所有数都相等这是集合G={rE,r∈R}，G是以βG={E}为基的一维向量空间（2）要求列、行及每条主、付对角线上各和都相等。得到5维泛对角方的向量空间B。例如：它的基BB为：12726121671232211161611217PH=N=R=C=46其中H为主对角线和，N为付对角线和。进一步讨论01101001011010011001011010010110010110101010010111000011110000112P3P4P5P10101010010101011P（3）要求行和，列和及两条对角线上的元素和相等得到8维向量空间Q。基向量QB={Q1，Q2，…，Q7，N0}，其中Q1，Q2，…，Q7是D的基，而01100000000