數(shù)學(xué)建模中用到的啟發(fā)式算法(共8頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上啟發(fā)式搜索 "啟發(fā)"( heuristic)是關(guān)于發(fā)現(xiàn)和發(fā)明規(guī)則及方法的研究。在狀態(tài)空間搜索中, 啟發(fā)式被定義成一系列規(guī)則, 它從狀態(tài)空間中選擇最有希望到達問題解的路徑。 人工智能問題求解者在兩種基本情況下運用啟發(fā)式策略: 1.一個問題由于在問題陳述和數(shù)據(jù)獲取方面固有的模糊性可能使它沒有一個確定的解。醫(yī)療診斷即是一例。所給出的一系列癥狀可能有多個原因; 醫(yī)生運用啟發(fā)搜索來選擇最有可能的論斷并依此產(chǎn)生治療的計劃。視覺問題又是一例?？吹降木拔锝?jīng)常是模糊的, 各個物體在其連接、范圍和方向上可以有多個解釋。光所造成的幻覺加大了這些模糊性, 視覺系統(tǒng)可運用啟

2、發(fā)式策略選擇一給定景象的最有可能解釋。 2.一個問題可能有確定解, 但是求解過程中的計算機代價令人難以接受。在很多問題(如國際象棋)中, 狀態(tài)空間的增長特別快, 可能的狀態(tài)數(shù)隨著搜索的深度呈指數(shù)級增長、分解。在這種情況下, 窮盡式搜索策略, 諸如深度優(yōu)先或廣度優(yōu)先搜索,在一個給定的較實際的時空內(nèi)很可能得不到最終的解。 啟發(fā)式策略通過指導(dǎo)搜索向最有希望的方向前進降低了復(fù)雜性。通過仔細考慮, 刪除某些狀態(tài)及其延伸, 啟發(fā)式算法可以消除組合爆炸, 并得到令人能接受的解。 然而, 和發(fā)明創(chuàng)造的所有規(guī)則一樣, 啟發(fā)式策略也是極易出錯的。在解決問題過程中啟發(fā)僅僅是下一步將要采取措施的一個猜想。它常常根據(jù)經(jīng)

3、驗和直覺來判斷。由于啟發(fā)式搜索只有有限的信息,諸如當(dāng)前Open表中狀態(tài)的描述,要想預(yù)測進一步搜索過程中狀態(tài)空間的具體的行為很難辦到。一個啟發(fā)式搜索可能得到一個次最佳解, 也可能一無所獲。這是啟發(fā)式搜索固有的局限性。這種局限性不可能由所謂更好的 啟發(fā)式策略或更有效的搜索算法來消除。 啟發(fā)式策略及算法設(shè)計一直是人工智能的核心問題。博奕和定理證明是兩個最古老的應(yīng)用: 二者都需要啟發(fā)式知識來剪枝以減少狀態(tài)空間。顯然, 檢查數(shù)學(xué)領(lǐng)域中每一步推理或棋盤上每一步可能的移動是不可行的。啟發(fā)式搜索常常僅是實踐中的解答。 近來, 專家系統(tǒng)的研究把啟發(fā)式策略作為問題求解的一個重要部分。當(dāng)一個專家解決問題時, 他檢查

4、所獲取的信息并作出決定。實際上, 專家用來解決問題的"拇指法則"很大程度上是啟發(fā)式的。 這些啟發(fā)性知識被專家系統(tǒng)的設(shè)計者提取出來并形成規(guī)則。 通常啟發(fā)式算法由兩部分組成: 啟發(fā)方法和使用該方法搜索狀態(tài)空間的算法。本章先介紹最好優(yōu)先搜索的算法, 再討論啟發(fā)式算法的設(shè)計和評估。 在一字棋游戲中(圖4.5), 窮盡搜索的組合數(shù)很大。第一步移動共有九種移法 , 每一種又有八種對應(yīng)走法依次類推, 這個問題在窮盡搜索策略下需考慮9!個狀態(tài)。 根據(jù)對稱性可以減少搜索空間的數(shù)目。棋盤上很多構(gòu)造是等價的。譬如, 第一步實際上只有三種移法, 角、邊的中央以及網(wǎng)絡(luò)正中。在狀態(tài)空間的第二層上, 由

5、對稱性可進一步減少到12×7!種。在圖5.1 中可見到該狀態(tài)空間比最初的狀態(tài)空間要小, 但它在擴展過程中還要繼續(xù)分解。然而, 一個簡單的啟發(fā)式策略幾乎可以整個地消除復(fù)雜的搜索過程。首先, 將棋子移到棋盤上×有最多的贏線的點。最初的三種狀態(tài)顯示在圖5.2中。 若兩種狀態(tài)有相等的贏的機率, 取其中的第一個。這樣的話,可設(shè)計一種算法(完全實現(xiàn)啟發(fā)式搜索), 它選擇并移到具有最高啟發(fā)值的狀態(tài)。在這種情況下, ×占椐網(wǎng)絡(luò)的中間點, 其它的各種狀態(tài)都不再考慮, 它們的延伸狀態(tài)同時也給消除了。如圖5.3 所示三分之二的狀態(tài)空間就這樣給剪枝了。第一步走完后, 對方只能有兩種走法(

6、見圖5.3)。無論選擇哪種走法,我方均可以通過啟發(fā)式搜索選擇下一步可能的走法。在搜索過程中, 每一步只需估價一下單個節(jié)點的子結(jié)點; 不需要強力搜索。圖5.3 顯示了游戲前三步簡化了的搜索過程。每種狀態(tài)都標(biāo)記了它的啟發(fā)值。 要精確地計算待檢查的狀態(tài)的數(shù)目比較難, 但可以大致計算它的上限。一盤棋最多走九步, 每步的下一步平均有四、五種走法。這樣大約就是4.5×9, 近40種狀態(tài), 比9!改善了很多。 5.1 啟發(fā)信息和估計函數(shù) 人工智能的核心課題是問題求解。所謂"問題求解"就是在廣義圖中尋找一條從初始狀態(tài)出發(fā), 到達目標(biāo)狀態(tài)的解樹。例如旅行問題是解決從出發(fā)點到達目的地

7、的路線和工具問題; 機器人裝配機器, 就是給出把一堆零件變成一臺機器的一系列操作; 定理證明就是尋找一條從前提條件到達結(jié)論的通路等等。 在實際解決一個具體問題時, 人們常常把一個具有復(fù)雜聯(lián)系的實際問題抽象化,保留某些主要因素, 忽略掉大量次要因素, 從而將這個實際問題轉(zhuǎn)化成具有明確結(jié)構(gòu)的有限狀態(tài)空間問題, 這個空間中的狀態(tài)和變化規(guī)律都是已知的有限集合, 因此可以找到一個求解該問題的算法。 然而, 在智能活動中使用最多的不是具有完備性的算法, 而是不一定完備的啟發(fā)式方法。其原因有二: 首先, 大多數(shù)情況下, 智能系統(tǒng)不知道與實際問題有關(guān)的全部信息, 因而無法知道該問題的全部狀態(tài)空間, 不可能用一

8、套算法來求解其中的所有問題, 這樣就只能依靠部分狀態(tài)空間和一些特殊的經(jīng)驗性規(guī)則來求解其中的部分問題。 其次, 有些問題在理論上存在求解算法, 但是在工程實踐中, 這些算法不是效率太低, 就是根本無法實現(xiàn), 為了提高解題的效率, 不得不放棄使用這些算法, 而求助于一些經(jīng)驗性的啟發(fā)式規(guī)則。 例如在博弈問題中, 計算機為了保證最后勝利, 可以將所有可能的走法都試一遍, 然后選擇最佳走步。這樣的算法是可以找到的, 但計算所需的時空代價十分驚人。就可能有的棋局數(shù)講, 一字棋是9!=3.6×105, 西洋跳棋是1078, 國際象棋是10120, 圍棋是10761。假設(shè)每步可能選擇一種棋局, 用極

9、限并行速度(10-104年/步)計算, 國際象棋的算法也得1016年即1億億年才可以算完, 而我們已知的宇宙史才 100億年! 由此看來, 啟發(fā)式的問題求解, 不僅在實踐上是需要的, 而且在理論上也是必不可少的。 對問題空間進行搜索時, 提高搜索效率需要有和被解問題的解有關(guān)的大量控制性知識作為搜索的輔助性策略。有兩種極端的情況: 一種是沒有任何這種控制性知識作為搜索的依據(jù), 因而搜索的每一步完全是隨意的, 如隨機搜索; 另一種是有充分控制性知識作為依據(jù), 因而搜索的每步選擇都是正確的, 這種搜索叫最佳搜索。一般情況是介于二者之間, 這些控制性信息反映在估價函數(shù)之中。 估價函數(shù)的任務(wù)就是估計待搜

10、索結(jié)點的重要程度, 給它們排定次序。估價函數(shù)f(x)可以是任意一種函數(shù), 如有的定義它是結(jié)點x處于最佳路徑上的概率, 或是x結(jié)點和目標(biāo)結(jié)點之間的距離, 或是x格局的得分等等。一般來說, 估價一個結(jié)點的價值, 必須綜合考慮兩方面的因素: 已經(jīng)付出的代價和將要付出的代價。在此, 我們把估價函數(shù)f(n)定義為從初始結(jié)點經(jīng)過n 結(jié)點到達目標(biāo)結(jié)點的最小代價路徑的代價估計值, 它的一般形式是: f(n)=g(n)+h(n) 其中g(shù)(n)是從初始結(jié)點到n的實際代價, h(n)是從n到目標(biāo)結(jié)點的最佳路徑的估計代價, 主要是h(n)體現(xiàn)了搜索的啟發(fā)信息。因為實際代價g(n)可以根據(jù)生成的搜索樹實際計算出來, 而

11、估計代價h(n)卻依賴于某種經(jīng)驗估計, 它來源于我們對問題的解的某些特性的認識, 這些特性可以幫助我們更快地找到問題的解。 一般地, 在f(n)中, g(n)的比重越大, 越傾向于廣度優(yōu)先搜索方式; h(n)的比重越大, 越傾向于深度優(yōu)先搜索方式。 g(n)的作用一般是不可忽略的, 因為它代表了從初始結(jié)點經(jīng)過n 到達目標(biāo)結(jié)點的總代價估值中實際已付出的那一部分。保持g(n)項就保持了搜索的廣度優(yōu)先趨勢, 這有利于搜索的完備性, 但影響搜索的效率。在特殊情況下, 如果只希望找到達到目標(biāo)結(jié)點的路徑而不關(guān)心已付出的代價, 則g(n)的作用可以忽略。另外, h(n)> >g(n)時, 也可以

12、忽略g(n), 這時有f(n)=h(n), 這有利于搜索的效率, 但影響搜索的完備性。 給定一個問題后, 根據(jù)問題的特性和解的特性, 可以有多種方法定義估價函數(shù), 用不同的估價函數(shù)指導(dǎo)搜索, 其效果可以相差很遠。因此,必須盡可能選擇最能體現(xiàn)問題特性的, 最佳的估價函數(shù)。 5.2 啟發(fā)式搜索算法 5.2.1 局部擇優(yōu)搜索法(瞎子爬山法) 實現(xiàn)啟發(fā)式搜索最簡單的方法是瞎子爬山法(hill climbing)。 瞎子爬山法在搜索過程中擴展當(dāng)前結(jié)點并估價它的子結(jié)點。最優(yōu)的子結(jié)點被選擇并進一步擴展; 該子結(jié)點的兄弟結(jié)點和父結(jié)點都不再保留。當(dāng)搜索達到一種狀態(tài), 該狀態(tài)比它的所有子結(jié)點都要好, 則搜索停止。

13、瞎子爬山法可以這樣理解一個盲人急切地想登上山頂, 他總是沿著最陡的山路向上爬, 直到再不能找到新的路徑。瞎子爬山法有這樣一個缺陷: 一個錯誤的啟發(fā)知識可能導(dǎo)致搜索無法沿著正確的路徑前進, 從而增加了搜索的深度, 甚至是無窮盡地搜索。由于瞎子爬山法不保存所走過的結(jié)點信息, 故瞎子爬山算法無法修正錯誤的路徑。 瞎子爬山法還可能在一個局部的最佳點上停止。當(dāng)搜索到一個結(jié)點, 它的估計代價比任一個子結(jié)點都要小, 則算法結(jié)束。如果此時并不是目標(biāo)狀態(tài), 而只是一個局部最優(yōu)結(jié)點, 則該算法就不能得到目標(biāo)解。因此, 在一個限定的環(huán)境下, 瞎子爬山法可能會極大地提高搜索效率, 但是對于整個搜索空間, 就有可能無法

14、得到最佳解。重排九宮游戲就是一個突出的例子。為了將一個特定的格局移到它的目標(biāo)位置上, 常常需要移動已經(jīng)在其目標(biāo)位置上的將牌。這對于完成拼圖是必要的, 但它顯然暫時惡化了拼板上的狀態(tài)。由于"更好"并不是"最好", 瞎子爬山法無法區(qū)別局部和全局最優(yōu)解。處理這個問題時有許多種方法, 譬如隨時地修正估價函數(shù)來突破局部最優(yōu)的限制。但是總的來說, 沒有一種方法能保證瞎子爬山法的最佳效率。下面 介紹一個瞎子爬山法的例子跳棋程序。 在人工智能中, Samuel的跳棋程序最早應(yīng)用該方法。在跳棋程序中, 不僅運用了啟發(fā)式搜索, 還實現(xiàn)了簡單的學(xué)習(xí)功能。 跳棋程序中根據(jù)幾個不

15、同啟發(fā)值的總和來估算棋局的狀態(tài): aixii 其中xi是棋局的一系列特征, 如殘局優(yōu)勢、殘局棋子力量分布, 中心點位置的控制等。這些xi的系數(shù)由它在整個估值中所處的重要性來確定。也就是說, 如果殘局優(yōu)勢比控制中心點重要, 則殘局優(yōu)勢的系數(shù)要大。 該程序?qū)⑺阉骺臻g擴展到一定局數(shù)并根據(jù)多項式估值函數(shù)估算該局中所有狀態(tài)值。根據(jù)5.4.2節(jié)介紹的極大極小法, 程序可倒推出圖中所有狀態(tài)的估值。 游戲者根據(jù)結(jié)點的最佳狀態(tài)走棋; 對手走棋后, 根據(jù)新的棋局狀態(tài), 整個過程將再來一遍。 若多項式估值函數(shù)導(dǎo)向一系列不能取勝的移動, 程序?qū)⒄{(diào)整其系數(shù)以提高能力。具有較大系數(shù)的因素由于在輸棋原因中占很大比重, 它的

16、系數(shù)將減小, 而較小的系數(shù)將增 大以提高相關(guān)因素的影響力。如果取勝則情況相反。 通過與人或其自身的不同版本對抗, 程序不斷訓(xùn)練學(xué)習(xí)。 可以看出, 跳棋游戲在學(xué)習(xí)過程中采用的是瞎子爬山法, 通過對多項式估值函數(shù)的局部的改進來提高自身的性能。該程序能不斷改進到水平很高為止。然而, 由于算法依靠瞎子爬山法, 它不可避免地具有某些限制。例如, 由于采用的不是全局的策略, 程序容易被對手利用某種啟發(fā)策略導(dǎo)向陷阱。同樣, 程序的自學(xué)習(xí)功能容易被對手的隨手棋所迷惑; 例如, 老對手靈活地采用多種策略, 或故意亂下棋, 這就會使多項式估值函數(shù)的系數(shù)隨意性很大, 從而全面降低了程序的能力。 上例表明, 盡管瞎子

17、爬山法有其局限性, 但是若估價函數(shù)選取得當(dāng)并能夠避免局部最優(yōu)解和無窮搜索時, 它就會充分發(fā)揮搜索的高效率。總之, 啟發(fā)式搜索需要一個具有很多啟發(fā)信息的算法, 而最好優(yōu)先搜索就提供了這一算法。  5.2.2 最好優(yōu)先搜索法(有序搜索法) 和第四章中所提到的深度優(yōu)先及廣度優(yōu)先搜索算法一樣, 最好優(yōu)先搜索算法也使用了兩張表來記錄結(jié)點信息: 在Open表中保留所有已生成而未考察的結(jié)點; 在Closed表中記錄已訪問過的結(jié)點。算法中有一步是根據(jù)某些啟發(fā)信息, 按結(jié)點距離目標(biāo)狀態(tài)的長度大小重排Open表中的結(jié)點這樣。循環(huán)中的每一步只考慮Open表中狀態(tài)最好的結(jié)點, 這就是最好優(yōu)先搜索算法,又稱為

18、有序搜索法。其數(shù)據(jù)結(jié)構(gòu)(Open表)既不同于廣度優(yōu)先使用的隊(先進先出), 也不同于深度優(yōu)先使用的棧(后進先出) , 而是一個按結(jié)點的啟發(fā)估計函數(shù)值的大小為序排列的一個表, 有時也稱為"優(yōu)先隊"。進入優(yōu)先隊的結(jié)點不是簡單地排在隊尾(或隊首), 而是根據(jù)其估值的大小插入隊中 合適的位置, 每次從隊中優(yōu)先取出估值最小的結(jié)點加以擴展。 最好優(yōu)先搜索的算法描述如下: PROCEDURE BEST-FIRST-SEARCH INITIALIZE:OPEN=START;CLOSED= ; WHILE OPEN DO BEGIN REMOVE THE NEXT STATE FROM OP

19、EN, CALL IT X; IF X IS A GOAL THEN RETURN THE SOLUTION PATH THAT LED TO X; PROCESS X,GENERATING ALL ITS CHILDREN; FOR EACH CHILD OF X DO CASE THE CHILD IS NOT ALREADY ON OPEN OR CLOSED: BEGIN ASSIGN A HEURISTIC VALUE TO THE CHILD STATE; ADD THE CHILD STATE TO OPEN; END; THE CHILD IS ALREADY ON OPEN:

20、 IF THE CHILD WAS REACHED ALONG A SHORTER PATH THAN THE STATE CURRENLTY ON OPEN THEN GIVE THE STATE ON OPEN THIS SHORTER PATH VALUE THE CHILD IS ALREADY ON CLOSED: IF THE CHILD WAS REACHED ALONG A SHORTER PATH THAN THE STATE CURRENLTY ON CLOSED THEN BEGIN GIVE THE STATE ON CLOSED THIS SHORTER PATH V

21、ALUE; MOVE THIS STATE FROM CLOSED TO OPEN END END; PUT X ON CLOSED; RE-ORDER STATES ON OPEN ACCORDING TO HEURISTIC MERIT (BEST VALUES FIRST) END; RETURN(FAILURE); %OPEN IS EXHAUSTED END. 在每一次重復(fù)中, 最好優(yōu)先搜索算法從Open表中取出第一個元素, 如果該元素滿足目標(biāo)條件, 則算法返回到達該元素的搜索路徑。在這里, 每個結(jié)點都保留父結(jié)點的信息, 以保證返回完整的搜索路徑。 若Open表的第一個元素不是目標(biāo)結(jié)

22、點, 則算法應(yīng)用相應(yīng)的規(guī)則進行一系列操作來產(chǎn)生它的子結(jié)點。如果子結(jié)點的狀態(tài)已在Open(或Closed表)中, 則算法保證新的狀態(tài)記錄兩個求解路徑中花費小的一個, 不保留重復(fù)的狀態(tài)。這樣, 當(dāng)Open表(或Closed表)中的結(jié)點再一次被發(fā)現(xiàn)時, 通過刷新它的祖先結(jié)點的歷史記錄, 算法就極有可能得到到達目標(biāo)結(jié)點的更短的路徑。 接著, 最好優(yōu)先搜索法估算Open表中每個結(jié)點的狀態(tài)的啟發(fā)值, 按照值的大小重新排序, 將值最小的狀態(tài)放在表頭。 圖5.4是一個層次式狀態(tài)空間, 有些結(jié)點旁邊標(biāo)上了相應(yīng)的啟發(fā)值。 標(biāo)上值的那些狀態(tài)都是在最好優(yōu)先搜索中實際生成的。在這張圖中, 啟發(fā)搜索算法擴展的狀態(tài)都已顯示

23、; 算法無需搜索所有的狀態(tài)空間。最好優(yōu)先搜索算法的目標(biāo)是盡可能地減小搜索空間而得到解, 啟發(fā)信息給得越多, 處理的狀態(tài)就越少。 下面給出了這張圖的最好優(yōu)先搜索算法的運行過程。假定P是目標(biāo)狀態(tài), 則到P 的路徑上的結(jié)點狀態(tài)有較低的啟發(fā)值。在這里, 啟發(fā)信息難免會有錯誤; 狀態(tài)O比P的值小而先被檢查。然而, 不象瞎子爬山法, 該算法本身有糾錯功能, 能從此狀態(tài)返回并找到正確的目標(biāo)狀態(tài)。 1. Open=A5; Closed= 2. 估算A5; Open=B4,C4,D6; Closed=A5 3. 估算B4; Open=C4,E5,F5,D6; Closed=B4,A5 4. 估算C4; Open

24、=H3,G4,E5,F5,D6; Closed=C4,B4,A5 5. 估算H3; Open=O2,P3,G4,E5,F5,D6; Closed=H3,C4,B4,A5 6. 估算O2; Open=P3,G4,E5,F5,D6; Closed=O2,H3,C4,B4,A5 7. 估算P3; 已得到解! 圖5.5是算法執(zhí)行了五次循環(huán)后的狀態(tài)空間圖。Open表和Closed 表中的狀態(tài)以不同的亮度顯示。Open表中記錄搜索的當(dāng)前結(jié)點, Closed表中保存已考察過的狀態(tài)。 最好優(yōu)先搜索算法總是從Open表中選取最"好"的狀態(tài)進行擴展。但是, 由于啟發(fā)信息有時可能出錯, 故算法并

25、不丟棄其它的狀態(tài)而把它們保留在Open表中。當(dāng)某一個啟發(fā)信息將搜索導(dǎo)向錯誤路徑時, 算法可以從Open表中檢索先前產(chǎn)生的" 次最好"狀態(tài), 并且將考察方向轉(zhuǎn)向空間的另一部分上。如圖5.4, 當(dāng)算法發(fā)現(xiàn)狀態(tài)B 的子結(jié)點有很差的啟發(fā)值時, 搜索轉(zhuǎn)移到C, 但B的子結(jié)點都保留在Open表中, 以防算法在未來的某一步再一次轉(zhuǎn)向它們。在最好優(yōu)先搜索算法中, 就象第四章中的算法一樣, 當(dāng)某一路徑無法到達目標(biāo)解時, 可使搜索轉(zhuǎn)到另一條路徑上。 5.2.3 啟發(fā)估計函數(shù)的實現(xiàn) 不同的啟發(fā)策略對解決九宮問題有不同的影響。圖5.6 顯示了九宮問題的起始狀態(tài)、目標(biāo)狀態(tài)以及搜索過程中產(chǎn)生的前三個狀

26、態(tài)。 最簡單的啟發(fā)策略是計算每種格局下與目標(biāo)結(jié)點的格局相比時位置不符的將牌數(shù)目。從感覺上來說, 這種策略很有效, 因為在其它條件相同的情況下, 位置不符將牌數(shù)目越少, 它看上去和最終目標(biāo)越近, 因而是檢驗的下一個狀態(tài)。 但是, 這種策略并沒有充分利用所能獲得的信息, 它沒有考慮將牌所需移動的距離。一個"較好"的啟發(fā)策略是將牌移到目標(biāo)位置上時所需移動距離的總和相加作為啟發(fā)值。這兩種策略都沒有考慮將牌逆轉(zhuǎn)時的情況, 也就是, 如果兩塊將牌相鄰但是和目標(biāo)格局相比位置相反, 這至少需要移動兩次才能將它們移到正確的位置上, 將這一點加以考慮的啟發(fā)策略對每一對逆轉(zhuǎn)將牌乘以一個小倍數(shù)(如

27、2)。圖5.8顯示的就是將這三種策略運用到圖5.6的三個子狀態(tài)情況下所得到的結(jié)果。 在圖5.8中, "距離總和" 策略看上去比僅僅計算位置不符將牌數(shù)目的策略提供了一個更精確的估算。而且, 由于在這些狀態(tài)中, 沒有直接給出逆位數(shù), 故都給予估值。第四種策略克服了僅計算將牌逆轉(zhuǎn)數(shù)目策略的局限, 它將位置不符將牌數(shù)目總和與2倍將牌逆轉(zhuǎn)數(shù)目相加。 這個例子說明, 設(shè)計一個好的啟發(fā)策略具有相當(dāng)?shù)碾y度。設(shè)計算法的目標(biāo)就是利用有限的信息作出一個明智的選擇。上述策略都忽略了一些重要的信息, 需加以改進。好的啟發(fā)策略的設(shè)計是一個經(jīng)驗問題, 判斷和直覺是很重要的因素, 但是衡量的最終尺度則是具

28、體應(yīng)用時的效果。 由于所有的啟發(fā)策略都可能出錯, 每一種搜索算法都可能導(dǎo)向錯誤的路徑, 但是在深度優(yōu)先搜索中, 可用深度計數(shù)探查無效路徑來解決這個問題。這個思想也可運用到啟發(fā)式搜索中。如果兩種狀態(tài)具有相等的啟發(fā)值, 通常先考察離根較近的那個狀態(tài)。這個狀態(tài)極有可能就處在到達目標(biāo)狀態(tài)的最佳路徑上?？捎靡粋€深度計數(shù)來記錄從起始狀態(tài)到其子孫狀態(tài)的距離。計數(shù)起始值為0, 每搜索一層計數(shù)值加1。 這個值可加到啟發(fā)值上, 層數(shù)越淺的狀態(tài)越優(yōu)先。 這樣, 就得到了估計函數(shù)f, 它由兩個因素所組成: f(n)=g(n)+h(n)其中g(shù)(n)是狀態(tài)n到達起始狀態(tài)的路徑的實際長度, h(n)是狀態(tài)n到目標(biāo)狀態(tài)的最佳

29、路徑的啟發(fā)值。 在九宮問題中, 可令h(n)為位置不符的將牌數(shù)目。若將這個估計函數(shù)值運用到 圖5.6的子狀態(tài)中, 它們的f值分別是6,4,6(見圖5.9)。 各個狀態(tài)的f(n)值 這里f(n)=g(n)+h(n) g(n)=從n到初始狀態(tài)的實際長度 h(n)=位置不符的將牌數(shù)目 圖5.9 九宮圖的估計函數(shù)f值 在圖5.10中, 使用上面所定義的f函數(shù)得到一個完整的搜索樹。 每種狀態(tài)都以一個字母及它的估計函數(shù)值f來標(biāo)記。每種狀態(tài)頭部的數(shù)字顯示該狀態(tài)從Open 表中取出時的順序。有些狀態(tài)沒有數(shù)字標(biāo)記, 這是因為當(dāng)算法結(jié)束時, 這些狀態(tài)仍在Open表中。 圖5.10 啟發(fā)式搜索產(chǎn)生的九宮圖狀態(tài)空間 產(chǎn)生圖5.10的一系列過程如下: 1.open=a4; closed= 2.open=c4,b6,d6; closed=a4 3.open=e5,f5,g6,b6,d6; closed=a4,c4 4.open=f5,h6,g6,b6,d6,i7; closed=a4,c4,e5 5.open=j5,h6,g6,b6,d6,k7,i7; closed=a4,c4,e5,f5 6.open=l5,h6,g6,b6,d6,k7,i7; closed=a4,c4,e5,f5,j5 7.open=m5,h6,g6,b6,d6,n7,k7,i7; closed=a4,c4,e5,