人貓雞米渡河問題地數(shù)學模型

1、人貓雞米渡河問題的數(shù)學模型摘要：人帶著貓、雞、米過河，從左岸到右岸，船除了需要人劃之外(船除了要載 人外)，只能載貓、雞、米三者之一，而當人不在場時貓要吃雞、雞要吃米。本文將設計 一個安全過河方案，使渡河次數(shù)盡量地少。模仿“商人過河”的模型設計出新的數(shù)學模型關(guān)鍵字：窮舉法，Matlab運算求解。、問題的提出課本P19.T5:模仿“商人過河”模型，做下面游戲：人帶著貓、雞、米過河，船除需 要人劃之外，至多能載貓、雞、米三者之一，而當人不在場時貓要吃雞、雞要吃米。設計 一個過河方案，建立數(shù)學模型，并使渡河次數(shù)盡量地少。、問題的分析因為這是個簡單問題，研究對象少，所以可以用窮舉法，簡單運算即可解題。

2、此問題是從狀態(tài)向量A (1,1,1,1 )經(jīng)過奇數(shù)次運算向量B變?yōu)闋顟B(tài)向量A (0,0,0,0 ) 的狀態(tài)。轉(zhuǎn)移過程為什么是奇數(shù)次？我們注意到過河有兩種，奇數(shù)次的為從左岸到右岸， 而偶數(shù)的為右岸回到左岸，因此得到下述轉(zhuǎn)移過程，所以最后應該是過河完成時狀態(tài)轉(zhuǎn)移 數(shù)為奇數(shù)次。三、問題的假設:假設船除了載人之外，至多只能載貓、雞、米三者之一。:當人不在場時，貓一定會吃雞、雞一定會吃米。四、定義符號說明：我們將人，貓，雞，米依次用四維向量中的分量表示，當一物在左岸時，相應的分量 記為1,在右岸時記為0.如向量（1,0,1,0 ）表示人和雞在左岸，貓和米在右岸，并將這 些向量稱為狀態(tài)向量。例如（1,1,

3、1,1 ）表示它們都在左岸，（0,1,1,0 ）表示貓，雞在左 岸，人，米在右岸；由于問題中的限制條件，有些狀態(tài)是允許的，有些狀態(tài)是不允許的。凡問題可以允許存在的狀態(tài)稱為可取狀態(tài)。A向量定義為狀態(tài)變量。比如A（1,0,1,0 ）是-個可取狀態(tài)向量，但A2（0,0,1,1）是一個不可取狀態(tài)向量。止匕外，B向量定義為運載變量。 把每運載一次也用一個四維向量來表示。如 耳（1,1,0,0 ）表示人和貓在船上，而雞和米不在 船上，這自然是可取的運載，因為船可載兩物，而B2（1,0,1,1）則是不可取運載，依此規(guī)律類推。五、模型的建立對于這個問題我們用窮舉的方法來解決，首先將此問題化為狀態(tài)轉(zhuǎn)移問題來解決

4、。對本問題來說：可取狀態(tài)向量A共有10個，可以用窮舉法列出來：1,1,1,10,0,0,01,1,1,00,0,0,11,1,0,10,0,1,01,0,1,10,1,0,01,0,1,00,1,0,1右邊5個正好是左邊5個的相反狀態(tài)?？扇∵\載B共有4個:1,1,0,01,0,1,01,0,0,11,0,0,0可取運算：規(guī)定 A與B相加時對每一分量按 二進制法則（異或運算）進行 0 0 =0,1 - 0 = 0-1= 1,1 1=。這樣，一次渡河就是一個可取狀態(tài)向量與一 個可取運載向量相加，可取狀態(tài)經(jīng)過加法運算仍是一個可取狀態(tài)，這種運算稱 為可取運算。在上述規(guī)定下，問題轉(zhuǎn)化為：從初始狀態(tài)（1,

5、1,1,1）至少經(jīng)過多少次（奇數(shù)次）可取運算才能轉(zhuǎn)化為狀態(tài)（0,0,0,0 ）。六、模型的求解如果一個狀態(tài)是可取的就打 V,否則就打X ,雖然可取但已重復就打A,于是問題可 用窮舉法解答如下：1)(1,1,1,11+71,0,1,0) (1,1,0,0) (1,0,0,1) J1,0,0,0)01,0,1 W 0,1,1 產(chǎn) (0,1,1,0 戶 (0,1,1。(2)0,1,0,1口,0,1,0) (1,1,0,0) (1,0,0,1) (1,0,0,0)(1,1,1,11 八 (1,0,1,1)父 (1,1,0,0戶 (1,1,0,1)v(1,0,1,0)(0,1,1,1 二(3)(1,1,

6、0,1)+1,1,0,01,0,0,1(0,0,0,1 - (0,1,0,0)v(4)0,0,0,0)“1,0,121 0,0,0,1,1,0,1,0)(1,0,0,1)(1,0,0,。戶(4)0,1,0,01,1,0,01,0,0,1(5)(6)1(1,0,0,0 )1(1,0,0,1 產(chǎn)(0.0;0:l)A(1,1,0,0)卜 T(070,1,0)v(001、(5)4,0,1,0)(0,0,1,0 )+1,1,0,01,0,0,1(1,0,0,0 )(1,0,0,0 尸(1,1,1,0)八(1,0,1,1)八(1,0,1,0W0,1,1,0)v (1,0,0,0y ,1,0,1)八。,1,

7、0,0(1.0. L0)(MQ0 4(1A0.11QLLDx#(1.0.0.011(1,0,0,0)(1,0,1,0),、1,1,0,0)1,0,1,0(1,0,0,1)(1,0,0,0)0,0,0,0 戶嚴,1,1,0產(chǎn)(0,0,1,1尸 0,0,1,0)八第7步已經(jīng)出現(xiàn)了（0,0,0,0）狀態(tài)，說明經(jīng)7次運載即可，其過程為：去回去回去回去t （人，雞（人”（人貓（或米）H （人，雞A （人，米（或貓）h （人”（人，雞） 因此，該問題的最優(yōu)方案有2種：1、人先帶雞過河，然后人再回來，把米帶過河，然后把雞運回河岸，人再把貓帶過河，最后人回來把雞帶過去。2、人先帶雞過河，然后人再回來，把貓帶過

8、河，然后把雞運回河岸，人再把米帶過河,最后人回來把雞帶過去。七、模型的評價優(yōu)點：本算法將研究對象用四維向量中的分量用 0,1表示，運用窮舉法找出所有可取狀態(tài)向 量再用一些基礎可取運算方法將結(jié)果列出來再以圖形表示出來。模型簡單，切合實際，易 于理解，整個過程易懂合理。缺點：由于問題的求解沒有使用LINGQ LINDO或MATLA歐件，當狀態(tài)和決策過多時，采用 上述方法求解顯得繁瑣，容易出錯，所以下面給出此問題的matlab求解過程。7. 3、推廣：正如課本上的商人們安全過河問題，當商人和隨從人數(shù)增加或小船的容量加大時，靠 邏輯思考就有些困難了，而適當?shù)卦O置狀態(tài)和決策，確定狀態(tài)轉(zhuǎn)移率，建立多步?jīng)Q策

9、模型, 仍可方便有效地求解此類型問題。八、mathlab求解過程模型假設與建立：由上可知，可取狀態(tài)向量 A共有10個，即：1,1,1,10,0,0,01,1,1,00,0,0,11,1,0,10,0,1,01,0,1,10,1,0,01,0,1,00,1,0,1可取運載B有4個：(1,1,0,0 )、(1,0,1,0 )、(1,0,0,1 )、(1,0,0,0 )。算法設計：規(guī)定A和B的每一分量相加時按二進制法則進行，這樣一次渡河就是一個可取狀態(tài)和一個可取運載相加，在判斷和向量是否屬于可取狀態(tài)即可?？梢詫⒖扇顟B(tài)及可取運載分別編成矩陣。共分為五個m文件，一個主文件xduhe.m數(shù)，四個子文件分

10、別為：duhe (L,B,M,s )函數(shù)：用來實現(xiàn)渡河總思路。思路為：將起始矩陣A分別與可取運載相加(使用二進制法則)，判斷相加后的矩陣 C是否是(0, 0, 0, 0),如果是，則渡河成 功。否則，用fuhe(C,M)函數(shù)判斷C是否是可取狀態(tài)，如果是，則打印并將C與初始矩陣合并成新矩陣，繼續(xù)調(diào)用 duhe.m函數(shù)。fuhe(C,M)函數(shù)：判斷和矩陣C是否屬于矩陣M如果是，則返回1,否則返回0.Panduan(S)函數(shù)：判斷S矩陣中是否有兩個相同的狀態(tài)，即行向量。如果有，則返回 0,否則返 回1.print(K,C,s)函數(shù)：打印相應的狀態(tài)。程序代碼：xduhe.m 文件：clear;clc;

11、A=1,1,1,1；B=1,0,1,0;1,1,0,0;1,0,0,1;1,0,0,0;M=1,1,1,0;0,0,0,1;1,1,0,1;0,0,1,0;1,0,1,1;0,1,0,0;1,0,1,0;0,1,0,1;duhe(A,B,M,1);duhe.m文件：function duhe(L,B,M,s);h,l=size(L);for k=s:hfor i=1:4C=mod(L(k,:)+B(i,:),2); if C=0,0,0,0print(B(i,:),C,s);fprintf(渡河成功 nn);break;else if fuhe(C,M)=1print(B(i,:),C,s);

12、S=L;C;if Panduan(S)=1duhe(S,B,M,s+1)；elsefprintf(此渡河方案不可行nn);endendendendendfuhe.m 文件：function y=fuhe(C,M)y=0;for i=1:8if(C=M(i,:)y=1;break;endendPanduan.m文件:function z=Panduan(S) z=1;m,n=size(S);for p=1:mfor q=(p+1):mif S(p,:)-S(q,:)=0,0,0,0z=0;break;endendendprint.m 文件:function print(K,C,s)fprintf

13、(第故渡河:,s);if K(1)=1fprintf( 人，)；文案大全endif K(2)=1 fprintf( 貓，)；endif K(3)=1 fprintf( 雞,);endif K(4)=1 fprintf( 米，)；endif C(1)=0fprintf(從左岸到達右岸n);elsefprintf（ 從右岸回到左岸n）;end模型結(jié)論在matlab中運行，結(jié)果如下:第1次渡河:人，雞，從左岸到達右岸 第2次渡河二人，從右岸回到左岸第3次渡河二人，貓，從左岸到達右岸 第4次渡河1人，雞，從右岸回到左岸 第5次渡河:人，鴻，從左岸到達右岸 此渡河方案不可行第5次渡河二人，米，從左岸到達

14、右岸 第6次渡河二人，貓，從右岸回到左岸 第7次渡河二人，雞,從左岸到達右岸 第8次渡河:人，雞,從右岸回到左岸 此渡河方案不可行第8次渡河:人，米，從右岸回到左岸 此渡河方案不可行第T次渡河:人，貓，從左岸到達右岸 此渡河方案不可行第6次渡河二人，米，從右岸回到左岸 此渡河方案不可行第6次渡河:人，從右岸回到左岸第T次渡河:人，雞，從左岸到達右岸 渡河成功第4次渡河二人，貓，從右岸回到左岸 此渡河方案不可行第3次渡河:人，米，從左岸到達右岸 ,第4次渡河:人，雞，從右岸回到左岸 W第5次渡河二人，雞，從左岸到達右岸此渡河方案不可行第5次渡河工人，貓，從左岸到達右岸 第6次渡河:人，貓，從右岸

15、回到左岸 此渡河方案不可行第6次渡河:人,米,從右岸回到左岸 第T次渡河:人，鴻，從左岸到達右岸 第次渡河:人，雞,從右岸回到左岸 此渡河方案不可行第8次渡河:人,貓，從右岸回到左岸 此渡河方案不可行第7次渡河:人，米，從左岸到達右岸 此渡河方案不可行第6次渡河:人從右岸回到左岸第7次渡河工人雞，從左岸到達右岸 渡河成功 第4次渡河:人，米,從右岸回到左岸 此渡河方案不可行 第3次渡河:人，從左岸到達右岸 此渡河方案不可行從運行結(jié)果可以看出，共有兩種運送方案:人先帶雞過河，然后人再回來，把米帶過河，然后把雞運回河岸，人再把貓帶過河，最后人回來把雞帶過去。人先帶雞過河，然后人再回來，把貓帶過河，

16、然后把雞運回河岸，人再把米帶過河，最后人回來把雞帶過去。收獲與不足：復習和加深了對matlab的學習，見識了 MATLA7.10.0(R2010a)的厲害，引發(fā)了我對 數(shù)學建模的強大興趣。而且，利用 MATLA加以非常容易而且很直觀地得出問題的解決方 案，從而在不斷深化對問題認識的同時，把問題普遍化。但是這個問題的求解過程是請教 了師姐才得以完成的。九、“商人過河”的算法步驟和 matlab求解過程另外，由于本次數(shù)學建模的啟發(fā)，我們組根據(jù)老師上課講的“商人過河”的算法步驟, 用matlab編程出程序，求解過程如下：模型建立:此問題可視為一個 多步?jīng)Q策多步?jīng)Q策：決策過程難以一次完成，而要分步優(yōu)化

17、，最后獲取一個全局最優(yōu)方案的決 策方法稱為多步?jīng)Q策。問題：每一步就是一次渡河，每次渡河就是一次狀態(tài)轉(zhuǎn)移。用三維變量(XJZ)表示狀態(tài)：工的取值范圍：0, 1, 2, 3;了的取值范圍：0,1, 2, 3;2的取值范圍：0,1?？杀硇椋汉?0,3x = 1,2工 冏人數(shù)J-隨從數(shù) 船那么安全狀態(tài)(可取向量)安全狀態(tài)=安全狀態(tài)：商人們安全是指在兩岸都安全，故當 x=0,3時，y=0,1,2,3 ,而當x=1,2 時，此岸要求xy,對岸要求3-x 3-y,綜合即x=y;安全狀態(tài)：商人們安全是指在兩岸都安全，故當x=0,3 時，y=0,1,2,3 ,而當 x=1,2時，此岸要求xy,對岸要求3-x 3-y,綜合即x=y;(3,2,1)(3,1,1)(2,2,1)(3,0,1)(0,3,1)(0,2,1)(1,1,1)(0,1,1)(3,2,0)(3,1,0)(2,2,0)(3,0,0)(0,3,0)(0,2,0)(1,1,0)(0,1,0)(0,0,0)這就是此問題的數(shù)學模型。模型求解:這樣問題要求由(3, 3, 1)變到(0, 0, 0)的一條道路。根據(jù)題意，狀態(tài)轉(zhuǎn)移時要滿足一定的規(guī)則：.