【正文】 決8數碼問題的編程實現 基于A*算法解決把數碼問題 《人工智能》 專 業(yè)： 信息與計算科學 班 級： 101001 學 號： 101001102 姓 名： 陳 斌 指導老師： 時 華 日 期：2013年10月14日一、問題描述8數碼問題又稱9宮問題，與游戲“華容道”類似。為方便編程和表示，本文中8個格子內的符號分別取1—8的8個數字表示，空格用0表示。但要在計算機上通過編程解決該問題，還應當解決該問題在計算機上表示的方式，并設計合適的啟發(fā)函數，以提高搜索效率。如圖3所示，表示問題的結構體包括表示當前節(jié)點狀態(tài)的DATA和指向open表中下一個待擴展節(jié)點的指針NEXT。根據A*算法的定義，當前節(jié)點的代價值由估價函數給出，即：其中：表示當前節(jié)點n在搜索樹中的深度； 是啟發(fā)函數。圖4 問題的狀態(tài)表示②啟發(fā)函數的設計根據A*算法的定義，啟發(fā)函數應滿足：。顯然，后者的不小于前者，因此本文中采用數碼“不在位”的距離和作為啟發(fā)函數。因此移動的規(guī)則庫可以寫成如下形式：左移：if(pj_0=1) //空格所在列號不小于1,可左移 { temp=pfather。amp。amp。 //新節(jié)點與其祖父節(jié)點相同，無操作 else //新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 { ……(擴展新節(jié)點，并判斷是否加入open表)//詳細代碼見源程序 } }//end右移上移：if(pi_0=1) //空格所在列號不小于1,可上移 { temp=pfather。amp。amp。 //新節(jié)點與其祖父節(jié)點相同，無操作 else //新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 { ……(擴展新節(jié)點，并判斷是否加入open表)//詳細代碼見源程序 } }//end下移④程序流程主程序流程圖：其中，擴展節(jié)點n的具體步驟如下：a) 首先判斷其是否在closed表已經出現過, 如果出現過，并且新節(jié)點的代價值比其小，則應將其從closed表刪除，同時將新節(jié)點加入到open表；如果沒有出現過，則轉b。void Calculate_f(int deepth,struct node *p)。int Test_A_B(struct node *p1,struct node *p2)。void Print_result(struct node *p)。 //當前空格所在列號 int f。 //指向解路徑上該節(jié)點的父節(jié)點 struct node *next。 //定義目標狀態(tài)struct node *open=NULL。 Copy_node(amp。s)。 //輸出解路徑 else printf(問題求解失??！)。 Add_to_open(p)。 open=temp。 //擴展節(jié)點n } return NULL。amp。 else //新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 { temp=(struct node *)malloc(sizeof(struct node))。 tempj_0。 //新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,temp)) //在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 { if(tempfsamef) //temp指向的節(jié)點,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 { Remove_p(closed,same)。 } else if(same=Search_A(open,temp)) //在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 { if(tempfsamef) //temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代價小，加入open表 { Remove_p(open,same)。 } else //新節(jié)點為完全不同的新節(jié)點，加入open表 { Add_to_open(temp)。amp。 else //新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 { temp=(struct node *)malloc(sizeof(struct node))。 tempj_0++。 //新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,temp)) //在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 { if(tempfsamef) //temp指向的節(jié)點,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 { Remove_p(closed,same)。 } else if(same=Search_A(open,temp)) //在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 { if(tempfsamef) //temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代價小，加入open表 { Remove_p(open,same)。 } else //新節(jié)點為完全不同的新節(jié)點，加入open表 { Add_to_open(temp)。amp。 else //新節(jié)點與其祖父節(jié)點不同，或其父節(jié)點為起始節(jié)點 { temp=(struct node *)malloc(sizeof(struct node))。 tempi_0。 //新節(jié)點指向其父節(jié)點 if(same=Search_A(closed,temp)) //在closed表中找到與新節(jié)點狀態(tài)相同的節(jié)點 { if(tempfsamef) //temp指向的節(jié)點,其代價比closed表中相同狀態(tài)節(jié)點代價小，加入open表 { Remove_p(closed,same)。 } else if(same=Search_A(open,temp)) //在open表中找到與新節(jié)點狀態(tài)相同的節(jié)點 { if(tempfsamef) //temp指向的節(jié)點,其代價比open表中相同狀態(tài)節(jié)點代價小，加入open表 { Remove_p(open,same)。 } else //新節(jié)點為完全不同的新節(jié)點，加入open表 { Add_to_open(temp)。a