傳教士與野人過河問題(存儲版)
【正文】 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）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 Q10 用狀態(tài)空間法求解傳教士和食人者問題例62 傳教士和食人者問題（The Missionaries and Cannibals Problem）。為了建立這個問題的狀態(tài)空間，設(shè)左岸的傳教士數(shù)為m，則有m={0，1，2，3}；對應(yīng)右岸的傳教士數(shù)為3—m；左岸的食人者數(shù)為c，則有c={0，1，2，3}；對應(yīng)右岸食人者數(shù)為3—c；左岸船數(shù)為b，故又有b={0，1}；右岸的船數(shù)為1b。在這個問題世界中，S0={3，3，1}為初始狀態(tài)，S31=Sg=（0，0，0）為目標(biāo)狀態(tài)。這樣，任何一條從S0到達(dá)S31的路徑都是該問題的解。/* 本結(jié)點(diǎn)的父結(jié)點(diǎn)和同層的下一個結(jié)點(diǎn)的地址 */ }spq。 struct SPQ *uend。 int stretch(struct SPQ* ntx)。 } void recorder() { int i , loop。 i++ ) { newnode = (struct SPQ*) malloc (sizeof(spq))。 newnode spt = ntx spt。 resultnum++。 } for ( i = 0 。 /* 在左岸上的人數(shù) */ struct SPQ* nodefree。 result = result nextnode。 printf(傳教士%8d%8d\t\t%8d\n,fpl,result spt,fpr)。) { printf(是否繼續(xù)？(Y/N)\n)。N39。 releasemem()。 }void initiate() { int x。 /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ unopened nextnode = unopened。 unopened spr = 0。他們怎樣才能用這條船安全的把所有人都渡過河去\n)。 if(choice==39。 } else printf(\n輸入值應(yīng)大于0！\n請重新輸入)。 } break。 /* 從待擴(kuò)展鏈表中提取最前面的一個 */ if(ntxloop == maxloop) return 0。 /* 返回時船上的人數(shù) */ struct SPQ *newnode。amp。 exit(0)。 newnode spt = spt。 } else if ((fpr fsr) * fpr = 0) /* 判斷是否滿足傳教士人數(shù)必須大于或等于野人人數(shù) */ { fsl = fsl + sst。 ffsl = fsl ssr。 } newnode upnode = ntx。 newnode spr = spr。 } 。 newnode spt = spt。 if(newnode==NULL) { printf(\n內(nèi)存不夠！\n)。amp。 openednum++。 newnode pl = opened pr。 (fsr == 0))/* 搜索成功 */ { newnode = (struct SPQ*) malloc (sizeof(spq))。 fpl = ntx pl。 /* 在左岸上的人數(shù) */ int sst , spt 。 /* 提供將要擴(kuò)展的結(jié)點(diǎn)的指針 */ for( 。 break。 if(x0) { unopened pr = x。choice)。在任何時候，如果野人人數(shù)超過傳教士人數(shù)，野人\n)。 unopened spt = 0。 openednum
法律信息相關(guān)推薦
鄂ICP備17016276號-1