人樣狼草過(guò)河數(shù)學(xué)建模newVIP

1、課 程 設(shè) 計(jì) 報(bào) 告課程名稱：數(shù)學(xué)建模設(shè)計(jì)題目：人狼羊草過(guò)河問(wèn)題姓名學(xué)號(hào)：馬高松（200705030） 易文輝（200705050） 陳邦生（200705010）指導(dǎo)老師：李沐春完成時(shí)間：2010年5月8日問(wèn)題的提出在河的一岸，人、狼、羊、草、均要過(guò)河，船需人劃，而且最多載一物，當(dāng)人不在時(shí)，狼會(huì)吃羊，羊會(huì)吃草；試安排人狼羊草安全渡河。一 問(wèn)題的分析人帶著狼、羊和草，身處河的一岸。他要把這些東西全部運(yùn)到彼岸。問(wèn)題是他面前只有一條小船，船小到只能容下他和一件物品，另外船必須有人劃。而且，因?yàn)槔悄艹匝?，而羊?ài)吃草，所以人不能留下羊和草或者狼和羊單獨(dú)在河的一邊。以下是解決方案：整個(gè)過(guò)程中我們把該過(guò)程

2、分為兩種狀態(tài)A和B，在各狀態(tài)中，將人羊狼草用一個(gè)四維向量表示，A狀態(tài)表示人羊狼草在河的左右岸的狀態(tài)，當(dāng)一物在左岸時(shí)，用分量0表示，當(dāng)一物在右岸時(shí)，用分量1表示，例如狀態(tài)A1(1,1,0,1)表示人羊草在河的右岸，狼崽河左岸，根據(jù)題中的要求，有些狀態(tài)時(shí)允許的，有些狀態(tài)是不允許的，這就牽涉到該方案的安全性，于是我們規(guī)定由條件允許存在的狀態(tài)我們稱之為可取狀態(tài)，比如A1(0,1,0,1)是一個(gè)可取狀態(tài)，而A2(0,0,1,1)則是一個(gè)不可取狀態(tài)，因?yàn)樗硎狙虿菰诤拥挠野?，是不可取的；人然后是B狀態(tài)，B狀態(tài)表示用船渡河過(guò)程中表示船內(nèi)運(yùn)載的狀況，當(dāng)一物在船上時(shí)用1表示，不再船上則用0表示，當(dāng)滿足問(wèn)題條件的

3、運(yùn)載稱為可取運(yùn)載，當(dāng)不滿足條件的運(yùn)載則是不可取運(yùn)載，如B1（1，1，0，0）表示人狼崽船上，但它不是可取狀態(tài)，同樣B2（1，0，1，1）也不是可取狀態(tài)，應(yīng)為船不能載三物。我們可以通過(guò)窮舉法得到可取狀態(tài)向量： 人不在時(shí)： 三個(gè)全不在的 （1，1，1，1） 兩個(gè)不在的 （1，1，1，0）、（1，1，0，1）、（1，0，1，1） 一個(gè)不在的 （1，0，1，0） 人在時(shí)： 三個(gè)全在的 （0，0，0，0） 一個(gè)不在的 （0，0，0，1）、（0，0，1，0）、（0，1，0，0） 兩個(gè)不在的 （0，1，0，1）一共有10種狀態(tài)。建模 狀態(tài)轉(zhuǎn)移方程：原狀態(tài)運(yùn)載現(xiàn)狀態(tài) 一可取狀態(tài)向量可取運(yùn)載向量，稱之為過(guò)河。

4、其中運(yùn)算方式為“1+10，1+01，0+11，0+00”。二、模型 在規(guī)則“1+10，1+01，0+11，0+00”下，試求從最初可取狀態(tài)向量（0，0，0，0）經(jīng)過(guò)N步到最終狀態(tài)向量（1，1，1，1）的可取轉(zhuǎn)移方式。三 解法 1.窮舉法注：在得到的狀態(tài)后面的標(biāo)示符中，“！”表示該狀態(tài)不可取，“+”表示該狀態(tài)可取，“*”表示該狀態(tài)已經(jīng)出現(xiàn)過(guò)，為重復(fù)狀態(tài)。（1） （1，1，0，0） =（1,1,0,0） ! (0,0,0,0) + （1，0，1，0） =（1,0,1,0） +（1，0，0，1） =（1,0,0,1） !(1, 0, 0, 0) =（1,0,0,0） ! (2) (1 , 1 ,0

5、, 0 ) =(0,1,1,0) ! (1,0 ,1,0 ) + (1, 0, 1, 0 ） =(0,0,0,0) *(1, 0 , 0 , 1） =(0,0,1,1) ! (1 , 0 ,0 ,0 ) =(0,0,1,0) +(3) (1 , 1 ,0 , 0 ) =(1,1,1,0) + (0,0 ,1,0 ) + (1, 0, 1, 0 ） =(1,0,0,0) !(1, 0 , 0 , 1） =(1,0,1,1) + (1 , 0 ,0 ,0 ) =(1,0,1,0) *第三步中得到的結(jié)果有兩個(gè)可取狀態(tài)，故應(yīng)分別計(jì)算先?。?，1，1，0）計(jì)算： (4)1 (1 , 1 ,0 , 0 )

6、 =(0,0,1,0) * (1,1 ,1,0 ) +(1, 0, 1, 0 ） =(0,1,0,0) +(1, 0 , 0 , 1） =(0,1,1,1) ! (1 , 0 ,0 ,0 ) =(0,1,1,0) !(5)1 (1 , 1 ,0 , 0 ) =(1,0,0,0) ! (0,1,0,0 ) +(1, 0, 1, 0 ） =(1,1,1,0) *(1, 0 , 0 , 1） =(1,1,0,1) + (1 , 0 ,0 ,0 ) =(1,1,0,0) !(6)1 (1 , 1 ,0 , 0 ) =(0,0,0,1) * (1,1,0,1 ) + (1, 0, 1, 0 ） =(0,

7、1,1,1) !(1, 0 , 0 , 1） =(1,0,0,0) ! (1 , 0 ,0 ,0 ) =(0,1,0,1) +(7)1 (1 , 1 ,0 , 0 ) =(1,0,0,1 ) ! (0,1,0,1 ) + (1, 0, 1, 0 ） =(1,1,1,1) +(1, 0 , 0 , 1） =(1,1,0,0) ! (1 , 0 ,0 ,0 ) =(1,1,0,1) *?。?，0，1，1）計(jì)算：(4)2 (1 , 1 ,0 , 0 ) =(0,1,1,1) ! (1,0,1,1) + (1, 0, 1, 0 ） =(0,0,0,1) +(1, 0 , 0 , 1） =(0,0,1,

8、0) * (1 , 0 ,0 ,0 ) =(0,0,1,1) !(5)2 (1 , 1 ,0 , 0 ) =(1,1,0,1) + (0,0,0,1 ) + (1, 0, 1, 0 ） =(1,0,1,1) *(1, 0 , 0 , 1） =(1,0,0,0) ! (1 , 0 ,0 ,0 ) =(1,0,0,1) !得到的可取狀態(tài)和（5）1步驟一樣，故運(yùn)算（6）2、（7）2應(yīng)該和（6）1、（7）1一樣。所以總共可以通過(guò)七步運(yùn)算使得人、狼、羊、草安全過(guò)河。 2.圖解法四、算法實(shí)現(xiàn)1.問(wèn)題分析完成了上面的準(zhǔn)備工作，要模擬農(nóng)夫過(guò)河問(wèn)題，首先需要選擇一個(gè)對(duì)問(wèn)題中每個(gè)角色的位置進(jìn)行描述的方法。一個(gè)很方

9、便的辦法是用四位二進(jìn)制數(shù)順序分別表示人狼羊草的位置。例如用0表示人或者某物在河的南岸，1表示在河的北岸。因此整數(shù)3(其二進(jìn)制表示為0011) 表示人和狼在河的南岸，而羊和草在河的北岸?，F(xiàn)在的問(wèn)題變成：從初始狀態(tài)二進(jìn)制0000(全部在河的南岸) 出發(fā)，尋找一種全部由安全狀態(tài)構(gòu)成的狀態(tài)序列，它以二進(jìn)制1111(全部到達(dá)河的北岸) 為最終目標(biāo)，并且在序列中的每一個(gè)狀態(tài)都可以從前一狀態(tài)通過(guò)人（可以帶一樣?xùn)|西）劃船過(guò)河的動(dòng)作到達(dá)。2. 算法選擇求解這個(gè)問(wèn)題的最簡(jiǎn)單的方法是一步一步進(jìn)行試探，每一步都搜索所有可能的選擇，對(duì)前一步合適的選擇再考慮下一步的各種方案。用計(jì)算機(jī)實(shí)現(xiàn)上述求解的搜索過(guò)程可以采用兩種不同

10、的策略：一種是廣度優(yōu)先搜索，另一種是深度優(yōu)先搜索。深度優(yōu)先搜索就是在搜索樹(shù)的每一層始終先只擴(kuò)展一個(gè)子節(jié)點(diǎn)，不斷地向縱深前進(jìn)直到不能再前進(jìn)（到達(dá)葉子節(jié)點(diǎn)或受到嘗試限制）時(shí)，才從當(dāng)前節(jié)點(diǎn)返回到上一級(jí)節(jié)點(diǎn)，沿另一方向又繼續(xù)前進(jìn)。這種方法的搜索是從樹(shù)根開(kāi)始一枝一枝逐漸形成的。深度優(yōu)先搜索亦稱為縱向搜索。由于一個(gè)有解的問(wèn)題樹(shù)可能含有無(wú)窮分枝，深度優(yōu)先搜索如果誤入無(wú)窮分枝（即深度無(wú)限），則不可能找到目標(biāo)節(jié)點(diǎn)。所以，深度優(yōu)先搜索策略是不完備的。另外，應(yīng)用此策略得到 的解不一定是最佳解（最短路徑）。深度優(yōu)先搜索算法中，是深度越大的結(jié)點(diǎn)越先得到擴(kuò)展。如果在搜索中把算法改為按結(jié)點(diǎn)的層次進(jìn)行搜索，本層的結(jié)點(diǎn)沒(méi)有搜索

11、處理完時(shí)，不能對(duì)下層結(jié)點(diǎn)進(jìn)行處理，即深度越小的結(jié)點(diǎn)越先得到擴(kuò)展，也就是說(shuō)先產(chǎn)生的結(jié)點(diǎn)先得以擴(kuò)展處理，這種搜索算法稱為廣度優(yōu)先搜索法。 廣度優(yōu)先的含義就是在搜索過(guò)程中總是首先搜索下面一步的所有可能狀態(tài)，然后再進(jìn)一步考慮更后面的各種情況。要實(shí)現(xiàn)廣度優(yōu)先搜索，一般都采用隊(duì)列作為輔助結(jié)構(gòu)。把下一步所有可能達(dá)到的狀態(tài)都列舉出來(lái)，放在這個(gè)隊(duì)列中，然后順序取出來(lái)分別進(jìn)行處理，處理過(guò)程中把再下一步的狀態(tài)放在隊(duì)列里。 由于隊(duì)列的操作遵循先進(jìn)先出的原則，在這個(gè)處理過(guò)程中，只有在前一步的所有情況都處理完后，才能開(kāi)始后面一步各情況的處理。 五、程序代碼#include<iostream>usin

12、g namespace std;int man(int n)return (0!=(n & 8);/ 判斷農(nóng)夫在不在，如果返回1，則表示農(nóng)夫在。int wolf(int n)return (0!=(n & 4);int sheep(int n)return (0!=(n & 2);int grass(int n)return (0!=(n & 1);/安全檢驗(yàn)int isSafe(int n)if(sheep(n)=grass(n) && sheep(n)!=man(n) return 0;if(sheep(n)=wolf(n) &&am

13、p; wolf(n)!=man(n) return 0;return 1;/1表示安全，0表示不安全/過(guò)河，使用廣度優(yōu)深算法遍歷 int crossRiver(int result)int Status,nextStatus,choice=8,9,10,12;/農(nóng)夫從某一狀態(tài)出發(fā)，有4種走法 int queue16,front,rear;/定義循環(huán)隊(duì)列 int i,j,visited16;/visitedi=0表示i未訪問(wèn)過(guò) int route16;/routei表示第i步的前一步，意即往第i步走的方式rear=front=0;/隊(duì)列初始化 for(i=0;i<16;i+)routei=

14、-1;visitedi=0;Status=0;nextStatus=-1; /從狀態(tài)0（全部在南岸）開(kāi)始 queuerear=Status; rear=(rear+1)%16;/入隊(duì)while(front!=rear)Status=queuefront;front=(front+1)%16;/出隊(duì)visitedStatus=1; /訪問(wèn) for(j=0;j<4;j+)nextStatus=Statuschoicej; /從curStatus狀態(tài)到下一狀態(tài)nextStatus if(visitednextStatus=0 && isSafe(nextStatus)queue

15、rear=nextStatus; rear=(rear+1)%16;/入隊(duì)routenextStatus=Status;/僅表示從Sattus可以走到nextStatus /如route10=0,意即從0000有路可走到1010/處理路徑表:從路徑表中反推（從最終步->開(kāi)始步） i=15;/最后一步 if(routei=-1) /若沒(méi)有方法可以走到1111，則任務(wù)失敗。 cout<<"過(guò)河失敗!"<<endl;return 0;for(j=15;routei!=-1 && i>=0;j-) /routei!=-1相當(dāng)于那一

16、步走不通，那就不用選取了resultj=i;i=routei; resultj=i; /第一步 return 1; int main()int i,j,result16; /存結(jié)果序列 /16種狀態(tài)（0000->1111）對(duì)應(yīng)的文字提示 char name1620="人狼羊草tt空", "人狼羊ttt草", "人狼草ttt羊", "人狼ttt羊草", "人羊草ttt狼", "人羊ttt狼草", "人草ttt狼羊", "人ttt狼羊草&quo

17、t;, "狼羊草tt人", "狼羊ttt人草", "狼草ttt人羊", "狼ttt人羊草", "羊草ttt人狼", "羊ttt人狼草", "草ttt人狼羊", "空ttt人狼羊草" for(i=0;i<16;i+)resulti=-1;/初始化結(jié)果序列 if(crossRiver(result)=0) return 0;/輸出結(jié)果 cout<<"步驟t南岸ttt北岸"<<endl; cout<<"-"<<endl;for(i=0,j=0;j<16;j+)if(resultj>=0) cout<<"第"<<i<<