傳教士與野人過河問題-文庫吧
2025-07-08 08:09 本頁面
【正文】 岸稱之為Qij操作，下標(biāo)的定義同前。則共有10種操作，操作集為 F={P01，P10，P11，P02，P20，Q01，Q10，Q11，Q02，Q20}（4）估計全部的狀態(tài)空間數(shù)，并盡可能列出全部的狀態(tài)空間或予以描述。在這個問題世界中，S0={3，3，1}為初始狀態(tài)，S31=Sg=（0，0，0）為目標(biāo)狀態(tài)。全部的可能狀態(tài)共有32個，如表6—1所示。 表6—1 傳教士和食人者問題的全部可能狀態(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ī)定的條件，我們應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。例如，首先可以劃去岸邊食人者數(shù)目超過傳教士的情況，即ＳSSSS2S25等6種狀態(tài)是不合法的；其次，應(yīng)該劃去右岸邊食人者數(shù)目超過修道士的情況，即SSS1S2S2S27等情況；余下20種合法狀態(tài)中，又有4種是不可能出現(xiàn)的狀態(tài)；S15和S16不可能出現(xiàn)，因為船不可能?？吭跓o人的岸邊；S3不可能出現(xiàn)，因為傳教士不可能在數(shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃回來；還應(yīng)該劃去S28，因為傳教士也不可能在數(shù)量占優(yōu)勢的食人者眼皮底下把船安全地劃向?qū)Π??？梢?，在狀態(tài)空間中，真正符合題目規(guī)定條件的只有16個合理狀態(tài)。（5） 當(dāng)狀態(tài)數(shù)量不是很大時，按問題的有序元組畫出狀態(tài)空間圖，依照狀態(tài)空間圖搜索求解。 根據(jù)上述分析，共有16個合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖6—4所示。 021111010320220321311020S0S17S2111011002S1S2200111013310120S290210S30S1401S13010111102S19300S5221S10S12031S24110S1831002S13000圖6—4 傳教士和食人者問題的狀態(tài)空間如圖6—4所示，由于劃船操作是可逆的，所以圖中狀態(tài)節(jié)點間用雙向箭頭連接，箭頭旁邊所標(biāo)的數(shù)字表示了Ｐ或Ｑ操作的下標(biāo)，即分別表示船載的傳教士數(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個傳教士，實際可以改動*/ define slavenum 3struct SPQ{ int sr,pr。 /* 船運(yùn)行一個來回后河右岸的野人、傳教士的人數(shù) */ int sl,pl。 /* 船運(yùn)行一個來回后河左岸的野人、傳教士的人數(shù) */ int ssr,spr。 /* 回來（由左向右時）船上的人數(shù) */ int sst,spt。 /* 去時（由右向左時）船上的人數(shù) */ int loop。 /* 本結(jié)點所在的層數(shù) */ struct SPQ *upnode ,*nextnode。/* 本結(jié)點的父結(jié)點和同層的下一個結(jié)點的地址 */ }spq。 int loopnum。/* 記錄總的擴(kuò)展次數(shù) */ int openednum。/* 記錄已擴(kuò)展節(jié)點個數(shù) */ int unopenednum。/* 記錄待擴(kuò)展節(jié)點個數(shù) */ int resultnum。 struct SPQ *opened。 struct SPQ *oend。 struct SPQ *unopened。 struct SPQ *uend。 struct SPQ *result。 void initiate()。 void releasemem()。
法律信息相關(guān)推薦
鄂ICP備17016276號-1