启发式搜索算法解决八数码问题(C语言).doc

《启发式搜索算法解决八数码问题(C语言).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、`1、程序源代码#include#includestructnode{inta[3][3];//用二维数组存放8数码inthx;//函数h（x）的值，表示与目标状态的差距structnode*parent;//指向父结点的指针structnode*next;//指向链表中下一个结点的指针};//------------------hx函数-------------------//inthx(ints[3][3]){//函数说明：计算s与目标状态的差距值inti,j;inthx=0;intsg[3][3]={1,2,3,8,0,4,7,6,5

2、};for(i=0;i<3;i++)for(j=0;j<3;j++)if(s[i][j]!=sg[i][j])hx++;returnhx;}//-------------hx函数end----------------------////-------------extend扩展函数----------------//structnode*extend(node*ex){//函数说明：扩展ex指向的结点，并将扩展所得结点组成一条//单链表，head指向该链表首结点，并且作为返回值inti,j,m,n;//循环变量intt;//临时替换变量intflag=0;intx[3][3];

3、//临时存放二维数组structnode*p,*q,*head;head=(node*)malloc(sizeof(node));//headp=head;q=head;head->next=NULL;//初始化for(i=0;i<3;i++)//找到二维数组中0的位置{for(j=0;j<3;j++)Word文档`if(ex->a[i][j]==0){flag=1;break;}if(flag==1)break;}for(m=0;m<3;m++)//将ex->a赋给xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];//根据0的位置的不同，对x进行相应的

4、变换//情况1if(i-1>=0){t=x[i][j];x[i][j]=x[i-1][j];x[i-1][j]=t;flag=0;for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n])flag++;if(flag!=9){q=(node*)malloc(sizeof(node));for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);q->next=NULL;p->next=

5、q;p=p->next;}}//情况2for(m=0;m<3;m++)//将ex->a重新赋给x，即还原xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];Word文档`if(i+1<=2){t=x[i][j];x[i][j]=x[i+1][j];x[i+1][j]=t;flag=0;for(m=0;m<3;m++)for(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n])flag++;if(flag!=9){q=(node*)malloc(sizeof(node));for(m=0;m<3;m++)//将x赋给afo

6、r(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);q->next=NULL;p->next=q;p=p->next;}}//情况3for(m=0;m<3;m++)//将ex->a重新赋给x，即还原xfor(n=0;n<3;n++)x[m][n]=ex->a[m][n];if(j-1>=0){t=x[i][j];x[i][j]=x[i][j-1];x[i][j-1]=t;flag=0;for(m=0;m<3;m++)for(n=0;n<3;n++)if(x[m][n]==ex->parent->a[m][n]

7、)flag++;if(flag!=9){q=(node*)malloc(sizeof(node));for(m=0;m<3;m++)//将x赋给afor(n=0;n<3;n++)q->a[m][n]=x[m][n];q->parent=ex;q->hx=hx(q->a);Word文档`q->next=NULL;p->next=q;p=p->next;}}//情况4for(m=0;m<3;m++)//将ex->a重新赋给x，即还原xfor(n=0;n<3;n++)x[m][n]=ex->a[m