启发式图搜索过程.docx

《启发式图搜索过程.docx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、姓名：学号：启发式图搜索过程启发式图搜索过程一、过程A描述：①OPEN:=(s),f(s):=g(s)+h(s);②LOOP:IFOPEN=()THENEXIT(FAIL);③n:=FIRST(OPEN);④IFGOAL(n)THENEXIT(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

2、,OPEN),标记mi到n的指针。·IFf(n,mk)

3、n)是处在h*(n)的下界范围，即满足h(n)<=h*(n)时，则把这个算法称为算法A*。在下面解决八数码问题的程序中，采用h(n)=P(n),P(n)定义为每一个将牌与其目标位置之间的距离的总和。三、算法实现（1）数据结构classStateNode{public:intgs,hs,fs;//分别表示算法中的g(n)、h(n)、f(n)StateNode*psn;//一个指向扩展出它的父节点的指针StateNode();//构造函数，初始化节点voidputstartnode();//输入开始节点voidp

4、utgoalnode();//输入目标节点intgetnode(inti,intj);//读取node[i][j]voidswap(inti,intj,intm,intn);//交换数组中指定位置的两个元素的数值booloperator==(StateNode&sn);//重载了运算符==，方便后面进行比较voidoperator=(StateNode&sn);//重载了运算符=，方便后面对节点进行整体赋值voidprintstatenode();//将每个节点的内容按照一定格式输出private:intno

5、de[3][3];//八数码的每个节点用一个二维数组存储};voidevaluatefunction(StateNode&sn,StateNode&goal);//启发函数，计算某个节点的h(n)值boolisgoal(StateNode&sn,StateNode&goal);//判断当前节点是否目标节点booluninlist(StateNode&sn,list&lsn);//判断当前节点是不是在OPEN表或者CLOSED表中voidaddtolist(StateNode&sn,lis

6、t&lsn,list&lcsn);//根据当前扩展到的节点的类型（mj,mk,ml）选择不同的操作方式voidexpandnode(StateNode&sn,StateNode&goal,list&lsn,list&lcsn);//扩展节点，计算节点的评价函数值，根据新的节点的类型选择不同的操作listOPEN;//使用STL中的list类型来存放OPEN表listCLOSED;

7、//使用STL中的list类型来存放CLOSED表（2）运行过程演示：四、程序代码（C++）：#include#include#includeusingnamespacestd;#defineMAXNUM1000classStateNode//这是一个节点类型的类，定义了与节点相关的信息及函数{public:intgs,hs,fs;StateNode*psn;StateNode(){gs=0;hs=0;fs=gs+hs;psn=0;for(inti=0;i<3;

8、i++){for(intj=0;j<3;j++){node[i][j]=0;}}}voidputstartnode(){cout<<"请输入目标状态！（空闲的格子用0表示）"<>node[i][j];}}cout<