傳教士與野人過河問題(完整版)
【正文】 de ssr = ntx ssr。 if(newnode==NULL) { printf(\n內(nèi)存不夠！\n)。 struct SPQ *newnode。 void recorder()。 struct SPQ *result。 int loopnum。這樣，通過運(yùn)用狀態(tài)空間表示法就解決了傳教士和食人者問題的求解。全部的可能狀態(tài)共有32個(gè)，如表6—1所示。（2）確定狀態(tài)組，分別列出初始狀態(tài)集和目標(biāo)狀態(tài)集。傳教士野人問題有N個(gè)傳教士和N個(gè)野人要過河，現(xiàn)在有一條船只能承載K個(gè)人（包括野人），KN，在任何時(shí)刻，如果有野人和傳教士在一起，必須要求傳教士的人數(shù)多于或等于野人的人數(shù)。問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述，以左岸的狀態(tài)來標(biāo)記，即右岸的狀態(tài)可以不必標(biāo)出。 表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)，這樣可以加快搜索求解的效率。源代碼：include include include define maxloop 100 /* 最大層數(shù)，對(duì)于不同的擴(kuò)展方法自動(dòng)調(diào)整取值 */ define pristnum 3 /*初始化時(shí)設(shè)定有3個(gè)野人3個(gè)傳教士，實(shí)際可以改動(dòng)*/ define slavenum 3struct SPQ{ int sr,pr。/* 記錄總的擴(kuò)展次數(shù) */ int openednum。 void initiate()。 void addtoopened(struct SPQ *ntx) /*擴(kuò)展節(jié)點(diǎn)*/ { unopened = unopened nextnode。 struct SPQ *ntx。 exit(0)。 newnode spr = ntx spr。 struct SPQ* nodefree。 i++ ) { nodefree = unopened。 printf(%d個(gè)野人 ,result sr)。 printf(\n\n\t左岸人數(shù) 船上人數(shù)及方向 右岸人數(shù)\n)。 printf(傳教士%8d%8d\t\t%8d\n,result pl,result spr,result pr result spr)。choice)。 } }int main() { int flag。 goon()。 uend = unopened = (struct SPQ*)malloc(sizeof(spq))。 unopened pr = pristnum。 printf(*********************************************************************\n)。 printf(\n默認(rèn)的n、m值皆為3\n)。) { printf(\n請(qǐng)輸入傳教士人數(shù))。 for(。N39。 /* 將ntx加入已擴(kuò)展鏈表，并將這個(gè)節(jié)點(diǎn)從待擴(kuò)展鏈表中去掉 */ flag = stretch(ntx)。 sst = 2 。 fsr = fsr sst。 /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ newnode nextnode = NULL。 newnode spr = 0。 for (ssr = 0 。 if ((ffpl ffsl) * ffpl = 0) { /* 若符合條件則分配內(nèi)存并付值 */ int ffsr , ffpr。 newnode pr = ffpr。 uend nextnode = newnode。 unopenednum++。 newnode pl = ffpl。 ffpr = fpr + s
法律信息相關(guān)推薦
鄂ICP備17016276號(hào)-1