启发式图搜索过程.docx

姓名：学号：启发式图搜索过程启发式图搜索过程一、过程A描述： OPEN := (s), f(s) := g(s) + h(s); LOOP : IF OPEN=() THEN EXIT(FAIL); n := FIRST(OPEN); IF GOAL(n) THEN EXIT(SUCCESS); REMOVE(n, OPEN) , ADD(n, CLOSED); EXPAND(n) mi , 计算f(n, mi) = g(n, mi) + h(mi); g(n, mi)是从s通过n到mi的耗散值，f(n, mi)是从s通过n、mi到目标节点耗散值的估计；ADD(mj , OPEN), 标记mi到n的指针。IF f(n, mk)f(mk) THEN f(mk) := f(n, mk),标记mk到n的指针；比较f(n, mk)和f(mk),f(mk)是扩展n之前计算的耗散值。IF f(n, ml)f(m1) THEN f(ml) := f(n, ml),标记ml到n的指针，ADD(ml,OPEN);当f(n, ml)f(ml)时，把ml重放回OPEN中，不必考虑修改到其子节点的指针。 OPEN中的节点按f值从小到大排列； GO LOOP。二、最佳图搜索算法A*：当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)=h*(n)时，则把这个算法称为算法A*。在下面解决八数码问题的程序中，采用h(n)=P(n), P(n)定义为每一个将牌与其目标位置之间的距离的总和。三、算法实现（1）数据结构class StateNodepublic:int gs,hs,fs;/分别表示算法中的g(n)、h(n)、f(n)StateNode *psn;/一个指向扩展出它的父节点的指针StateNode();/构造函数，初始化节点void putstartnode();/输入开始节点void putgoalnode();/输入目标节点int getnode(int i,int j);/读取nodeijvoid swap(int i,int j,int m,int n);/交换数组中指定位置的两个元素的数值bool operator =(StateNode &sn);/重载了运算符=，方便后面进行比较void operator =(StateNode &sn);/重载了运算符=，方便后面对节点进行整体赋值void printstatenode();/将每个节点的内容按照一定格式输出private:int node33;/八数码的每个节点用一个二维数组存储;void evaluatefunction(StateNode &sn,StateNode &goal);/启发函数，计算某个节点的h(n)值bool isgoal(StateNode &sn,StateNode &goal);/判断当前节点是否目标节点bool uninlist(StateNode &sn,list &lsn);/判断当前节点是不是在OPEN表或者CLOSED表中void addtolist(StateNode &sn,list &lsn,list &lcsn);/根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式void expandnode(StateNode &sn,StateNode &goal,list &lsn,list &lcsn); /扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作list OPEN;/使用STL中的list类型来存放OPEN表list CLOSED;/使用STL中的list类型来存放CLOSED表（2）运行过程演示：四、程序代码（C+）：#include #include #include using namespace std;#define MAXNUM 1000class StateNode/这是一个节点类型的类，定义了与节点相关的信息及函数public:int gs,hs,fs;StateNode *psn;StateNode()gs=0;hs=0;fs=gs+hs;psn=0;for (int i=0;i3;i+)for (int j=0;j3;j+)nodeij=0;void putstartnode()cout请输入目标状态！（空闲的格子用0表示）endl;for (int i=0;i3;i+)for (int j=0;jnodeij;coutendl;void putgoalnode()cout请输入初始状态！（空闲的格子用0表示）endl;for (int i=0;i3;i+)for (int j=0;jnodeij;coutendl;int getnode(int i,int j)/读取nodeijreturn nodeij;void swap(int i,int j,int m,int n)/交换数组中指定位置的两个元素的数值int temp;temp=nodeij;nodeij=nodemn;nodemn=temp;bool operator =(StateNode &sn)/重载了运算符=，方便后面进行比较int n=0;for (int i=0;i3;i+)for (int j=0;j3;j+)if (nodeij=sn.getnode(i,j)n+;if (n9)return false;else return true;void operator =(StateNode &sn)/重载了运算符=，方便后面对节点进行整体赋值for (int i=0;i3;i+)for (int j=0;jgs=sn.gs;this-hs=sn.hs;this-fs=sn.fs;this-psn=sn.psn;void printstatenode()/将每个节点的内容按照一定格式输出for (int i=0;i3;i+)for (int j=0;j3;j+)coutnodeij ;coutn;protected:private:int node33;void evaluatefunction(StateNode &sn,StateNode &goal)/启发函数，计算某个节点的h(n)值for (int i=0;i3;i+)for (int j=0;j3;j+)if (sn.getnode(i,j)!=goal.getnode(i,j) & sn.getnode(i,j)!=0)for (int m=0;m3;m+)for (int n=0;n3;n+)if (sn.getnode(i,j)=goal.getnode(m,n)sn.hs+=(abs(i-m)+abs(j-n);bool isgoal(StateNode &sn,StateNode &goal)/判断当前节点是否目标节点return sn=goal;bool uninlist(StateNode &sn,list &lsn) /判断当前节点是不是在OPEN表或者CLOSED表中list:iterator iter;for (iter=lsn.begin();iter!=lsn.end();iter+)if (*iter=sn)return false;return true;void addtolist(StateNode &sn,list &lsn,list &lcsn)/根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式list:iterator iter;list:iterator iterc;if (uninlist(sn,lsn) & uninlist(sn,lcsn)for (iter=lsn.begin();iter!=lsn.end() & sn.fs=iter-fs;iter+)lsn.insert(iter,sn);else if(!uninlist(sn,lsn)for (iter=lsn.begin();iter!=lsn.end();iter+)if (*iter=sn)break;if (iter-fssn.fs)*iter=sn;else if (!uninlist(sn,lcsn)for (iterc=lcsn.begin();iterc!=lcsn.end();iterc+)if (*iterc=sn)break;if(iterc-fssn.fs)for (iter=lsn.begin();iter!=lsn.end() & sn.fs=iter-fs;iter+)lsn.insert(iter,*lcsn.erase(iterc);void evaluandadd(StateNode &temsn,StateNode &sn,StateNode &goal,list &lsn,list &lcsn)temsn.gs=sn.gs+1;temsn.hs=0;evaluatefunction(temsn,goal);temsn.fs=temsn.gs+temsn.hs;addtolist(temsn,lsn,lcsn);void expandnode(StateNode &sn,StateNode &goal,list &lsn,list &lcsn)/扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作StateNode temsn;list:iterator iter;for (int i=0;i3;i+)for (int j=0;j0)/向左移动temsn=sn;temsn.swap(i,j,i-1,j);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);if (i0)/向上移动temsn=sn;temsn.swap(i,j,i,j-1);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);if (j2)/向下移动temsn=sn;temsn.swap(i,j,i,j+1);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);int main()StateNode Start,SNMAXNUM,Goal;int i,j=0;list OPEN;list CLOSED;list:iterator iter;list:iterator iterc;Goal.putgoalnode();Start.putstartnode();evaluatefunction(Start,Goal);Start.gs=0;Start.fs=Start.gs+Start.hs;OPEN.push_back(Start);for (iter=OPEN.begin(),i=0;iter!=OPEN.end() &