人工智能與機器翻譯

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