C語言實現(xiàn)8數(shù)碼問題

1、 實驗?zāi)康氖煜と斯ぶ悄芟到y(tǒng)中的問題求解過程；熟悉狀態(tài)空間中的盲目搜索策略；掌握盲目搜索算法，重點是寬度優(yōu)先搜索和深度優(yōu)先搜索算法。2、 實驗要求用VC語言編程，采用寬度優(yōu)先搜索和深度優(yōu)先搜索方法，求解 8數(shù)碼問題3、 實驗內(nèi)容1）采用寬度優(yōu)先算法，運行程序，要求輸入初始狀態(tài)假設(shè)給定如下初始狀態(tài)S0283164705和目標(biāo)狀態(tài)Sg216408753驗證程序的輸出結(jié)果，寫出心得體會。（2）對代碼進行修改（選作），實現(xiàn)深度優(yōu)先搜索求解該問題提示：每次選擴展節(jié)點時，從數(shù)組的最后一個生成的節(jié)點開始找，找一個沒有被擴展的節(jié)點。這樣也需要對節(jié)點添加一個是否被擴展過的標(biāo)志。源代碼及實驗結(jié)果截圖#include<stdio.h>#include<stdlib.h>#include<math.h>八數(shù)碼狀態(tài)對應(yīng)的節(jié)點結(jié)構(gòu)體structNode{ints[3][3];// 保存八數(shù)碼狀態(tài)，0代表空格intf,g;// 啟發(fā)函數(shù)中的 f和g值structNode*next;structNode*previous;//};

保存其父節(jié)點intopen_N=0;// 記錄Open列表中節(jié)點數(shù)目八數(shù)碼初始狀態(tài)intinital_s[3][3]={2,8,3,1,6,4,7,0,5};八數(shù)碼目標(biāo)狀態(tài)intfinal_s[3][3]={2,1,6,4,0,8,7,5,3};//------------------------------------------------------------------------添加節(jié)點函數(shù)入口，方法：通過插入排序向指定表添加//------------------------------------------------------------------------voidAdd_Node(structNode*head,structNode*p){structNode*q;if(head->next)// 考慮鏈表為空{(diào) q=head->next;if(p->f<head->next->f){// 考慮插入的節(jié)點值比鏈表的第一個節(jié)點值小p->next=head->next;head->next=p;}else{while(q->next)// 考慮插入節(jié)點 x，形如a<=x<=b{if((q->f<p->f||q->f==p->f)&&(q->next->f>p->f||q->next->f==p->f)){p->next=q->next;q->next=p;break;}q=q->next;}if(q->next==NULL)// 考慮插入的節(jié)點值比鏈表最后一個元素的值更大q->next=p;}}elsehead->next=p;}//------------------------------------------------------------------------刪除節(jié)點函數(shù)入口//------------------------------------------------------------------------voiddel_Node(structNode*head,structNode*p){structNode*q;q=head;while(q->next){if(q->next==p){q->next=p->next;p->next=NULL;if(q->next==NULL)return;free(p);}q=q->next;}}//------------------------------------------------------------------------判斷兩個數(shù)組是否相等函數(shù)入口//------------------------------------------------------------------------intequal(ints1[3][3],ints2[3][3]){inti,j,flag=0;for(i=0;i<3;i++)for(j=0;j<3;j++)if(s1[i][j]!=s2[i][j]){flag=1;break;}if(!flag)return1;elsereturn0;}//------------------------------------------------------------------------判斷后繼節(jié)點是否存在于Open或Closed表中函數(shù)入口//------------------------------------------------------------------------intexit_Node(structNode*head,ints[3][3],structNode*Old_Node){structNode*q=head->next;intflag=0;while(q)if(equal(q->s,s)){flag=1;Old_Node->next=q;return1;}elseq=q->next;if(!flag)return0;}//------------------------------------------------------------------------計算p(n)的函數(shù)入口其中p(n)為放錯位的數(shù)碼與其正確的位置之間距離之和具體方法：放錯位的數(shù)碼與其正確的位置對應(yīng)下標(biāo)差的絕對值之和//------------------------------------------------------------------------intwrong_sum(ints[3][3]){inti,j,fi,fj,sum=0;for(i=0;i<3;i++)for(j=0;j<3;j++){for(fi=0;fi<3;fi++)for(fj=0;fj<3;fj++)if((final_s[fi][fj]==s[i][j])){sum+=fabs(i-fi)+fabs(j-fj);break;}}returnsum;}//------------------------------------------------------------------------//獲取后繼結(jié)點函數(shù)入口//檢查空格每種移動的合法性，如果合法則移動空格得到后繼結(jié)點//------------------------------------------------------------------------intget_successor(structNode*BESTNODE,intdirection,structNode*Successor)// 擴展BESTNODE，產(chǎn)生其后繼結(jié)點SUCCESSOR{inti,j,i_0,j_0,temp;for(i=0;i<3;i++)for(j=0;j<3;j++)Successor->s[i][j]=BESTNODE->s[i][j];//獲取空格所在位置for(i=0;i<3;i++)for(j=0;j<3;j++)if(BESTNODE->s[i][j]==0){i_0=i;j_0=j;break;}switch(direction){case0:if((i_0-1)>-1){temp=Successor->s[i_0][j_0];Successor->s[i_0][j_0]=Successor->s[i_0-1][j_0];Successor->s[i_0-1][j_0]=temp;return1;}elsereturn0;case1:if((j_0-1)>-1){temp=Successor->s[i_0][j_0];Successor->s[i_0][j_0]=Successor->s[i_0][j_0-1];Successor->s[i_0][j_0-1]=temp;return1;}elsereturn0;case2:if((j_0+1)<3){temp=Successor->s[i_0][j_0];Successor->s[i_0][j_0]=Successor->s[i_0][j_0+1];Successor->s[i_0][j_0+1]=temp;return1;}elsereturn0;case3:if((i_0+1)<3){temp=Successor->s[i_0][j_0];Successor->s[i_0][j_0]=Successor->s[i_0+1][j_0];Successor->s[i_0+1][j_0]=temp;return1;}elsereturn0;}}//------------------------------------------------------------------------從OPen表獲取最佳節(jié)點函數(shù)入口//------------------------------------------------------------------------structNode*get_BESTNODE(structNode*Open){returnOpen->next;}//------------------------------------------------------------------------輸出最佳路徑函數(shù)入口//------------------------------------------------------------------------voidprint_Path(structNode*head){structNode*q,*q1,*p;inti,j,count=1;p=(structNode*)malloc(sizeof(structNode));通過頭插法變更節(jié)點輸出次序p->previous=NULL;q=head;while(q){q1=q->previous;q->previous=p->previous;p->previous=q;q=q1;}q=p->previous;while(q){if(q==p->previous)printf("

八數(shù)碼的初始狀態(tài)：

\n");elseif(q->previous==NULL)printf("

八數(shù)碼的目標(biāo)狀態(tài)：

\n");elseprintf("

八數(shù)碼的中間態(tài)

%d\n",count++);for(i=0;i<3;i++)for(j=0;j<3;j++){printf("%4d",q->s[i][j]);if(j==2)printf("\n");}printf("f=%d,g=%d\n\n",q->f,q->g);q=q->previous;}}//------------------------------------------------------------------------//A*子算法入口:處理后繼結(jié)點//------------------------------------------------------------------------voidsub_A_algorithm(structNode*Open,structNode*BESTNODE,structNode*Closed,structNode*Successor){structNode*Old_Node=(structNode*)malloc(sizeof(structNode));Successor->previous=BESTNODE;//

建立從

successor

返回BESTNODE的指針Successor->g=BESTNODE->g+1;//

計算后繼結(jié)點的

g值//檢查后繼結(jié)點是否已存在于

Open和Closed

表中，如果存在：該節(jié)點記為

old_Node，比較后繼結(jié)點的

g值和表中

old_Node節(jié)點//g 值，前者小代表新的路徑比老路徑更好，將 Old_Node的父節(jié)點改為 BESTNODE，并修改其f，g值，后者小則什么也不做。即不存在Open也不存在Closed表則將其加入OPen表，并計算其f值if(exit_Node(Open,Successor->s,Old_Node)){if(Successor->g<Old_Node->g){Old_Node->next->previous=BESTNODE;//

將Old_Node的父節(jié)點改為

BESTNODEOld_Node->next->g=Successor->g;//

修改g值Old_Node->next->f=Old_Node->g+wrong_sum(Old_Node->s);//

修改f

值// 排序~~~~~~~~~~~~~~~~~~del_Node(Open,Old_Node);Add_Node(Open,Old_Node);}}elseif(exit_Node(Closed,Successor->s,Old_Node)){if(Successor->g<Old_Node->g){Old_Node->next->previous=BESTNODE;Old_Node->next->g=Successor->g;Old_Node->next->f=Old_Node->g+wrong_sum(Old_Node->s);排序~~~~~~~~~~~~~~~~~~del_Node(Closed,Old_Node);Add_Node(Closed,Old_Node);}}else{Successor->f=Successor->g+wrong_sum(Successor->s);Add_Node(Open,Successor);open_N++;}}//------------------------------------------------------------------------//A*算法入口//八數(shù)碼問題的啟發(fā)函數(shù)為： f(n)=d(n)+p(n)//其中A*算法中的g(n)根據(jù)具體情況設(shè)計為 d(n)，意為n節(jié)點的深度，而 h(n)設(shè)計為p(n)，//意為放錯的數(shù)碼與正確的位置距離之和//------------------------------------------------------------------------voidA_algorithm(structNode*Open,structNode*Closed)//A* 算法{inti,j;structNode*BESTNODE,*inital,*Successor;inital=(structNode*)malloc(sizeof(structNode));// 初始化起始節(jié)點for(i=0;i<3;i++)for(j=0;j<3;j++)inital->s[i][j]=inital_s[i][j];inital->f=wrong_sum(inital_s);inital->g=0;inital->previous=NULL;inital->next=NULL;Add_Node(Open,inital);// 把初始節(jié)點放入 OPEN表open_N++;while(1){if(open_N==0){printf("failure!");return;}else{BESTNODE=get_BESTNODE(Open);//從OPEN表獲取f值最小的BESTNODE，將其從OPEN表刪除并加入 CLOSED表中del_Node(Open,BESTNODE);open_N--;Add_Node(Closed,BESTNODE);if(equal(BESTNODE->s,final_s)){// 判斷BESTNODE是否為目標(biāo)節(jié)點printf("success!\n");print_Path(BESTNODE);return;}// 針對八數(shù)碼問題，后繼結(jié)點 Successor的擴展方法：空格（二維數(shù)組中的 0）上下左右移動，// 判斷每種移動的有效性，有效則轉(zhuǎn)向 A*子算法處理后繼節(jié)點，否則進行下一種移動else{Successor=(structNode*)malloc(sizeof(structNode));Successor->next=NULL;if(get_successor(BESTNODE,0,Successor))sub_A_algorithm(Open,BESTNODE,Closed,Successor);Successor=(structNode*)malloc(sizeof(structNode));Successor->next=NULL;if(get_suc