啟發(fā)式搜索算法解決八數(shù)碼問(wèn)題C語(yǔ)言

1、1、程序源代碼#include <stdio.h>#include<malloc.h>struct nodeint a33;/用二維數(shù)組存放8數(shù)碼 int hx;/函數(shù)h（x）的值，表示與目標(biāo)狀態(tài)的差距struct node *parent;/指向父結(jié)點(diǎn)的指針struct node *next;/指向鏈表中下一個(gè)結(jié)點(diǎn)的指針;/-hx函數(shù)-/int hx(int s33)/函數(shù)說(shuō)明：計(jì)算s與目標(biāo)狀態(tài)的差距值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(s

2、ij!=sgij)hx+; return hx;/-hx函數(shù)end-/-extend擴(kuò)展函數(shù)-/struct node *extend(node *ex) /函數(shù)說(shuō)明：擴(kuò)展ex指向的結(jié)點(diǎn)，并將擴(kuò)展所得結(jié)點(diǎn)組成一條/單鏈表，head指向該鏈表首結(jié)點(diǎn)，并且作為返回值int i,j,m,n; /循環(huán)變量int t; /臨時(shí)替換變量int flag=0; int x33;/臨時(shí)存放二維數(shù)組struct node *p,*q,*head; head=(node *)malloc(sizeof(node);/headp=head;q=head;head->next=NULL;/初始化for(i=0;

3、i<3;i+)/找到二維數(shù)組中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;/根據(jù)0的位置的不同，對(duì)x進(jìn)行相應(yīng)的變換/情況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+;

4、 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;

5、 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->

6、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->

7、;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&l

8、t;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函數(shù)end-/-insert函數(shù)-/ node* insert(node *open,node * head) /函數(shù)說(shuō)明：將head鏈表的結(jié)點(diǎn)依次插入到open鏈表相應(yīng)的位置， /使open表中的結(jié)點(diǎn)按從小到大排序。函數(shù)返回open指針node *p,*q;/p、q均

9、指向open表中的結(jié)點(diǎn)，p指向q所指的前一個(gè)結(jié)點(diǎn)int i,j;int flag=0;if(open=NULL)/初始狀態(tài)，open表為空 /首先將head表第一個(gè)結(jié)點(diǎn)直接放入open表中open=head;q=head; head=head->next;q->next=NULL; /再插入第二個(gè)結(jié)點(diǎn) if(head->hx<open->hx)/插入到首結(jié)點(diǎn)位置open=head;head=head->next;open->next=q; else /或者第二個(gè)結(jié)點(diǎn)的位置 q->next=head; head=head->next; q=q

10、->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指像第二個(gè)結(jié)點(diǎn)，p指向q前一個(gè)結(jié)點(diǎn)while(q->next!=NULL) /將head的一個(gè)結(jié)點(diǎn)插入到鏈表中（非表尾的位置）if(q->hx<head-&g

11、t;hx) q=q->next;p=p->next;elsep->next=head;head=head->next;p->next->next=q; break;if(q->next=NULL)/將head的一個(gè)結(jié)點(diǎn)插入到表尾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 o

12、pen;/insert/-insert函數(shù) end-/-main-/ void main()int i,j;node s0; node *open,*close;node *p,*q;node *newlist;printf("請(qǐng)輸入初始狀態(tài)的8數(shù)碼（按每行從左往右依次輸入,用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(s

13、0.a);open=&s0;p=&s0;if(open->hx=0)printf("該狀態(tài)已為最終狀態(tài)！n");return;q=&s0;close=&s0;open=NULL;newlist=extend(q);/newlist指向新擴(kuò)展出來(lái)的鏈表open=insert(open,newlist);/將擴(kuò)展出來(lái)的結(jié)點(diǎn)插入到open表中while(1)q->next=open;/q始終指向close表尾結(jié)點(diǎn)。將open表的第一個(gè)元素加到close表open=open->next;q=q->next;q->next=NULL;if(q->hx=0)printf("n搜索成功！n");break;newlist=extend(q);/對(duì)close表最后一個(gè)結(jié)點(diǎn)進(jìn)行擴(kuò)展，擴(kuò)展得到的鏈表接到open表尾 open=insert(open,newlist);/將擴(kuò)展的結(jié)點(diǎn)按順序插入到open表中 p=close; printf("擇優(yōu)搜索過(guò)程如下：n");while(p!=N