數(shù)學(xué)建模狀態(tài)轉(zhuǎn)移法PPT學(xué)習(xí)教案

1、會(huì)計(jì)學(xué)1 數(shù)學(xué)建模狀態(tài)轉(zhuǎn)移法數(shù)學(xué)建模狀態(tài)轉(zhuǎn)移法 (2) 可取運(yùn)算可取運(yùn)算. 狀態(tài)轉(zhuǎn)移需經(jīng)狀態(tài)運(yùn)算來(lái)實(shí)現(xiàn)狀態(tài)轉(zhuǎn)移需經(jīng)狀態(tài)運(yùn)算來(lái)實(shí)現(xiàn). 在實(shí)際問(wèn)題中在實(shí)際問(wèn)題中, 擺一次擺一次 渡可改變現(xiàn)有的狀態(tài)渡可改變現(xiàn)有的狀態(tài), 為此引進(jìn)一個(gè)四維的狀態(tài)運(yùn)算向量為此引進(jìn)一個(gè)四維的狀態(tài)運(yùn)算向量, 用它來(lái)反用它來(lái)反 映擺渡操作情況映擺渡操作情況. 根據(jù)題意根據(jù)題意, 狀態(tài)運(yùn)算向量集合為狀態(tài)運(yùn)算向量集合為: D D = ( 1, 0, 1, 0 ) , ( 1, 1, 0, 0 ) , ( 1, 0, 0, 1 ) , ( 1, 0, 0, 0 ) . 把每一次擺渡運(yùn)作看成為一個(gè)可取狀態(tài)向量和一個(gè)狀態(tài)運(yùn)算向量把每一次

2、擺渡運(yùn)作看成為一個(gè)可取狀態(tài)向量和一個(gè)狀態(tài)運(yùn)算向量 的向量相加或相減的向量相加或相減 (去往對(duì)岸為相減，返回此岸為相加）去往對(duì)岸為相減，返回此岸為相加）. 在以上所規(guī)定的意義下在以上所規(guī)定的意義下, 這個(gè)問(wèn)題的狀態(tài)轉(zhuǎn)移模型可表示為這個(gè)問(wèn)題的狀態(tài)轉(zhuǎn)移模型可表示為: s i+1 = s i + (-1) i d k , 其中其中 s i S S , d k D D ; ; 且對(duì)任意且對(duì)任意 j i , 都有都有 s j s i 令令 s1 = ( 1, 1, 1, 1 ) , sn = ( 0, 0, 0, 0 ) , 利用計(jì)算機(jī)編程處理利用計(jì)算機(jī)編程處理, 例如，例如， 可以用可以用 Math 軟

3、件編程求解這個(gè)擺渡操作方案軟件編程求解這個(gè)擺渡操作方案 , 即求出即求出 n 和和 d1 , d2 , d3 , , dn 各是多少各是多少. 第1頁(yè)/共11頁(yè) 具體的結(jié)果為：具體的結(jié)果為： （ 1，1，1，1 ） )0 , 1 , 0 , 1( )0, 0, 0, 1( )0 , 0 , 1 , 1( )0 , 1 , 0 , 1( )1 , 0, 0, 1( )0,0,0, 1( )0 , 1 , 0 , 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 ） 。 或者為：或者

4、為： （ 1，1，1，1 ） )0 , 1 , 0 , 1( （ 0，1，0，1 ） )0, 0, 0, 1( （ 1，1，0，1 ） )1 , 0 , 0 , 1( （ 0，1，0，0 ） )0 , 1 , 0 , 1( （ 1，1，1，0 ） )0 , 0 , 1 , 1( （ 0，0，1，0 ） )0 , 0 , 0 , 1( （ 1，0，1，0 ） )0 , 1 , 0 , 1( （ 0，0，0，0 ）。）。 第2頁(yè)/共11頁(yè) 問(wèn)題問(wèn)題 2 . 商人過(guò)河問(wèn)題商人過(guò)河問(wèn)題 三名商人各帶一名仆人過(guò)河三名商人各帶一名仆人過(guò)河, 渡船最多載渡船最多載 2 人人. 在任何一岸在任何一岸, 仆人數(shù)

5、不允許大于商人數(shù)仆人數(shù)不允許大于商人數(shù), 否則仆人就要?dú)⑷嗽截浄駝t仆人就要?dú)⑷嗽截? 請(qǐng)制定一個(gè)安全渡河的操作方案請(qǐng)制定一個(gè)安全渡河的操作方案. 求解求解. 用一個(gè)二維向量來(lái)表示此岸的商人數(shù)、仆人數(shù)的具體狀態(tài)用一個(gè)二維向量來(lái)表示此岸的商人數(shù)、仆人數(shù)的具體狀態(tài). 例如例如: ( 3, 3 ) 表示此岸有三個(gè)商人表示此岸有三個(gè)商人, 三個(gè)仆人三個(gè)仆人 ; ( 0, 2 ) 表示此岸表示此岸 無(wú)商人無(wú)商人 , 兩個(gè)仆人兩個(gè)仆人 ; 等等等等 . 狀態(tài)運(yùn)算向量集合狀態(tài)運(yùn)算向量集合 為為: D D = ( 0, 1 ) , ( 0 , 2 ) , ( 1, 1 ) , ( 1, 0 ) , ( 2, 0

6、 ) . 把每一次擺渡運(yùn)作看成為一個(gè)可取狀態(tài)向量和一個(gè)狀態(tài)運(yùn)算向量把每一次擺渡運(yùn)作看成為一個(gè)可取狀態(tài)向量和一個(gè)狀態(tài)運(yùn)算向量 的向量相加或相減的向量相加或相減 （去往對(duì)岸為相減，返回此岸為相加）（去往對(duì)岸為相減，返回此岸為相加）. 允許狀態(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 ) 第3頁(yè)/共11頁(yè) 和上一問(wèn)題一樣和上一問(wèn)題一樣, 可以用可以用 Mathematica 軟件編程求解軟件編

7、程求解. 具體的結(jié)果為（具體的結(jié)果為（ 4 種方案）：種方案）： 方案方案 1： （ 3，3 ） )2, 0( （ 3，1 ） )1 , 0( （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 , 2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 , 2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （ 0，1 ） )1 , 0( （ 0，2 ） )2, 0( （ 0，0 ） 。 在以上所規(guī)定的意義下在以上所規(guī)定的意義下, 這個(gè)問(wèn)題的狀態(tài)轉(zhuǎn)移模型可表示為這個(gè)問(wèn)題的狀態(tài)轉(zhuǎn)移模型可表示為: s i+1 = s i + (-1) i d

8、k , 其中其中 s i S S , d k D D ; ; 且對(duì)任意且對(duì)任意 j i , 都有都有 s j s i . . 方案方案 2： （ 3，3 ） )2, 0( （ 3，1 ） )1 , 0( （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 ,2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 ,2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （ 0，1 ） )0 , 1( （ 1，1 ） )1 , 1( （ 0，0 ） 。 第4頁(yè)/共11頁(yè) 方案方案 3： （ 3，3 ） )1 , 1( （ 2，2 ） )0 , 1(

9、 （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 ,2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 ,2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （ 0，1 ） )1 , 0( （ 0，2 ） )2, 0( （ 0，0 ） 。 方案方案 4： （ 3，3 ） )1 , 1( （ 2，2 ） )0 , 1( （ 3，2 ） )2, 0( （ 3，0 ） )1 , 0( （ 3，1 ） )0 ,2( （ 1，1 ） )1 , 1( （ 2，2 ） )0 ,2( （ 0，2 ） )1 , 0( （ 0，3 ） )2, 0( （

10、0，1 ） )0 , 1( （ 1，1 ） )1 , 1( （ 0，0 ） 。 本題還可以用作圖方法來(lái)求解，具體做法可參考教科書(shū)第本題還可以用作圖方法來(lái)求解，具體做法可參考教科書(shū)第11頁(yè)頁(yè). 以上兩個(gè)例子本身并無(wú)多大實(shí)際意義以上兩個(gè)例子本身并無(wú)多大實(shí)際意義, 但它們展示了如何將實(shí)際問(wèn)但它們展示了如何將實(shí)際問(wèn) 題轉(zhuǎn)化為題轉(zhuǎn)化為 狀態(tài)轉(zhuǎn)移狀態(tài)轉(zhuǎn)移 問(wèn)題問(wèn)題, 并用并用 狀態(tài)轉(zhuǎn)移法狀態(tài)轉(zhuǎn)移法 來(lái)求解問(wèn)題的過(guò)程和來(lái)求解問(wèn)題的過(guò)程和 思考方法思考方法. 習(xí)題習(xí)題. 在與問(wèn)題在與問(wèn)題2同樣的假定下同樣的假定下, 試求解四對(duì)商人過(guò)河問(wèn)題。試求解四對(duì)商人過(guò)河問(wèn)題。 如果渡船最多可載如果渡船最多可載 3 人，試

11、求解五對(duì)商人和六對(duì)商人過(guò)河問(wèn)題。人，試求解五對(duì)商人和六對(duì)商人過(guò)河問(wèn)題。 如果渡船最多可載如果渡船最多可載 4 人，試求解任意對(duì)商人過(guò)河問(wèn)題。人，試求解任意對(duì)商人過(guò)河問(wèn)題。 第5頁(yè)/共11頁(yè) 問(wèn)題問(wèn)題 3. 取石游戲問(wèn)題取石游戲問(wèn)題 三堆石子三堆石子, 各堆數(shù)目任意各堆數(shù)目任意. 兩人輪流取走石子兩人輪流取走石子, 規(guī)定只準(zhǔn)在一堆中規(guī)定只準(zhǔn)在一堆中 至少取走一顆至少取走一顆, 至于是哪一堆可任意選定至于是哪一堆可任意選定. 誰(shuí)取到最后的一顆石子誰(shuí)取到最后的一顆石子 為輸為輸, 請(qǐng)制定一個(gè)取勝策略請(qǐng)制定一個(gè)取勝策略. 建模思想建模思想 : 利用利用二進(jìn)制二進(jìn)制 及及 “與與 ”、“非非 ” 運(yùn)算來(lái)

12、模擬狀態(tài)及其轉(zhuǎn)運(yùn)算來(lái)模擬狀態(tài)及其轉(zhuǎn) 移過(guò)程移過(guò)程. 建立狀態(tài)轉(zhuǎn)移模型建立狀態(tài)轉(zhuǎn)移模型: 設(shè)在操作中某一狀態(tài)的三堆石子數(shù)分別為設(shè)在操作中某一狀態(tài)的三堆石子數(shù)分別為 n1 , n2 , n3 . 將它們化將它們化 為二進(jìn)制數(shù)為二進(jìn)制數(shù) : 其中其中 a1 , b1 , c1 不都為零不都為零. . n1( a1 a2 an ) , n2( b1 b2 bn ) ,n3( c1 c2 cn ) , 令令: N = ( a1 a2 an ) + ( b1 b2 bn ) + ( c1 c2 cn ) , 稱(chēng)它為稱(chēng)它為 狀態(tài)狀態(tài) n1 , n2 , n3 的的 狀態(tài)指標(biāo)數(shù)狀態(tài)指標(biāo)數(shù) . 這里三個(gè)二進(jìn)制數(shù)

13、各對(duì)應(yīng)數(shù)位這里三個(gè)二進(jìn)制數(shù)各對(duì)應(yīng)數(shù)位 上的數(shù)字相加法則規(guī)定為上的數(shù)字相加法則規(guī)定為 “與與 ” 、“或或 ” 運(yùn)算運(yùn)算: 1 + 1 = 0 , 1 + 0 = 1 , 0 + 1 = 1 , 0 + 0 = 0 . 第6頁(yè)/共11頁(yè) 若若 N = 0 , 則稱(chēng)狀態(tài)則稱(chēng)狀態(tài) n1 , n2 , n3 為為 必必 輸狀態(tài)輸狀態(tài) , 簡(jiǎn)稱(chēng)為簡(jiǎn)稱(chēng)為 L狀態(tài)狀態(tài) ( Lost ) . 若若 N 0 , 則稱(chēng)狀態(tài)則稱(chēng)狀態(tài) n1 , n2 , n3 為為 必贏狀態(tài)必贏狀態(tài), 簡(jiǎn)稱(chēng)為簡(jiǎn)稱(chēng)為 W狀態(tài)狀態(tài) ( Win ) . 顯然任顯然任 何一種狀態(tài)要末是何一種狀態(tài)要末是 L狀態(tài)狀態(tài) , 要末是要末是 W狀態(tài)狀

14、態(tài) , 亦即兩者必居其一亦即兩者必居其一. 設(shè)對(duì)某一設(shè)對(duì)某一 L狀態(tài)狀態(tài) n1 , n2 , n3 ( N = 0 ) 進(jìn)行一次取石操作進(jìn)行一次取石操作, 無(wú)妨設(shè)無(wú)妨設(shè) n1 n1 , 相應(yīng)的二進(jìn)制數(shù)相應(yīng)的二進(jìn)制數(shù) ( a1 a2 an ) ( a1 a2 a n ) . L狀態(tài)狀態(tài) n1 , n2 , n3 狀態(tài)狀態(tài) n1 , n2 , n3 ; 相應(yīng)地相應(yīng)地 , N = 0 N . 若若 a1 a1 , 則則 a1 = 1 - - a1 . 因因 a1 + b1 + c1 = 0 a1 + b1 + c1 = 1 N 0 . 若若 a1 = a1, 則考察則考察 a2 與與 a2 , 如果

15、如果 a2 a2 , 同理可得同理可得 N 0 , 否則否則 繼續(xù)考察下去繼續(xù)考察下去. 因?yàn)楸卮嬖谀硞€(gè)下標(biāo)號(hào)因?yàn)楸卮嬖谀硞€(gè)下標(biāo)號(hào) k ,使使ak ak , 故必有故必有 N 0 , 這說(shuō)明一個(gè)這說(shuō)明一個(gè) L狀態(tài)狀態(tài) , 任意進(jìn)行一次取石操作任意進(jìn)行一次取石操作, 都會(huì)變成一個(gè)都會(huì)變成一個(gè) W狀態(tài)狀態(tài) . 模型的理論分析模型的理論分析: (1) 一個(gè)一個(gè) L 狀態(tài)狀態(tài) , 任意進(jìn)行一次取石操作任意進(jìn)行一次取石操作 , 都會(huì)都會(huì) 變成一個(gè)變成一個(gè) W 狀態(tài)狀態(tài) . 第7頁(yè)/共11頁(yè) (2) 對(duì)于任一個(gè)對(duì)于任一個(gè) W 狀態(tài)狀態(tài) , 總存在著某一個(gè)取石操作總存在著某一個(gè)取石操作 , 使它變成使它變成

16、 一個(gè)一個(gè) L 狀態(tài)狀態(tài) . 假定一個(gè)假定一個(gè) W 狀態(tài)為狀態(tài)為: n1 , n2 , n3 ( N 0 ) . 記與三個(gè)十進(jìn)制數(shù)記與三個(gè)十進(jìn)制數(shù) n1 , n2 , n3 相對(duì)應(yīng)的二進(jìn)制數(shù)分別為相對(duì)應(yīng)的二進(jìn)制數(shù)分別為 : ( a1 a2 an ) , ( b1 b2 bn ) , ( c1 c2 cn ) . 以下三種情況必有一種是成立的以下三種情況必有一種是成立的: i) ( a1 a2 an ) ( (b1 + c1)(b2 + c2)(bn + cn) ) ; ii) ( b1 b2 bn ) ( (a1 + c1)(a2 + c2)(an + cn) ) ; iii) ( c1 c2

17、 cn ) ( (a1 + b1)(a2 + b2)(an + bn) ) . 無(wú)妨設(shè)第無(wú)妨設(shè)第 i) 種情況成立種情況成立 . 這說(shuō)明這說(shuō)明 , 二進(jìn)制數(shù)二進(jìn)制數(shù) ( a1 a2 an ) 所對(duì)應(yīng)的十進(jìn)制數(shù)所對(duì)應(yīng)的十進(jìn)制數(shù) n1 與與 二進(jìn)制數(shù)二進(jìn)制數(shù) ( (b1 + c1)(b2 + c2)(bn + cn) ) 所對(duì)應(yīng)的十進(jìn)制數(shù)所對(duì)應(yīng)的十進(jìn)制數(shù) n 有關(guān)系有關(guān)系 : n1 n . 由此由此 , 只須在第一堆中取走只須在第一堆中取走 (n1 - - n ) 顆石子顆石子, W狀態(tài)狀態(tài) n1 , n2 , n3 變化而成一個(gè)新?tīng)顟B(tài)變化而成一個(gè)新?tīng)顟B(tài) n , n2 , n3 , 這個(gè)狀態(tài)的這個(gè)

18、狀態(tài)的 狀態(tài)指標(biāo)數(shù)狀態(tài)指標(biāo)數(shù) N = 0 . 這說(shuō)明這說(shuō)明: 對(duì)于任一個(gè)對(duì)于任一個(gè) W 狀態(tài)狀態(tài), 總存在著某一個(gè)取石操作總存在著某一個(gè)取石操作, 使它變成一個(gè)使它變成一個(gè) L 狀態(tài)狀態(tài) . 第8頁(yè)/共11頁(yè) 制定取勝策略制定取勝策略 : 選取某堆選取某堆 , 從中取走適量石子從中取走適量石子 , 使這三堆構(gòu)成使這三堆構(gòu)成 L狀態(tài)狀態(tài). 備注備注：（：（1） N = 0 時(shí)未必有時(shí)未必有 n1 + n2 = n3 ，例如：，例如： n1 = 15 0 1 1 1 1 ， n2 = 21 1 0 1 0 1 ， n3 = 26 1 1 0 1 0 ， 顯然顯然 n1 + n2 n3 , 但此時(shí)，但此時(shí)，N = 0 0 0 0 0 = 0 ； n1 = 3 0 0 0 0 0 1 1 ， n2 = 69 1 0 0 0 1 0 1 ， n3 = 70 1 0 0 0 1 1 0 ， 顯然又有顯然又有 n1 + n2 n3 , 但此時(shí)但此時(shí) ，N = 0 0 0 0 0 = 0 ； 又例如：又例如： （2） n1 + n2 = n3 時(shí)未必有時(shí)未必有 N = 0 ，例如：，例如： n1 = 15 0 0 1 1 1 1 ， n2 = 21 0 1 0 1 0 1 ， n3 = 36 1 0 0 1 0 0 ， 顯然顯然 n1