商人過河模型問題的求解

1、數(shù)學(xué)建模實(shí)驗(yàn)課程考試試題商人安全過河數(shù)學(xué)建模與求解一問題提出：4名商人帶4名隨從乘一條小船過河，小船每次自能承載至多兩人。隨從們密約,在河的任一岸,一旦隨從的人數(shù)比商人多,就殺人越貨.乘船渡河的方案由商人決定，商人們?nèi)绾尾拍馨踩珊幽囟Ｐ图僭O(shè)：商人和隨從都會(huì)劃船，天氣很好，無大風(fēng)大浪，且船的質(zhì)量很好，可以保證很多次安全的運(yùn)載商人和隨從。三問題分析：商隨過河問題可以視為一個(gè)多步?jīng)Q策過程，通過多次優(yōu)化，最后獲取一個(gè)全局最優(yōu)的決策方案。對(duì)于每一步，即船由此岸駛向彼岸或由彼岸駛向此岸，都要對(duì)船上的人員作出決策，在保證兩岸的商人數(shù)不少于隨從數(shù)的前提下，在有限步內(nèi)使全部人員過河。用狀態(tài)變量表示某一岸的人

2、員狀況，決策變量表示船上的人員狀況，可以找出狀態(tài)隨決策變化的規(guī)律，問題轉(zhuǎn)化為在狀態(tài)的允許變化范圍內(nèi)(即安全渡河條件)，確定每一步的決策，達(dá)到安全渡河的目標(biāo)。四模型構(gòu)成：Xk第k次渡河前此岸的商人數(shù)，y第k次渡河前此岸的隨從數(shù)xyk=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,35第k次渡船上的商人數(shù)Vk-第k次渡船上的隨從數(shù)dk=(uk,vk)決策，D=(u,v)|1uv2,uk,vk=0,1,2允許決策集合k=1,2,因?yàn)閗為奇數(shù)時(shí)船從此岸駛向彼岸，k為偶數(shù)時(shí)船

3、從彼岸駛向此岸，所以狀態(tài)Sk隨決策dk的變化規(guī)律是Ski=Sk+(1)kdktfcS轉(zhuǎn)移律求dkeD(k=1,2,-n),使SkeS,并按轉(zhuǎn)移律由Si=(4,4)到達(dá)X犬態(tài)Sn1=(0,0)。五.模型求解：1 .圖解法：對(duì)于人數(shù)不多的情況，可以利用圖解法來求解。在xofRW坐標(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使由S=(4,4)經(jīng)過那些圓點(diǎn)最終移動(dòng)到原點(diǎn)(0,0)。由初始狀態(tài)(4,4)到原點(diǎn)(0,0),無論怎樣走，都要經(jīng)過(2,

4、2),但是無論怎樣變(由d7狀態(tài)無法不重復(fù)化人數(shù)，也只能到達(dá)此點(diǎn)后不能繼續(xù)走下去，只能循環(huán)走循環(huán)地走下去)，達(dá)不到最終的目標(biāo)(0,0),因此該問題無解2 .窮舉法：根據(jù)分析可以通過編程上機(jī)求解，所用的甜序如下所示:#include<>#defineN30intxN,yN,u6,v6,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ù)，船從此岸到彼岸*/xk+1=xk-ui;yk+1=yk-vi;else

5、/*k+1為奇數(shù)，船從彼岸到此岸*/xk+1=xk+ui;yk+1=yk+vi;return;allow(intp,intq)/*判定狀態(tài)是否允許,是否重復(fù)*/intok,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&&q=yj)ok=0;/*此時(shí)狀

6、態(tài)出現(xiàn)重復(fù)*/break;if(j<=0)ok=1;/*此時(shí)狀態(tài)屬于允許集，且不重復(fù)*/returnok;voidmain()inti,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",&xk);printf("隨從數(shù)=");scanf("%d",&

7、amp;yk);while(flag)for(i=1;i<6;i+)/*遍歷各種決策*/next(k,i);/*計(jì)算下一狀態(tài)*/if(allow(xk+1,yk+1)/*若新狀態(tài)允許且不重復(fù)*/mk=i;/*記錄采用的決策序號(hào)*/if(xk+1=0&&yk+1=0)/*若到達(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/*若未到達(dá)目標(biāo)狀態(tài)*/k+;/*生成下一

8、步的步數(shù)值*/break;/*遍歷終止，進(jìn)入下一步*/else/*若新狀態(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-;/*回溯退回1步，尋找新路徑*/i=mk;if(flag)continue;/*本步?jīng)Q策尚未遍歷時(shí)*/elsebreak;/*本步?jīng)Q策遍歷時(shí)*/當(dāng)冏人數(shù)和隨從數(shù)分別取(2,2)(3,3)(4,4)時(shí),程序輸出結(jié)果如下：I&in叵r*E;DRbugT商人過河問題啟k初始值:商人2隨從2第1次i2第次第4次第5次'i"bs&any22Si0keyt;a0continue，EDgbug'，