人樣狼草過河數(shù)學建模new

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

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

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

4、其中運算方式為“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)過N步到最終狀態(tài)向量（1，1，1，1）的可取轉(zhuǎn)移方式。三 解法 1.窮舉法注：在得到的狀態(tài)后面的標示符中，“！”表示該狀態(tài)不可取，“+”表示該狀態(tài)可取，“*”表示該狀態(tài)已經(jīng)出現(xiàn)過，為重復狀態(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é)果有兩個可取狀態(tài)，故應分別計算先?。?，1，1，0）計算： (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）計算：(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步驟一樣，故運算（6）2、（7）2應該和（6）1、（7）1一樣。所以總共可以通過七步運算使得人、狼、羊、草安全過河。 2.圖解法四、算法實現(xiàn)1.問題分析完成了上面的準備工作，要模擬農(nóng)夫過河問題，首先需要選擇一個對問題中每個角色的位置進行描述的方法。一個很方

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

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

11、處理完時，不能對下層結(jié)點進行處理，即深度越小的結(jié)點越先得到擴展，也就是說先產(chǎn)生的結(jié)點先得以擴展處理，這種搜索算法稱為廣度優(yōu)先搜索法。 廣度優(yōu)先的含義就是在搜索過程中總是首先搜索下面一步的所有可能狀態(tài)，然后再進一步考慮更后面的各種情況。要實現(xiàn)廣度優(yōu)先搜索，一般都采用隊列作為輔助結(jié)構。把下一步所有可能達到的狀態(tài)都列舉出來，放在這個隊列中，然后順序取出來分別進行處理，處理過程中把再下一步的狀態(tà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);/安全檢驗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表示不安全/過河，使用廣度優(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)隊列 int i,j,visited16;/visitedi=0表示i未訪問過 int route16;/routei表示第i步的前一步，意即往第i步走的方式rear=front=0;/隊列初始化 for(i=0;i<16;i+)routei=

14、-1;visitedi=0;Status=0;nextStatus=-1; /從狀態(tài)0（全部在南岸）開始 queuerear=Status; rear=(rear+1)%16;/入隊while(front!=rear)Status=queuefront;front=(front+1)%16;/出隊visitedStatus=1; /訪問 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;/入隊routenextStatus=Status;/僅表示從Sattus可以走到nextStatus /如route10=0,意即從0000有路可走到1010/處理路徑表:從路徑表中反推（從最終步->開始步） i=15;/最后一步 if(routei=-1) /若沒有方法可以走到1111，則任務失敗。 cout<<"過河失敗!"<<endl;return 0;for(j=15;routei!=-1 && i>=0;j-) /routei!=-1相當于那一

16、步走不通，那就不用選取了resultj=i;i=routei; resultj=i; /第一步 return 1; int main()int i,j,result16; /存結(jié)果序列 /16種狀態(tài)（0000->1111）對應的文字提示 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<<