數學建模狀態(tài)轉移法VIP

§12.常見的數學建模方法(7)----狀態(tài)轉移法

處理問題的類型:狀態(tài)轉移問題,屬離散性模型問題.問題的內容：討論在一定的條件下，系統(tǒng)由一個狀態(tài)轉移到另一個狀態(tài)是否可能,如果可能的話，應該如何具體實現(xiàn)。基本方法及數學技巧:

用向量來模擬狀態(tài).將狀態(tài)的演變描述成向量的運算,以便于計算機程序處理.問題1.人、狗、雞、米過河問題某人要帶人、狗、雞、米用渡船過河,但渡船需要人劃外,最多只能載一物過河,而且當人不在場時,狗要咬雞,雞要吃米.問此人應如何安全渡河?求解.把此問題視為一個狀態(tài)轉移問題.具體規(guī)定:可取狀態(tài).

用一個四維向量來表示人、物在此岸與不在此岸的狀態(tài).這個四維向量中的第一至第四分量元素分別表示人、狗、雞、米,它們的取值只能為1或0,其中1表示在此岸,0表示不在此岸.例如:(1,0,1,0)表示人、雞在此岸,狗與米在對岸.由題意,允許發(fā)生的狀態(tài)向量集合為: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)可取運算.狀態(tài)轉移需經狀態(tài)運算來實現(xiàn).在實際問題中,擺一次渡可改變現(xiàn)有的狀態(tài),為此引進一個四維的狀態(tài)運算向量,用它來反映擺渡操作情況.根據題意,狀態(tài)運算向量集合為:D={(1,0,1,0),(1,1,0,0),(1,0,0,1),(1,0,0,0)}.把每一次擺渡運作看成為一個可取狀態(tài)向量和一個狀態(tài)運算向量的向量相加或相減(去往對岸為相減，返回此岸為相加）.在以上所規(guī)定的意義下,這個問題的狀態(tài)轉移模型可表示為: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）?；蛘邽椋?/p>

（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人.在任何一岸,仆人數不允許大于商人數,否則仆人就要殺人越貨.請制定一個安全渡河的操作方案.求解.用一個二維向量來表示此岸的商人數、仆人數的具體狀態(tài).例如:(3,3)表示此岸有三個商人,三個仆人;(0,2)表示此岸無商人,兩個仆人;等等.狀態(tài)運算向量集合為:

D

={(0,1),(0,2),(1,1),(1,0),(2,0)}.把每一次擺渡運作看成為一個可取狀態(tài)向量和一個狀態(tài)運算向量的向量相加或相減（去往對岸為相減，返回此岸為相加）.允許狀態(tài)向量集合為: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）

。

在以上所規(guī)定的意義下,這個問題的狀態(tài)轉移模型可表示為: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頁.以上兩個例子本身并無多大實際意義,但它們展示了如何將實際問題轉化為狀態(tài)轉移問題,并用狀態(tài)轉移法來求解問題的過程和

思考方法.習題.在與問題2同樣的假定下,試求解四對商人過河問題。如果渡船最多可載3人，試求解五對商人和六對商人過河問題。如果渡船最多可載4人，試求解任意對商人過河問題。

(2)

對于任一個W狀態(tài),總存在著某一個取石操作,使它變成一個L狀態(tài).假定一個W狀態(tài)為:{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狀態(tài){n1,n2,n3}變化而成一個新狀態(tài){n’

,n2,n3},這個狀態(tài)的狀態(tài)指標數

N’=0.這說明:對于任一個W狀態(tài),總存在著某一個取石操作,使它變成一個L狀態(tài).制定取勝策略:選取某堆,從中取走適量石子,使這三堆構成

L狀態(tài).備注：（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,