八数码问题实验报告

《八数码问题实验报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、八数码问题实验报告一、实验要求：九宫重排问题:在3×3的井子九宫格棋盘上摆有8个牌，分别标有1-8个数码。棋盘上尚有一个空格，允许其周围的将牌向空格移动。这个通过移动将牌就可以变换将牌布局。现给定如下两种布局，一种为初始状态，一种为目标状态，问如何移动将牌，以将初始状态变换为目标状态？二、实验思路：A*算法取g(n)=d(n)，h(n)=w(n)，其中w(n)表示以目标为基准，结点n的状态中不在位将牌的个数。由于从结点n转换成目标结点至少需要w(n)步，所以对任意n，恒有w(n)≤h*(n)。三、实验代码：#include#include

2、h>#include#include#include#definesize3longtotal;typedefcharboard[size][size];boardtarget={1,2,3,8,0,4,7,6,5};//目标状态classNode{public:boarddata;//存放状态Node*parent;//存放父节点地址Node*child[4];//存放子节点地址,最多个Node*next;intf,h,g,how;//how中记录了其父节点如何移动生成该节点Node();intgeth();};Nod

3、e::Node()//构造函数{parent=NULL;next=NULL;for(inti=0;i<4;i++){child[i]=NULL;}h=0;g=0;how=0;f=0;}intNode::geth()//计算h值(h值为每个将牌与其目标位的总和){inth=0;for(inti=0;idata[i][j]&&target[x][y]!=0)h+=abs(x-i)+

4、abs(y-j);returnh;}/***************************************************************/boolcan_solve(Node*start){//搜索前判断是否可解longi,j,k1,k2;for(i=0;idata[i][j]==0){start->data[i][j]=size*size;k1=(size-1-i)+(size-1-j);}if(target[i][j]==0){target[i][j]=size

5、*size;k2=(size-1-i)+(size-1-j);}}for(i=0;idata[i/size][i%size]>start->data[j/size][j%size])k1++;if(target[i/size][i%size]>target[j/size][j%size])k2++;}for(i=0;idata[i][j]==size*size)start->data[i][

6、j]=0;if(target[i][j]==size*size)target[i][j]=0;}return(k1%2)==(k2%2);}Node*head;//判断temp状态是否是目标状态boolgoal(boardtemp){for(inti=0;i

7、data[i][j]==0){x=i;y=j;}}//扩展p所指向的节点voidExpand(Node*p){intx,y;getxy(p,x,y);inti=0;//y!=0(左边有节点)并且how!=4(不是父节点右移得到的),进行左移if(y!=0&&p->how!=4){p->child[i]=newNode;for(intk=0;kchild[i]->data[k][j]=p->data[k][j];p->ch