人工智能导论 启发式图搜索

《人工智能导论 启发式图搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、(北京)CHINAUNIVERSITYOFPETROLEUM人工智能导论启发式图搜索院系名称：地球物理与信息工程学院专业名称：计算机科学与技术学号：姓名：完成日期2015年6月16日一、过程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)à{},计算f(n,)=g(n,)+h();g(n,

2、)是从s通过n到的耗散值，f(n,)是从s通过n、到目标节点耗散值的估计；·ADD(,OPEN),标记到n的指针。·IFf(n,)

3、处在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();//输入开始节点voidputgoalnode()

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

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

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

7、代码（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;i++){for(intj=0;j<3;j++){node[i][j]=0;}}}voidput

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