4名商人帶4名隨從安全過河

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

2、化范圍內(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ù)dk=(uk, vk)決策，D=(u , v)| 1=<u+v=<2,uk, vk=0,1,2 允許決策集合 k=1,2, 因?yàn)閗為奇數(shù)時(shí)船從此岸駛向此岸，k為偶數(shù)時(shí)船從此岸駛向此岸，所以狀態(tài)S

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

4、只能到達(dá)此點(diǎn)后不能繼續(xù)走下去，只能循環(huán)走(由d7狀態(tài)無法不重復(fù)循環(huán)地走下去)，達(dá)不到最終的目標(biāo)(0,0)，因此該問題無解。2.窮舉法：根據(jù)分析可以通過編程上機(jī)求解，所用的c程序如下所示：#include <stdio.h>#define 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)/*計(jì)算下一狀態(tài)*/if(k%2) /* k+1 為偶數(shù)，船從此岸到此岸 */xk+1=xk-ui;yk+1=yk-v

5、i;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; /* 此時(shí)狀態(tài)不屬于允許集 */elsefor(j=k-1;j>0;j-=2) /* 是否重復(fù)與船在河的哪一岸有關(guān) */if(p=xj

6、 && q=yj )ok=0; /* 此時(shí)狀態(tài)出現(xiàn)重復(fù) */break;if(j<=0)ok=1; /* 此時(shí)狀態(tài)屬于允許集，且不重復(fù) */return ok;void main()int i,j,mN,flag=1;/* m:采用的決策序號(hào)，flag:回溯標(biāo)記 */u1=2; v1=0; /* 給決策編號(hào)并賦值 */u2=0; v2=2;u3=1; v3=0;u4=0; v4=1;u5=1; v5=1;k=1; /* 從初始狀態(tài)出發(fā) */printf("請(qǐng)輸入商人和隨從的初始狀態(tài):n商人數(shù)=");scanf("%d",&x

7、k);printf("隨從數(shù)=");scanf("%d",&yk);while(flag)for(i=1;i<6;i+) /* 遍歷各種決策 */next(k,i); /* 計(jì)算下一狀態(tài) */if(allow(xk+1,yk+1) /* 假設(shè)新狀態(tài)允許且不重復(fù) */ mk=i; /* 記錄采用的決策序號(hào) */if(xk+1=0 && yk+1=0) /* 假設(shè)到達(dá)目標(biāo)狀態(tài),輸出結(jié)果 */ printf("初始值:商人%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)遍歷時(shí) */if(k=1)printf("此題無解!n");flag=0;break;else /* 未到達(dá)初始狀態(tài) */k-; /* 回溯