启发式搜索算法解决八数码问题C语言.doc
word1、程序源代码#include <stdio.h>#include<malloc.h>struct nodeint a33;/用二维数组存放8数码 int hx;/函数hx的值，表示与目标状态的差距struct node *parent;/指向父结点的指针struct node *next;/指向链表中下一个结点的指针;/-hx函数-/int hx(int s33)/函数说明：计算s与目标状态的差距值int i,j;int hx=0;int sg33=1,2,3,8,0,4,7,6,5;for(i=0;i<3;i+)for(j=0;j<3;j+)if(sij!=sgij)hx+; return hx;/-hx函数end-/-extend扩展函数-/struct node *extend(node *ex) /函数说明：扩展ex指向的结点，并将扩展所得结点组成一条/单链表，head指向该链表首结点，并且作为返回值int i,j,m,n; /循环变量int t; /临时替换变量int flag=0; int x33;/临时存放二维数组struct node *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+)if(ex->aij=0)flag=1;break;if(flag=1)break; for(m=0;m<3;m+)/将ex->a赋给xfor(n=0;n<3;n+)xmn=ex->amn;/根据0的位置的不同，对x进展相应的变换/情况1 if(i-1>=0)t=xij;xij=xi-1j;xi-1j=t; flag=0;for(m=0;m<3;m+)/将x赋给a for(n=0;n<3;n+) if(xmn=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->amn=xmn; q->parent=ex; q->hx=hx(q->a); q->next=NULL; p->next=q; p=p->next; /情况2 for(m=0;m<3;m+)/将ex->a重新赋给x，即复原xfor(n=0;n<3;n+)xmn=ex->amn;if(i+1<=2)t=xij;xij=xi+1j;xi+1j=t; flag=0;for(m=0;m<3;m+) for(n=0;n<3;n+) if(xmn=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->amn=xmn; 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+)xmn=ex->amn;if(j-1>=0) t=xij;xij=xij-1;xij-1=t;flag=0;for(m=0;m<3;m+) for(n=0;n<3;n+) if(xmn=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->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，即复原xfor(n=0;n<3;n+)xmn=ex->amn;if(j+1<=2) t=xij;xij=xij+1;xij+1=t; flag=0;for(m=0;m<3;m+) for(n=0;n<3;n+) if(xmn=ex->parent->amn) flag+; if(flag!=9) q=(node *)malloc(sizeof(node); for(m=0;m<3;m+) 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链表的结点依次插入到open链表相应的位置， /使open表中的结点按从小到大排序。函数返回open指针node *p,*q;/p、q均指向open表中的结点，p指向q所指的前一个结点int i,j;int flag=0;if(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 /或者第二个结点的位置 q->next=head; head=head->next; q=q->next; q->next=NULL; p=open;p=open;q=open->next; /end ifwhile(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的一个结点插入到链表中非表尾的位置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->next;q->next->next=NULL;/if/whilereturn open;/insert/-insert函数 end-/-main-/ void main()int i,j;node s0; node *open,*close;node *p,*q;node *newlist;printf("请输入初始状态的8数码按每行从左往右依次输入,用0表示空格：n"); for(i=0;i<3;i+)for(j=0;j<3;j+)scanf("%d",&s0.aij); s0.parent=(node *)malloc(sizeof(node);s0.parent->hx=9; s0.hx=hx(s0.a);open=&s0;p=&s0;if(open->hx=0)printf("该状态已为最终状态！n");return;q=&s0;close=&s0;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("n搜索成功！n");break;newlist=extend(q);/对close表最后一个结点进展扩展，扩展得到的链表接到open表尾open=insert(open,newlist);/将扩展的结点按顺序插入到open表中 p=close; printf("择优搜索过程如下：n");while(p!=NULL) for(i=0;i<3;i+)for(j=0;j<3;j+) printf("%d ",p->aij);printf("n");printf("n");p=p->next;2、 程序运行结果截图截图1： 初始态为：2 8 31 47 6 5运行结果如右图所示： 截图2：初始状态为 2 8 3 时，程序运行结果如下： 1 6 4 7 5 9 / 9
