啟發式搜索算法解決八數碼問題(C語言)珍藏版

(相關資料圖)

《啟發式搜索算法解決八數碼問題(C語言)》由會員分享，可在線閱讀，更多相關《啟發式搜索算法解決八數碼問題(C語言)(9頁珍藏版)》請在人人文庫網上搜索。

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的一個結點插入到鏈表中(非表尾的位置) printfC請輸入初始狀態的8數碼(按每行從左往右依次輸入，用0表示空格)：)； for(i=0;i3;i +) for(j=0;jhx二9; =hx; open二 p= if (open-hx=0) printf (該狀態已為最終狀態！ n); return; q= close二 open二NULL; newlist=extend(q) ;/newlist指向新擴展出來。

9、的鏈表 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+) for(j=0;jai j); printf(n); printf(*n*); p=p-next; 2程序運行結果截圖 4 7 截圖1： r 初始態 2 1 7 為 3 4 5 運行結果 右圖所示 1 0 請輸入初始狀態的 8 3 6 4 0 5 0 2 3 18 4 ? 6 5 Press any kwy to continue。