数学建模状态转移法

§12.常见的数学建模方法(7)----状态转移法

处理问题的类型:状态转移问题,属离散性模型问题.问题的内容：讨论在一定的条件下，系统由一个状态转移到另一个状态是否可能,如果可能的话，应该如何具体实现。基本方法及数学技巧:

用向量来模拟状态.将状态的演变描述成向量的运算,以便于计算机程序处理.问题1.人、狗、鸡、米过河问题某人要带人、狗、鸡、米用渡船过河,但渡船需要人划外,最多只能载一物过河,而且当人不在场时,狗要咬鸡,鸡要吃米.问此人应如何安全渡河?求解.把此问题视为一个状态转移问题.具体规定:可取状态.

用一个四维向量来表示人、物在此岸与不在此岸的状态.这个四维向量中的第一至第四分量元素分别表示人、狗、鸡、米,它们的取值只能为1或0,其中1表示在此岸,0表示不在此岸.例如:(1,0,1,0)表示人、鸡在此岸,狗与米在对岸.由题意,允许发生的状态向量集合为: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)可取运算.状态转移需经状态运算来实现.在实际问题中,摆一次渡可改变现有的状态,为此引进一个四维的状态运算向量,用它来反映摆渡操作情况.根据题意,状态运算向量集合为:D={(1,0,1,0),(1,1,0,0),(1,0,0,1),(1,0,0,0)}.把每一次摆渡运作看成为一个可取状态向量和一个状态运算向量的向量相加或相减(去往对岸为相减，返回此岸为相加）.在以上所规定的意义下,这个问题的状态转移模型可表示为:si+1=si+(-1)i·dk,其中si

S

,

dk

D;且对任意j>i,都有sj≠si

令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，1，1，0）

（0，0，1，0）

（1，0，1，0）

（0，0，0，0）。问题2.商人过河问题三名商人各带一名仆人过河,渡船最多载2人.在任何一岸,仆人数不允许大于商人数,否则仆人就要杀人越货.请制定一个安全渡河的操作方案.求解.用一个二维向量来表示此岸的商人数、仆人数的具体状态.例如:(3,3)表示此岸有三个商人,三个仆人;(0,2)表示此岸无商人,两个仆人;等等.状态运算向量集合为:

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软件编程求解.具体的结果为（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)i·dk,其中si

S

,

dk

D;且对任意j>i,都有sj≠si.

方案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）

（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同样的假定下,试求解四对商人过河问题。如果渡船最多可载3人，试求解五对商人和六对商人过河问题。如果渡船最多可载4人，试求解任意对商人过河问题。

(2)

对于任一个W状态,总存在着某一个取石操作,使它变成一个L状态.假定一个W状态为:{n1,n2,n3}(N≠0).记与三个十进制数n1,n2,n3相对应的二进制数分别为:(a1a2……an),(b1b2……bn),(c1c2……cn).以下三种情况必有一种是成立的:i)(a1a2……an)>((b1+c1)(b2+c2)……(bn+cn));ii)(b1b2……bn)>((a1+c1)(a2+c2)……(an+cn));iii)

(c1c2……cn)>((a1+b1)(a2+b2)……(an+bn)).无妨设第i)种情况成立.这说明,二进制数(a1a2……an)所对应的十进制数n1与二进制数((b1+c1)(b2+c2)……(bn+cn))所对应的十进制数n’

有关系:n1>n’.由此,只须在第一堆中取走(n1-n’)颗石子,W状态{n1,n2,n3}变化而成一个新状态{n’

,n2,n3},这个状态的状态指标数

N’=0.这说明:对于任一个W状态,总存在着某一个取石操作,使它变成一个L状态.制定取胜策略:选取某堆,从中取走适量石子,使这三堆构成

L状态.备注：（1）

N=0

时未必有n1+n2=n3

，例如：

n1=15

01111，n2=21

10101，

n3=26

11010，

显然n1+n2

n3,但此时，N=00000=0；

n1=3

0000011，n2=69

1000101，

n3=70

1000110，

显然又有n1+n2

n3,但此时，N=00000=0；

又例如：

（2）n1+n2=n3

时未必有N=0，例如：

n1=15

001111，

n2=21

010101，

n3=36

100100，

显然n1+n2=n3,为了取胜，可将(n1,n2,n3)=(15,21,36)变成:(n1,n2,n3’)=(15,21,26)即可。但此时，N=111110

0.又如：n1=11

01011，n1=7

111，所以制胜策略并非是

“两堆数字之和等于第三堆数字”。但此时，N=11100；等等。

但此时，N=1000；为了取胜，可将(n1,n2,n3)=(11,18,29)变成:(n1,n2,n3’)=(11,18,25)即可。为了取胜，可将(n1,n2,n3)=(7,21,