野人与传教士问题A算法

野人与传教士问题(A*算法)SY0903620赵磊一、 实验题目请用A*算法实现传教士和野人问题问题：设有3个传教士和3个野人来到河边，打算乘一只船从右岸渡到左岸去。该船的负载能力为两人。在任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉。他们怎样才能用这条船安全地把所有人都渡过河去？算法设计要求给出：状态表示，规则库，启发函数等二、 实验目的通过具体问题的编程求解，利用A*算法解决此经典问题，了解人工智能的启发式搜索算法的基本过程与原理。三、 设计思想1、 编程工具采用C++语言在VisualStudio6.0环境下编写；2、 整体思想把初始结点So放入OPEN表中，计算f(So)。如果OPEN为空，则搜索失败，退出。把OPEN中的第一个节点(记为节点n)从表中移出放入CLOSED表。考察节点n是否为目标节点。若是，则求得问题的解，退出。若节点n不可扩展，则转第(2)步。扩展节点n，用估价函数f(x)计算每个子节点的估价值，并为每个子节点配置指向父节点的指针，把这些子节点都送到OPEN表中，然后对OPEN表中的全部节点按估价值从小到大的顺序排列。3、 具体说明用A*算法求解传教士与野人问题。M=C=5,K=3。节点估价值设为f(n)=h(n)+g(n)，g(n)设为节点搜索深度，而h(n)=m(n)+c(n)-2b(n),其中m：河左岸的传教士人数；c：河左岸的野人人数；b：船是否在左岸，1：表示在左岸，0：表示不在左岸。采用结构体定义形式，定义状态节点*NewNode(intm,intc,intb)，其中包含m左岸传教士人数、c左岸野人人数、b船状态(左或右)。开始状态为(3,3,1),目标状态为(0,0,0)。若需要条件满足，即任何时候，如果野人人数超过传教士人数，那么野人就会把传教士吃掉，要对状态结点的安全性进行判断，判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。对于超出参数范围的状态，也认为是不安全的。即判断：if(pNode->m<0IIpNode->c<0IIpNode->m>MIIpNode->c>M)return0;if(pNode->m==MIIpNode->m==0)return1;要扩展节点n生成其全部后继节点.对于n的每一个后继节点m配置指向父节点的指针时：计算f(m)如果m既不在OPEN表中，也不在CLOSED表中，则用估价函数f把它添入OPEN表.从m加一指向父辈节点n的指针。如果m已在OPEN表或CLOSED表上，则比较刚刚对m计算过的值f和前面计算过的该节点在表中的f值.如果新的f值较小，则以此新值取代旧值从m指向n,而不是指向它的父辈节点如果节点m在CLOSED表中，则把它移回OPEN表四、具体函数功能1)intEqual(structNODE*pNode1,structNODE*pNode2)功能：判断两个节点所表示的状态是否相等入口参数：pNode1：指向节点1的指针pNode2:指向节点2的指针返回值：当两个节点所表示的状态相等时，返回1，否则返回02)功能：动态产生一个节点，其状态值由参数m,c,b给定。入口参数：m：河左岸的传教士人数c：河左岸的野人人数b：船是否在左岸，1：表示在左岸，0：表示不在左岸返回值：指向新产生的节点的指针，或者空间不够时，返回NULL3)voidFreeList(structNODE*pList)功能：释放动态产生的链表入口参数：pList：指向OPEN表或者CLOSED表的指针返回值：无4)structNODE*In(structNODE*pNode,structNODE*pList)功能：判断一个节点是否在一个链表中入口参数：pNode:指向给定节点的指针pList：指向给点链表的指针返回值：当pNode在pList中时，返回以pNode为首的链表的后一部分；否则返回NULL5)structNODE*Del(structNODE*pNode,structNODE*pList)功能：从链表pList中删除节点pNode入口参数：pNode:指向给定节点的指针pList：指向给定的链表返回值：删除给定节点后的链表6)功能：将一个节点按照f值(从小到大)插入到OPEN表中入口参数：pNode:指向给定节点的指针pOpen:指向OPEN表的指针返回值：指向插入给定节点后OPEN表的指针注意：同一个节点(具有相同指针的一个节点)，只能向表中添加一次，否则可能会造成循环链表7)structNODE*AddToClosed(structNODE*pNode,structNODE*pClosed)功能：将一个节点插入到CLOSED表中入口参数：pNode:指向给定节点的指针pClosed:指向CLOSED表的指针返回值：指向插入给定节点后CLOSED表的指针注意：同一个节点(具有相同指针的一个节点)，只能向表中添加一次，否则可能会造成循环链表8)voidPrintList(structNODE*pList)功能：在屏幕上打印一个链表，用于调试程序入口参数：pList：指向链表的指针返回值：无9)voidPrintNode(structNODE*pNode)功能：在屏幕上打印一个节点，用于调试程序入口参数：pNode:指向节点的指针返回值：无10)功能：在屏幕上打印解路径。在搜索过程中，每个节点指向其父节点，从目标节点开始，逆向打印各节点，既得到解路径入口参数：pGoal：指向求解得到的目标节点返回值：无11)intIsGrandFather(structNODE*pNode,structNODE*pFather)功能：判断一个节点是否与自己的祖父节点所表示的状态一样入口参数：pNode:指向给定节点的指针pFather:指向给定节点的父节点的指针返回值：当给定节点所表示的状态与自己的祖父一样时，返回1，否则返回012)intIsGoal(structNODE*pNode)功能：判断给定节点是否为目标节点入口参数：pNode:指向给定节点的指针返回值：当给定节点是目标节点时，返回1，否则返回013)intSafe(structNODE*pNode)功能：判断一个状态是否为安全的，即是否满足在河的任何一岸，传教士人数不少于野人人数，或者只有野人而没有传教士。对于超出参数范围的状态，也认为是不安全的入口参数：pNode:指向给定节点的指针返回值：当给定节点安全时，返回1，否则返回0intH_Function(structNODE*pNode)功能：计算给定节点的h值，h=m+c-2b

入口参数：pNode:指向给定节点的指针返回值：h值15)structNODE*A_Star(structNODE*s)功能：A*算法主函数入口参数：s：指向初始节点的指针返回值：指向求解得到的目标节点的指针，或者返回NULL表示空间不够用或者找不到问题的解五、程序源代码#defineM3〃传教士总人数#defineC3〃野人总人数#defineK2〃船一次可以乘坐的最多人数structNODE〃在左岸的传教士人数〃在左岸的野人人数〃在左岸的传教士人数〃在左岸的野人人数//b=1表示船在左岸,b=0表示船在右岸〃该节点的g值〃该节点的f值〃指向该节点的父节点//在OPEN表或者CLOSED表中，指向下一个元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表为空{pNode->pNext=NULL;returnpNode;}if(pNode->f<pOpen->f)//给定节点的f值小于OPEN表第一个节点的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表不空{n=g_pOpen; //取出OPEN表的第一个元素nif(IsGoal(n))returnn;//如果n为目标节点，则成功结束g_pOpen=g_pOpen->pNext;//否则，从OPEN表中删除ng_pClosed=AddToClosed(n,g_pClosed);//将n加入到CLOSED中//以下两重循环，i表示上船的传教士人数，j表示上船的野人人数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) 〃当船在左岸时{ _m=NewNode(n->m-i,n->c-j,0);//产生下一个状态m}else〃当船在右岸时{m=NewNode(n->m+i,n->c+j,1); 〃产生下一个状态m}if(m==NULL)returnNULL; 〃如果空间不够用，则失败结束if(IsGrandFather(m,n)||!Safe(m)) {free(m);continue;}m->pFather=n;//标记其父节点为nm->g=n->g+1;//其g值为其父节点的g值加1m->f=m->g+H_Function(m);〃计算其f值，f=g+hif(pNode=In(m,g_pOpen))〃如果m已经出现在OPEN表中{if(m->f<pNode->f)//如果m的f值小于OPEN表中相同状态的f值{〃则将该节点从OPEN表中删除，并将m加入到OPEN表中。g_pOpen=AddToOp