《数学建模状态转移法.ppt》由会员分享，可在线阅读，更多相关《数学建模状态转移法.ppt（11页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、12.12.常见的数学建模方法常见的数学建模方法(7)-(7)-状态转移法状态转移法 处理问题的类型处理问题的类型:状态转移问题状态转移问题,属离散性模型问题属离散性模型问题.问题的内容问题的内容：讨论在一定的条件下，系统由一个状态转移到另一个讨论在一定的条件下，系统由一个状态转移到另一个状态是否可能状态是否可能,如果可能的话，应该如何具体实现。如果可能的话，应该如何具体实现。基基本本方方法法及及数数学学技技巧巧:用用向向量量来来模模拟拟状状态态.将将状状态态的的演演变变描描述述成成向向量量的运算的运算,以便于计算机程序处理以便于计算机程序处理.问题问题1.人人、狗狗、鸡鸡、米过河问题米过河问
2、题某某人人要要带带人人、狗狗、鸡鸡、米米用用渡渡船船过过河河,但但渡渡船船需需要要人人划划外外,最最多多只只能能载载一一物物过过河河,而而且且当当人人不不在在场场时时,狗狗要要咬咬鸡鸡,鸡鸡要要吃吃米米.问问此此人人应如何安全渡河应如何安全渡河?求解求解.把此问题视为一个状态转移问题把此问题视为一个状态转移问题.具体规定具体规定:(1)可取状态可取状态.用一个四维向量来表示人、物在此岸与不在此岸的状用一个四维向量来表示人、物在此岸与不在此岸的状(2)态态.这个四维向量中的第一至第四分量元素分别表示人、狗、鸡这个四维向量中的第一至第四分量元素分别表示人、狗、鸡(3)、米、米,它们的取值只能为它们
3、的取值只能为1或或0,其中其中1表示在此岸表示在此岸,0表示不在表示不在(4)此此岸岸.例例如如:(1,0,1,0)表表示示人人、鸡鸡在在此此岸岸,狗狗与与米米在在对对岸岸.由由题题(5)意意,允许发生的状态向量集合为允许发生的状态向量集合为:S S=(1,1,1,1),(1,1,1,0),(1,1,0,1),(1,0,1,1),(1,0,1,0),(0,1,0,1),(0,1,0,0),(0,0,1,0),(0,0,0,1),(0,0,0,0).(2)可可取取运运算算.状状态态转转移移需需经经状状态态运运算算来来实实现现.在在实实际际问问题题中中,摆摆一一次次渡渡可可改改变变现现有有的的状状
4、态态,为为此此引引进进一一个个四四维维的的状状态态运运算算向向量量,用用它它来来反反映摆渡操作情况映摆渡操作情况.根据题意根据题意,状态运算向量集合为状态运算向量集合为:D D=(1,0,1,0),(1,1,0,0),(1,0,0,1),(1,0,0,0).把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量的向量相加或相减的向量相加或相减(去往对岸为相减，返回此岸为相加）去往对岸为相减，返回此岸为相加）.在以上所规定的意义下在以上所规定的意义下,这个问题的状态转移模型可表示为这个问题的状态转移模型可表示为:si+1=si+(-1)i
5、dk,其中其中si S S ,dk D D;且对任意且对任意 ji,都有都有 sjsi 令令 s1=(1,1,1,1),sn=(0,0,0,0),利用计算机编程处理利用计算机编程处理,例如，例如，可可以以用用Math软软件件编编程程求求解解这这个个摆摆渡渡操操作作方方案案,即即求求出出n和和d1,d2,d3,dn各是多少各是多少.具体的结果为：具体的结果为：（1，1，1，1）（0，1，0，1）(1，1，0，1）（0，0，0，1）（1，0，1，1）（0，0，1，0）（1，0，1，0）（0，0，0，0）。或者为：或者为：（1，1，1，1）（0，1，0，1）（1，1，0，1）（0，1，0，0）（1，
6、1，1，0）（0，0，1，0）（1，0，1，0）（0，0，0，0）。）。问题问题 2.商人过河问题商人过河问题三三名名商商人人各各带带一一名名仆仆人人过过河河,渡渡船船最最多多载载2人人.在在任任何何一一岸岸,仆仆人人数数不不允允许许大大于于商商人人数数,否否则则仆仆人人就就要要杀杀人人越越货货.请请制制定定一一个个安安全全渡河的操作方案渡河的操作方案.求解求解.用一个二维向量来表示此岸的商人数、仆人数的具体状态用一个二维向量来表示此岸的商人数、仆人数的具体状态.例如例如:(3,3)表示此岸有三个商人表示此岸有三个商人,三个仆人三个仆人;(0,2)表示此岸表示此岸无商人无商人,两个仆人两个仆人
7、;等等等等.状态运算向量集合状态运算向量集合为为:D D =(0,1),(0,2),(1,1),(1,0),(2,0).把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量的向量相加或相减的向量相加或相减（去往对岸为相减，返回此岸为相加）（去往对岸为相减，返回此岸为相加）.允许状态向量集合允许状态向量集合为为:S=(3,3),(3,2),(3,1),(3,0),(2,2),(1,1),(0,3),(0,2),(0,1)，(0,0)和和上上一一问问题题一一样样,可可以以用用Mathematica软软件件编编程程求求解解.具具体体的的结结
8、果果为（为（4种方案）：种方案）：方案方案 1：（3，3）（3，1）（3，2）（3，0）（3，1）（1，1）（2，2）（0，2）（0，3）（0，1）（0，2）（0，0）。在以上所规定的意义下在以上所规定的意义下,这个问题的状态转移模型可表示为这个问题的状态转移模型可表示为:si+1=si+(-1)idk,其中其中si S S ,dk D D ;且对任意且对任意 ji,都有都有 sjsi .方案方案 2：（3，3）（3，1）（3，2）（3，0）（3，1）（1，1）（2，2）（0，2）（0，3）（0，1）（1，1）（0，0）。方案方案 3：（3，3）（2，2）（3，2）（3，0）（3，1）（1，1
9、）（2，2）（0，2）（0，3）（0，1）（0，2）（0，0）。方案方案 4：（3，3）（2，2）（3，2）（3，0）（3，1）（1，1）（2，2）（0，2）（0，3）（0，1）（1，1）（0，0）。本题还可以用作图方法来求解，具体做法可参考教科书第本题还可以用作图方法来求解，具体做法可参考教科书第11页页.以上两个例子本身并无多大实际意义以上两个例子本身并无多大实际意义,但它们展示了如何将实际问但它们展示了如何将实际问 题转化为题转化为 状态转移状态转移 问题问题,并用并用 状态转移法状态转移法 来求解问题的过程和来求解问题的过程和 思考方法思考方法.习题习题.在与问题在与问题2同样的假定下
10、同样的假定下,试求解四对商人过河问题。试求解四对商人过河问题。如果渡船最多可载如果渡船最多可载3人，试求解五对商人和六对商人过河问题。人，试求解五对商人和六对商人过河问题。如果渡船最多可载如果渡船最多可载4人，试求解任意对商人过河问题。人，试求解任意对商人过河问题。问题问题 3.取石游戏问题取石游戏问题三三堆堆石石子子,各各堆堆数数目目任任意意.两两人人轮轮流流取取走走石石子子,规规定定只只准准在在一一堆堆中中至至少少取取走走一一颗颗,至至于于是是哪哪一一堆堆可可任任意意选选定定.谁谁取取到到最最后后的的一一颗颗石石子子为输为输,请制定一个取胜策略请制定一个取胜策略.建建模模思思想想:利利用用
11、二二进进制制 及及“与与”、“非非”运运算算来来模模拟拟状状态态及及其转其转移过程移过程.建立状态转移模型建立状态转移模型:设在操作中某一状态的三堆石子数分别为设在操作中某一状态的三堆石子数分别为n1,n2,n3.将它们化将它们化为二进制数为二进制数:其中其中a1,b1,c1不都为零不都为零.n1(a1a2an),n2(b1b2bn),n3(c1c2cn),令令:N=(a1a2an)+(b1b2bn)+(c1c2cn),称称它它为为状状态态n1,n2,n3的的状状态态指指标标数数 .这这里里三三个个二二进进制制数数各各对对应应数数位位上的数字相加法则规定为上的数字相加法则规定为“与与”、“或或
12、”运算运算:1+1=0,1+0=1,0+1=1,0+0=0.若若N=0,则称状态则称状态n1,n2,n3为为必必 输状态输状态,简称为简称为L状态状态 (Lost).若若N0,则称状态则称状态n1,n2,n3为为必赢状态必赢状态,简称为简称为W状态状态 (Win).显然任显然任何一种状态要末是何一种状态要末是L状态状态,要末是要末是W状态状态,亦即两者必居其一亦即两者必居其一.设设对对某某一一L状状态态n1,n2,n3(N=0)进进行行一一次次取取石石操操作作,无无妨妨设设n1n1,相相应应的的二二进进制制数数(a1a2an)(a1a2an).L状态状态n1,n2,n3状态状态n1,n2,n3
13、;相应地相应地,N=0N.若若a1a1,则则a1=1-a1.因因a1+b1+c1=0a1+b1+c1=1N 0.若若a1=a1,则则考考察察a2与与a2,如如果果a2a2,同同理理可可得得N 0,否则否则继继续续考考察察下下去去.因因为为必必存存在在某某个个下下标标号号k,使使akak,故故必必有有N 0,这这说说明明一一个个L状状态态,任任意意进进行行一一次次取取石石操操作作,都都会会变变成成一一个个W状状态态 .模型的理论分析模型的理论分析:(1)一个一个L状态状态,任意进行一次取石操作任意进行一次取石操作,都会都会变成一个变成一个W状态状态.(2)对对于于任任一一个个W状状态态,总总存存
14、在在着着某某一一个个取取石石操操作作,使使它它变成变成一个一个L状态状态.假假定定一一个个W状状态态为为:n1,n2,n3(N0).记记与与三三个个十十进进制制数数n1,n2,n3相对应的二进制数分别为相对应的二进制数分别为:(a1a2an),(b1b2bn),(c1c2cn).以以下下三三种种情情况况必必有有一一种种是是成成立立的的:i)(a1a2an)(b1+c1)(b2+c2)(bn+cn);ii)(b1b2bn)(a1+c1)(a2+c2)(an+cn);iii)(c1c2cn)(a1+b1)(a2+b2)(an+bn).无妨设第无妨设第i)种情况成立种情况成立.这说明这说明,二进制数
15、二进制数(a1a2an)所所对对应应的的十十进进制制数数n1与与二二进进制制数数(b1+c1)(b2+c2)(bn+cn)所对应的十进制数所对应的十进制数n有关系有关系:n1n.由由此此,只只须须在在第第一一堆堆中中取取走走(n1-n)颗颗石石子子,W状状态态 n1,n2,n3变化而成一个新状态变化而成一个新状态n,n2,n3,这个状态的这个状态的状态指标数状态指标数N =0.这说明这说明:对于任一个对于任一个W 状态状态,总存在着某一个取石操作总存在着某一个取石操作,使它变成一个使它变成一个L 状态状态 .制定取胜策略制定取胜策略:选取某堆选取某堆,从中取走适量石子从中取走适量石子,使这三堆
16、构成使这三堆构成L状态状态.备注备注：（：（1）N=0时未必有时未必有n1+n2=n3，例如：，例如：n1=1501111，n2=2110101，n3=2611010，显然显然n1+n2 n3,但此时，但此时，N=00000=0；n1=30000011，n2=691000101，n3=701000110，显然又有显然又有n1+n2 n3,但此时但此时 ，N=00000=0；又例如：又例如：（2）n1+n2=n3时未必有时未必有N=0，例如：，例如：n1=15001111，n2=21010101，n3=36100100，显然显然n1+n2=n3,为了取胜，为了取胜，可将可将(n1,n2,n3)=
17、(15,21,36)变成变成:(n1,n2,n3)=(15,21,26)即可。即可。但此时但此时，N=111110 0.又如又如：n1=1101011，n1=7111，所所以以制制胜胜策策略略并并非非是是“两两堆堆数数字字之之和和等等于于第第三三堆堆数数字字”。但此时但此时 ，N=1110 0；等等；等等 。但此时但此时，N=100 0；为了取胜为了取胜，可将可将(n1,n2,n3)=(11,18,29)变成变成:(n1,n2,n3)=(11,18,25)即可。即可。为了取胜为了取胜，可将可将(n1,n2,n3)=(7,21,28)变成变成:(n1,n2,n3)=(7,21,18)即可。即可。n2=2110101，n3=2811100，显然显然 n1+n2=n3,n2=1810010，n3=2911101，显然显然n1+n2=n3,