1、 基于A*算法求解八數碼問題班級：20110616學號：2011061618姓名：唐宗林摘要：利用人工智能中的經典啟發式搜索算法求解八數碼問題，在啟發式搜索算法上對A*算法的定義進行了解釋，詳細的描述了啟發式A*搜索算法，并將之運用至解決八數碼問題，對八數碼問題求解過程進行了詳細解釋，取得了預期的搜索解，達到了本實驗課程的預期目的。關鍵詞：人工智能；啟發式搜索算法；A*算法；八數碼問題本組成員：唐宗林，陶濤，湯蘆山本人分工：主要承擔A*算法中啟發函數的設計、八數碼問題解存在問題判斷等工作。1引言在信息社會中，人們越來越依賴于搜索技術來獲取有用的信息，搜索是人工智能中的一個基本問題，是推理不可分

2、割的一部分，它直接關系到智能系統的性能及運行效率。通常搜索策略的主要任務是確定如何選取規則的方式。一般有兩種方式：一種是不考慮所給問題所具有的的特定知識系統根據事先確定好的某種固定排序，一次調用規則或隨機調用規則，這實際上是盲目搜索的策略；另一種是考慮問題領域可應用的知識，動態的確定規則的排序，優先調用較合適的規則排序，這就是通常所稱為的啟發式搜索策略。啟發式搜索是利用問題所擁有的啟發式信息來引導搜索，以達到減少搜索范圍，降低問題復雜度的目的。在本課程實驗中我們以八數碼問題為背景，運用啟發式搜索算法來達到求解目的。通過解決八數碼問題來加深對A*算法的理解及運用，以更好地將課堂所學知識運用到實際

3、問題的解決之中。在實驗中我的任務主要是A*算法中啟發函數的設計、八數碼問題解存在問題判斷等工作，所以接下來的敘述也將圍繞這幾項工作來展開。算法原理與系統設計2.1八數碼問題八數碼游戲（八數碼問題）描述為：在3x3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1-8八個數碼中的某一個數碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格移動，這樣通過移動將牌就可以不斷改變將牌的布局。這種游戲求解的問題是：給定一種初始的將牌布局或結構（稱初始狀態）和一個目標的布局（稱目標狀態），問如何移動將牌，實現從初始狀態到目標狀態的轉變。初始狀態：8個數字將牌和空格在九宮格棋盤上的所有格局組成了問題的狀態

4、空間。其中，狀態空間中的任一種狀態都可以作為初始狀態。后繼函數：通過移動空格（上、下、左、右）和周圍的任一棋子一次，到達新的合法狀態。目標測試：比較當前狀態和目標狀態的格局是否一致。路徑消耗：每一步的耗散值為1，因此整個路徑的耗散值是從起始狀態到目標狀態的棋子移動的總步數。2.2八數碼解存在判斷在對八數碼問題進行正式求解前，我們會首先對八數碼是否有解作出判斷。我們對一個任意的棋局狀態p=clc2c3c4c5c6c7c8進行分析：引理1：如果交換任何兩個相鄰的棋子，那么棋子數列的逆序數將發生奇偶性互變(奇偶性互變是指由奇數變為偶數，或由偶數變為奇數，下同)。引理2：如果棋子數列經過n次相鄰棋子交

5、換后，若n為偶數，則數列逆序數奇偶性不變；若n為奇數，則數列逆序數將發生奇偶性互變。引理3：在滿足上述約定的八數碼問題中，空格與相鄰棋子的交換不會改變棋局中棋子數列的逆序數的奇偶性。定理l：當初始狀態棋局的棋子數列的逆序數是奇數時，八數碼問題無解；當初始狀態棋局的棋子數列的逆序數是偶數時，八數碼問題有解。2.3啟發式搜索啟發式搜索算法的基本思想是：定義一個評價函數f，對當前的搜索狀態進行評估，找出一個最有希望的節點來擴展。2.4啟發信息啟發性信息是指那種與具體問題求解過程有關的，并可指導搜索過程朝著最有希望的方向前進的控制信息。有余下三種啟發性信息：有效的幫助確定擴展節點的信息；有效的幫助決定

6、那些后記節點被生成的信息；能決定在擴展一個節點時那些節點應從搜索樹上刪除的信息；估價函數f*(n)=g*(n)+h*(n)上式中g*(n)表示從初始節點s到當前節點n的最短路徑的耗散值；h*(n)表示從當前節點n到目標節點g的最短路徑的實際耗散值，f*(n)表示從初始節點s經過n到目標節點g的最短路徑的耗散值。A*算法如果我們分別以g(n)及h(n)代替g*(n)及h*(n)，其中g(n)是對g*的一個合理估計，它們可能不相等：g(n)=g*(n)只有當發現了到狀態n的最短路徑時它們才是相等的。同理，以對到目標狀態的最小代價的啟發式估計h(n)代替h*(n)，如果評估函數滿足h(n)=h*(n

7、)，我們把它稱為A*算法。信息度更高的啟發是更好的啟發，A*算法的信息度越高，要得到最優解而需要展開的空間就越小。但采用高信息度的啟發所需的計算量可能會增大，以至于抵消了搜索數量降低而帶來的優勢。算法描述算法的功能：產生8數碼問題的解(由初始狀態到達目標狀態的過程)輸入：初始狀態，目標狀態輸出：從初始狀態到目標狀態的一系列過程算法描述：Begin：讀入初始狀態和目標狀態，并計算初始狀態評價函數值f;根據初始狀態和目標狀態，判斷問題是否可解；If（問題可解）把初始狀態假如open表中；While（未找到解&狀態表非空）在open表中找到評價值最小的節點，作為當前結點；判斷當前結點狀態和目標狀態是

8、否一致，若一致，跳出循環；否則跳轉到；對當前結點，分別按照上、下、左、右方向移動空格位置來擴展新的狀態結點，并計算新擴展結點的評價值f并記錄其父節點；對于新擴展的狀態結點，判斷其是否重復，若不重復，把其加入到open表中；把當前結點從open表中移除；EndwhileEndif輸出結果；End2.8算法流程圖算法流程圖如下圖2.8所示：曰否否曰是否可解結束是否是目標節點丄開始在Open表中找到評價值最小的節點，作為當前節點擴展新狀態，把不重復的新狀態加入Open表中初始狀態加入Open表當前節點從Open表移除讀入棋局初始狀態輸出結果圖2.8算法流程圖系統實現3.1啟發式函數設計3.1.1啟發

9、函數1啟發函數1數出每個狀態與目標狀態相比錯位的牌數錯位牌數最少的狀態可能最接近預期目標，所以它是接下來要分析的最佳狀態。缺點是沒有使用從棋盤上得到的全部信息。因為它沒有把牌要移動的距離納入到考慮之中關鍵代碼：intcamp(stringstr1,stringstr2)intsum=0;for(inti=0;i9;i+)if(str1i!=str2i)sum+;coutsumps;strings=s0;inth=0;inttemp，tempg;for(inti=0;i=8;i+)if(si=0)continue;/。的距離已經包含在其他數字的移動過程中，所以應該舍去temp=strchr(ps

10、，si)-ps;tempg=strchr(psg，si)-psg;h+=abs(temp/3-tempg/3)+abs(temp%3-tempg%3);returnh;3.1.3啟發函數3啟發函數3：對每一個相互顛倒(兩張相鄰的牌要滿足目標位置必須交換順序)乘以一個小的數字(例如2)但這種啟發函數的問題是如果當前狀態如果不存在直接顛倒，則不能對當前狀態做出正確的評估。關鍵代碼：intcamp(stringstrl，stringstr2)intsum=0;for(inti=0;i9;i+)if(str1i=0)continue;for(intj=0;j9;j+)if(str1i=str2j&st

11、r2j=str2i)sum+;coutsum/2endl;3.1.4啟發函數4啟發函數4：把錯位牌的距離與直接顛倒數的二倍相加。這樣就綜合了啟發函數2和啟發函數3的優點，克服了單純顛倒啟發的不足之處，加強了評估函數的準確性。3.2八數碼問題解存在判斷boolcansolve(stringsO,stringsg)檢驗用戶輸入的初始狀態是否有解/*當初始狀態的逆序數和目標狀態的逆序數的奇偶性相同時,問題有解；否則問題無解。逆序數定義如下：把三行數展開排成一行,并且丟棄數字0不計入其中,所有的數之前比該數小的數字的個數之和是該狀態的逆序數。*/inti0,ig,i,j;i0=ig=0;for(i=0

12、;i=8;i+)if(s0i=0)continue;for(j=0;ji;j+)if(s0j=0)continue;if(s0j-0)(s0i-0)i0+;for(i=0;i=8;i+)if(sgi=0)continue;for(j=0;ji;j+)if(sgj=0)continue;if(sgj-0)(sgi-0)ig+;couti0igendl;return(i0-ig)%2=0);實驗或測試結果4.1有解狀況分析有解狀況分析如下圖4.1所示，目標狀態默認為123804765，初始狀態為283164750。覘別斷戎戀:23B2BM31&4750圖4.1有解狀態分析4.2無解狀態分析無解狀況

13、分析如下圖4.2所示，目標狀態默認為123804765,初始狀態為823164705。|31&4706汗蛉直趟拼團圖4.2無解狀態分析5結論通過本實驗中對八數碼問題的解決，我加深了對啟發式搜索算法的理解與運用，更加深刻的理解了A*算法的實質，同時加深了我對人工智能課程的興趣。在本課程實驗中我主要負責A*算法中啟發函數的設計及八數碼問題解存在判斷等工作，通過這些內容我深深理解了實踐的重要性，課本中學到的知識只有通過實際問題的解決才能真正被掌握與吸收。在完成實驗的過程中，我參考了許多參考資料，認真的學習了啟發函數的設計原理，同時比較了常用幾種啟發函數的優缺點，加深了理解。在實驗中的不足之處是由于時間原因沒有對這幾種啟發函數進行實際效率比對，只是在理論上進行了比較。通過本課程提高了我的解決實際問題的自信心，但同時也讓我更加深刻的認識