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

4名商人帶4名隨從安全過(guò)河4名商人帶4名隨從安全過(guò)河4名商人帶4名隨從安全過(guò)河資料僅供參考文件編號(hào)：2022年4月4名商人帶4名隨從安全過(guò)河版本號(hào)：A修改號(hào)：1頁(yè)次：1.0審核：批準(zhǔn):發(fā)布日期：4名商人帶4名隨從安全過(guò)河一．問(wèn)題提出：4名商人帶4名隨從乘一條小船過(guò)河，小船每次自能承載至多兩人。隨從們密約,在河的任一岸,一旦隨從的人數(shù)比商人多,就殺人越貨.乘船渡河的方案由商人決定，商人們?nèi)绾尾拍馨踩珊幽兀慷Ｐ图僭O(shè)：商人和隨從都會(huì)劃船。三．問(wèn)題分析：商隨過(guò)河問(wèn)題可以視為一個(gè)多步?jīng)Q策過(guò)程，通過(guò)多次優(yōu)化，最后獲取一個(gè)全局最優(yōu)的決策方案。對(duì)于每一步，即船由此岸駛向彼岸或由彼岸駛向此岸，都要對(duì)船上的人員作出決策，在保證兩岸的商人數(shù)不少于隨從數(shù)的前提下，在有限步內(nèi)使全部人員過(guò)河。用狀態(tài)變量表示某一岸的人員狀況，決策變量表示船上的人員狀況，可以找出狀態(tài)隨決策變化的規(guī)律，問(wèn)題轉(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)~過(guò)程的狀態(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)Sk隨決策dk的變化規(guī)律是Sk1=Sk+(-1)kdk~狀態(tài)轉(zhuǎn)移律求dk∈D(k=1,2,…n),使Sk∈S,并按轉(zhuǎn)移律由S1=(4,4)到達(dá)狀態(tài)Sn1=(0,0)。五．模型求解：1.圖解法：對(duì)于人數(shù)不多的情況，可以利用圖解法來(lái)求解。在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)過(guò)那些圓點(diǎn)最終移動(dòng)到原點(diǎn)(0,0)。由初始狀態(tài)(4,4)到原點(diǎn)(0,0)，無(wú)論怎樣走，都要經(jīng)過(guò)(2,2)，但是無(wú)論怎樣變化人數(shù)，也只能到達(dá)此點(diǎn)后不能繼續(xù)走下去，只能循環(huán)走(由d7狀態(tài)無(wú)法不重復(fù)循環(huán)地走下去)，達(dá)不到最終的目標(biāo)(0,0)，因此該問(wèn)題無(wú)解。2.窮舉法：根據(jù)分析可以通過(guò)編程上機(jī)求解，所用的c程序如下所示：#include<stdio.h>#defineN30intx[N],y[N],u[6],v[6],k;/*x,y：狀態(tài)值，分別表示此岸商人、隨從數(shù)*//*u,v：決策值，分別表示船上商人、隨從數(shù)*//*k：決策步數(shù)；k的奇偶性標(biāo)志著船在河的此岸或彼岸*/next(intk,inti)/*計(jì)算下一狀態(tài)*/{if(k%2)/*k+1為偶數(shù)，船從此岸到彼岸*/x[k+1]=x[k]-u[i];y[k+1]=y[k]-v[i];}else/*k+1為奇數(shù)，船從彼岸到此岸*/{x[k+1]=x[k]+u[i];y[k+1]=y[k]+v[i];}return;}allow(intp,intq)/*判定狀態(tài)是否允許,是否重復(fù)*/{intok,j;/*ok:標(biāo)記狀態(tài)是否允許,是否重復(fù)；j:循環(huán)變量*/if(p<0||p>x[1]||p!=0&&q>p||(x[1]-p)!=0&&(y[1]-q)>(x[1]-p)||q<0||q>y[1])ok=0;/*此時(shí)狀態(tài)不屬于允許集*/else{for(j=k-1;j>0;j-=2)/*是否重復(fù)與船在河的哪一岸有關(guān)*/if(p==x[j]&&q==y[j]){ok=0;/*此時(shí)狀態(tài)出現(xiàn)重復(fù)*/break;}if(j<=0)ok=1;/*此時(shí)狀態(tài)屬于允許集，且不重復(fù)*/}returnok;}voidmain(){inti,j,m[N],flag=1;/*m:采用的決策序號(hào)，flag:回溯標(biāo)記*/u[1]=2;v[1]=0;/*給決策編號(hào)并賦值*/u[2]=0;v[2]=2;u[3]=1;v[3]=0;u[4]=0;v[4]=1;u[5]=1;v[5]=1;k=1;/*從初始狀態(tài)出發(fā)*/printf("請(qǐng)輸入商人和隨從的初始狀態(tài):\n商人數(shù)=");scanf("%d",&x[k]);printf("隨從數(shù)=");scanf("%d",&y[k]);while(flag)for(i=1;i<6;i++)/*遍歷各種決策*/{next(k,i);/*計(jì)算下一狀態(tài)*/if(allow(x[k+1],y[k+1]))/*若新狀態(tài)允許且不重復(fù)*/{m[k]=i;/*記錄采用的決策序號(hào)*/if(x[k+1]==0&&y[k+1]==0)/*若到達(dá)目標(biāo)狀態(tài),輸出結(jié)果*/{printf("初始值:商人%d隨從%d\n",x[1],y[1]);for(j=1;j<=k;j++)printf("第%2d次%d%d\n",j,x[j+1],y[j+1]);flag=0;break;}else/*若未到達(dá)目標(biāo)狀態(tài)*/{k++;/*生成下一步的步數(shù)值*/break;/*遍歷終止，進(jìn)入下一步*/}}else/*若新狀態(tài)不允許或重復(fù)*/{while(i==5)/*本步?jīng)Q策已經(jīng)遍歷時(shí)*/{if(k==1){printf("本題無(wú)解!\n");flag=0;break;}else/*未到達(dá)初始狀態(tài)*/{