基于八數碼問題的搜索算法的研究

楚孟慧，吳姝瑤

（山東科技大學電氣信息系，山東濟南，250031）

0 引言

人工智能這個詞已經成為現代科技前沿的的代表了。人工智能在最近幾年逐漸成為互聯網方向的主流，作為一種新興的現代技術在互聯網領域的多種服務上已經有所體現。其中搜索過程是人工智能技術實現的一個重要環節，是推理不可或缺的一部分。求解一個問題實質上就是對現有知識進行搜索，搜索也是求解問題的方法和過程。掌握搜索算法對人工智能的開發至關重要。

1 搜索的概括與八數碼問題

搜索是如何利用知識找到問題的解并記錄下求解路線或者求解過程的算法。搜索分為兩種，一種是盲目搜索一種是啟發式搜索。盲目搜索即在沒有任何提示，或者知識的指導下，按照系統規定的規則對知識庫進行搜索，無論什么問題都采用相同的搜索方式。這種搜索方式雖然適用于所有問題但當碰到復雜的問題時就需要耗費相當長的時間，效率較低，因此盲目搜索只適用于解決較為簡單的搜索問題。啟發式搜索是在盲目搜索的基礎上不斷的增加搜索信息改變搜索方向使問題得到更快的解決，提高搜索解決問題的效率的一種新的搜索方式。

八數碼問題：在3＊3的棋盤上擺放著八個數碼1、2、3、4、5、6、7、8有一個地方是空格，我們可以對空格進行上下左右的移動使得八數碼盤從初始狀態如圖1轉變為目標狀態如圖2所示。

圖1 初始狀態

圖2 目標狀態

2 盲目搜索

■2.1 寬度優先搜索

寬度優先搜索策略的核心思想為從初始結點開始首先判斷初始結點是否為目標結點如果為目標結點則搜索結束，若不為目標結點則遍歷該結點的所有子結點并同時判斷遍歷的每一個子結點是否為目標結點。然后依次將每一個子結點作為初始結點完成上面的操作，直到找到目標結點。針對八數碼問題給出寬度優先搜索的算法步驟如下：

a.把初始結點S0放入鏈表1中。

b.如果鏈表1是空表，則沒有解，失敗退出；否則繼續。

c.把鏈表1中的第一個結點（記為結點n）移出，并放入 鏈表2中。

d.判斷結點n是否為目標結點，如果是，則求解結束，并用回溯法找出解的路徑，退出；否則繼續執行e。

e.若結點n 不可擴展，轉b；否則繼續執行e。

f.對結點n進行擴展，將它的所有子結點放入鏈表1的末端，并為這些子結點設置指向父結點n的指針，然后轉b。

以下是寬度優先搜索策略解決八數碼問題的搜索樹如圖3所示。

圖3中每個方塊代表一個狀態，每個狀態左邊的數字為此狀態的編碼，開始結點為S0首先對判斷S0是否為目標結點，若S0為目標結點則該搜索過程結束，若不是則拓展S0，對于此問題來說S0并不是目標狀態，于是我們拓展S0并且判斷S0的子結點是否為目標結點以此作為循環直到每一層的結點擴展結束再進行下一層的判斷，直到找到目標結點。目標結點為Sg經過27個結點最終到達目標結點可以看出其路徑為：S0，3 , 8 , 16 , Sg。

圖3 寬度優先搜索樹

由圖3可以看出寬度優先搜索解決八數碼問題時會產生大量的無用結點。但寬度優先搜索總能找到最后的解。

■2.2 深度優先搜索

深度優先搜索的核心思想是從初始結點出發，擴展順序總是先擴展最新產生的結點，這樣搜索順序就會順著一條路徑一直延伸下去，直到最后的結點不能產生新的結點或找到目標結點為止。當搜索到不能產生新的結點且還是無法找到目標結點時，就會沿著最終結點的反方向尋找能夠產生新的結點的結點并且搜索新產生的結點，就這樣執行以上步驟，直到找到目標結點或者再無可擴展結點為止。針對八數碼問題給出深度優先搜索的算法步驟：

a.將初始結點S0放入鏈表1。

b.如果鏈表1為空，則問題無解并退出程序。

c.在鏈表1中將第一個結點（結點n）移出，放入已經擴展結點鏈表2中。

d.考察結點n是否為目標結點，如果是，即找到問題的解，并回溯法求解的路徑然后退出。

e.若結點n不可再擴展，則轉b。

f.擴展結點n，將其子結點放到鏈表1的前端，并為其設置指向結點n的指針，之后轉b。由于過程詳細此處不再展示搜索樹。

深度優先搜索容易陷入某個錯誤的方向，在錯誤的分支上一去不返，造成大量的結點浪費，而且深度優先搜索并不能保證找到目標狀態，容易陷入一個死循環。

3 啟發式搜索

根據以上盲目搜索中它們進行的搜索路線是事先確定好的，沒有根據被求解問題的任何有利信息。沒有考慮現在正在搜索的路徑是否更有利于接近目標結點。所以啟發式搜索正是彌補了盲目搜索的這一劣勢，啟發式搜索在搜索過程中關鍵是如何確定哪一個是下一個要被判斷的結點，在確定下一個需要被判斷的結點時要利用有關結點能夠做出判斷的信息，計算出結點的重要性，并且要選擇重要性高的結點來拓展。因此啟發式優先搜索應定義一個估價函數f(x)，我們以八數碼問題為例f(x)由兩部分組成一部分是該結點所在層數計為m(x)，另一部分是該結點與目標結點中數字所處不同位置的個數計為n(x)。所以估價函數可寫作：f(x)=m(x)+n(x)。例如當S0結點位于第0層時它的m(x)=0,與目標結點數字不相符的地方有3處所以n(x)=3那么f(x)=3。由f(x)的定義可知，f(x)越小說明距離目標結點越近，所以我們應首先考察和拓展f(x)值最小的點。針對八數碼問題給出啟發式搜索算法步驟：

a.將初始結點S0放入鏈表1，并計算f(S0)的值。

b.如果鏈表1為空鏈表，則問題無解并退出。

c.將鏈表1中第一個結點記為結點n移入鏈表2中。

d.考察結點n是否為目標結點，如果是，則求得問題的解并退出；否則轉e。

e.若結點n可擴展，轉f；否則轉b。

f.對結點n進行擴展之后，并計算所有子結點的估價函數f(x)的值，并為每個子結點設置指向n的指針。

g.把這些子結點都送入鏈表1，然后對鏈表1中的全部結點按照估價值從小到大的順序進行排序。

h.轉b。

根據這些規則可以得到算法流程圖如圖4所示。

圖4 啟發式搜索算法流程圖

根據此算法得出搜索樹如圖5所示。

圖5中每一個方塊代表一個狀態，每個狀態左邊的數字代表估價函數的值。首先判斷S0是否為目標結點，若S0為目標結點則搜索過程結束，若S0不為目標結點，則拓展S0并計算所有子結點的代價函數，取其中代價函數最小的結點進行判斷，若不是目標結點則擴展此結點，并計算其子結點的代價函數，這時再次尋找沒有判斷過的代價函數最小的結點直到找到目標結點。由圖5可知搜索的結點數目與盲目搜索相比減少了很多，經過搜索13個結點找到了目標結點并且面對更加復雜的問題時啟發式搜索的效率會明顯增加。

圖5 啟發式搜索

4 總結

現實中的問題都是通過一步一步求解得到答案的，所以人工智能也是仿造人類一步一步搜索出最終答案。盲目搜索在不加入任何特征信息時進行搜索，這種搜索類似于沒有方法但知道答案的范圍將答案帶入問題去匹配，只有少數問題能夠比較幸運的快速算出，大多數較為復雜的問題在進行搜索時就會耗費大量內存。啟發式搜索就像得到了解決問題的方案，每走一步都是距離目標更近的一步，對于復雜的問題往往能快速找到解決方案。因此掌握啟發式搜索技術對于研究人工智能領域有著重要意義。