人工智能與機器翻譯

人工智能與機器翻譯主講：楊憲澤——產(chǎn)生式系統(tǒng)及其搜索方法第3章產(chǎn)生式系統(tǒng)及其搜索方法3.1產(chǎn)生式系統(tǒng)3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略3.3圖搜索算法3.4產(chǎn)生式系統(tǒng)的規(guī)則問題3.5應用舉例3.6產(chǎn)生式系統(tǒng)的不確定性問題3.7系統(tǒng)設計技巧3.1產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)使用類似于文法的規(guī)則,對符號串作替換運算。它是智能軟件中使用最普遍、最典型的一種結構。為什么要采用產(chǎn)生式系統(tǒng)作為智能軟件的主要結構呢?這可以有兩點理由:

(1)用產(chǎn)生式系統(tǒng)結構求解問題的過程和人類求解問題時的思維過程很相象,因而可以用它來模擬人類求解問題時的思維過程;(2)可以把產(chǎn)生式系統(tǒng)作為智能軟件中的基本結構單元或基本模式看待,就好象是積木世界中的積木塊一樣,因而研究產(chǎn)生式系統(tǒng)的基本問題就具有一般意義。3.1產(chǎn)生式系統(tǒng)3.1.1產(chǎn)生式系統(tǒng)的組成部分一個智能軟件用產(chǎn)生式系統(tǒng)設計的基本組成是:一個綜合數(shù)據(jù)庫;一組產(chǎn)生式規(guī)則;一個控制系統(tǒng)。綜合數(shù)據(jù)庫是產(chǎn)生式系統(tǒng)所使用的主要數(shù)據(jù)結構,用來表述問題的狀態(tài)或有關事實。它包含求解問題的信息,其中有些部分可以是不變的,有些部分可能只與當前問題的解有關。人們可以根據(jù)問題的性質(zhì),用適當?shù)姆椒▉順嬙炀C合數(shù)據(jù)庫的信息。3.1產(chǎn)生式系統(tǒng)

3.1.1產(chǎn)生式系統(tǒng)的組成部分產(chǎn)生式規(guī)則的一般形式為:條件─→行動或前提─→結論即表示成為:if┄┄then┄┄的形式。其中,左邊確定了該規(guī)則可應用的先決條件;右邊描述了應用這條規(guī)則所采取的行動或得出的結論。一條產(chǎn)生式規(guī)則滿足了應用的先決條件之后,就可對綜合數(shù)據(jù)庫進行操作,使其發(fā)生變化。如綜合數(shù)據(jù)庫代表當前狀態(tài),則應用規(guī)則后就使狀態(tài)發(fā)生轉換,生成新狀態(tài)。3.1產(chǎn)生式系統(tǒng)

3.1.1產(chǎn)生式系統(tǒng)的組成部分控制系統(tǒng)是軟件的控制程序,也是規(guī)則的解釋(推理)程序。它規(guī)定了如何選擇一條可應用的規(guī)則對數(shù)據(jù)庫進行操作,即確定了求解過程的推理路線。當數(shù)據(jù)庫滿足結束條件時,系統(tǒng)就應停止運行;還要使系統(tǒng)在求解過程中記住應用過的規(guī)則序列,以便最終能給出解的路徑?？刂葡到y(tǒng)也稱控制策略,它也可以是從規(guī)則集中選擇規(guī)則并作用于狀態(tài)的一種廣義選取函數(shù)。確定某一種策略后,可以算法的形式給出。在建立產(chǎn)生式系統(tǒng)描述時,還要給出初始狀態(tài)和目標條件,具體說明所求解的問題。產(chǎn)生式系統(tǒng)中控制策略的作用就是從初始狀態(tài)出發(fā),尋求一個滿足一定條件的問題狀態(tài)。目標條件也是產(chǎn)生式系統(tǒng)結束條件的基礎。3.1產(chǎn)生式系統(tǒng)

3.1.1產(chǎn)生式系統(tǒng)的組成部分上述產(chǎn)生式系統(tǒng)的定義具有一般性,它可用來模擬任一可計算過程。在研究人類進行問題求解過程時,完全可用一個產(chǎn)生式系統(tǒng)來模擬求解過程,及可作為描述搜索的一種有效方法。作為智能中的一種形式體系,它還具有以下優(yōu)點:

(1)適合于模擬強數(shù)據(jù)驅(qū)動特點的智能行為。當一些新的數(shù)據(jù)數(shù)入時,系統(tǒng)的行為就要改變;(2)易于添加新規(guī)則去適應新的情況,而不破壞系統(tǒng)的其他部分。這是由于產(chǎn)生式系統(tǒng)的各組成部分具有相對的獨立性,因而便于擴展和修改。3.1產(chǎn)生式系統(tǒng)3.1.1產(chǎn)生式系統(tǒng)的組成部分

用產(chǎn)生式系統(tǒng)來求解問題,首先必須建立起問題的產(chǎn)生式系統(tǒng)描述,即規(guī)定出數(shù)據(jù)庫、規(guī)則集合及其控制策略。這種把一個問題的敘述轉化為產(chǎn)生式系統(tǒng)的三個組成部分,在智能技術中通常稱為問題的表示。一般來說一個問題可有多種表示方式,而選擇一種較好的表示是運用智能技術解決實際問題首先要考慮的,而且要有一定的技巧。建立了產(chǎn)生式系統(tǒng)描述之后,通過控制策略,可求得實現(xiàn)目標的一個規(guī)則序列,這就是所謂問題的解,這個解序列是根據(jù)控制系統(tǒng)記住搜索目標過程中用過的所有規(guī)則而構造出來的。3.1產(chǎn)生式系統(tǒng)

3.1.1產(chǎn)生式系統(tǒng)的組成部分在一般情況下,問題可能有多個解的序列,但有時會要求得到有某些附加約束條件的解,例如要求步數(shù)最少、距離最短等。這些約束條件通常是用耗散或代價這一概念來概括,這時問題可稱為尋找具有最小耗散的解。在用產(chǎn)生式系統(tǒng)求解問題時,有時引入狀態(tài)空間圖。狀態(tài)空間圖是一個有向圖,其節(jié)點可表示問題的各種狀態(tài)(綜合數(shù)據(jù)庫),節(jié)點之間的弧線代表一些操作(產(chǎn)生式規(guī)則),它們可把一種狀態(tài)導向另一種狀態(tài)。這樣建立起來的狀態(tài)空間圖,描述了問題所有可能出現(xiàn)的狀態(tài)及狀態(tài)和操作之間的關系,因而可以較直觀地看出問題的解路徑及其性質(zhì)。當然,只有問題空間規(guī)模較小才可能作出狀態(tài)空間圖。3.1產(chǎn)生式系統(tǒng)

3.1.1產(chǎn)生式系統(tǒng)的組成部分

建立產(chǎn)生式系統(tǒng)描述的過程,就是所謂問題的表示。對問題表示的好壞,往往對求解過程的效率有很大的影響。一種較好的表示法會簡化狀態(tài)空間和規(guī)則集表示,此外,高效率的問題求解過程與控制策略有關,合適的控制策略可縮小狀態(tài)空間的搜索范圍,提高求解的效率。從以上論述可知,用產(chǎn)生式系統(tǒng)來描述和求解問題,就是在問題空間中搜索一條從初始狀態(tài)到達某一個目標狀態(tài)的路徑。這完全可以模擬人的求解過程,也就是可以把產(chǎn)生式系統(tǒng)作為求解問題思考過程的一種模擬。3.1產(chǎn)生生式式系系統(tǒng)統(tǒng)產(chǎn)產(chǎn)生生式式系系統(tǒng)統(tǒng)的的基基本本算算法法E1:DATA←←初初始始事事實實庫庫E2:untilDATA滿滿足足結結束束條條件件以以前前,doE3:beginE4:在在規(guī)則則集中,選某一一條可用用于DATA的的規(guī)則E5:DATA←規(guī)規(guī)則應用用到DATA得得到的結結果E6:結結束3.1產(chǎn)生式系系統(tǒng)3.1.3產(chǎn)產(chǎn)生式系系統(tǒng)的類類型正向、逆逆向、雙雙向產(chǎn)生生式系統(tǒng)統(tǒng)用產(chǎn)生式式系統(tǒng)求求解某一一問題時時,如如果按按照規(guī)則則使用的的方式或或者說按按推理方方向來劃劃分的話話,有有正正向、逆逆向和雙雙向產(chǎn)生生式系統(tǒng)統(tǒng)。正正向產(chǎn)生生式系統(tǒng)統(tǒng)是從初初始狀態(tài)態(tài)出發(fā)朝朝著目標標狀態(tài)這這個方向向使用規(guī)規(guī)則,即即正推的的方式工工作,稱稱這些規(guī)規(guī)則為F規(guī)則;若若選選目標狀狀態(tài)作為為初始數(shù)數(shù)據(jù)庫庫逆向進進行求解解,即即逆向使使用規(guī)則則,產(chǎn)產(chǎn)生生子目標標狀態(tài),反反方方向一步步一步朝朝著初始始狀態(tài)方方向求解解,整整個逆逆推方式式工作,稱稱逆逆向產(chǎn)生生式系統(tǒng)統(tǒng),逆逆向應用用的規(guī)則則稱B規(guī)規(guī)則;若若以雙雙向搜索索的方式式(即正正向和逆逆向同時時進行)去求解解問題,則稱稱為雙向向產(chǎn)生式式系統(tǒng)。。3.1產(chǎn)產(chǎn)生式式系統(tǒng)3.1.3產(chǎn)產(chǎn)生式系系統(tǒng)的類類型可交換的的產(chǎn)生式式系統(tǒng)可交換式式產(chǎn)生式式系統(tǒng)的的可交換換性指幾幾條規(guī)則則的應用用可以任任意交換換次序而而不影響響求解。。一般來說說,當當一一個產(chǎn)生生式系統(tǒng)統(tǒng)對任何何一個數(shù)數(shù)據(jù)庫D都具有有如下性性質(zhì)時,這這樣一一個產(chǎn)生生式系統(tǒng)統(tǒng)是可可交換的的。(1)可可應用于于D的規(guī)規(guī)則集合合,使使用用了其中中任意一一條規(guī)則則之后所所生成的的任何數(shù)數(shù)據(jù)庫,這這樣一一個規(guī)則則集合還還適用;(2)滿滿足目目標條件件的某個個數(shù)據(jù)庫庫D,當當應用任任何一個個可應用用于數(shù)據(jù)據(jù)庫D的的規(guī)則則之后所所生成成的任何何數(shù)據(jù)庫庫,任任然滿足足目標條條件;(3)若若對D應用某某一規(guī)則則序列后后得到的的一個數(shù)數(shù)據(jù)庫D'(并并能達到到解),當當改變這這些規(guī)則則次序后后,任任然然可求得得解,即即求得D'與使使用滿足足D的可可應用規(guī)規(guī)則集合合中的規(guī)規(guī)則次序序無關。。3.1產(chǎn)生式系系統(tǒng)3.1.3產(chǎn)產(chǎn)生式系系統(tǒng)的類類型可交換的的產(chǎn)生式式系統(tǒng)例:給定定一個整整數(shù)集合合的初始始狀態(tài){a,b,c},設目目標狀態(tài)態(tài)為具有有a,b,c,ab,bc,ca這六六個元素素組成的的集合。?？蓱糜玫囊?guī)則則集合為為R1:if{a,b,c}then{a,b,c,ab}R2:if{a,b,c}then{a,b,c,bc}R3:if{a,b,c}then{a,b,c,ca}顯然,這這個產(chǎn)產(chǎn)生式實實例具有有可交換換性。一個產(chǎn)生生式系統(tǒng)統(tǒng)具有可可交換性性,求求解時時只需搜搜索其中中任一條條途徑,只只要解解存在就就一定定能找到到目標,不不必探索索多條途途徑,因因此不可可撤回的的控制方方式(下下節(jié)論述述)在在這種系系統(tǒng)中使使用很合合適,因因解與最最初可應應用的規(guī)規(guī)則系列列的次序序無關,系系統(tǒng)不必必提供特特殊選擇擇規(guī)則的的機理。3.1產(chǎn)生式系系統(tǒng)3.1.3產(chǎn)產(chǎn)生式系系統(tǒng)的類類型可分解的的產(chǎn)生式式系統(tǒng)先研究一一個重寫寫問題的的產(chǎn)生式式系統(tǒng),初初始數(shù)據(jù)據(jù)庫為(C,B,Z),產(chǎn)產(chǎn)生式式規(guī)則如如下:R1:C→(D,L)R2:C→(B,M)R3:B→(M,M)R4:Z→(B,B,M)結束條件件是生成成只包含含M組成成的數(shù)據(jù)據(jù)庫,即即(M,……,M)。。3.1產(chǎn)生式系系統(tǒng)3.1.3產(chǎn)產(chǎn)生式系系統(tǒng)的類類型可分解的的產(chǎn)生式式系統(tǒng)用圖搜索索方式求求解這個個問題時時,搜搜索得到到的部分分狀態(tài)空空間圖見見圖26。圖圖中只給給出兩條條達到目目標的路路徑和一一條失敗敗的路徑徑。實際際搜索時時有可能能去探索索更多的的路徑,往往往往導致效效率降低低。對于個問問題,為為了避免免搜索多多余的路路徑,可可以將將初始數(shù)數(shù)據(jù)庫分分解成幾幾個可以以獨立加加以處理理的分量量,分分別對它它們進行行求解。。即即可以分分別對每每一個分分量數(shù)據(jù)據(jù)庫,測測試產(chǎn)產(chǎn)生式規(guī)規(guī)則可以以應用的的條件,如如此進進行下去去,直直到分量量數(shù)據(jù)庫庫滿足某某種結束束條件為為止。要要注意意一般結結束條條件應是是所有分分量數(shù)據(jù)據(jù)庫都已已滿足結結束條件件。3.1產(chǎn)生式系系統(tǒng)3.1.3產(chǎn)產(chǎn)生式系系統(tǒng)的類類型可分解的的產(chǎn)生式式系統(tǒng)能夠分解解產(chǎn)生式式系統(tǒng)的的綜合數(shù)數(shù)據(jù)庫和和結束條條件的產(chǎn)產(chǎn)生式系系統(tǒng)稱為為可分解解的產(chǎn)生生式系統(tǒng)統(tǒng)。一個個可分解解的產(chǎn)生生式系統(tǒng)統(tǒng),其其基本算算法描述述如下:(1)DATA:=初始數(shù)數(shù)據(jù)庫(2){Di}:=DATA的分分解式;每個個Di元元素都看看成單獨獨的數(shù)據(jù)據(jù)庫(3)Until{Di}的所所有元素素都滿足足結束條條件之前前,do:(4)begin(5)從從{Di}中選選一個不不滿足結結束條件件的D*(6)從從{Di}中刪刪去D*(7)在在規(guī)則集集中選擇擇一條可可應用于于D*的的規(guī)則R(8){di}:=R應用于于D*的的結果(9)在在{Di}上添添加di(10)end下圖為分分解方式式(C,B,Z)初態(tài)┌────────┼────────┐↓R2↓↓R4R1↓↓(B,M,B,Z)(C,B,B,B,M)(D,L,B,Z)↓R3↓↓R2↓↓R3(M,M,M,B,Z)(B,M,B,B,B,M)(D,L,M,M,Z)↓R3↓↓R3↓↓R4(M,M,M,M,M,Z)(M,M,M,B,B,B,M)(D,L,M,M,B,B,M)│┌┌──────┘││↓R4↓R3↓↓R3(M,M,M,M,M,B,B,M)(D,L,M,M,M,B,M)↓R3↓↓R3(M,M,M,M,M,M,M,B,M)──┐(D,L,M,M,M,M,M,M,M)R3↓目標(M,M,M,M,M,M,M,M,M,M)圖263.2產(chǎn)生生式系統(tǒng)的搜搜索(控制)策略在3.1.2節(jié)的的算法中,如如何選擇擇一條可應用用的規(guī)則,作作用于當當前的綜合數(shù)數(shù)據(jù)庫,生生成新的的狀態(tài)以及及記住選用的的規(guī)則序列是是構成控制策策略的主要內(nèi)內(nèi)容。對大多多數(shù)的智能應應用問題,所所擁有有的控制策略略知識或信息息并不足以使使每次通過算算法E4時,一下子子就能選出最最合適的一一條規(guī)則來,因而而產(chǎn)生式系統(tǒng)統(tǒng)還必須把E4擴大成搜搜索(推理)算法,以以至于基本本算法的每一一循環(huán)中選選一條規(guī)則試試用,最最終找出某某一序列能產(chǎn)產(chǎn)生一個滿足足結束條件的的數(shù)據(jù)庫為止止。由此可見見,高效率率的控制策略略需要有關被被求解問題的的足夠知識,這樣才才能在搜索過過程減少盲盲目性,比比較快的找到到解路徑。過去三十多年年中,人們們研究了許多多種搜索算法法,歸納起來來主要有兩類類:一一類是非啟發(fā)發(fā)式算法;另一類是是啟發(fā)式算法法。非啟發(fā)發(fā)式算法是按按預定的控制制策略進行搜搜索,在在其過程中獲獲得的中間信信息不用來改改進控制策略略。由于搜搜索總是按預預先規(guī)定的路路線進行,沒沒有考慮慮問題本身的的特性,所所以不容容易選擇到最最優(yōu)的搜索途途徑,效效率較低,且出現(xiàn)"組合爆炸"的頻率高。。啟發(fā)式算算法是在搜索索中加入了與與問題有關的的啟發(fā)性信息息,用以以指導搜索朝朝著最有希望望的方向前進進,加速問問題的求解過過程并找到最最優(yōu)解。3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略3.2.1產(chǎn)產(chǎn)生式式系統(tǒng)控制策策略分類可分解的產(chǎn)生生式系統(tǒng)控制策略可劃劃分為兩大類類:┌不可撤回方方法┌回回溯方法└試探性方法法─┤└圖搜索方法法3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略3.2.2不不可撤撤回方法這種方法相當當于沿著單獨獨一條路搜索索下去,利利用問題給給出的局部知知識決定如何何選取規(guī)則,就是是說根據(jù)當前前可靠的局部部知識選一條條可應用規(guī)則則并作用于當當前綜合數(shù)據(jù)據(jù)庫。接著著再根據(jù)新狀狀態(tài)繼續(xù)選取取規(guī)則,搜搜索過程一一直進行,不不必考慮撤撤回用過的規(guī)規(guī)則。這是是由于在搜索索過程中如能能有效利用局局部知識,即即使使使用了一條不不理想的規(guī)則則,也不不妨礙下一步步選得另一條條更合適的規(guī)規(guī)則。這樣不不撤消用過的的規(guī)則,并并不影響響求到解,只只是解序序列中可能多多了一些不必必要的規(guī)則。。顯然這種策策略具有控制制簡單的優(yōu)點點。3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略3.2.2不不可撤撤回方法爬山法不僅適適用于爬山問問題,那些些目標為極大大值,搜搜索過程是不不斷接近目標標的單值問題題都可應用這這一方法。使使用不可撤回回策略,雖雖然不可能能對任何狀態(tài)態(tài)總能選得最最優(yōu)的規(guī)則,但是如果果應用了一條條不合適的規(guī)規(guī)則之后,不不去撤消消它并不排除除下一步應用用一條合適的的規(guī)則,那那么只是解序序列有些多余余的規(guī)則而已已,求得的的解不是最優(yōu)優(yōu)解,但控控制較簡單。。此外還應當當指出,一一般很難對給給定問題構造造出任何情況況下都能通用用的爬山函數(shù)數(shù),因而而不可撤回回的方法具有有一定的局限限性。3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略回回溯方法在問題求解過過程中,有有時會發(fā)現(xiàn)現(xiàn)應用一條不不合適的規(guī)則則會阻擾或拖拖延達到目標標的過程。在在這種情況下下,需要有有這樣的控制制策略:先先試一試某一一條規(guī)則,如如果以后后發(fā)現(xiàn)這條規(guī)規(guī)則不合適,則允允許退回去,另選選一條規(guī)則來來試?；厮莘椒椒ú槐Ａ敉晖暾乃阉鳂錁浣Y構,只只記住當當前工作的一一條路徑,回回溯就就是對這條路路徑進行修正正。使用回溯策略略首要的問題題要研究在什什么情況下應應該回溯,即即要確定定回溯條件的的問題。其次次就是如何利利用有用知識識進行規(guī)則排排序,以減減少回溯次數(shù)數(shù)?；厮輵獞l(fā)生在以下下三種情況:(1)新新生成的狀狀態(tài)在通向初初始狀態(tài)的路路徑上已出現(xiàn)現(xiàn)過;(2)從從初始狀態(tài)態(tài)開始,應應用的規(guī)則數(shù)數(shù)目達到所規(guī)規(guī)定的數(shù)目之之后還未找到到目標狀態(tài)(這一組規(guī)則則的數(shù)目實際際上就是搜索索深度范圍所所規(guī)定的);(3)對當當前狀態(tài),再再沒有可應應用的規(guī)則。。3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略回回溯方法搜索深度的設設置是一個值值得注意的問問題,設置置太淺,有有可能找找不到解;設設置太太深,有可可能導致回溯溯次數(shù)巨增。。因而應根據(jù)據(jù)實際情況來來規(guī)定搜索范范圍,先先設置適中的的深度搜索,失敗時再再逐步加深。。回溯過程是一一種可試探的的方法,從從形式上上無論是否存存在對選擇規(guī)規(guī)則有用的知知識,都都可以采用這這種策略。即即如果沒有有有用的知識來來引導規(guī)則選選取,那那么規(guī)則可可按任意方式式(固定排序序或隨機)選選取;如如果有好的的選擇規(guī)則的的知識可用,那么用這這種知識來引引導規(guī)則選取取,就會會減少盲目性性,降低回回溯次數(shù),甚甚至不回溯溯就能找到解解,總之之一般來說有有利于提高效效率。此外由由于引入回溯溯機理,可可以避免陷入入局部極大值值的情況,繼繼續(xù)尋找找其他達到目目標的路徑。。3.2產(chǎn)產(chǎn)生式系統(tǒng)的的搜索(控制制)策略回回溯方法可用遞歸算法法描述回溯策策略:YX0:選選擇一條新路路徑搜索;YX1:搜搜索已超出規(guī)規(guī)定指標(無無新路徑、超超時,超深深度等),失失敗退出;否則搜索繼繼續(xù);YX2:搜搜索的狀態(tài)找找不到可用規(guī)規(guī)則,回溯溯到YX0;YX3:搜搜索的狀態(tài)依依某種原則(任意排列或或按啟發(fā)式準準則)取有用用規(guī)則;YX4:若若規(guī)則用完未未找到目標,回溯YX0;YX5:取取頭條可用規(guī)規(guī)則Ri;YX6:刪刪去頭條規(guī)則則,減少搜搜索中規(guī)則集集長度(注意意,這不動動原始規(guī)則集集);YX7:規(guī)規(guī)則Ri作用用于當前狀態(tài)態(tài),生成新新狀態(tài);YX8:若若找到目標,成功退出出;若生成成的"新狀態(tài)態(tài)"已出現(xiàn)過過,回溯到到YX0;YX9:記記錄新狀態(tài),對新狀態(tài)態(tài)遞規(guī)調(diào)用YX1～YX7;產(chǎn)生式系統(tǒng)求求解問題時,如果控控制系統(tǒng)保留留所有規(guī)則應應用后生成并并鏈接起來的的狀態(tài)記錄圖圖,則則稱工作在這這種方式下的的控制系統(tǒng)使使用了圖搜索索策略。實實際上圖搜索索策略是實現(xiàn)現(xiàn)從一個隱含含圖中,生生成一部分確確實含有一個個目標節(jié)點的的顯式表示的的子圖搜索過過程。3.3圖搜搜索算法3.3圖搜搜索算法3.3.1一一般性圖搜索索算法步驟1G←←S,OPEN←(S);建立一一個搜索圖G,它只含有有初始節(jié)點S,建立一一個OPEN表(今后后它用于存儲儲生成的節(jié)點點),開始始它只含有初初始節(jié)點S。。步驟2CLOSED←←();建立一個個CLOSED表(今后后它用于存儲儲已擴展節(jié)點點或?qū)⒁獢U展展的某個節(jié)點點),它它的初始狀態(tài)態(tài)為空表。步驟3LOOP:ifOPEN=()thenreturnFAIL;進進入循環(huán)。。如果OPEN表已空空,說說明沒有節(jié)點點可擴展,就就返回FAIL,即即失敗。步驟4n←←FIRST(OPEN),CLOSED←←(n,CLOSED);從從OPEN表中取出一一個節(jié)點n,將其放放入CLOSED表中中。3.3圖搜搜索算法典典型的非非啟發(fā)式圖搜搜索算法分析析與改進廣度優(yōu)先搜索索法該方法從初始始節(jié)點開始,序擴展展生成下一級級各子節(jié)點,OPEN表中已已有的節(jié)點后后面(實現(xiàn)現(xiàn)先生成的子子節(jié)點先擴展展),然然后從OPEN表中中提取最前的的一個節(jié)點檢檢查是否是目目標節(jié)點,否否則再擴擴展,再再重復上述操操作。這這種方法認為為同一級各節(jié)節(jié)點對問題求求解的價值是是同等的,因因而對對全部節(jié)點沿沿廣度進行橫橫向掃描,按按各節(jié)節(jié)點生成的先先后次序,先先生成、先檢檢查、先擴展展,沿廣廣度遍歷所有有節(jié)點。這種方法只要要問題有解,即若若樹圖上存在在目標節(jié)點,經(jīng)搜搜索一定能找找到。所以以,廣度度優(yōu)先搜索法法是完備的,是一種推推理算法。但但是,在在問題大節(jié)節(jié)點多,且且目標節(jié)點點距離初始節(jié)節(jié)點較遠時將將會產(chǎn)生許多多無用節(jié)點,搜索效率率低,還可可能產(chǎn)生組合合爆炸。因因此,這種種方法較適宜宜問題不大的的環(huán)境中3.3圖搜搜索算法典典型的非非啟發(fā)式圖搜搜索算法分析析與改進深度優(yōu)先搜索索法該方法從初始始節(jié)點開始,順序序擴展生成下下一級各子節(jié)節(jié)點,放在OPEN表中中已有的節(jié)點點前面(實現(xiàn)現(xiàn)后生成的子子節(jié)點先擴展展),然然后從OPEN表中中提取最前的的一個節(jié)點檢檢查是否是目目標節(jié)點,否否則再再擴展,再再重復上上述操作。這這種方法每每一次擴展最最晚生成的子子節(jié)點,沿沿著最晚生生成的子節(jié)點點分支,逐逐級縱向向深入發(fā)展。。這種方法搜索索一旦進入某某個分支,就就將沿著該該分支一直向向下搜索。如如果目標標節(jié)點恰好好在此分支上上,則可可較快地得到到解。但是是,如如果目標節(jié)點點不在此分支支上,不不回溯就不不可能得到解解。所以,深度度優(yōu)先搜索是是不完備的,只是推理理步驟。如如果回溯,不不難證明明其平均效效率與廣度優(yōu)優(yōu)先搜索法相相同。因此此,深度優(yōu)優(yōu)先搜索法如如果沒有啟發(fā)發(fā)信息,很很難有實實用價值。3.3圖搜搜索算法典典型的非非啟發(fā)式圖搜搜索算法分析析與改進代價驅(qū)動搜索索法該方法考慮了了從一個節(jié)點點經(jīng)過一條支支路,轉轉移到另一一個節(jié)點時所所需要支付的的代價,如如費用、時時間等。該該方法從初始始節(jié)點開始,擴展展生成下一級級各子節(jié)點,這些子子節(jié)點中若沒沒有目標節(jié)點點需再擴展搜搜索。把它它們放進OPEN表中,依據(jù)初始始節(jié)點到它們們各自所付出出的代價大大小進行排序序,代價小小的節(jié)點放在在前面擴展,周而復始始重復上述操操作,直直至找到目標標節(jié)點為止。。這種方法根據(jù)據(jù)各條支路所所需支付的代代價有差別,所以以具有同樣路路徑長度(所所經(jīng)過的支支路數(shù))的的搜索過程,其搜索代代價(所支付付的總代價)可能不同,優(yōu)選最最小代價的搜搜索路徑,進進行推理理求解問題。。代價驅(qū)動動搜索無論在在理論研究方方面還是實際際應用方面都都很有前景,例如如最短路徑問問題。進一步步的研究認為為最短路徑問問題的改進應應為以下幾點點:3.3圖搜搜索算法典典型的非啟啟發(fā)式圖搜索索算法分析與與改進代價驅(qū)動搜索索法1)OPEN表的節(jié)節(jié)點排序問題題,特特別是在問題題節(jié)點多達成成千上萬時尤尤為重要.這這一排序應采采用映射排序序，它是一一個基于地址址計算的排序序,在在預置路徑最最大代價dmax后,開開辟一一個數(shù)組P(dmax),就就可把節(jié)點送送入其值與P數(shù)組下標相相等的對應元元素中,顯顯然di=50它對對應P(50);dj=500,對對應P(500)。相相同代價值值的節(jié)點落在在同一數(shù)組元元素中,用用計數(shù)方方式可知有有幾個。由由于數(shù)組元素素是有序的,500>50,數(shù)數(shù)組元素的下下標自然把節(jié)節(jié)點一次定好好了位置,排排序即即完成。這這一排序的時時間復雜性為為O(N),對于OPEN表面面臨的無數(shù)次次排序操作,極大大的提高了效效率.2)搜搜索過程中,如如果到達某一一節(jié)點的代價價≥任一初始始節(jié)點到目標標節(jié)點的路徑徑代價,這這一節(jié)點點的路徑刪去去。3)搜搜索過程中,如果果同時出現(xiàn)了了兩條到達某某一節(jié)點的路路徑,代代價大的那條條路徑即時刪刪去。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進搜索過程中,如果在在確定擴展那那一個節(jié)點時時能充分利用用與問題求解解有關的特性性信息,就就可以估估計出節(jié)點的的重要性,就能使搜搜索選擇重要要性較高的節(jié)節(jié)點,以以利于求得最最優(yōu)解。象象這樣就可可用于指導搜搜索過程,且且與具體體問題求解有有關的控制性性信息稱為啟啟發(fā)性信息。。啟發(fā)性性信息可以用用于估價節(jié)點點重要性,表表示為函函數(shù)形式:f(x)=g(x)+h(x)其中,g(x)為初始始節(jié)點S。到到節(jié)點x已經(jīng)經(jīng)付出的代價價;h(x)是從從節(jié)點x到目目標節(jié)點Sg的最優(yōu)路路徑的估計代代價,它體體現(xiàn)了問題的的啟發(fā)性信息息,其形式式根據(jù)問題的的特性確定。。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法如果對一般性性圖搜索算法法作以下限制制,則它成成為A*算法法:(1)OPEN表中中的節(jié)點按估估價函數(shù)f(x)=g(x)+h(x)的的值從小小至大進行排排序.(2)g(x)是是到目前為止止,從S。到x的一一條最小耗散散值路徑的耗耗散值,是是作為從從S。到x最小耗散散值路徑的耗耗散值g*(x)的估計計值,g(x)>0。。(3)h(x)是是h*(x)的下界,即即對所有有x均有h(x)≤h*(x)。而而h*(x)是從節(jié)點點x到目標節(jié)節(jié)點的最小代代價,若若有多個目標標節(jié)點,則則為其中中最小的一個個。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法幾個個重要性質(zhì):性質(zhì)1對對于有限圖圖,A*算算法一定會在在有限步內(nèi)終終止.證明：對對于有限圖,其節(jié)點個個數(shù)是有限的的,A*算法在在經(jīng)過若干次次循環(huán)后會出出現(xiàn)兩種情況況:或或者搜索到目目標節(jié)點在步步驟5結束;或者者OPEN表表中的節(jié)點被被取完在步驟驟3結束。不不管那那種情況,A*算法法都在有限步步內(nèi)終止。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法幾個個重要性質(zhì):性質(zhì)2對對于無限限圖,只要要從初始節(jié)點點到目標節(jié)點點有路徑存在在,A*算法也必必然終止。證明:分分兩步.第第一步證明A*算法結束束前,OPEN表表中存在節(jié)點點x‘,它它是最優(yōu)路路徑上的一一個節(jié)點,且滿足f(x')≤f*(s).。設最優(yōu)路徑是是S。x1,x2,…,S*g由于A*算法中的h(x)滿足足h(x)≤h*(x)所以f(s0),f(x1),f(x2),……,f(xm)均不大大于f(sg*)=f*(s0).又因為A*算算法是廣度代代價擇優(yōu),所所以在它它結束之前,OPEN表中一定定含有S。x1,x2,…,S*g中中的一些節(jié)點點,設x'是其中最前前面的一個,則它必然然滿足f(x')≤≤f*(S0)至此,第一一步證明結束束;3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法幾個個重要性質(zhì):性質(zhì)2對對于無限限圖,只要要從初始節(jié)點點到目標節(jié)點點有路徑存在在,A*算法也必必然終止。第二步證明：：用反證法,假設A*算法不終止止,并設e是圖中各條條邊的最小代代價,d*(xn)是從S。到到節(jié)點xn的的最短路徑長長度,則顯顯然有g*(xn)≥d*(xn)×e又因為g(xn)≥≥g*(xn)所以有g(xn)≥≥d*(xn)×e再因h(xn)≥0,f(xn)≥≥g(xn)故得到f(xn)≥≥d*(xn)×e由于A*算法法不終止,隨隨著搜索的的進行,d*(xn)會無限增大大,從從而使f(xn)也無限限增大。這這與第一步證證明得出的結結論矛盾,因因?qū)山鉅顮顟B(tài)空間來說說,f*(s0)一定定是有限值。。所以,只要要從初始節(jié)點點到目標節(jié)點點有路徑存在在,即使對對于無限圖,A*算算法也一定定會終止。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法幾個個重要性質(zhì):性質(zhì)3A*算法一一定終止在最最佳路徑上證明:假假設A*算法不是在在最優(yōu)路徑上上終止,而而是在某個目目標節(jié)點t處處終止,則則f(t)=g(t)>f*(s0)。但是是由性質(zhì)2證證明可知,在在A*算法結束之之前,OPEN表表中存在著節(jié)節(jié)點x‘,它它應該該在最優(yōu)路徑徑上,且且滿足f(x')≤f*(s0)此此時,A*算算法一定會選選擇x'來擴擴展而不會選選擇t,這這就與假假設矛盾,所所以,A*算法一定定會終止在最最優(yōu)路徑上。。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法幾個個重要性質(zhì):性質(zhì)4A*算法法是最優(yōu)的證明:A*算算法的搜索效效率很大程度度上取決h(x),在在滿足h(x)≤h*(x)的前提提下,h(x)的值越越大越好。h(x)值值越大,表表明它攜帶的的啟發(fā)信息越越多,搜索索時擴展的節(jié)節(jié)點數(shù)越少,搜索索的效率越高高。設f1(x)與f2(x)是對同一一問題的兩個個估價函數(shù)f1(x)=g1(x)+h1(x)f2(x)=g2(x)+h2(x)A1*和A2*分別是以以f1(x)及f2(x)為估價函函數(shù)的A*算算法,且對對于所有的非非目標節(jié)點x均有h1(x)<h2(x)。3.3圖搜搜索算法3.3.3典典型型的啟發(fā)式搜搜索算法分析析與改進A*算法幾個重重要性質(zhì):性質(zhì)4A*算法是最最優(yōu)的證明（接前前頁):此情況下證證明A1*擴展的節(jié)節(jié)點數(shù)不會會比A*2擴展的節(jié)節(jié)點數(shù)少,用歸納納法:設K表示搜搜索樹的深深度當K=0時時,結論論顯然成立立;設當搜索樹樹的深度為為K-1時時結論成立立,即A*2擴展展了的節(jié)點點,A*1也擴展展了;現(xiàn)僅證明A*2擴展展的第K代代的任一節(jié)節(jié)點xk也也被A*1擴展:3.3圖圖搜索算算法3.3.3典典型的的啟發(fā)式搜搜索算法分分析與改進進A*算法幾幾個重要性性質(zhì):性質(zhì)4A*算法是最最優(yōu)的證明（接前前頁):由由假設設可知,A*2擴展的的前K-1代節(jié)點A*1也都都擴展了,因因此A1*搜索樹樹中有一條條從初始節(jié)節(jié)點S。到到xk的路路徑,其其費用不會會比A*2搜索樹從從S。到xk的費用用更大。即即g1(xk)≤g2(xk)假設A*1不擴展節(jié)節(jié)點xk,這表示示A*1能找到另另一個具有有更小估價價值的節(jié)點點進行擴展展并找到最最優(yōu)解,此時有f1(xk)≥f*(S0)即即g1(xk)+h1(xk)≥f*(S0)應用關系式式g1(xk)≤g2(xk)到上列列不等式中中,得h1(xk)≥≥f*(S0)-g2(xk),由于h2(xk)=f*(S0)-g2(xk),這這就得到h1(xk)≥≥h2(xk)這與最初的的假設h1(x)<h2(x)相矛盾盾證畢畢。3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進A*算法的的改進改進1OPEN表中自自始至終的的排序,采采用3.3.2.3節(jié)中介介紹的映射射方法。改進2h(x)單調(diào)調(diào)限制:A*算法法中,每每當擴展展一個節(jié)點點時都要檢檢查其子節(jié)節(jié)點是否已已在OPEN表或CLOSED表中,有時還還需調(diào)整指指向父節(jié)點點的指針,這就增增加了搜索索代價。如如果對啟啟發(fā)函數(shù)h(x)單單調(diào)限制,可減少少檢查和調(diào)調(diào)整的工作作量,從從而提高搜搜索效率。。3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進A*算法的的改進所謂單調(diào)限限制h(x)應滿足足兩個條件件:(1)h(Sg)=0(2)設設xj是節(jié)節(jié)點xi的的任一子節(jié)節(jié)點,則則有h(xi)-h(xj)≤c(xi,xj)其中,Sg是目標標節(jié)點;c(xi,xj)是節(jié)點xi到其子子節(jié)點xj的邊代價價。若把上式改改寫h(xi)≤h(xj)+c(xi,xj),可可看出出節(jié)點xi到目標節(jié)節(jié)點的估價價不會超過過xi到到其子子節(jié)點xj邊代價加加從xj到到目標節(jié)點點的估價。。3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進A*算法的的改進當A*算法法的啟發(fā)函函數(shù)h(x)滿足單單調(diào)限制時時,可得得出以下兩兩個結論:(1)若若A*算法法選擇節(jié)點點xn進行行擴展,則則g(xn)=g*(xn)(2)由由A*算法法所擴展的的節(jié)點序列列其f值是是非遞減的的。這兩個結論論都是在h(x)滿滿足單調(diào)限限制時才成成立.對對于第2個個結論,當當h(x)不滿足足單調(diào)限限制時,有有可能某某個要擴展展的節(jié)點比比以前擴展展的節(jié)點具具有較小的的f值.3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進A*算法的的改進改進3引引入感感興趣集的的算法:這這一改進進的思路是是這樣的,問題求求解時,人人們往往往知道最最佳路徑上上有關節(jié)點點的某些啟啟發(fā)信息。。例如,在求求城市A到到城市B的的最佳路徑徑時,人人們往往往憑自己的的經(jīng)驗斷定定所要求的的最佳路徑徑必經(jīng)城市市C和城市市H,這這里我們稱稱{C,H}是是感興趣趣集合。若若知道感感興趣集且且啟發(fā)式搜搜索算法恰恰當?shù)貞糜酶信d趣集集,則則肯定可以以改善算法法的搜索效效率。3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進A*算法的的改進算法的改進進使用OPEN1和和OPEN2,CLOSED1和CLOSED2四個個表,對對任一節(jié)點點x,若若從s到到節(jié)點x的的當前路徑徑中不含感感興趣集中中的節(jié)點,則x放放入OPEN1中;否則放放入OPEN2中。。選擇節(jié)節(jié)點擴展展時,首首先擴展OPEN2中的節(jié)點點,因為為OPEN2中含有有感興趣集集中的節(jié)點點,可可能比比OPEN1中的節(jié)節(jié)點更有希希望在最佳佳路徑上,而且所所擴展的節(jié)節(jié)點數(shù)目總總不會多于于原算法。。3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進討論(1)啟發(fā)式搜索索算法在大大問題中一一般優(yōu)于非非啟發(fā)式搜搜索算法,因此此,有有效地分析析利用啟發(fā)發(fā)信息尤為為重要。含含有啟發(fā)發(fā)信息的評評價函數(shù)可可寫成下列列形式:f(x)=v·g(x)+w·h(x)其中,v、w為權權系數(shù)且≥≥0.當當w↑,強強調(diào)啟發(fā)發(fā)信息,搜搜索過程程沿最有希希望的方向向進行,效效率率肯定高,但降低低了完備性性;當v↑,強強調(diào)歷史信信息,搜搜索過程沿沿橫向掃描描,有利利于完備備性,但但降低了搜搜索效率。。3.3圖圖搜索算算法3.3.3典典型的啟啟發(fā)式搜索索算法分析析與改進討論(2)根據(jù)啟發(fā)信信息,可可將復雜的的、規(guī)模大大的問題分分解為簡單單的規(guī)模小小的若干子子問題。那那么各子子問題的搜搜索過程A1,A2,…,An是完備備的,則則搜索過程程A也是完完備的。A=A1∩∩A2∩……∩An根據(jù)啟發(fā)信信息,可可將原始始的問題進進行同構或或同態(tài)的等等價變換,轉換換為若干等等價問題。。那么等等價問題的的搜索過程程A1,A2,…,An是完完備的,則則搜索過程程A也是完完備的。A=A1∪∪A2∪……∪An.3.3圖圖搜索算算法3.3.4AND/OR圖搜搜索算法上節(jié)探討的的算法具有有重要的意意義。但但對于復雜雜的問題,它們并并不是唯一一的途徑,若利利用它們直直接求解往往往還比較較困難。AND/OR圖圖算法是用用于表示問問題及其求求解過程的的又一種種形式化方方法。定義1AND圖及AND圖算算法把一一個復雜的的問題分解解成若干個個較為簡單單的子問題題,每每個子問問題又可繼繼續(xù)分解為為更為簡單單的子問題題,重復復此過程,直到到不需要再再分解或者者不能再分分解為止。。這個分分解圖是與與圖,根根據(jù)這個圖圖對每個子子問題分別別求解,然然后把把這些解合合并起來得得到原問題題解的過程程是AND圖算法。。3.3圖圖搜索算算法3.3.4AND/OR圖搜搜索算法定義2OR圖圖及OR圖圖算法把一一個復雜雜問題利用用同構或同同態(tài)的等價價變換,使之之成為若干干個較容易易求解的新新問題。這這個變換換圖是OR圖,根根據(jù)這這個圖對新新問題求解解,當當且僅當新新問題有有一個可解解,就得得到原問題題的解的解解過程是AO圖算法法。定義3可可解節(jié)節(jié)點在AND/OR圖中,滿足下下列條件之之一者為可可解節(jié)點:(1)它它是一個終終止節(jié)點.(2)它它是一個OR節(jié)點,且子節(jié)節(jié)點中至少少有一個是是可解節(jié)點點.(3)它它是一個AND節(jié)點點,且其其子節(jié)點全全部是可解解節(jié)點。3.3圖圖搜索算算法3.3.4AND/OR圖搜搜索算法定義4不不可解解節(jié)點定定義3中三三個條件全全部不滿足足的節(jié)點稱稱為不可解解節(jié)點。下面分析AND/OR圖AO*搜索算算法,作作一些改改進探討;探探討類比搜搜索方法.為此,我我們首先先給出AND/OR圖的一般般搜索過程程:(1)把把原始問題題作為初始始節(jié)點,并并作為當當前節(jié)點。。(2)應應用分解或或等價變換換算符對當當前節(jié)點進進行擴展。。(3)為為每個子節(jié)節(jié)點設置指指向父節(jié)點點的指針。。(4)選選擇合適的的子節(jié)點作作為當前節(jié)節(jié)點,反反復執(zhí)行(2)和(3),直直至找找到可解節(jié)節(jié)點或不可可解節(jié)點為為止。下班可解或或不可解的的搜索過程程都是至上上而下的。。如果確確定某個節(jié)節(jié)點是可解解節(jié)點,則則不可可解的后后裔節(jié)點不不再有用,可從搜搜索圖中刪刪去;同同樣,如如果確定某某個節(jié)點是是不可解節(jié)節(jié)點,則則全部部后裔節(jié)點點都不在有有用,也也可從搜索索圖中刪去去。3.3圖圖搜索算算法3.3.5AO*搜搜索算法分分析與改進進定義定義5設設AND/OR圖G,則則從節(jié)點n到一立即即可解的葉葉節(jié)點集合合N的一解解圖G'定定義為:(1)G'是G的的子圖;(2)若若節(jié)點n是是集合N中中的元素,則G'是由單一一節(jié)點n組組成的;(3)若若節(jié)點n有有一個指向向節(jié)點{n1,n2,……,nk}的k-連接符,使得從從每個后繼繼節(jié)點ni到集合合N有一個個解圖(i=1,2,……,k),則G'由節(jié)點點n、k-連接符、、節(jié)點{n1,n2,…,nk}以及及從{n1,n2,…,nk}中的每個個節(jié)點到集集合N的解解圖組成。。(4)否否則,從從節(jié)點n到到集合N不不存在解圖圖。3.3圖圖搜索算算法3.3.5AO*搜搜索算法分分析與改進進定義定義6從從AND/OR圖任意意節(jié)點n到到一立即可可解的葉節(jié)節(jié)點集合N的解圖耗耗散值k(n,N)可遞歸歸地定義為為：(1)若若節(jié)點n是是集合N中中的元素,則k(n,N)=0;(2)否否則,節(jié)節(jié)點n有有一個通通到解圖中中后繼節(jié)點點集合{n1,n2,…,ni}的連連接符.令令該連接接符的耗散散值為Cn,則k(n,N)=Cn+k(n1,N)+k(n2,N)+…+k(ni,N)3.3圖圖搜索算算法3.3.5AO*搜搜索算法分分析與改進進定義定義7AND/OR圖求解中中,從從起始節(jié)點點到一可解解葉節(jié)點集集合具有最最小耗散值值的一個解解圖稱為為最佳解圖圖。令函函數(shù)h*(n)表示示從AND/OR圖圖中的節(jié)點點n到一一可解的葉葉節(jié)點集合合的最佳解解圖的耗耗散值;啟啟發(fā)式估估價函數(shù)h(n)是是h*(n)的估計計。定義義8若若啟啟發(fā)發(fā)式式估估價價函函數(shù)數(shù)h滿滿足足單單調(diào)調(diào)限限制制,即即對對AND/OR圖圖中中任任意意節(jié)節(jié)點點n及及其其適適用用于于n的的任任一一k-連連接接符符,有有h(n)≤≤Ck+h(n1)+……+h(nk)其中中,Ck為為k-連連接接符符的的耗耗散散值值,n1,n2,……,nk是是應應用用k-連連接接符符于于節(jié)節(jié)點點n所所得得的的全全部部后后繼繼節(jié)節(jié)點點。。3.3圖圖搜搜索索算算法法3.3.5AO*搜搜索索算算法法分分析析與與改改進進AO*算算法法A1:建建立立一一個個搜搜索索圖圖G,G:=s,計計算算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED);開開始始時時圖圖G只只包包含含s,耗耗散散值值估估計計為為h(s),若若s是是終終節(jié)節(jié)點點,則則標標記記能能解解.A2:Untils已已標標記記上上SOLVED,do:A3:beginA4:G':=FIND(G);根根據(jù)據(jù)連連接接符符標標記記(指指針針)找找出出一一個個待待擴擴展展的的局局部部解解圖圖G'.A5:n:=G'中中的的任任一一非非終終節(jié)節(jié)點點;選選一一個個非非終終節(jié)節(jié)點點作作為為當當前前節(jié)節(jié)點點.A6:EXPAND(n),生生成成子子節(jié)節(jié)點點集集{nj},G:=ADD({nj},G),計計算算q(nj)=h(nj),其其中中nj∈∈G,IFGOAL(nj)THENM(nj,SOLVED);把把n的的子子節(jié)節(jié)點點添添加加到到G中中,對對G中中未未出出現(xiàn)現(xiàn)的的子子節(jié)節(jié)點點計計算算耗耗散散值值,若若有有終終節(jié)節(jié)點點則則加加能能解解標標記記.A7:S:={n};建建立立含含n的的單單一一節(jié)節(jié)點點集集合合S.A8:UntilS為為空空,do3.3圖圖搜搜索索算算法法3.3.5AO*搜搜索索算算法法分分析析與與改改進進AO*算算法法(接接前前頁頁)A9:beginA10:REMOVE(m,S),mc∈∈{S};這這個個m的的子子節(jié)節(jié)點點mc應應不不在在S中中.A11:(1)修修改改m的的耗耗散散值值q(m):對m指指向向節(jié)節(jié)點點集集{n1i,n2i,……,nki}的的每每一一個個連連接接符符i分分別別計計算算qi,qi(m)=Ci+q(n1i)+……+q(nki),q(m):=minqi(m);對對m個個的的i個個連連接接符符,取取計計算算結結果果最最小小的的那那個個耗耗散散值值為為q(m).(2)加加指指針針到到minqi(m)的的連連接接符符上上,或或把把指指針針修修改改到到minqi(m)的的連連接接符符上上,即即原原來來指指針針與與新新確確定定的的不不一一致致時時應應刪刪去去.(3)IFM(nji,SOLVED)THENM(m,SOLVED);若若該該連連接接符符的的所所有有子子節(jié)節(jié)點點都都是是能能解解的的,則則m也也標標上上能能解解.A12:IFM(m,SOLVED)∨∨(q(m)≠≠q0(m))THENADD(ma,S);m能能解解或或修修正正的的耗耗散散值值與與原原先先估估算算q0不不同同,則則把把m的的所所有有先先輩輩節(jié)節(jié)點點ma添添加加到到S中中.A13:endA14:end3.3圖圖搜搜索索算算法法3.3.5AO*搜搜索索算算法法分分析析與與改改進進分析析與與改改進進算法法AO*可可以以理理解解為為兩兩個個主主要要運運算算:A1～～A6,完完成成自自上上而而下下的的圖圖生生成成,通通過過有有標標記記的的連連接接符符,尋尋找找最最好好的的局局部部解解圖圖,然然后后對對其其中中一一個個非非終終節(jié)節(jié)點點進進行行擴擴展展,并并對對其其后后繼繼節(jié)節(jié)點點賦賦給給耗耗散散值值;A7～～A12,完完成成自自下下而而上上的的耗耗散散值值修修正正、、連連接接符符標標記記和和節(jié)節(jié)點點的的能能解解標標記記。。(1)耗耗散散值值的的修修正正從從剛剛被被擴擴展展的的節(jié)節(jié)點點n開開始始,其其修修正正耗耗散散值值q(n)取取估估計計h*(n)的的所所有有值值中中最最小小的的一一個個,然然后后根根據(jù)據(jù)耗耗散散值值遞遞歸歸計計算算公公式式逐逐級級向向上上修修正正先先輩輩節(jié)節(jié)點點的的耗耗散散值值,只只有有下下層層節(jié)節(jié)點點耗耗散散值值修修正正后后,才才可可能能影影響響上上一一層層節(jié)節(jié)點點的的耗耗散散值值,因因此此必必須須自自底底向向上上一一直直修修正正到到初初始始節(jié)節(jié)點點。。(2)在在A6中中擴擴展展節(jié)節(jié)點點n時時,若若不不存存在在后后繼繼節(jié)節(jié)點點(即即限限入入死死胡胡同同),則則可可在在A11中中對對m(即即n)賦賦一一個個高高的的q值值,這這個個高高的的q值值會會依依次次傳傳遞遞到到s,使使得得含含有有節(jié)節(jié)點點n的的子子圖圖具具有有高高的的q(s),從從而而排排除除了了被被當當作作后后選選局局部部解解圖圖的的可可能能性性。。3.3圖圖搜搜索索算算法法3.3.5AO*搜搜索索算算法法分分析析與與改改進進分析析與與改改進進(3)A5中中怎怎樣樣選選G'中中的的一一個個非非終終節(jié)節(jié)點點擴擴展展值值得得研研究究:一一般般可可以以選選一一個個最最可可能能導導致致該該局局部部解解圖圖耗耗散散值值發(fā)發(fā)生生較較大大變變化化的的那那個個節(jié)節(jié)點點先先擴擴展展,因因為為選選這這個個節(jié)節(jié)點點先先擴擴展展,會會促促使使及及時時修修改改局局部部解解圖圖的的標標記記。。(4)與節(jié)節(jié)A算算法法類類似似,應應讓讓h(n)滿滿足足單單調(diào)調(diào)限限制制條條件件,這這樣樣,當當h(n)≤≤h*(n)則則AO*一一定定能能找找到到最最佳佳解解圖圖。。當當h(n)≡≡0時時,AO*成成寬寬度度優(yōu)優(yōu)先先算算法法。。(5)AO*中評評價函數(shù)只考考慮h(n)分量,計計算g沒沒有必要也不不可能。其其次由于k-連接符連連接的有關關子節(jié)點,對對于父父節(jié)點能解與與否以及耗散散值都有影響響,因因而不能象A算法那樣優(yōu)優(yōu)先擴展其中中具有最小耗耗散值的節(jié)點點。3.3圖搜搜索算法3.3.6類類比搜搜索方法探討討構思在AO*和A算法中,所所使使用的啟發(fā)信信息大多是人人們依據(jù)具體體領域問題靠靠經(jīng)驗總結得得來的,啟啟發(fā)發(fā)信息獲取十十分困難,且且精精確性和可靠靠性也難以保保證。此外外,搜搜索算法一一般執(zhí)行一次次性搜索,將將同同一問題的多多次搜索視為為彼此獨立、、毫無相關的的過程。每每次求解問問題時,面面臨的都都是全新的搜搜索圖,即即使使求解的是相相同問題,算算法法仍然從零開開始,這這顯然然與人類求解解問題的方式式不符。人人類求解問題題的一個重要要特點,就就是常常利利用以前求解解相同或相相似問題的經(jīng)經(jīng)驗來指導新新問題的求解解。這實際際上是一種類類比學習機制制,如果果將這種機制制引入搜索算算法,則則多次次搜索被看成成相互關聯(lián)的的過程,前前面搜搜索積累的經(jīng)經(jīng)驗將有助于于提高后面面搜索的效率率。即,利利用用類比獲得與與新問題相似似的過去問題題的求解過程程,作作為啟發(fā)信信息來指導新新問題的求解解,這這樣可以縮縮小搜索范圍圍,降降低問題求求解的復雜性性。也就是是說,如如果算算法設計恰當當,可以以自動獲得啟啟發(fā)信息。3.3圖搜搜索算法3.3.6類類比搜搜索方法探討討方法探討AO*、A及及其它算法在在問題的求解解過程中利用用與該問題相相關的啟發(fā)信信息來幫助搜搜索,啟啟發(fā)信息通通常被用于三三種情況:(1)幫幫助確定擴擴展節(jié)點。(2)在在擴展節(jié)節(jié)點的過程中中,幫助決決定產(chǎn)生后繼繼節(jié)點。(3)在在擴展節(jié)節(jié)點的過程中中,決定定那些節(jié)點可可從搜索樹上上刪除。值得得注意的是,啟發(fā)信息息是一種局部部信息,只只在搜索索路徑的每個個節(jié)點上為選選擇操作提供供參考。3.3圖搜搜索算法類類比比搜索索方法法探討討方法探探討類比搜搜索方方法把把類比比推理理技術術與狀狀態(tài)空空間的的啟發(fā)發(fā)式搜搜索相相結合合,實實際上上是對對人類類求解解問問題、、積累累經(jīng)驗驗和增增加求求解問問題能能力的的一種種模擬擬。要要實實現(xiàn)它它,需需要解解決如如下一一些主主要問問題:(1)如如何積積累問問題求求解的的經(jīng)驗驗,即即在在一個個問題題的求求解過過程中中,需需要記記錄那那些有有用信信息。。(2)如如何何定義義和判判斷兩兩個問問題的的求解解情況況是相相似的的,如如何何高效效的進進行檢檢索。。(3)如如何何有效效地使使用類類比結結論,即即相相似的的過去去問題題的求求解經(jīng)經(jīng)驗,作作為為特殊殊的啟啟發(fā)信信息指指導新新問題題的求求解。。3.3圖圖搜搜索算算法類類比比搜索索方法法探討討方法探探討基于上上述幾幾點,需需要建建立一一個類類比的的啟發(fā)發(fā)式搜搜索求求解模模型。。它它主主要包包括生生成求求解事事例、、檢索索及指指導求求解三三個推推理過過程。。類比比搜索索方法法在每每次求求解一一個新新問題題時,不不是直直接去去搜索索給定定的狀狀態(tài)空空間,而而是首首先在在求解解事例例庫中中檢索索,查查找與與該問問題相相似的的過去去問題題的求求解事事例。。若若存在在相似似問題題的求求解事事例,則則以此此作為為啟發(fā)發(fā)信息息,指指導導該問問題的的求解解。具具體體地說說,就就是是在新新問題題的求求解過過程中中,對對過去去問題題的求求解事事例中中記錄錄的成成功搜搜索路路徑上上每個個操作作的依依據(jù)條條件重重新測測試.如如果依依據(jù)條條件仍仍滿足足,則則算算法根根隨成成功的的求解解路徑徑。否否則則,對對原原求解解過程程進行行改寫寫,形形成成的新新問題題求解解過程程作為為一個個新事事例存存儲在在事例例庫中中,以以便指指導將將來相相似問問題的的求解解。過過去去問題題與新新問題題的相相似性性越高高,求求解過過程需需要的的搜索索就越越少。。在在最理理想的的情況況下,甚甚至不不需要要搜索索。當當沒沒有檢檢索到到一個個與新新問題題相似似的過過去問問題的的求解解事例例時,則則使用用A*或AO*等算算法進進行,并并在獲獲得解解時將將求解解過程程作為為一個個求解解事事例存存儲在在事例例庫中中。3.3圖圖搜搜索算算法類類比比搜索索方法法探討討方法探探討系統(tǒng)最最初使使用時時,由由于于事例例庫中中缺少少求解解事例例,只只