《启发式搜索算法解决八数码问题.doc》由会员分享，可在线阅读，更多相关《启发式搜索算法解决八数码问题.doc（10页珍藏版）》请在三一文库上搜索。
1、1、程序源代码include <>#include<> struct nodeint 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;i<3;i+)for(j=0;j<3;j+)if (si j
2、 !=sgi j)hx+;return hx;/hx 函数 end/extend 扩展函 数/struct node *extend(node *ex) /函数说明：扩展ex指向的结点，并将扩展所得结点组成一条/单链表，head指向该链表首结点，并且作为返回值intn; 循环变量int t;临时替换变量int flag=0;int x;/临时存放二维数组struct node *p, *q, *head;head=(node *)malloc(sizeof(node);/headp=head;q二head;head->next=NULL; /初始化 for(i=0;i<3;i+)/
3、找到二维数组中0的位宜for(j=0;j<3;j+) if(ex->alij=0) flag=l; break;if(flag=l)break;for (m=0: m<3; m*) /将 ex->a 赋给 x for (n=0;n<3;n+)xmn=ex->amLn;根据0的位宜的不同，对X进行相应的变换情况1if(i-l>=0)t=xij ;xi j二xi-1 j ;Xi-lj=t; flag=0;for (m=0; m<3: m+) /将 x 赋给 afor(n=0;n<3;n+)if(xmn=ex->parent->amL
4、n) flag 卄；if(flag!=9)q=(node *)malloc(sizeof(node); for (m=0;m<3;m-r+) /将 x 赋给 a for(n=0;n<3;n+) q->amn二xm n; q->parent=ex; q->hx二hx(q->a); q->next=NULL; p->next=q; p=p->next;情况2for (m=0;m<3;m+) /将 ex->a 重新赋给 x,即还原 x for (n=0;n<3;n+)xmn=ex->amn;if(i+l<=2)t二x
5、i j ;xi j二xi+l j ;xi+l j二t; flagO;for(m=0;m<3;m+)for (n=0;n<3;n+)if(xEmn=ex->parent>amLn) flag 卄；if (flag!=9)q=(node *)malloc(sizeof(node); for (m=0;m<3;m+) /将 x 賦给 a for (n=0;n<3;n 卄) q->am n=xm n; q->parent=ex; q->hx二hx(q->a); q->next=NULL; p->next=q; p=p->ne
6、xt;情况3for (m=0;m<3;m+) 将 ex->a 重新赋给 x,即还原 x for (n=0;n<3;n+)xmn=ex->amn;if(j-l>=0)t=xi j ;xi j二xi j-l ;Xi j-l=t; flag=0;for(m=0;m<3;m+)for (n=0;n<3;n+) if(xEmn=ex->parent>amn) flag 卄；if(flag!=9)q二(node *)malloc(sizeof(node); for (m=0;m<3;m+)/将 x 赋给 a for(n=0;n<3;n+)q
7、->amn=xmn; q->parent=ex; q->hx二hx(q->a);q->next=NULL;p->next=q; p=p->next;情况4for (m=0;m<3;m+) /将 ex->a 重新赋给 x,即还原 x for (n=0;n<3;n+)xmn=ex->amn;if(j+l<=2)t=xi j ;xi j二xi j+1 ;xij+l=t;flag=0;for(m=0;m<3;m+)for (n=0;n<3;n 卄)if(xEmn=ex->parent->amn)flag 卄
8、；if (flag!=9)q=(node *)malloc(sizeof(node); for (m=0;m<3;m-r+)for (n=0;n<3;n+) q->amn二xmn;q->parent=ex;q->hx二hx(q->a); q->next=NULL; p->next=q; p=p->next;head=head->next;return head;/extend 函数 end/insert 函数/node* insert(node *open, node * head) /函数说明：将head链表的结点依次插入到。pm链
9、表相应的位置,/使open表中的结点按从小到大排序。函数返回open指针node *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->next=NULL;再插入第二个结点if (head->hx<open->hx)/插入到首结点位置open=head;head=head->next;open->next=q;else或者第二个结点的位置
10、q->next=head;head=head->next;q=q->next;q->next=NULL;p=open;p二open;q=open->next; /end ifwh 订e(head!=NULL)q=open;if (head->hx<open->hx) /插入到表头open=head;head=head->next;open->next=q;continue;else q=q->next;p=open; /否则，q指像第二个结点，p指向q前一个结点while (q->next! =NULL) /将head的一
11、个结点插入到链表中(非表尾的位置) if(q->hx<head->hx)q二q_>next; p=p->next;elsep->next=head; head=head->next; p->next->next=q; break; if (q->next=NULL)/将head的一个结点插入到表尾if(q->hx>head->hx)p->next=head;head=head->next;p->next->next=q;elseq->next=head;head=head->nex
12、t;q->next->next=NULL;/if/wh 订 ereturn open;/insert/insert 函数 end/OHMWMMvoid mainOint i, j；node sO;node *open, *close;node *p,*q;node *newlist;printfC请输入初始状态的8数码(按每行从左往右依次输入，用0表示空格)：)； for(i=0;i<3;i +)for(j=0;j<3;j+)scanf &i j);=(node *)malloc(sizeof(node);>hx二9;=hx;open二&s0;p=
13、&sO;if (open->hx=0)printf ("该状态已为最终状态！ n");return;q=&sO;close二&s0;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-
14、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;i<3;i+)for(j=0;j<3;j+)printf C%d ”, p->ai j); printf("n");printf(*n*);p=p->next;2程序运行结果截图截图1： r 初始态 217为345运行结果 右图所示10请输入初始状态的&数码（按每行从左往右依次输入）2S48342171072860176217撰索成功！:怪优捜索过程如下匕s0Press any key to continue截图2:初始状态为2178 3时，程序运行结果如下:6 45 D:M S Dev98Bin Debu gV 黴码赵贰请输入初始状态的8数码（按每行从左往右依次输入用©表示空格厂28314705诒籠蠶第B程如下;8 36 40 50 2 318 4? 6 5Press any kwy to continue