




版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)
文檔簡介
§12.常見的數(shù)學(xué)建模方法(7)----狀態(tài)轉(zhuǎn)移法
處理問題的類型:狀態(tài)轉(zhuǎn)移問題,屬離散性模型問題.問題的內(nèi)容:討論在一定的條件下,系統(tǒng)由一個狀態(tài)轉(zhuǎn)移到另一個狀態(tài)是否可能,如果可能的話,應(yīng)該如何具體實現(xiàn)?;痉椒皵?shù)學(xué)技巧:
用向量來模擬狀態(tài).將狀態(tài)的演變描述成向量的運算,以便于計算機(jī)程序處理.問題1.人、狗、雞、米過河問題某人要帶人、狗、雞、米用渡船過河,但渡船需要人劃外,最多只能載一物過河,而且當(dāng)人不在場時,狗要咬雞,雞要吃米.問此人應(yīng)如何安全渡河?求解.把此問題視為一個狀態(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),為此引進(jìn)一個四維的狀態(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),利用計算機(jī)編程處理,例如,可以用Math軟件編程求解這個擺渡操作方案,即求出n和d1,d2,d3,……,dn各是多少.具體的結(jié)果為:(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軟件編程求解.具體的結(jié)果為(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)移法來求解問題的過程和
思考方法.習(xí)題.在與問題2同樣的假定下,試求解四對商人過河問題。如果渡船最多可載3人,試求解五對商人和六對商人過河問題。如果渡船最多可載4人,試求解任意對商人過河問題。
(2)
對于任一個W狀態(tài),總存在著某一個取石操作,使它變成一個L狀態(tài).假定一個W狀態(tài)為:{n1,n2,n3}(N≠0).記與三個十進(jìn)制數(shù)n1,n2,n3相對應(yīng)的二進(jìn)制數(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)).無妨設(shè)第i)種情況成立.這說明,二進(jìn)制數(shù)(a1a2……an)所對應(yīng)的十進(jìn)制數(shù)n1與二進(jìn)制數(shù)((b1+c1)(b2+c2)……(bn+cn))所對應(yīng)的十進(jìn)制數(shù)n’
有關(guān)系:n1>n’.由此,只須在第一堆中取走(n1-n’)顆石子,W狀態(tài){n1,n2,n3}變化而成一個新狀態(tài){n’
,n2,n3},這個狀態(tài)的狀態(tài)指標(biāo)數(shù)
N’=0.這說明:對于任一個W狀態(tài),總存在著某一個取石操作,使它變成一個L狀態(tài).制定取勝策略:選取某堆,從中取走適量石子,使這三堆構(gòu)成
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)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 2024年圖書管理員考試知識共享平臺試題及答案
- 投資咨詢工程師投資成功與失敗案例分析試題及答案
- 2024專升本語言技巧的實踐運用試題及答案
- 投資咨詢行業(yè)的專業(yè)試題及答案研究
- 黑龍江省雙鴨山市第三十一中學(xué)2025屆高三5月統(tǒng)一檢測試題歷史試題試卷含解析
- 黑龍江省哈爾濱市尚志市2025年初三第二學(xué)期開學(xué)質(zhì)量檢測試題化學(xué)試題試卷含解析
- 黑龍江省牡丹江市穆棱市2024-2025學(xué)年數(shù)學(xué)三下期末教學(xué)質(zhì)量檢測模擬試題含解析
- 黑龍江省鶴崗三中2024-2025學(xué)年高三下學(xué)期第四次質(zhì)量檢測試題語文試題含解析
- 黑龍江省齊齊哈爾市2025年四年級數(shù)學(xué)第二學(xué)期期末教學(xué)質(zhì)量檢測模擬試題含解析
- 黑龍江科技大學(xué)《法律論辯訓(xùn)練》2023-2024學(xué)年第二學(xué)期期末試卷
- 學(xué)校膳食管理委員會組織及工作職責(zé)
- 廣西壯族自治區(qū)工程造價綜合定額答疑匯編2022年11月更新
- 中國教育學(xué)會教育科研規(guī)劃課題結(jié)題報告格式(參考)doc
- 機(jī)動車駕駛員培訓(xùn)機(jī)構(gòu)質(zhì)量信譽(yù)考核評分表doc-附件1
- (完整word)蘇教八年級初二下冊英語單詞默寫表
- 城市規(guī)劃原理課件(完整版)
- 民法案例分析教程(第五版)完整版課件全套ppt教學(xué)教程最全電子教案
- DBJ03-107-2019 房屋建筑和市政工程施工危險性較大的分部分項工程安全管理規(guī)范
- 國家電網(wǎng)有限公司十八項電網(wǎng)重大反事故措施(修訂版)
- 夜景照明工程驗收標(biāo)準(zhǔn)
- 家長類型分析及溝通技巧
評論
0/150
提交評論