【正文】 S222,1,0S300,1,0S72,0,1S150,0,1S232,0,0S310,0,0值得注意的是按照題目規(guī)定的條件，我們應(yīng)該劃去不合法的狀態(tài)，這樣可以加快搜索求解的效率。傳教士野人問題有N個(gè)傳教士和N個(gè)野人要過河，現(xiàn)在有一條船只能承載K個(gè)人（包括野人），KN，在任何時(shí)刻，如果有野人和傳教士在一起，必須要求傳教士的人數(shù)多于或等于野人的人數(shù)。全部的可能狀態(tài)共有32個(gè)，如表6—1所示。 int loopnum。 void recorder()。 if(newnode==NULL) { printf(\n內(nèi)存不夠！\n)。 } } void releasemem() { int i。 printf(%d個(gè)傳教士,result pr)。 printf(野 人%8d%8d\t\t%8d\n,fsl,result sst,fsr)。)exit(0)。 char choice。 unopened loop = 0。Y39。 } if(choice==39。 for (sst = 0 。 } newnode upnode = ntx。 fpl = fpl + spt。 /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ newnode sr = ffsr。 } } } } } } return 0。 newnode = (struct SPQ*) malloc (sizeof(spq))。 oend = newnode。amp。 /* 在右岸上的人數(shù) */ int fsl , fpl 。 if(x0) { unopened sr = x。 scanf(%s,amp。 unopened sst = 0。 goon()。Y39。 fpr = result pr result spr。 } } void showresult() /*顯示*/ { int i。 if(i == 0) result = newnode。 resultnum = 0。 void addtoopened(struct SPQ *ntx)。 /* 回來（由左向右時(shí)）船上的人數(shù) */ int sst,spt。仍然以河的左岸為基點(diǎn)來考慮，把船從左岸劃向右岸定義為Pij操作。解 我們按上述步驟來進(jìn)行求解分析。 根據(jù)上述分析，共有16個(gè)合法狀態(tài)和允許的操作，可以劃出傳教士和食人者問題的狀態(tài)空間圖，如圖6—4所示。 struct SPQ *oend。 oend = ntx。 newnode pl = ntx pl。 opened = opened nextnode。 i resultnum 。 } void goon() /*循環(huán)操作選擇*/ { char choice。 flag = search ()。 openednum=0。在任何時(shí)候，如果野人人數(shù)超過傳教士人數(shù)，野人\n)。 if(x0) { unopened pr = x。 /* 提供將要擴(kuò)展的結(jié)點(diǎn)的指針 */ for( 。 fpl = ntx pl。 newnode pl = opened pr。amp。 newnode spt = spt。 newnode spr = spr。 ffsl = fsl ssr。 newnode spt = spt。amp。 /* 從待擴(kuò)展鏈表中提取最前面的一個(gè) */ if(ntxloop == maxloop) return 0。 } else printf(\n輸入值應(yīng)大于0！\n請(qǐng)重新輸入)。他們?cè)鯓硬拍苡眠@條船安全的把所有人都渡過河去\n)。 /* 保存父結(jié)點(diǎn)的地址以成鏈表 */ unopened nextnode = unopened。 releasemem()。) { printf(是否繼續(xù)？(Y/N)\n)。 result = result nextnode。 } for ( i = 0 。 newnode spt = ntx spt。 } void recorder() { int i , loop。 struct SPQ *uend。這樣，任何一條從S0到達(dá)S31的路徑都是該問題的解。為了建立這個(gè)問題的狀態(tài)空間，設(shè)左岸的傳教士數(shù)為m，則有m={0，1，2，3}；對(duì)應(yīng)右岸的傳教士數(shù)為3—m；左岸的食人者數(shù)為c，則有c={0，