启发式图搜索过程姓名：学号：启发式图搜索过程一、过程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) {m i} , 计算f(n, m i) = g(n, m i) + h(m i); g(n, m i)是从s通过n 到m i的耗散值，f(n, m i)是从s通过n、m i到目标节点耗散值的估计；·ADD(m j , OPEN), 标记m i到n的指针。
·IF f(n, m k)<f(m k) THEN f(m k) := f(n, m k),标记m k到n的指针；比较f(n, m k)和f(m k),f(m k)是扩展n之前计算的耗散值。
·IF f(n, m l)<f(m1) THEN f(m l) := f(n, m l),标记m l到n的指针，ADD(m l,OPEN);当f(n, m l)<f(m l)时，把m l重放回OPEN中，不必考虑修改到其子节点的指针。
⑦ OPEN中的节点按f值从小到大排列；⑧ GO LOOP。
二、最佳图搜索算法A*：当在算法A的评价函数中，使用的启发函数h(n)是处在h*(n)的下界范围，即满足h(n)<=h*(n)时，则把这个算法称为算法A*。
在下面解决八数码问题的程序中，采用h(n)=P(n), P(n)定义为每一个将牌与其目标位置之间的距离的总和。
三、算法实现（1）数据结构class StateNode{public:int gs,hs,fs; //分别表示算法中的g(n)、h(n)、f(n) StateNode *psn; //一个指向扩展出它的父节点的指针StateNode(); //构造函数，初始化节点void putstartnode(); //输入开始节点void putgoalnode(); //输入目标节点int getnode(int i,int j); //读取node[i][j]void swap(int i,int j,int m,int n);//交换数组中指定位置的两个元素的数值bool operator ==(StateNode &sn);//重载了运算符==，方便后面进行比较void operator =(StateNode &sn);//重载了运算符=，方便后面对节点进行整体赋值void printstatenode();//将每个节点的内容按照一定格式输出private:int node[3][3]; //八数码的每个节点用一个二维数组存储};void evaluatefunction(StateNode &sn,StateNode &goal);//启发函数，计算某个节点的h(n)值bool isgoal(StateNode &sn,StateNode &goal);//判断当前节点是否目标节点bool uninlist(StateNode &sn,list<StateNode> &lsn);//判断当前节点是不是在OPEN表或者CLOSED表中void addtolist(StateNode &sn,list<StateNode> &lsn,list<StateNode> &lcsn);//根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式void expandnode(StateNode &sn,StateNode &goal,list<StateNode> &lsn,list<StateNode> &lcsn);//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作list<StateNode> OPEN; //使用STL中的list类型来存放OPEN 表list<StateNode> CLOSED; //使用STL中的list类型来存放CLOSED表（2）运行过程演示：四、程序代码（C++）：#include <iostream>#include <list>#include <math.h>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;i<3;i++){for (int j=0;j<3;j++){node[i][j]=0;}}}void putstartnode(){cout<<"请输入目标状态！（空闲的格子用0表示）"<<endl;for (int i=0;i<3;i++){for (int j=0;j<3;j++){cin>>node[i][j];}}cout<<endl;}void putgoalnode(){cout<<"请输入初始状态！（空闲的格子用0表示）"<<endl;for (int i=0;i<3;i++){for (int j=0;j<3;j++){cin>>node[i][j];}}cout<<endl;}int getnode(int i,int j) //读取node[i][j]{return node[i][j];}void swap(int i,int j,int m,int n) //交换数组中指定位置的两个元素的数值{int temp;temp=node[i][j];node[i][j]=node[m][n];node[m][n]=temp;}bool operator ==(StateNode &sn) //重载了运算符==，方便后面进行比较{int n=0;for (int i=0;i<3;i++){for (int j=0;j<3;j++){if (node[i][j]==sn.getnode(i,j)){n++;}}}if (n<9){return false;}else return true;}void operator =(StateNode &sn) //重载了运算符=，方便后面对节点进行整体赋值{for (int i=0;i<3;i++){for (int j=0;j<3;j++){node[i][j]=sn.getnode(i,j);}}this->gs=sn.gs;this->hs=sn.hs;this->fs=sn.fs;this->psn=sn.psn;}void printstatenode() //将每个节点的内容按照一定格式输出{for (int i=0;i<3;i++){for (int j=0;j<3;j++){cout<<node[i][j]<<" ";}cout<<"\n";}}protected:private:int node[3][3];};void evaluatefunction(StateNode &sn,StateNode &goal) //启发函数，计算某个节点的h(n)值{for (int i=0;i<3;i++){for (int j=0;j<3;j++){if (sn.getnode(i,j)!=goal.getnode(i,j) && sn.getnode(i,j)!=0){for (int m=0;m<3;m++){for (int n=0;n<3;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<StateNode> &lsn){ //判断当前节点是不是在OPEN表或者CLOSED表中list<StateNode>::iterator iter;for (iter=lsn.begin();iter!=lsn.end();iter++){if (*iter==sn){return false;}}return true;}void addtolist(StateNode &sn,list<StateNode> &lsn,list<StateNode> &lcsn){ //根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式list<StateNode>::iterator iter;list<StateNode>::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->fs>sn.fs) {*iter=sn;}}else if (!uninlist(sn,lcsn)){for (iterc=lcsn.begin();iterc!=lcsn.end();iterc++){if (*iterc==sn) {break;}}if(iterc->fs>sn.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<StateNode> &lsn,list<StateNode> &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<StateNode> &lsn,list<StateNode> &lcsn){ //扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作StateNode temsn;list<StateNode>::iterator iter;for (int i=0;i<3;i++){for (int j=0;j<3;j++){if (sn.getnode(i,j)==0){if (i>0) //向左移动{temsn=sn;temsn.swap(i,j,i-1,j);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);}if (i<2) //向右移动{temsn=sn;temsn.swap(i,j,i+1,j);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);}if (j>0) //向上移动{temsn=sn;temsn.swap(i,j,i,j-1);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);}if (j<2) //向下移动{temsn=sn;temsn.swap(i,j,i,j+1);temsn.psn=&sn;evaluandadd(temsn,sn,goal,lsn,lcsn);}}}}}int main(){StateNode Start,SN[MAXNUM],Goal;int i,j=0;list<StateNode> OPEN;list<StateNode> CLOSED;list<StateNode>::iterator iter;list<StateNode>::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() && i<MAXNUM;iter=OPEN.begin(),i++) {if (OPEN.empty()) {return 0;}SN[i]=OPEN.front();if (isgoal(SN[i],Goal)){cout<<"搜索过程如下所示："<<endl;for (StateNode *tempsn=&SN[i];!(*tempsn==Start);tempsn=tempsn->psn,j++){cout<<"第"<<j<<"步搜索："<<endl;tempsn->printstatenode();cout<<endl;}cout<<"第"<<j<<"步搜索："<<endl;Start.printstatenode();return 1;}OPEN.pop_front();CLOSED.push_back(SN[i]);if (CLOSED.size()>MAXNUM){cout<<"该初始节点不可扩展至目标节点！"<<endl;return 0;}expandnode(SN[i],Goal,OPEN,CLOSED);}return 0;（注：可编辑下载，若有不当之处，请指正，谢谢!）。
