用盲目搜索技术解决八数码问题.doc

《用盲目搜索技术解决八数码问题.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、用盲目搜索技术解决八数码问题题目在3×3的棋盘，有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：任意给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。算法流程使用宽度优先搜索从初始节点开始，向下逐层对节点进形依次扩展，并考察它是否为目标节点，再对下层节点进行扩展（或搜索）之前，必须完成对当层的所有节点的扩展。再搜索过程中，未扩展节点表OPEN中的节点排序准则是：先进入的节点排在前面，后进入的节点排在

2、后面。宽度优先算法如下：把初始结点S0放入OPEN表中若OPEN表为空，则搜索失败，问题无解取OPEN表中最前面的结点N放在CLOSE表中，并冠以顺序编号n若目标结点，则搜索成功，问题有解若N无子结点，则转2扩展结点N，将其所有子结点配上指向N的放回指针，依次放入OPEN表的尾部，转2源程序#include#include#includeusingnamespacestd;constintROW=3;//行数constintCOL=3;//列数constintMAXDISTAN

3、CE=10000;//最多可以有的表的数目constintMAXNUM=10000;typedefstruct_Node{intdigit[ROW][COL];intdist;//distancebetweenonestateandthedestination一个表和目的表的距离intdep;//thedepthofnode深度//Sothecommentfunction=dist+dep.估价函数值intindex;//pointtothelocationofparent父节点的位置}Node;Nodesrc,dest;//

4、父节表目的表vectornode_v;//storethenodes存储节点boolisEmptyOfOPEN()//open表是否为空{for(inti=0;i

5、_v[index].digit[i][j]!=digit[i][j])returnfalse;}returntrue;}ostream&operator<<(ostream&os,Node&node){for(inti=0;i&rstep_v)//输出每一个遍历的节点深度遍历{rstep_v.push_ba

6、ck(node_v[index]);index=node_v[index].index;while(index!=0){rstep_v.push_back(node_v[index]);index=node_v[index].index;}for(inti=rstep_v.size()-1;i>=0;i--)//输出每一步的探索过程cout<<"Step"<

7、dAssign(Node&node,intindex){for(inti=0;i

8、eif((node_v[i].dist+node_v[i].dep)