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

1、1、程序源代码 include #include struct node int a33;用二维数组存放8数码 int hx;/函数h (x)的值，表示与目标状态的差距 struct node *parent;/指向父结点的指针 struct node *next;/指向链表中F个结点的指针 ; /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;i+)

2、/找到二维数组中0的位宜 for(j=0;jalij=0) flag=l; break; if(flag=l) break; for (m=0: ma 赋给 x for (n=0;namLn; 根据0的位宜的不同，对X进行相应的变换 情况1 if(i-l=0) t=xij ;xi j二xi-1 j ;Xi-lj=t; flag=0; for (m=0; m3: m+) /将 x 赋给 a for(n=0;nparent-amLn) flag 卄； if(flag!=9) q=(node *)malloc(sizeof(node); for (m=0;m3;m-r+) /将 x 赋给 a for

3、(n=0;namn二xm n; q-parent=ex; q-hx二hx(q-a); q-next=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 ;xi j二xi+l j ;xi+l j二t; flagO; for(m=0;m3;m+) for (n=0;nparentamLn) flag 卄； if (flag!=9) q=(node *)malloc(sizeof(node); for (m=0;m3;m+) /将 x 賦给 a for (n=0;nam n=xm

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

5、q-hx二hx(q-a); q-next=NULL; p-next=q; p=p-next; 情况4 for (m=0;ma 重新赋给 x,即还原 x for (n=0;namn; if(j+l=2) t=xi j ;xi j二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-r+) for (n=0;namn二xmn; q-parent=ex; q-hx二hx(q-a); q-next=N

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

7、ead; q=head; head二head-next; q-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 if wh 订e(head!=NULL) q=open; if (head-hxhx) /插入到表头 open=head; head=head-next; open

8、-next=q; continue; else q=q-next;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; if (q-next=NULL)/将head的一个结点插入到表尾 if(q-hxhead-hx) p-next=head; head=head-next; p-next-next=q; else q-n

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

10、; return; q= close二 open二NULL; newlist=extend(q) ;/newlist指向新扩展出来的链表 open=insert (open, newlist);/将扩展岀来的结点插入到open表中 wh 订 e(l) q-next=open;/q始终指向close表尾结点。将open表的第一个元素加到close 表 open=open-next; q=q-next; q-next=NULL; if (q-hx=0) printf (n 搜索成功！ n); break; newlist=extend(q) ;/对close表最后一个结点进行扩展，扩展得到的链表接到 open表尾 open=insert (open, newlist) ;/将扩展的结点按顺序插入到open表中p=close; printfC择优搜索过程如下：n); while(p!=NULL) for(i=0;i3;i+)