4名商人帶4名隨從安全過河(20220215232607)

1、4 名商人帶 4 名隨從平安過河一問題提出：4 名商人帶 4 名隨從乘一條小船過河，小船每次自能承載至多兩人。 隨從們密約 , 在河的任一岸 , 一旦隨從的人數(shù)比商人多 , 就殺人越貨 . 乘船渡河的方案由商人決定，商人們?nèi)绾尾拍芷桨捕珊幽?？二模型假設(shè)：商人和隨從都會劃船。三問題分析：商隨過河問題可以視為一個多步?jīng)Q策過程，通過屢次優(yōu)化，最后獲 取一個全局最優(yōu)的決策方案。 對于每一步，即船由此岸駛向此岸或由此 岸駛向此岸， 都要對船上的人員作出決策，在保證兩岸的商人數(shù)不少于 隨從數(shù)的前提下， 在有限步內(nèi)使全部人員過河。用狀態(tài)變量表示某一岸 的人員狀況， 決策變量表示船上的人員狀況， 可以找出狀態(tài)

2、隨決策變化 的規(guī)律，問題轉(zhuǎn)化為在狀態(tài)的允許變化范圍內(nèi) ( 即平安渡河條件 )，確定 每一步的決策，到達(dá)平安渡河的目標(biāo)。四模型構(gòu)成：xk第k次渡河前此岸的商人數(shù)，yk-第k次渡河前此岸的隨從數(shù)xk, yk=0,1,2,3,4; k=1,2,Sk=(xk, yk) 過程的狀態(tài) ,S允許狀態(tài)集合，S=(x,y)|x=0, y=0,1,2,3,4;x=4 ,y=0,1,2,3,4;x=y=1,2,3 uk第k次渡船上的商人數(shù)vk第k次渡船上的隨從數(shù)學(xué)習(xí)文檔 僅供參考dk=(uk, vk) 決策，D=(u , v)| 仁<u+v=<2,uk, vk=0,1,2 允許 決策集合k=1,2,因為

3、k為奇數(shù)時船從此岸駛向此岸，k為偶數(shù)時船從此岸駛向此岸， 所以狀態(tài)Sk隨決策dk的變化規(guī)律是Sk 1=Sk+(-1) kdk狀態(tài)轉(zhuǎn)移律求dk D(k=1,2,n),使Sk S,并按轉(zhuǎn)移律由S仁(4,4)到達(dá)狀 態(tài) Sn 1=(0,0)。五.模型求解：1.圖解法：對于人數(shù)不多的情況，可以利用圖解法來求解。在xoy平面坐標(biāo)系上畫出如下列圖的方格，方格點表示狀態(tài)s=(x,y),允許狀態(tài)集合S是圓點標(biāo)出的13個格子點，允許決策dk是沿方格線移 動1格或2格，k為奇數(shù)時向左、下方移動，k為偶數(shù)時向右、上方移 動。要確定一系列的 dk使由S仁(4,4)經(jīng)過那些圓點最終移動到原點 (0,0)。由初始狀態(tài)(4

4、,4)到原點(0,0)，無論怎樣走，都要經(jīng)過(2,2)，但是 無論怎樣變化人數(shù)，也只能到達(dá)此點后不能繼續(xù)走下去， 只能循環(huán)走(由 d7狀態(tài)無法不重復(fù)循環(huán)地走下去)，達(dá)不到最終的目標(biāo)(0,0),因此該問 題無解。2.窮舉法：根據(jù)分析可以通過編程上機(jī)求解，所用的 c程序如下所示：#i nclude <stdio.h>#defi ne N 30int xN,yN,u6,v6,k;/* x,y :狀態(tài)值，分別表示此岸商人、隨從數(shù)*/*u,v :決策值，分別表示船上商人、隨從數(shù)*/* k :決策步數(shù)；k的奇偶性標(biāo)志著船在河的此岸或此岸*/next(int k,int i)/*計算下一狀態(tài) *

5、/if(k%2)/* k+1為偶數(shù)，船從此岸到此岸*/xk+1=xk-ui;yk+1=yk-vi;else /* k+1 為奇數(shù)，船從此岸到此岸 */xk+1=xk+ui;yk+1=yk+vi;return;allow(int p,int q)/* 判定狀態(tài)是否允許 , 是否重復(fù) */int ok,j; /* ok:標(biāo)記狀態(tài)是否允許 , 是否重復(fù)； j: 循環(huán)變量 */if(p<0|p>x1|p!=0&&q>p|(x1-p)!=0&&(y1-q)>(x1-p)|q<0|q>y1) ok=0; /* 此時狀態(tài)不屬于允許集 */e

6、lsefor(j=k-1;j>0;j-=2) /* 是否重復(fù)與船在河的哪一岸有關(guān) */if(p=xj && q=yj )ok=0; /* 此時狀態(tài)出現(xiàn)重復(fù) */break;if(j<=0)ok=1; /* 此時狀態(tài)屬于允許集，且不重復(fù) */return ok;void main()int i,j,mN,flag=1;/* m:采用的決策序號， flag: 回溯標(biāo)記 */u1=2; v1=0; /* 給決策編號并賦值 */u2=0; v2=2;u3=1; v3=0;u4=0; v4=1;u5=1; v5=1;k=1; /* 從初始狀態(tài)出發(fā) */printf("

7、; 請輸入商人和隨從的初始狀態(tài) :n 商人數(shù) ="); scanf("%d",&xk);printf(" 隨從數(shù) =");scanf("%d",&yk);while(flag)for(i=1;i<6;i+) /* 遍歷各種決策 */next(k,i); /*計算下一狀態(tài) */if(allow(xk+1,yk+1) /* 假設(shè)新狀態(tài)允許且不重復(fù) */ mk=i; /* 記錄采用的決策序號 */if(xk+1=0 &&yk+1=0) /* 假設(shè)到達(dá)目標(biāo)狀態(tài) , 輸出結(jié)果 */ printf(

8、" 初始值:商人 d隨從 dn",x1,y1);for(j=1;j<=k;j+)printf(" 第 %2d 次 %d %dn",j,xj+1,yj+1); flag=0;break;else /*假設(shè)未到達(dá)目標(biāo)狀態(tài) */k+; /*生成下一步的步數(shù)值 */break; /* 遍歷終止，進(jìn)入下一步 */else /* 假設(shè)新狀態(tài)不允許或重復(fù) */while(i=5) /* 本步?jīng)Q策已經(jīng)遍歷時 */if(k=1)printf(" 此題無解 !n");flag=0;break;else /*未到達(dá)初始狀態(tài)*/k-; /*回溯一一退回1步，尋找新路徑*/i=mk;ifflagcontin ue; /*本步?jīng)Q策尚