




版權說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權,請進行舉報或認領
文檔簡介
§12.常見的數(shù)學建模方法(7)----狀態(tài)轉(zhuǎn)移法
處理問題的類型:狀態(tài)轉(zhuǎn)移問題,屬離散性模型問題.問題的內(nèi)容:討論在一定的條件下,系統(tǒng)由一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)是否可能,如果可能的話,應該如何具體實現(xiàn)?;痉椒皵?shù)學技巧:
用向量來模擬狀態(tài).將狀態(tài)的演變描述成向量的運算,以便于計算機程序處理.問題1.人、狗、雞、米過河問題某人要帶人、狗、雞、米用渡船過河,但渡船需要人劃外,最多只能載一物過河,而且當人不在場時,狗要咬雞,雞要吃米.問此人應如何安全渡河?求解.把此問題視為一個狀態(tài)轉(zhuǎn)移問題.具體規(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)轉(zhuǎn)移需經(jīng)狀態(tài)運算來實現(xiàn).在實際問題中,擺一次渡可改變現(xiàn)有的狀態(tài),為此引進一個四維的狀態(tài)運算向量,用它來反映擺渡操作情況.根據(jù)題意,狀態(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)轉(zhuǎn)移模型可表示為: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人.在任何一岸,仆人數(shù)不允許大于商人數(shù),否則仆人就要殺人越貨.請制定一個安全渡河的操作方案.求解.用一個二維向量來表示此岸的商人數(shù)、仆人數(shù)的具體狀態(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)轉(zhuǎn)移模型可表示為: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頁.以上兩個例子本身并無多大實際意義,但它們展示了如何將實際問題轉(zhuǎn)化為狀態(tài)轉(zhuǎn)移問題,并用狀態(tài)轉(zhuǎn)移法來求解問題的過程和
思考方法.習題.在與問題2同樣的假定下,試求解四對商人過河問題。如果渡船最多可載3人,試求解五對商人和六對商人過河問題。如果渡船最多可載4人,試求解任意對商人過河問題。
(2)
對于任一個W狀態(tài),總存在著某一個取石操作,使它變成一個L狀態(tài).假定一個W狀態(tài)為:{n1,n2,n3}(N≠0).記與三個十進制數(shù)n1,n2,n3相對應的二進制數(shù)分別為:(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)種情況成立.這說明,二進制數(shù)(a1a2……an)所對應的十進制數(shù)n1與二進制數(shù)((b1+c1)(b2+c2)……(bn+cn))所對應的十進制數(shù)n’
有關系:n1>n’.由此,只須在第一堆中取走(n1-n’)顆石子,W狀態(tài){n1,n2,n3}變化而成一個新狀態(tài){n’
,n2,n3},這個狀態(tài)的狀態(tài)指標數(shù)
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,所以制勝策略并非是
“兩堆數(shù)字之和等于第三堆數(shù)字”。但此時,N=11100;等等。
但此時,N=1000;為了取勝,可將(n1,n2,n3)=(11,18,29)變成:(n1,n2,n3’)=(11,18,25)即可。為了取勝,可將(n1,n2,n3)=(7,21,
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預覽,若沒有圖紙預覽就沒有圖紙。
- 4. 未經(jīng)權益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負責。
- 6. 下載文件中如有侵權或不適當內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 年產(chǎn)2000噸鍛造套圈項目可行性研究報告寫作模板-備案審批
- 二零二五年度教育信息化合作協(xié)議補充協(xié)議
- 二零二五年度智能交通系統(tǒng)工程合作協(xié)議書
- 餐飲行業(yè)2025年度校園飯?zhí)媒?jīng)營權轉(zhuǎn)讓合同
- 媒體合作合同履約金條款
- 2025年度智慧社區(qū)車位產(chǎn)權出售協(xié)議書
- 農(nóng)田土地流轉(zhuǎn)合同模板
- 建材采購合同變更協(xié)議
- 二零二五年度拓展活動知識產(chǎn)權保護協(xié)議
- 二零二五年度臨時工勞動權益保護與勞動合同簽訂規(guī)范
- 納米生物醫(yī)用材料課件
- 八年級-現(xiàn)在完成時復習(共26張)課件
- 第十章可持續(xù)發(fā)展理論與實踐課件
- 電氣基礎知識培訓要點課件
- 洗浴中心轉(zhuǎn)讓合同(5篇)
- 外研版小學英語五年級下冊課文翻譯
- YY-T 1823-2022 心血管植入物 鎳鈦合金鎳離子釋放試驗方法
- 年產(chǎn)12000噸水合肼(100%)項目環(huán)評報告書
- 鉆芯法檢測混凝土抗壓強度原始記錄1
- 液壓支架與泵站(第二版)課件匯總?cè)珪娮咏贪竿暾嬲n件最全幻燈片(最新)
- 分布式光伏電站支架結構及荷載計算書
評論
0/150
提交評論