八数码问题实验报告.doc

八数码问题实验报告一、 实验要求：九宫重排问题: 在33的井子九宫格棋盘上摆有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#include#include#include#define size 3long total;typedef char boardsizesize;board target = 1,2,3,8,0,4,7,6,5;/ 目标状态class Nodepublic:board data;/存放状态Node *parent;/存放父节点地址Node *child4;/存放子节点地址,最多个Node *next;int f,h,g,how;/how中记录了其父节点如何移动生成该节点Node();int geth();Node:Node()/构造函数parent=NULL;next=NULL;for(int i=0;i4;i+)childi=NULL;h=0;g=0;how=0;f=0;int Node:geth()/计算h值(h值为每个将牌与其目标位的总和)int h=0;for(int i=0;isize;i+)for(int j=0;jsize;j+)for(int x=0;xsize;x+)for(int y=0;ydataij&targetxy!=0)h+=abs(x-i)+abs(y-j);return h;/*/bool can_solve(Node *start) / 搜索前判断是否可解long i,j,k1,k2;for (i=0; isize; i+) for (j=0; jdataij=0) start-dataij = size*size;k1 = (size-1-i) + (size-1-j);if(targetij=0)targetij = size*size;k2 = (size-1-i) + (size-1-j);for (i=0; isize*size; i+) for (j=i+1; jdatai/sizei%size start-dataj/sizej%size) k1+;if (targeti/sizei%size targetj/sizej%size) k2+;for (i=0; isize; i+) for (j=0; jdataij=size*size) start-dataij=0;if (targetij=size*size) targetij=0;return (k1%2)=(k2%2);Node *head;/判断temp状态是否是目标状态bool goal(board temp)for(int i=0;isize;i+)for(int j=0;jsize;j+)if(tempij!=targetij)return false;return true;/返回所在的坐标void getxy(Node *temp,int &x,int &y)for(int i=0;isize;i+)for(int j=0;jdataij=0)x=i;y=j;/扩展p所指向的节点void Expand(Node *p)int x,y;getxy(p,x,y);int i=0;/y!=0(左边有节点)并且how!=4(不是父节点右移得到的),进行左移if(y!=0&p-how!=4)p-childi=new Node;for(int k=0;ksize;k+)for(int j=0;jchildi-datakj=p-datakj;p-childi-dataxy=p-dataxy-1;p-childi-dataxy-1=0;p-childi-parent=p;p-childi-h=p-childi-geth();p-childi-g=p-g+1;p-childi-how=1;p-childi-f=p-childi-h+p-childi-g;i+;total+;if(y!=2&p-how!=1)p-childi=new Node;for(int k=0;ksize;k+)for(int j=0;jchildi-datakj=p-datakj;p-childi-dataxy=p-dataxy+1;p-childi-dataxy+1=0;p-childi-parent=p;p-childi-h=p-childi-geth();p-childi-g=p-g+1;p-childi-how=4;p-childi-f=p-childi-h+p-childi-g;i+;total+;if(x!=0&p-how!=3)p-childi=new Node;for(int k=0;ksize;k+)for(int j=0;jchildi-datakj=p-datakj;p-childi-dataxy=p-datax-1y;p-childi-datax-1y=0;p-childi-parent=p;p-childi-h=p-childi-geth();p-childi-g=p-g+1;p-childi-how=2;p-childi-f=p-childi-h+p-childi-g;i+;total+;if(x!=2&p-how!=2)p-childi=new Node;for(int k=0;ksize;k+)for(int j=0;jchildi-datakj=p-datakj;p-childi-dataxy=p-datax+1y;p-childi-datax+1y=0;p-childi-parent=p;p-childi-h=p-childi-geth();p-childi-g=p-g+1;p-childi-how=3;p-childi-f=p-childi-h+p-childi-g;i+;total+;/插入open表for(int j=0;jf=p-childj-f)Node *temp=head;head=p-childj;p-childj-next=temp;elseNode *temp=head;Node *oldtemp=temp;while(temp!=NULL&temp-fchildj-f)oldtemp=temp;temp=temp-next;if(temp=NULL|oldtemp-next=NULL)oldtemp-next=p-childj;p-childj-next=NULL;elseoldtemp-next=p-childj;p-childj-next=temp;p-next=head;void main()int i,j,k;double totaltime;double fenzhi=0;double fenmu=0;int cs;char ch;/scanf(%ld, &cs);cs = 1;while (true)total=1;/输入原始状态Node begin;Node *start=&begin;srand(unsigned)time(NULL); /随机时间种子int a9;for(i=0;isize;i+)for(j=0;jdataij=k; ai*size+j=k; for(k=0;kdataij=ak) j-; break; printf(n初始状态为:n);for(int i=0;isize;i+)for(int j=0;jdataij);printf(n);printf(是否要修改目标状态?(y/n):n);scanf( %c,&ch);if(ch=Y|ch=y)printf(请输入新的目标状态:n);for (i=0;isize;i+)for(j=0;jg=0;start-h=start-geth();start-how=0;start-f=start-h+start-g;head=start;/加入open表,head为头指针while(true)if(goal(head-data)break;/将tempn(原来的head)从open表中删除Node *tempn=head;head=head-next;/扩展tempnExpand(tempn);fenmu=fenmu+1;/对open表进行排序i=0;fenzhi=fenzhi+1;while(tempn-childi!=NULL&i4)i+;fenzhi=fenzhi+1;printf(n%2.10f ,totaltime);totaltime=(double(clock()-totaltime)/CLOCKS_PER_SEC;printf(n%2.10f n,double(clock();fenzhi=fenzhi/fenmu;j=-1;/输出结果while(head!=NULL)for(int i=0;isize;i+)for(int j=0;jdataij);printf(n);head=head-parent;printf( n);j+;printf(总共%d步！n,j);printf( 运行时间: %2.8f seconds