野人與傳教士問(wèn)題(A*算法)SY0903620趙磊一、 實(shí)驗(yàn)題目請(qǐng)用A*算法實(shí)現(xiàn)傳教士和野人問(wèn)題問(wèn)題：設(shè)有3個(gè)傳教士和3個(gè)野人來(lái)到河邊，打算乘一只船從右岸渡到左岸去。該船的負(fù)載能力為兩人。在任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉。他們?cè)鯓硬拍苡眠@條船安全地把所有人都渡過(guò)河去？算法設(shè)計(jì)要求給出：狀態(tài)表示，規(guī)則庫(kù)，啟發(fā)函數(shù)等二、 實(shí)驗(yàn)?zāi)康耐ㄟ^(guò)具體問(wèn)題的編程求解，利用A*算法解決此經(jīng)典問(wèn)題，了解人工智能的啟發(fā)式搜索算法的基本過(guò)程與原理。三、 設(shè)計(jì)思想1、 編程工具采用C++語(yǔ)言在VisualStudio6.0環(huán)境下編寫；2、 整體思想把初始結(jié)點(diǎn)So放入OPEN表中，計(jì)算f(So)。如果OPEN為空，則搜索失敗，退出。把OPEN中的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)從表中移出放入CLOSED表。考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得問(wèn)題的解，退出。若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第(2)步。擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，把這些子節(jié)點(diǎn)都送到OPEN表中，然后對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)值從小到大的順序排列。3、 具體說(shuō)明用A*算法求解傳教士與野人問(wèn)題。M=C=5,K=3。節(jié)點(diǎn)估價(jià)值設(shè)為f(n)=h(n)+g(n)，g(n)設(shè)為節(jié)點(diǎn)搜索深度，而h(n)=m(n)+c(n)-2b(n),其中m：河左岸的傳教士人數(shù)；c：河左岸的野人人數(shù)；b：船是否在左岸，1：表示在左岸，0：表示不在左岸。采用結(jié)構(gòu)體定義形式，定義狀態(tài)節(jié)點(diǎn)*NewNode(intm,intc,intb)，其中包含m左岸傳教士人數(shù)、c左岸野人人數(shù)、b船狀態(tài)(左或右)。開(kāi)始狀態(tài)為(3,3,1),目標(biāo)狀態(tài)為(0,0,0)。若需要條件滿足，即任何時(shí)候，如果野人人數(shù)超過(guò)傳教士人數(shù)，那么野人就會(huì)把傳教士吃掉，要對(duì)狀態(tài)結(jié)點(diǎn)的安全性進(jìn)行判斷，判斷一個(gè)狀態(tài)是否為安全的，即是否滿足在河的任何一岸，傳教士人數(shù)不少于野人人數(shù)，或者只有野人而沒(méi)有傳教士。對(duì)于超出參數(shù)范圍的狀態(tài)，也認(rèn)為是不安全的。即判斷：if(pNode->m<0IIpNode->c<0IIpNode->m>MIIpNode->c>M)return0;if(pNode->m==MIIpNode->m==0)return1;要擴(kuò)展節(jié)點(diǎn)n生成其全部后繼節(jié)點(diǎn).對(duì)于n的每一個(gè)后繼節(jié)點(diǎn)m配置指向父節(jié)點(diǎn)的指針時(shí)：計(jì)算f(m)如果m既不在OPEN表中，也不在CLOSED表中，則用估價(jià)函數(shù)f把它添入OPEN表.從m加一指向父輩節(jié)點(diǎn)n的指針。如果m已在OPEN表或CLOSED表上，則比較剛剛對(duì)m計(jì)算過(guò)的值f和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的f值.如果新的f值較小，則以此新值取代舊值從m指向n,而不是指向它的父輩節(jié)點(diǎn)如果節(jié)點(diǎn)m在CLOSED表中，則把它移回OPEN表四、具體函數(shù)功能1)intEqual(structNODE*pNode1,structNODE*pNode2)功能：判斷兩個(gè)節(jié)點(diǎn)所表示的狀態(tài)是否相等入口參數(shù)：pNode1：指向節(jié)點(diǎn)1的指針pNode2:指向節(jié)點(diǎn)2的指針?lè)祷刂担寒?dāng)兩個(gè)節(jié)點(diǎn)所表示的狀態(tài)相等時(shí)，返回1，否則返回02)功能：動(dòng)態(tài)產(chǎn)生一個(gè)節(jié)點(diǎn)，其狀態(tài)值由參數(shù)m,c,b給定。入口參數(shù)：m：河左岸的傳教士人數(shù)c：河左岸的野人人數(shù)b：船是否在左岸，1：表示在左岸，0：表示不在左岸返回值：指向新產(chǎn)生的節(jié)點(diǎn)的指針，或者空間不夠時(shí)，返回NULL3)voidFreeList(structNODE*pList)功能：釋放動(dòng)態(tài)產(chǎn)生的鏈表入口參數(shù)：pList：指向OPEN表或者CLOSED表的指針?lè)祷刂担簾o(wú)4)structNODE*In(structNODE*pNode,structNODE*pList)功能：判斷一個(gè)節(jié)點(diǎn)是否在一個(gè)鏈表中入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針pList：指向給點(diǎn)鏈表的指針?lè)祷刂担寒?dāng)pNode在pList中時(shí)，返回以pNode為首的鏈表的后一部分；否則返回NULL5)structNODE*Del(structNODE*pNode,structNODE*pList)功能：從鏈表pList中刪除節(jié)點(diǎn)pNode入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針pList：指向給定的鏈表返回值：刪除給定節(jié)點(diǎn)后的鏈表6)功能：將一個(gè)節(jié)點(diǎn)按照f(shuō)值(從小到大)插入到OPEN表中入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針pOpen:指向OPEN表的指針?lè)祷刂担褐赶虿迦虢o定節(jié)點(diǎn)后OPEN表的指針注意：同一個(gè)節(jié)點(diǎn)(具有相同指針的一個(gè)節(jié)點(diǎn))，只能向表中添加一次，否則可能會(huì)造成循環(huán)鏈表7)structNODE*AddToClosed(structNODE*pNode,structNODE*pClosed)功能：將一個(gè)節(jié)點(diǎn)插入到CLOSED表中入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針pClosed:指向CLOSED表的指針?lè)祷刂担褐赶虿迦虢o定節(jié)點(diǎn)后CLOSED表的指針注意：同一個(gè)節(jié)點(diǎn)(具有相同指針的一個(gè)節(jié)點(diǎn))，只能向表中添加一次，否則可能會(huì)造成循環(huán)鏈表8)voidPrintList(structNODE*pList)功能：在屏幕上打印一個(gè)鏈表，用于調(diào)試程序入口參數(shù)：pList：指向鏈表的指針?lè)祷刂担簾o(wú)9)voidPrintNode(structNODE*pNode)功能：在屏幕上打印一個(gè)節(jié)點(diǎn)，用于調(diào)試程序入口參數(shù)：pNode:指向節(jié)點(diǎn)的指針?lè)祷刂担簾o(wú)10)功能：在屏幕上打印解路徑。在搜索過(guò)程中，每個(gè)節(jié)點(diǎn)指向其父節(jié)點(diǎn)，從目標(biāo)節(jié)點(diǎn)開(kāi)始，逆向打印各節(jié)點(diǎn)，既得到解路徑入口參數(shù)：pGoal：指向求解得到的目標(biāo)節(jié)點(diǎn)返回值：無(wú)11)intIsGrandFather(structNODE*pNode,structNODE*pFather)功能：判斷一個(gè)節(jié)點(diǎn)是否與自己的祖父節(jié)點(diǎn)所表示的狀態(tài)一樣入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針pFather:指向給定節(jié)點(diǎn)的父節(jié)點(diǎn)的指針?lè)祷刂担寒?dāng)給定節(jié)點(diǎn)所表示的狀態(tài)與自己的祖父一樣時(shí)，返回1，否則返回012)intIsGoal(structNODE*pNode)功能：判斷給定節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針?lè)祷刂担寒?dāng)給定節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)時(shí)，返回1，否則返回013)intSafe(structNODE*pNode)功能：判斷一個(gè)狀態(tài)是否為安全的，即是否滿足在河的任何一岸，傳教士人數(shù)不少于野人人數(shù)，或者只有野人而沒(méi)有傳教士。對(duì)于超出參數(shù)范圍的狀態(tài)，也認(rèn)為是不安全的入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針?lè)祷刂担寒?dāng)給定節(jié)點(diǎn)安全時(shí)，返回1，否則返回0intH_Function(structNODE*pNode)功能：計(jì)算給定節(jié)點(diǎn)的h值，h=m+c-2b

入口參數(shù)：pNode:指向給定節(jié)點(diǎn)的指針?lè)祷刂担篽值15)structNODE*A_Star(structNODE*s)功能：A*算法主函數(shù)入口參數(shù)：s：指向初始節(jié)點(diǎn)的指針?lè)祷刂担褐赶蚯蠼獾玫降哪繕?biāo)節(jié)點(diǎn)的指針，或者返回NULL表示空間不夠用或者找不到問(wèn)題的解五、程序源代碼#defineM3〃傳教士總?cè)藬?shù)#defineC3〃野人總?cè)藬?shù)#defineK2〃船一次可以乘坐的最多人數(shù)structNODE〃在左岸的傳教士人數(shù)〃在左岸的野人人數(shù)〃在左岸的傳教士人數(shù)〃在左岸的野人人數(shù)//b=1表示船在左岸,b=0表示船在右岸〃該節(jié)點(diǎn)的g值〃該節(jié)點(diǎn)的f值〃指向該節(jié)點(diǎn)的父節(jié)點(diǎn)//在OPEN表或者CLOSED表中，指向下一個(gè)元intm;intc;intb;doubleg;doublef;structNODE*pFather;structNODE*pNext;素};structNODE*g_pOpen=NULL;//全程變量，OPEN表structNODE*g_pClosed=NULL; 〃全程變量，CLOSED表intEqual(structNODE*pNode1,structNODE*pNode2){if(pNode1->m==pNode2->m&&pNode1->c==pNode2->c&&pNode1->b==pNode2->b)return1;elsereturn0;}structNODE*pNode=NULL;pNode=malloc(sizeof(structNODE));if(pNode==NULL)returnNULL;pNode->m=m;pNode->c=c;pNode->b=b;pNode->g=0;pNode->f=0;pNode->pFather=NULL;pNode->pNext=NULL;returnpNode;}voidFreeList(structNODE*pList){structNODE*pNode=NULL;while(pList){pNode=pList;pList=pList->pNext;free(pNode);}}structNODE*In(structNODE*pNode,structNODE*pList){if(pList==NULL)returnNULL;if(Equal(pNode,pList))returnpList;returnIn(pNode,pList->pNext);}structNODE*Del(structNODE*pNode,structNODE*pList){if(pList==NULL)returnpList;if(Equal(pNode,pList))returnpList->pNext;pList->pNext=Del(pNode,pList->pNext);returnpList;}structNODE*AddToOpen(structNODE*pNode,structNODE*pOpen){if(pOpen==NULL)//OPEN表為空{(diào)pNode->pNext=NULL;returnpNode;}if(pNode->f<pOpen->f)//給定節(jié)點(diǎn)的f值小于OPEN表第一個(gè)節(jié)點(diǎn)的f值{pNode->pNext=pOpen;〃插入到OPEN的最前面returnpNode;}pOpen->pNext=AddToOpen(pNode,pOpen->pNext);〃遞歸returnpOpen;}structNODE*AddToClosed(structNODE*pNode,structNODE*pClosed){pNode->pNext=pClosed;returnpNode;}voidPrintList(structNODE*pList){while(pList)//依次打印鏈表{printf("((%d%d%d)%f%f)\n",pList->m,pList->c,pList->b,pList->g,pList->f);pList=pList->pNext;}}voidPrintNode(structNODE*pNode){printf("((%d%d%d)%f%f)\n",pNode->m,pNode->c,pNode->b,pNode->g,pNode->f);}voidPrintPath(structNODE*pGoal){if(pGoal==NULL)return;PrintPath(pGoal->pFather);〃遞歸printf("(%d%d%d)\n",pGoal->m,pGoal->c,pGoal->b);}intIsGrandFather(structNODE*pNode,structNODE*pFather){if(pFather==NULL)return0;if(pFather->pFather==NULL)return0;returnEqual(pNode,pFather->pFather);intIsGoal(structNODE*pNode){if(pNode->m==0&&pNode->c==0&&pNode->b==0)return1;elsereturn0;}intSafe(structNODE*pNode){if(pNode->m<0IIpNode->c<0IIpNode->m>MIIpNode->c>M)return0;if(pNode->m==MIIpNode->m==0)return1;return(pNode->m==pNode->c);}intH_Function(structNODE*pNode){returnpNode->m+pNode->c-2*pNode->b;}structNODE*A_Star(structNODE*s){structNODE*n=NULL,*m=NULL,*pNode=NULL;inti,j;g_pOpen=s; 〃初始化OPEN表和CLOSED表g_pClosed=NULL;while(g_pOpen)//OPEN表不空{(diào)n=g_pOpen; //取出OPEN表的第一個(gè)元素nif(IsGoal(n))returnn;//如果n為目標(biāo)節(jié)點(diǎn)，則成功結(jié)束g_pOpen=g_pOpen->pNext;//否則，從OPEN表中刪除ng_pClosed=AddToClosed(n,g_pClosed);//將n加入到CLOSED中//以下兩重循環(huán)，i表示上船的傳教士人數(shù)，j表示上船的野人人數(shù)for(i=0;i<=K;i++){for(j=0;j<=K;j++){if(i+j==0II//非法的上船組合i+j>KII(i!=0&&i<j))continue;if(n->b==1) 〃當(dāng)船在左岸時(shí){ _m=NewNode(n->m-i,n->c-j,0);//產(chǎn)生下一個(gè)狀態(tài)m}else〃當(dāng)船在右岸時(shí){m=NewNode(n->m+i,n->c+j,1); 〃產(chǎn)生下一個(gè)狀態(tài)m}if(m==NULL)returnNULL; 〃如果空間不夠用，則失敗結(jié)束if(IsGrandFather(m,n)||!Safe(m)) {free(m);continue;}m->pFather=n;//標(biāo)記其父節(jié)點(diǎn)為nm->g=n->g+1;//其g值為其父節(jié)點(diǎn)的g值加1m->f=m->g+H_Function(m);〃計(jì)算其f值，f=g+hif(pNode=In(m,g_pOpen))〃如果m已經(jīng)出現(xiàn)在OPEN表中{if(m->f<pNode->f)//如果m的f值小于OPEN表中相同狀態(tài)的f值{〃則將該節(jié)點(diǎn)從OPEN表中刪除，并將m加入到OPEN表中。g_pOpen=AddToOp