《人工智能實驗指導書》課件-實驗4　啟發(fā)式算法-八數(shù)碼問題(九宮格問題)

一、實驗目的1.學習并掌握啟發(fā)式算法基本原理和實現(xiàn)方法。2.設計并改進啟發(fā)式算法，比較幾種常用的啟發(fā)式估價函數(shù)。3.使用啟發(fā)式算法實現(xiàn)八數(shù)碼問題的求解。二、實驗背景八數(shù)碼問題是人工智能的一個經(jīng)典問題。問題是在3?×?3的方格盤上放有八個數(shù)碼，第九個位置為空，每個空格其上下左右的數(shù)碼可移至空格位置。給定初始位置和目標位置，要求通過一系列數(shù)碼移動，將初始位置轉(zhuǎn)化為目標位置。八數(shù)碼問題的求解可以看作是一個搜索問題。如果把每個棋局作為一個節(jié)點，把每次移動作為邊，則該問題可以由一個狀態(tài)空間圖來表示，問題求解就等同于在狀態(tài)空間圖中尋找初始位置節(jié)點和目標位置節(jié)點之間的路徑。三、實驗原理啟發(fā)式算法是基于直觀或經(jīng)驗構造的算法，在可接受的花費下給出待解決組合優(yōu)化問題每一個實例的可行解，該可行解與最優(yōu)解的偏離程度一般不能被預計。相比于盲目搜索方法，啟發(fā)式算法利用與問題有關的信息從中得到啟發(fā)來引導搜索，以達到減少搜索量的目的。搜索中生成擴展的狀態(tài)數(shù)會隨著搜索深度的增加呈指數(shù)級增長。在這種情況下，窮盡式搜索策略在一個給定的時空內(nèi)可能得不到最終解。啟發(fā)式策略則通過引導向算法最有希望的方向進行搜索，進而降低了模型的復雜度。啟發(fā)式策略及算法設計一直是人工智能的重要問題，并且具有實際意義。在問題求解中，搜索深度過深或是搜索分支過多可能會使得狀態(tài)空間過大，需要通過啟發(fā)式算法來剪枝以減少狀態(tài)空間的大小。啟發(fā)式搜索通常由兩部分組成：啟發(fā)方法和基于該方法的搜索狀態(tài)空間算法。對于八數(shù)碼問題，狀態(tài)空間大小有限，使用寬度優(yōu)先搜索不用遍歷全部狀態(tài)空間，一旦得到可行解就是寬度優(yōu)先搜索方法的最優(yōu)解。而對于該問題，深度優(yōu)先搜索需要遍歷狀態(tài)空間，搜索量更大。寬度、深度優(yōu)先搜索是搜索狀態(tài)空間的最基本方法。寬度優(yōu)先搜索法的搜索順序如圖4-1所示。按層搜索節(jié)點，從初始狀態(tài)開始將該層所有狀態(tài)搜索結束后再搜索下一層，直到搜索到目的狀態(tài)或全部搜索完畢。在實現(xiàn)寬度優(yōu)先搜索時，為了保存狀態(tài)空間搜索的軌跡，需要用到兩個表：open表和closed表。open表包含了已經(jīng)生成出來但其子狀態(tài)未被搜索的狀態(tài)。open表中狀態(tài)的排列次序就是搜索的次序。在寬度優(yōu)先的搜索中，open表中的狀態(tài)均為相同或相鄰層狀態(tài)變化，相應的closed表記錄了已被生成擴展過的狀態(tài)。啟發(fā)式信息往往反映在估價函數(shù)之中。估價函數(shù)的任務就是估計待搜索節(jié)點的“有希望”程度，并依次給他們排定次序(在open表中)。估價函數(shù)f(x)可以是如下任意一種函數(shù)，如節(jié)點x處于最佳路徑上的概率，或x節(jié)點和目的節(jié)點之間的距離或差異，或x格局的得分等。一般來說，估價一個節(jié)點的價值，必須綜合考慮兩方面的因素：已經(jīng)付出的代價和將要付出的代價。在此，把估價函數(shù)定義為從初始節(jié)點經(jīng)過n節(jié)點到達目的節(jié)點的路徑的最小代價估計值，其一般形式如下：f(n)?=?g(n)?+?h(n)在八數(shù)碼問題中，搜素狀態(tài)空間的方法選用寬度優(yōu)先搜索。使用寬度優(yōu)先搜索時，所搜索的層數(shù)就表示初始節(jié)點到n節(jié)點的實際代價。而八數(shù)碼問題的估價函數(shù)可以有多種不同的設計。一般而言，最簡單常見的估價函數(shù)是當前格局和目的格局相比在各個對應位置存在差異的數(shù)碼數(shù)量。直觀上來說這種估價函數(shù)很有效，因為在其他條件相同時，與目的狀態(tài)位置不同的數(shù)碼越少，則該狀態(tài)與目的狀態(tài)越接近。但是這種估價函數(shù)沒有充分利用所能獲得的信息，沒有考慮移動數(shù)碼的距離。因此，一種簡單的改進是將各數(shù)碼移動到目標狀態(tài)的距離總和作為估價函數(shù)。但上述這些估價函數(shù)都沒考慮數(shù)字位置等相關重要信息?？紤]這一點，可以根據(jù)數(shù)字位置進一步改進估價函數(shù)。五、實驗總結1.闡述實驗過程對于本實驗中的八數(shù)碼問題，啟發(fā)式算法是在寬度優(yōu)先搜索算法的基礎上改進搜索策略。在實驗過程中，首先實現(xiàn)了寬度優(yōu)先搜索解決八數(shù)碼問題，盡管寬度優(yōu)先搜索可以快速解決簡單情況，但是隨著求解步數(shù)增加，復雜度會呈指數(shù)級增長。隨后，在此基礎之上引入啟發(fā)式算法的估價函數(shù)，得到結果和求解復雜度。最后對啟發(fā)式算法的估價函數(shù)進行進一步改進，深入探究和比較幾種算法的搜索步數(shù)和各自優(yōu)劣。2.理解實驗原理分析實驗結果，啟發(fā)式算法比寬度優(yōu)先搜索減少了大量的搜索步數(shù)，可以更快地得到最短路徑。引入合理的估價函數(shù)，可以有效避免一些錯誤的搜索方向。啟發(fā)式算法的關鍵問題就在于：(1)問題是否有充足的先驗知識；(2)是否選擇了合適的估價函數(shù)。對于不同的問題，啟發(fā)式算法雖能減少搜索的數(shù)量，但不能保證一定能得到問題最優(yōu)解。改進啟發(fā)式算法，即利用先驗知識改進估價函數(shù)，這樣做可以減少搜索復雜度并提升得到最優(yōu)解的可能性。3.分析實驗問題對于本實驗的八數(shù)碼問題，最優(yōu)解步數(shù)較多時寬度優(yōu)先搜索的復雜度很高，啟發(fā)式算法可以很好解決這一點。在啟發(fā)式算法中，一種樸素的估計方法是記錄當前節(jié)點與目的節(jié)點位置不同的數(shù)字數(shù)量，但是該方法忽略了移動數(shù)字到正確位置的距離，因此我們可以計算所有數(shù)字橫向縱向距離之和來進一步改進估計方法。而在考慮各數(shù)字距離目的狀態(tài)的總距離的基礎上，考慮不同數(shù)字的權重又可以進一步提高求解效率。4.達到實驗目的通過對八數(shù)碼問題的寬度優(yōu)先搜索實驗，讀者應理解和掌握盲目搜索的相關知識，并認識到其在計算復雜度上的缺