采用A算法解決八數(shù)碼問題

1、人工智能實驗一報告題目：采用A*算法解決八數(shù)碼問題姓名：張博涵學(xué)號：081110317專業(yè)：信息與計算科學(xué)提交日期：2014-05-22- -structSpringLink*next;/指向兄第結(jié)點SPLink,*PSPLink;PNodeopen;PNodeclosed;/開始狀態(tài)與目標狀態(tài)statusstartt=0,1,2,3,4,5,6,7,8;statustarget=1,4,2,3,5,8,6,7,0;/初始化一個空鏈表voidinitLink(PNode&Head)Head=(PNode)malloc(sizeof(NNode);Head-next=NULL;/判斷鏈表是否為空

2、boolisEmpty(PNodeHead)if(Head-next=NULL)returntrue;elsereturnfalse;/從鏈表中拿出一個數(shù)據(jù)voidpopNode(PNode&Head,PNode&FNode)if(isEmpty(Head)FNode=NULL;return;FNode=Head-next;Head-next=Head-next-next;FNode-next=NULL;/向結(jié)點的最終后繼結(jié)點鏈表中添加新的子結(jié)點voidaddSpringNode(PNode&Head,PNodenewData)PSPLinknewNode=(PSPLink)malloc(si

3、zeof(SPLink);newNode-pointData=newData;newNode-next=Head-child;Head-child=newNode;/釋放狀態(tài)圖中存放結(jié)點后繼結(jié)點地址的空間voidfreeSpringLink(PSPLink&Head)PSPLinktmm;while(Head!=NULL)tmm=Head;Head=Head-next;free(tmm);釋放open表與closed表中的資源voidfreeLink(PNode&Head)PNodetmn;tmn=Head;Head=Head-next;free(tmn);while(Head!=NULL)/

4、首先釋放存放結(jié)點后繼結(jié)點地址的空間freeSpringLink(Head-child);tmn=Head;Head=Head-next;free(tmn);/向普通鏈表中添加一個結(jié)點voidaddNode(PNode&Head,PNode&newNode)newNode-next=Head-next;Head-next=newNode;/向非遞減排列的鏈表中添加一個結(jié)點voidaddAscNode(PNode&Head,PNode&newNode)PNodeP;PNodeQ;P=Head-next;Q=Head;while(P!=NULL&P-fvaluefvalue)Q=P;P=P-next

5、;/上面判斷好位置之后，下面就是簡單的插入了newNode-next=Q-next;Q-next=newNode;計算結(jié)點額h值intcomputeHValue(PNodetheNode)intnum=0;for(inti=0;i3;i+)for(intj=0;jdataij!=targetij)num+;returnnum;計算結(jié)點的f,g,h值voidcomputeAllValue(PNode&theNode,PNodeparentNode)if(parentNode=NULL)theNode-gvalue=0;elsetheNode-gvalue=parentNode-gvalue+1;

6、theNode-hvalue=computeHValue(theNode);theNode-fvalue=theNode-gvalue+theNode-hvalue;/初始化函數(shù)，進行算法初始條件的設(shè)置voidinitial()初始化open以及closed表initLink(open);initLink(closed);/初始化起始結(jié)點，令初始結(jié)點的父節(jié)點為空結(jié)點PNodeNULLNode=NULL;PNodeStart=(PNode)malloc(sizeof(NNode);for(inti=0;i3;i+)for(intj=0;jdataij=starttij;Start-parent=

7、NULL;Start-child=NULL;Start-next=NULL;computeAllValue(Start,NULLNode);起始結(jié)點進入open表addAscNode(open,Start);/將B節(jié)點的狀態(tài)賦值給A結(jié)點voidstatusAEB(PNode&ANode,PNodeBNode)for(inti=0;i3;i+)for(intj=0;jdataij=BNode-dataij;/兩個結(jié)點是否有相同的狀態(tài)boolhasSameStatus(PNodeANode,PNodeBNode)for(inti=0;i3;i+)for(intj=0;jdataij!=BNode-

8、dataij)returnfalse;returntrue;/結(jié)點與其祖先結(jié)點是否有相同的狀態(tài)boolhasAnceSameStatus(PNodeOrigiNode,PNodeAnceNode)while(AnceNode!=NULL)if(hasSameStatus(OrigiNode,AnceNode)returntrue;AnceNode=AnceNode-parent;returnfalse;/取得方格中空的格子的位置voidgetPosition(PNodetheNode,int&row,int&col)for(inti=0;i3;i+)for(intj=0;jdataij=0)r

9、ow=i;col=j;return;/交換兩個數(shù)字的值voidchangeAB(int&A,int&B)intC;C=B;B=A;A=C;/檢查相應(yīng)的狀態(tài)是否在某一個鏈表中boolinLink(PNodespciNode,PNodetheLink,PNode&theNodeLink,PNode&preNode)preNode=theLink;theLink=theLink-next;while(theLink!=NULL)if(hasSameStatus(spciNode,theLink)theNodeLink=theLink;returntrue;preNode=theLink;theLin

10、k=theLink-next;returnfalse;/產(chǎn)生結(jié)點的后繼結(jié)點(與祖先狀態(tài)不同)鏈表voidSpringLink(PNodetheNode,PNode&spring)introw;intcol;getPosition(theNode,row,col);/空的格子右邊的格子向左移動if(col!=2)PNoderlNewNode=(PNode)malloc(sizeof(NNode);statusAEB(rlNewNode,theNode);changeAB(rlNewNode-datarowcol,rlNewNode-datarowcol+1);if(hasAnceSameStat

11、us(rlNewNode,theNode-parent)free(rlNewNode);/與父輩相同，丟棄本結(jié)點elserlNewNode-parent=theNode;rlNewNode-child=NULL;rlNewNode-next=NULL;computeAllValue(rlNewNode,theNode);/將本結(jié)點加入后繼結(jié)點鏈表addNode(spring,rlNewNode);/空的格子左邊的格子向右移動if(col!=0)PNodelrNewNode=(PNode)malloc(sizeof(NNode);statusAEB(lrNewNode,theNode);chan

12、geAB(lrNewNode-datarowcol,lrNewNode-datarowcol-1);if(hasAnceSameStatus(lrNewNode,theNode-parent)free(lrNewNode);/與父輩相同，丟棄本結(jié)點elselrNewNode-parent=theNode;lrNewNode-child=NULL;lrNewNode-next=NULL;computeAllValue(lrNewNode,theNode);/將本結(jié)點加入后繼結(jié)點鏈表addNode(spring,lrNewNode);/空的格子上邊的格子向下移動if(row!=0)PNodeudN

13、ewNode=(PNode)malloc(sizeof(NNode);statusAEB(udNewNode,theNode);changeAB(udNewNode-datarowcol,udNewNode-datarow-1col);if(hasAnceSameStatus(udNewNode,theNode-parent)free(udNewNode);/與父輩相同，丟棄本結(jié)點elseudNewNode-parent=theNode;udNewNode-child=NULL;udNewNode-next=NULL;computeAllValue(udNewNode,theNode);/將本

14、結(jié)點加入后繼結(jié)點鏈表addNode(spring,udNewNode);/空的格子下邊的格子向上移動if(row!=2)PNodeduNewNode=(PNode)malloc(sizeof(NNode);statusAEB(duNewNode,theNode);changeAB(duNewNode-datarowcol,duNewNode-datarow+1col);if(hasAnceSameStatus(duNewNode,theNode-parent)free(duNewNode);/與父輩相同，丟棄本結(jié)點elseduNewNode-parent=theNode;duNewNode-c

15、hild=NULL;duNewNode-next=NULL;computeAllValue(duNewNode,theNode);/將本結(jié)點加入后繼結(jié)點鏈表addNode(spring,duNewNode);/輸出給定結(jié)點的狀態(tài)voidoutputStatus(PNodestat)for(inti=0;i3;i+)for(intj=0;j3;j+)coutdataij;coutgvalue;if(goal-parent!=NULL)outputBestRoad(goal-parent);cout第deepnum-層的狀態(tài)：endl;outputStatus(goal);voidAStar()P

16、NodetmpNode;/指向從open表中拿出并放到closed表中的結(jié)點的指針PNodespring;/tmpNode的后繼結(jié)點鏈PNodetmpLNode;/tmpNode的某一個后繼結(jié)點PNodetmpChartNode;PNodethePreNode;/指向?qū)⒁獜腸losed表中移到open表中的結(jié)點的前一個結(jié)點的指針boolgetGoal=false;/標識是否達到目標狀態(tài)longnumcount=1;/記錄從open表中拿出結(jié)點的序號initial。;/對函數(shù)進行初始化initLink(spring);/對后繼鏈表的初始化tmpChartNode=NULL;cout從open表中

17、拿出的結(jié)點的狀態(tài)及相應(yīng)的值endl;while(!isEmpty(open)從open表中拿出f值最小的元素，并將拿出的元素放入closed表中popNode(open,tmpNode);addNode(closed,tmpNode);cout第numcount+個狀態(tài)是：endl;outputStatus(tmpNode);cout其f值為：fvalueendl;cout其g值為：gvalueendl;cout其h值為：hvaluegvaluegvalue)tmpChartNode-parent=tmpLNode-parent;tmpChartNode-gvalue=tmpLNode-gva

18、lue;tmpChartNode-fvalue=tmpLNode-fvalue;free(tmpLNode);狀態(tài)在closed表中已經(jīng)存在elseif(inLink(tmpLNode,closed,tmpChartNode,thePreNode)addSpringNode(tmpNode,tmpChartNode);if(tmpLNode-gvaluegvalue)PNodecommu;tmpChartNode-parent=tmpLNode-parent;tmpChartNode-gvalue=tmpLNode-gvalue;tmpChartNode-fvalue=tmpLNode-fvalue;freeSpringLink(tmpChartNode-child);tmpChartNode-child=NULL;popNode(thePreNode,commu);addAscNode(open