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

1、 1、程序源代码 ttinclude #include struct node int a33;/用二维数组存放8数码 int hx; 函数h (x)的值，表示与目标状态的差距struct n ode *pare向父结点的指针 struct node *next;/ 指 向链表中下一个结点的指针 ； /hx 函数/ int hx(int s33) /函数说明：计算s与目标状态的差距值 int i, j; int hx二0; int sg3 3二1,2, 3, 8, 0,4, 7, 6, 5; for(i=0;i3;i+) for(j=0;jnext=NULL; / 初始化 for(i=0;i3

2、;i+)/找到二维数组中0的位置 for(j=0;jaij=0) (flag=l; break; if(flag=l) break; for (m=0; ma 赋给 x for(n=0;nam n; /根据0的位置的不同，对x进行相应的变换 /情况1 if(i-l=0) ( flag=0; for (m=0; m3; m+) / 将 x 赋给 a for (n=0; nparent-amn) flag+; if(flag!=9) q= (node *)malloc(sizeof(node); for (m=0; mamjn=xmn; q-parent二ex; q-hx二hx(q-a); q-n

3、ext=NULL; p-next=q; p二p_next; ) /情况2 for (m=0;ma 重新赋给 x,即还原 x for(n=0;namn; if(i+l=2) ( t=xi j ;xij=xi+l j;xi+lj=t; flag=0; for(m二0;m3;m+) for(n=0;nparent-冶m n) flag+; if(flag!=9) q= (node *)malloc(sizeof(node); for (m=0; m3; m+) / 将 x 赋给 a for(n=0;na mJ n =x mJ Ln; q-parent二ex; q-hx二hx(q-a); q-next

4、=NULL; p-next二q; p=p-next; ) /情况3 for(m=0;ma重新赋给x,即还原x for(n=0;namJn; if(j-l=0) ( t=xi j ;xij=xi j-1 ;Xij-l=t; flag=0; for(m=0;m3;m+) for(n=0;nparent-amn) flag+； if(flag!=9) q= (node *)malloc(sizeof(node); for (m=0; m3; m+) / 将 x 赋给 a for(n=0;namn=xmn; q-parent=ex; q-hx二hx(q-a); q-next=NULL; p-next二

5、q; p=p-next; /情况 4 for(m=0;ma 重新赋给 x,即还原 x for (n=0;na m n; if (j+l=2) t=xij ;xij=xij+l ;xi j+1二t; flag=0; for(m=0;m3;m+) for(n=0;nparent-amJn) flag+; if(flag!=9) ( q= (node *)malloc(sizeof(node); for(m=0;m3;m+) for(n=0;namn=xmn; q-parent=ex; q-hx二hx(q-a); q-next=NULL; p_next二q; p二p_next; head=head-

6、next; return head; /ext end 函数 end/ /insert 函数 / node* insert(node *open,node * head) /函数说明：将head链表的结点依次插入到open链表相应的位置， /使open表屮的结点按从小到大排序。函数返回open指针node *p, *q；/p、q 均指向open表屮的结点，p指向q所指的前一个结点int i, j; int flag=0; 辻(open=NULL)/初始状态，open表为空 /首先将head表第一个结点直接放入open表中 open=head; q二head; head=head-next; q

7、-next二NULL; /再插入第二个结点 if(head-hxhx) /插入到首结点位置 open二head; head=head-next; open-next二q; else /或者第二个结点的位置 q-next=head; head=head-next; q二q_next; q-next二NULL; p二open; p=open; q=open-next; /end 辻 while(head!二NULL) q二open; 辻(head-hxhx) / 插入到表头 open二head; head=head-next; open-next二q; continue; else q=q-nex

8、t;p=open; /否则，q指像第二个结点，p指向q前一个结点 while （q-next!=NULL）/将head的一个结点插入到链表中（非表尾的位置）（ if (q-hxhx) q=q-next; p=p-next; else p-next二head; head=head-next; p-next-next=q; break; 辻(q-next=NULL) /将head的一个结点插入到表尾 if (q-hxheadhx) p-next=head; head=head-next; p-next-next=q; else q-next=head; head二head-next; q-next

9、-next二NULL; /if /while return open; /insert /insert 函数 end/ /main/ void main() int i, j； node sO; node *open，*close; node *p,*q； node *newlist; printf (“请输入初始状态的8数码(按每行从左往右依次输入，用0表不空格)：n); for(i=0;i3;i+) for(j=0;jhx=9; sO. hx二hx(sO. a); open二 p二 if (open-hx=0) printf (该状态已为最终状态！ rT); return; ) q= cl

10、ose二 open二NULL; newlist=extend(q) ;/newlist 指向新扩展出来的链表 open=insert(open, newlist) ;/ 将扩展出来的结点插入到open表中 while (1) q-next=open;/q始终指向close表尾结点。将open表的第一个元素加到close表 open=open-next; q=q-next; q-next二NULL; if(q-hx=0) printf Cn 搜索成功！ n)； break; newlist=extend(q) ;/对close表最后一,个结点进行扩展，扩展得到的链表接到open表尾 open=insert (open, newlist) ;/将扩展的结点按顺序插入到open表屮 p=close