傳教士與野人過河問題_第1頁
傳教士與野人過河問題_第2頁
傳教士與野人過河問題_第3頁
傳教士與野人過河問題_第4頁
傳教士與野人過河問題_第5頁
已閱讀5頁,還剩7頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

1、傳教士-野人問題有N個傳教士和N個野人要過河,現(xiàn)在有一條船只能承載K個人(包括野人),K=C且M+C = K初始狀態(tài)目標(biāo)狀態(tài)LRLRM30M03C30C03B10B01(1) 用三元組來表示(ML , CL , BL)其中0=ML , CL =野人數(shù)目f = 其它f=3 Q01f=2 P02f=1 Q01f=1 Q11f=1 P01f=2 P11(3,3,1)(3,2,0)(2,2,0)(3,1,0)(3,2,1)(3,0,0)f=3 P02(3,1,1)f=2 Q01(1,1,0)f=4 P20(2,2,1)f=2 Q11(1,1,0)f=4 P20(2,2,1)f=2 Q111(0,2,0

2、)f=4 P20(0,3,1)f=3 Q01(0,1,1)f=5 P02(0,2,1)f=4 Q01(0,0,0)f=3 Q01(1,1,1)f=4 Q106.2.3 用狀態(tài)空間法求解傳教士和食人者問題例6-2 傳教士和食人者問題(The Missionaries and Cannibals Problem)。在河的左岸有3個傳教士、1條船和3個食人者,傳教士們想用這條船將所有的成員運(yùn)過河去,但是受到以下條件的限制:(1)傳教士和食人者都會劃船,但船一次最多只能裝運(yùn)兩個;(2)在任何岸邊食人者數(shù)目都不得超過傳教士,否則傳教士就會遭遇危險:被食人者攻擊甚至被吃掉。此外,假定食人者會服從任何一種過

3、河安排,試規(guī)劃出一個確保全部成員安全過河的計(jì)劃。解 我們按上述步驟來進(jìn)行求解分析。(1)設(shè)定狀態(tài)變量及確定值域。為了建立這個問題的狀態(tài)空間,設(shè)左岸的傳教士數(shù)為m,則有m=0,1,2,3;對應(yīng)右岸的傳教士數(shù)為3m;左岸的食人者數(shù)為c,則有c=0,1,2,3;對應(yīng)右岸食人者數(shù)為3c;左岸船數(shù)為b,故又有b=0,1;右岸的船數(shù)為1-b。(2)確定狀態(tài)組,分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集。問題的狀態(tài)可以用一個三元數(shù)組來描述,以左岸的狀態(tài)來標(biāo)記,即右岸的狀態(tài)可以不必標(biāo)出。 Sk=(m, c, b)初始狀態(tài)只有一個:S0=(3, 3, 1),初始狀態(tài)表示全部成員在河的的左岸;目標(biāo)狀態(tài)也只有一個:Sg=(0,

4、0,0),表示全部成員從河的左岸全部渡河完畢。(3)定義并確定操作集。仍然以河的左岸為基點(diǎn)來考慮,把船從左岸劃向右岸定義為Pij操作。其中,第一下標(biāo)i表示船載的傳教士數(shù),第二下標(biāo)j表示船載的食人者數(shù);同理,從右岸將船劃回左岸稱之為Qij操作,下標(biāo)的定義同前。則共有10種操作,操作集為 F=P01,P10,P11,P02,P20,Q01,Q10,Q11,Q02,Q20(4)估計(jì)全部的狀態(tài)空間數(shù),并盡可能列出全部的狀態(tài)空間或予以描述。在這個問題世界中,S0=3,3,1為初始狀態(tài),S31=Sg=(0,0,0)為目標(biāo)狀態(tài)。全部的可能狀態(tài)共有32個,如表61所示。 表61 傳教士和食人者問題的全部可能狀

5、態(tài)狀 態(tài)m, c, b狀 態(tài)m, c, b狀 態(tài)m, c, b狀 態(tài) m, c, bS03,3,1S81,3,1S163,3,0S241,3,0S13,2,1S91,2,1S173,2,0S251,2,0S23,1,1S101,1,1S183,1,0S261,1,0S33,0,1S111,0,1S193,0,0S271,0,0S42,3,1S120,3,1S202,3,0S280,3,0S52,2,1S130,2,1S212,2,0S290,2,0S62,1,1S140,1,1S222,1,0S300,1,0S72,0,1S150,0,1S232,0,0S310,0,0值得注意的是按照題目規(guī)定

6、的條件,我們應(yīng)該劃去不合法的狀態(tài),這樣可以加快搜索求解的效率。例如,首先可以劃去岸邊食人者數(shù)目超過傳教士的情況,即4、S8、S9、S20、S24、S25等6種狀態(tài)是不合法的;其次,應(yīng)該劃去右岸邊食人者數(shù)目超過修道士的情況,即S6、S7、S11、S22、S23、S27等情況;余下20種合法狀態(tài)中,又有4種是不可能出現(xiàn)的狀態(tài);S15和S16不可能出現(xiàn),因?yàn)榇豢赡芡?吭跓o人的岸邊;S3不可能出現(xiàn),因?yàn)閭鹘淌坎豢赡茉跀?shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃回來;還應(yīng)該劃去S28,因?yàn)閭鹘淌恳膊豢赡茉跀?shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃向?qū)Π?。可見,在狀態(tài)空間中,真正符合題目規(guī)定條件的只有16個合理狀

7、態(tài)。(5) 當(dāng)狀態(tài)數(shù)量不是很大時,按問題的有序元組畫出狀態(tài)空間圖,依照狀態(tài)空間圖搜索求解。 根據(jù)上述分析,共有16個合法狀態(tài)和允許的操作,可以劃出傳教士和食人者問題的狀態(tài)空間圖,如圖64所示。 021111010320220321311020S0S17S2111011002S1S2200111013310120S290210S30S140119300S5221S10S12031S24110S1831002S13000圖64 傳教士和食人者問題的狀態(tài)空間如圖64所示,由于劃船操作是可逆的,所以圖中狀態(tài)節(jié)點(diǎn)間用雙向箭頭連接,箭頭旁邊所標(biāo)的數(shù)字表示了或操作的下標(biāo),即分別表示

8、船載的傳教士數(shù)和食人者數(shù)。這樣,任何一條從S0到達(dá)S31的路徑都是該問題的解。這樣,通過運(yùn)用狀態(tài)空間表示法就解決了傳教士和食人者問題的求解。源代碼:#include #include #include #define maxloop 100 /* 最大層數(shù),對于不同的擴(kuò)展方法自動調(diào)整取值 */ #define pristnum 3 /*初始化時設(shè)定有3個野人3個傳教士,實(shí)際可以改動*/ #define slavenum 3struct SPQ int sr,pr; /* 船運(yùn)行一個來回后河右岸的野人、傳教士的人數(shù) */ int sl,pl; /* 船運(yùn)行一個來回后河左岸的野人、傳教士的人數(shù) *

9、/ int ssr,spr; /* 回來(由左向右時)船上的人數(shù) */ int sst,spt; /* 去時(由右向左時)船上的人數(shù) */ int loop; /* 本結(jié)點(diǎn)所在的層數(shù) */ struct SPQ *upnode ,*nextnode;/* 本結(jié)點(diǎn)的父結(jié)點(diǎn)和同層的下一個結(jié)點(diǎn)的地址 */ spq; int loopnum;/* 記錄總的擴(kuò)展次數(shù) */ int openednum;/* 記錄已擴(kuò)展節(jié)點(diǎn)個數(shù) */ int unopenednum;/* 記錄待擴(kuò)展節(jié)點(diǎn)個數(shù) */ int resultnum; struct SPQ *opened; struct SPQ *oend; st

10、ruct SPQ *unopened; struct SPQ *uend; struct SPQ *result; void initiate(); void releasemem(); void showresult(); void addtoopened(struct SPQ *ntx); int search(); void goon(); int stretch(struct SPQ* ntx); void recorder(); void addtoopened(struct SPQ *ntx) /*擴(kuò)展節(jié)點(diǎn)*/ unopened = unopened - nextnode; uno

11、penednum-; if (openednum = 0 ) oend = opened = ntx; oend - nextnode = ntx; oend = ntx; openednum+; void recorder() int i , loop; struct SPQ *newnode; struct SPQ *ntx; loop = oend - loop; ntx = oend; resultnum = 0; for( i = 0 ; i sr = ntx - sr; newnode - pr = ntx - pr; newnode - sl = ntx - sl; newnod

12、e - pl = ntx - pl; newnode - sst = ntx - sst; newnode - spt = ntx - spt; newnode - ssr = ntx - ssr; newnode - spr = ntx - spr; newnode - nextnode = NULL; ntx = ntx - upnode; if(i = 0) result = newnode; newnode - nextnode = result; result = newnode; resultnum+; void releasemem() int i; struct SPQ* no

13、defree; for ( i = 1 ; i nextnode; free(nodefree); for ( i = 0 ; i nextnode; free(nodefree); void showresult() /*顯示*/ int i; int fsr , fpr ; /* 在右岸上的人數(shù) */ int fsl , fpl ; /* 在左岸上的人數(shù) */ struct SPQ* nodefree; printf(%d個傳教士,result - pr); printf(%d個野人 ,result - sr); printf(%d個傳教士,result - pl); printf(%d個

14、野人 ,result - sl); for ( i = 1 ; i nextnode; free(nodefree); printf(nnt左岸人數(shù) 船上人數(shù)及方向 右岸人數(shù)n); printf(第%d輪n,i); fpl = result - pl - result - spt + result - spr; fpr = result - pr - result - spr; fsl = result - sl - result - sst + result - ssr; fsr = result - sr - result - ssr; printf(傳教士%8d%8dt spt,fpr)

15、; printf(野 人%8d%8dt sst,fsr); printf(傳教士%8d%8dt-t%8dn,result - pl,result - spr,result - pr - result - spr); printf(野 人%8d%8dt-t%8dn,result - sl,result - ssr,result - sr - result - ssr); printf(n全體傳教士和野人全部到達(dá)對岸); free(result); void goon() /*循環(huán)操作選擇*/ char choice; for(;) printf(是否繼續(xù)?(Y/N)n); scanf (%s ,

16、 &choice); choice=toupper(choice); if(choice=Y)break; if(choice=N)exit(0); int main() int flag; /* 標(biāo)記擴(kuò)展是否成功 */ for( ; ; ) initiate(); flag = search (); if(flag = 1) recorder(); releasemem(); showresult(); goon(); else printf(無法找到符合條件的解); releasemem(); goon(); system(pause); return 0; void initiate()

17、 int x; char choice; uend = unopened = (struct SPQ*)malloc(sizeof(spq); if(uend=NULL) printf(n內(nèi)存不夠!n); exit(0); unopenednum=1; openednum=0; unopened - upnode = unopened; /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ unopened - nextnode = unopened; unopened - sr = slavenum; unopened - pr = pristnum; unopened - sl = 0; unopened

18、 - pl = 0; unopened - sst = 0; unopened - spt = 0; unopened - ssr = 0; unopened - spr = 0; unopened - loop = 0; printf(*n); printf(題目:設(shè)有n個傳教士和m個野人來到河邊,打算乘一只船從右岸到左岸去。n); printf(該船的負(fù)載能力為兩人。在任何時候,如果野人人數(shù)超過傳教士人數(shù),野人n); printf(就會把傳教士吃掉。他們怎樣才能用這條船安全的把所有人都渡過河去n); printf(*); printf(n默認(rèn)的n、m值皆為3n); for(;) print

19、f(n是否修改?(Y/N); scanf(%s,&choice); choice=toupper(choice); if(choice=Y) printf(n請輸入傳教士人數(shù)); for(;) scanf(%d,&x); if(x0) unopened - pr = x; break; else printf(n輸入值應(yīng)大于0!n請重新輸入); printf(n請輸入野人人數(shù)); for(;) scanf(%d,&x); if(x0) unopened - sr = x; break; else printf(n輸入值應(yīng)大于0!n請重新輸入); break; if(choice=N)break

20、; int search() int flag; struct SPQ *ntx; /* 提供將要擴(kuò)展的結(jié)點(diǎn)的指針 */ for( ; ) ntx = unopened; /* 從待擴(kuò)展鏈表中提取最前面的一個 */ if(ntx-loop = maxloop) return 0; addtoopened(ntx); /* 將ntx加入已擴(kuò)展鏈表,并將這個節(jié)點(diǎn)從待擴(kuò)展鏈表中去掉 */ flag = stretch(ntx); /* 對ntx進(jìn)行擴(kuò)展,返回-1,0,1 */ if(flag = 1) return 1; int stretch(struct SPQ *ntx) int fsr ,

21、fpr ; /* 在右岸上的人數(shù) */ int fsl , fpl ; /* 在左岸上的人數(shù) */ int sst , spt ; /* 出發(fā)時在船上的人數(shù) */ int ssr , spr ; /* 返回時船上的人數(shù) */ struct SPQ *newnode; for (sst = 0 ; sst sr; fpr = ntx - pr; fsl = ntx - sl; fpl = ntx - pl; if (sst = fsr) & ( 2 - sst) upnode = ntx; /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ newnode - nextnode = NULL; newnode - sr = 0; newnode - pr = 0; newnode - sl = opened - sr; newnode - pl = opened - pr; newnode - sst = sst; newnode - spt = spt; newnode - ssr = 0; newnode - spr = 0; newnode - loop = ntx - loop + 1;

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論