人工智能與機(jī)器翻譯

人工智能與機(jī)器翻譯主講：楊憲澤——產(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ī)則問(wèn)題3.5應(yīng)用舉例3.6產(chǎn)生式系統(tǒng)的不確定性問(wèn)題3.7系統(tǒng)設(shè)計(jì)技巧3.1產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)使用類似于文法的規(guī)則,對(duì)符號(hào)串作替換運(yùn)算。它是智能軟件中使用最普遍、最典型的一種結(jié)構(gòu)。為什么要采用產(chǎn)生式系統(tǒng)作為智能軟件的主要結(jié)構(gòu)呢?這可以有兩點(diǎn)理由:

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

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

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

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

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

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

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

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

建立產(chǎn)生式系統(tǒng)描述的過(guò)程,就是所謂問(wèn)題的表示。對(duì)問(wèn)題表示的好壞,往往對(duì)求解過(guò)程的效率有很大的影響。一種較好的表示法會(huì)簡(jiǎn)化狀態(tài)空間和規(guī)則集表示,此外,高效率的問(wèn)題求解過(guò)程與控制策略有關(guān),合適的控制策略可縮小狀態(tài)空間的搜索范圍,提高求解的效率。從以上論述可知,用產(chǎn)生式系統(tǒng)來(lái)描述和求解問(wèn)題,就是在問(wèn)題空間中搜索一條從初始狀態(tài)到達(dá)某一個(gè)目標(biāo)狀態(tài)的路徑。這完全可以模擬人的求解過(guò)程,也就是可以把產(chǎn)生式系統(tǒng)作為求解問(wèn)題思考過(guò)程的一種模擬。3.1產(chǎn)生式系統(tǒng)

3.1.2產(chǎn)生式系統(tǒng)的基本算法E1:DATA←初始事實(shí)庫(kù)E2:untilDATA滿足結(jié)束條件以前,doE3:beginE4:在規(guī)則集中,選某一條可用于DATA的規(guī)則E5:DATA←規(guī)則應(yīng)用到DATA得到的結(jié)果E6:結(jié)束3.1產(chǎn)生式系統(tǒng)

3.1.3產(chǎn)生式系統(tǒng)的類型正向、逆向、雙向產(chǎn)生式系統(tǒng)

用產(chǎn)生式系統(tǒng)求解某一問(wèn)題時(shí),如果按照規(guī)則使用的方式或者說(shuō)按推理方向來(lái)劃分的話,有正向、逆向和雙向產(chǎn)生式系統(tǒng)。正向產(chǎn)生式系統(tǒng)是從初始狀態(tài)出發(fā)朝著目標(biāo)狀態(tài)這個(gè)方向使用規(guī)則,即正推的方式工作,稱這些規(guī)則為F規(guī)則;若選目標(biāo)狀態(tài)作為初始數(shù)據(jù)庫(kù)逆向進(jìn)行求解,即逆向使用規(guī)則,產(chǎn)生子目標(biāo)狀態(tài),反方向一步一步朝著初始狀態(tài)方向求解,整個(gè)逆推方式工作,稱逆向產(chǎn)生式系統(tǒng),逆向應(yīng)用的規(guī)則稱B規(guī)則;若以雙向搜索的方式(即正向和逆向同時(shí)進(jìn)行)去求解問(wèn)題,則稱為雙向產(chǎn)生式系統(tǒng)。3.1產(chǎn)生式系統(tǒng)

3.1.3產(chǎn)生式系統(tǒng)的類型可交換的產(chǎn)生式系統(tǒng)可交換式產(chǎn)生式系統(tǒng)的可交換性指幾條規(guī)則的應(yīng)用可以任意交換次序而不影響求解。一般來(lái)說(shuō),當(dāng)一個(gè)產(chǎn)生式系統(tǒng)對(duì)任何一個(gè)數(shù)據(jù)庫(kù)D都具有如下性質(zhì)時(shí),這樣一個(gè)產(chǎn)生式系統(tǒng)是可交換的。

(1)可應(yīng)用于D的規(guī)則集合,使用了其中任意一條規(guī)則之后所生成的任何數(shù)據(jù)庫(kù),這樣一個(gè)規(guī)則集合還適用;(2)滿足目標(biāo)條件的某個(gè)數(shù)據(jù)庫(kù)D,當(dāng)應(yīng)用任何一個(gè)可應(yīng)用于數(shù)據(jù)庫(kù)D的規(guī)則之后所生成的任何數(shù)據(jù)庫(kù),任然滿足目標(biāo)條件;(3)若對(duì)D應(yīng)用某一規(guī)則序列后得到的一個(gè)數(shù)據(jù)庫(kù)D'(并能達(dá)到解),當(dāng)改變這些規(guī)則次序后,任然可求得解,即求得D'與使用滿足D的可應(yīng)用規(guī)則集合中的規(guī)則次序無(wú)關(guān)。3.1產(chǎn)生式系統(tǒng)

3.1.3產(chǎn)生式系統(tǒng)的類型可交換的產(chǎn)生式系統(tǒng)

例:給定一個(gè)整數(shù)集合的初始狀態(tài){a,b,c},設(shè)目標(biāo)狀態(tài)為具有a,b,c,ab,bc,ca這六個(gè)元素組成的集合?？蓱?yīng)用的規(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}顯然,這個(gè)產(chǎn)生式實(shí)例具有可交換性。一個(gè)產(chǎn)生式系統(tǒng)具有可交換性,求解時(shí)只需搜索其中任一條途徑,只要解存在就一定能找到目標(biāo),不必探索多條途徑,因此不可撤回的控制方式(下節(jié)論述)在這種系統(tǒng)中使用很合適,因解與最初可應(yīng)用的規(guī)則系列的次序無(wú)關(guān),系統(tǒng)不必提供特殊選擇規(guī)則的機(jī)理。3.1產(chǎn)生式系統(tǒng)

3.1.3產(chǎn)生式系統(tǒng)的類型可分解的產(chǎn)生式系統(tǒng)先研究一個(gè)重寫問(wèn)題的產(chǎn)生式系統(tǒng),初始數(shù)據(jù)庫(kù)為(C,B,Z),產(chǎn)生式規(guī)則如下:R1:C→(D,L)R2:C→(B,M)R3:B→(M,M)R4:Z→(B,B,M)結(jié)束條件是生成只包含M組成的數(shù)據(jù)庫(kù),即(M,…,M)。3.1產(chǎn)生式系統(tǒng)

3.1.3產(chǎn)生式系統(tǒng)的類型可分解的產(chǎn)生式系統(tǒng)用圖搜索方式求解這個(gè)問(wèn)題時(shí),搜索得到的部分狀態(tài)空間圖見(jiàn)圖26。圖中只給出兩條達(dá)到目標(biāo)的路徑和一條失敗的路徑。實(shí)際搜索時(shí)有可能去探索更多的路徑,往往導(dǎo)致效率降低。對(duì)于個(gè)問(wèn)題,為了避免搜索多余的路徑,可以將初始數(shù)據(jù)庫(kù)分解成幾個(gè)可以獨(dú)立加以處理的分量,分別對(duì)它們進(jìn)行求解。即可以分別對(duì)每一個(gè)分量數(shù)據(jù)庫(kù),測(cè)試產(chǎn)生式規(guī)則可以應(yīng)用的條件,如此進(jìn)行下去,直到分量數(shù)據(jù)庫(kù)滿足某種結(jié)束條件為止。要注意一般結(jié)束條件應(yīng)是所有分量數(shù)據(jù)庫(kù)都已滿足結(jié)束條件。3.1產(chǎn)生式系統(tǒng)

3.1.3產(chǎn)生式系統(tǒng)的類型可分解的產(chǎn)生式系統(tǒng)能夠分解產(chǎn)生式系統(tǒng)的綜合數(shù)據(jù)庫(kù)和結(jié)束條件的產(chǎn)生式系統(tǒng)稱為可分解的產(chǎn)生式系統(tǒng)。一個(gè)可分解的產(chǎn)生式系統(tǒng),其基本算法描述如下:

(1)DATA:=初始數(shù)據(jù)庫(kù)(2){Di}:=DATA的分解式;每個(gè)Di元素都看成單獨(dú)的數(shù)據(jù)庫(kù)(3)Until{Di}的所有元素都滿足結(jié)束條件之前,do:(4)begin(5)從{Di}中選一個(gè)不滿足結(jié)束條件的D*(6)從{Di}中刪去D*(7)在規(guī)則集中選擇一條可應(yīng)用于D*的規(guī)則R(8){di}:=R應(yīng)用于D*的結(jié)果(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↓目標(biāo)(M,M,M,M,M,M,M,M,M,M)圖263.2產(chǎn)生式系統(tǒng)的搜索(控制)策略

在3.1.2節(jié)的算法中,如何選擇一條可應(yīng)用的規(guī)則,作用于當(dāng)前的綜合數(shù)據(jù)庫(kù),生成新的狀態(tài)以及記住選用的規(guī)則序列是構(gòu)成控制策略的主要內(nèi)容。對(duì)大多數(shù)的智能應(yīng)用問(wèn)題,所擁有的控制策略知識(shí)或信息并不足以使每次通過(guò)算法E4時(shí),一下子就能選出最合適的一條規(guī)則來(lái),因而產(chǎn)生式系統(tǒng)還必須把E4擴(kuò)大成搜索(推理)算法,以至于基本算法的每一循環(huán)中選一條規(guī)則試用,最終找出某一序列能產(chǎn)生一個(gè)滿足結(jié)束條件的數(shù)據(jù)庫(kù)為止。由此可見(jiàn),高效率的控制策略需要有關(guān)被求解問(wèn)題的足夠知識(shí),這樣才能在搜索過(guò)程減少盲目性,比較快的找到解路徑。

過(guò)去三十多年中,人們研究了許多種搜索算法,歸納起來(lái)主要有兩類:一類是非啟發(fā)式算法;另一類是啟發(fā)式算法。非啟發(fā)式算法是按預(yù)定的控制策略進(jìn)行搜索,在其過(guò)程中獲得的中間信息不用來(lái)改進(jìn)控制策略。由于搜索總是按預(yù)先規(guī)定的路線進(jìn)行,沒(méi)有考慮問(wèn)題本身的特性,所以不容易選擇到最優(yōu)的搜索途徑,效率較低,且出現(xiàn)"組合爆炸"的頻率高。啟發(fā)式算法是在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息,用以指導(dǎo)搜索朝著最有希望的方向前進(jìn),加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。

3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略

3.2.1產(chǎn)生式系統(tǒng)控制策略分類可分解的產(chǎn)生式系統(tǒng)控制策略可劃分為兩大類:┌不可撤回方法┌回溯方法└試探性方法─┤└圖搜索方法3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略

3.2.2不可撤回方法

這種方法相當(dāng)于沿著單獨(dú)一條路搜索下去,利用問(wèn)題給出的局部知識(shí)決定如何選取規(guī)則,就是說(shuō)根據(jù)當(dāng)前可靠的局部知識(shí)選一條可應(yīng)用規(guī)則并作用于當(dāng)前綜合數(shù)據(jù)庫(kù)。接著再根據(jù)新?tīng)顟B(tài)繼續(xù)選取規(guī)則,搜索過(guò)程一直進(jìn)行,不必考慮撤回用過(guò)的規(guī)則。這是由于在搜索過(guò)程中如能有效利用局部知識(shí),即使使用了一條不理想的規(guī)則,也不妨礙下一步選得另一條更合適的規(guī)則。這樣不撤消用過(guò)的規(guī)則,并不影響求到解,只是解序列中可能多了一些不必要的規(guī)則。顯然這種策略具有控制簡(jiǎn)單的優(yōu)點(diǎn)。3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略3.2.2不可撤回方法

爬山法不僅適用于爬山問(wèn)題,那些目標(biāo)為極大值,搜索過(guò)程是不斷接近目標(biāo)的單值問(wèn)題都可應(yīng)用這一方法。使用不可撤回策略,雖然不可能對(duì)任何狀態(tài)總能選得最優(yōu)的規(guī)則,但是如果應(yīng)用了一條不合適的規(guī)則之后,不去撤消它并不排除下一步應(yīng)用一條合適的規(guī)則,那么只是解序列有些多余的規(guī)則而已,求得的解不是最優(yōu)解,但控制較簡(jiǎn)單。此外還應(yīng)當(dāng)指出,一般很難對(duì)給定問(wèn)題構(gòu)造出任何情況下都能通用的爬山函數(shù),因而不可撤回的方法具有一定的局限性。3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略

3.2.3回溯方法

在問(wèn)題求解過(guò)程中,有時(shí)會(huì)發(fā)現(xiàn)應(yīng)用一條不合適的規(guī)則會(huì)阻擾或拖延達(dá)到目標(biāo)的過(guò)程。在這種情況下,需要有這樣的控制策略:先試一試某一條規(guī)則,如果以后發(fā)現(xiàn)這條規(guī)則不合適,則允許退回去,另選一條規(guī)則來(lái)試。回溯方法不保留完整的搜索樹(shù)結(jié)構(gòu),只記住當(dāng)前工作的一條路徑,回溯就是對(duì)這條路徑進(jìn)行修正。使用回溯策略首要的問(wèn)題要研究在什么情況下應(yīng)該回溯,即要確定回溯條件的問(wèn)題。其次就是如何利用有用知識(shí)進(jìn)行規(guī)則排序,以減少回溯次數(shù)?；厮輵?yīng)發(fā)生在以下三種情況:

(1)新生成的狀態(tài)在通向初始狀態(tài)的路徑上已出現(xiàn)過(guò);(2)從初始狀態(tài)開(kāi)始,應(yīng)用的規(guī)則數(shù)目達(dá)到所規(guī)定的數(shù)目之后還未找到目標(biāo)狀態(tài)(這一組規(guī)則的數(shù)目實(shí)際上就是搜索深度范圍所規(guī)定的);(3)對(duì)當(dāng)前狀態(tài),再?zèng)]有可應(yīng)用的規(guī)則。3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略

3.2.3回溯方法搜索深度的設(shè)置是一個(gè)值得注意的問(wèn)題,設(shè)置太淺,有可能找不到解;設(shè)置太深,有可能導(dǎo)致回溯次數(shù)巨增。因而應(yīng)根據(jù)實(shí)際情況來(lái)規(guī)定搜索范圍,先設(shè)置適中的深度搜索,失敗時(shí)再逐步加深。回溯過(guò)程是一種可試探的方法,從形式上無(wú)論是否存在對(duì)選擇規(guī)則有用的知識(shí),都可以采用這種策略。即如果沒(méi)有有用的知識(shí)來(lái)引導(dǎo)規(guī)則選取,那么規(guī)則可按任意方式(固定排序或隨機(jī))選取;如果有好的選擇規(guī)則的知識(shí)可用,那么用這種知識(shí)來(lái)引導(dǎo)規(guī)則選取,就會(huì)減少盲目性,降低回溯次數(shù),甚至不回溯就能找到解,總之一般來(lái)說(shuō)有利于提高效率。此外由于引入回溯機(jī)理,可以避免陷入局部極大值的情況,繼續(xù)尋找其他達(dá)到目標(biāo)的路徑。3.2產(chǎn)生式系統(tǒng)的搜索(控制)策略

3.2.3回溯方法可用遞歸算法描述回溯策略:YX0:選擇一條新路徑搜索;YX1:搜索已超出規(guī)定指標(biāo)(無(wú)新路徑、超時(shí),超深度等),失敗退出;否則搜索繼續(xù);YX2:搜索的狀態(tài)找不到可用規(guī)則,回溯到Y(jié)X0;YX3:搜索的狀態(tài)依某種原則(任意排列或按啟發(fā)式準(zhǔn)則)取有用規(guī)則;YX4:若規(guī)則用完未找到目標(biāo),回溯YX0;YX5:取頭條可用規(guī)則Ri;YX6:刪去頭條規(guī)則,減少搜索中規(guī)則集長(zhǎng)度(注意,這不動(dòng)原始規(guī)則集);YX7:規(guī)則Ri作用于當(dāng)前狀態(tài),生成新?tīng)顟B(tài);YX8:若找到目標(biāo),成功退出;若生成的"新?tīng)顟B(tài)"已出現(xiàn)過(guò),回溯到Y(jié)X0;YX9:記錄新?tīng)顟B(tài),對(duì)新?tīng)顟B(tài)遞規(guī)調(diào)用YX1～YX7;產(chǎn)生式系統(tǒng)求解問(wèn)題時(shí),如果控制系統(tǒng)保留所有規(guī)則應(yīng)用后生成并鏈接起來(lái)的狀態(tài)記錄圖,則稱工作在這種方式下的控制系統(tǒng)使用了圖搜索策略。實(shí)際上圖搜索策略是實(shí)現(xiàn)從一個(gè)隱含圖中,生成一部分確實(shí)含有一個(gè)目標(biāo)節(jié)點(diǎn)的顯式表示的子圖搜索過(guò)程。3.3圖搜索算法3.3圖搜索算法3.3.1一般性圖搜索算法步驟1G←S,OPEN←(S);建立一個(gè)搜索圖G,它只含有初始節(jié)點(diǎn)S,建立一個(gè)OPEN表(今后它用于存儲(chǔ)生成的節(jié)點(diǎn)),開(kāi)始它只含有初始節(jié)點(diǎn)S。步驟2CLOSED←();建立一個(gè)CLOSED表(今后它用于存儲(chǔ)已擴(kuò)展節(jié)點(diǎn)或?qū)⒁獢U(kuò)展的某個(gè)節(jié)點(diǎn)),它的初始狀態(tài)為空表。步驟3LOOP:ifOPEN=()thenreturnFAIL;進(jìn)入循環(huán)。如果OPEN表已空,說(shuō)明沒(méi)有節(jié)點(diǎn)可擴(kuò)展,就返回FAIL,即失敗。步驟4n←FIRST(OPEN),CLOSED←(n,CLOSED);從OPEN表中取出一個(gè)節(jié)點(diǎn)n,將其放入CLOSED表中。3.3圖搜索算法3.3.2典型的非啟發(fā)式圖搜索算法分析與改進(jìn)廣度優(yōu)先搜索法

該方法從初始節(jié)點(diǎn)開(kāi)始,序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),OPEN表中已有的節(jié)點(diǎn)后面(實(shí)現(xiàn)先生成的子節(jié)點(diǎn)先擴(kuò)展),然后從OPEN表中提取最前的一個(gè)節(jié)點(diǎn)檢查是否是目標(biāo)節(jié)點(diǎn),否則再擴(kuò)展,再重復(fù)上述操作。這種方法認(rèn)為同一級(jí)各節(jié)點(diǎn)對(duì)問(wèn)題求解的價(jià)值是同等的,因而對(duì)全部節(jié)點(diǎn)沿廣度進(jìn)行橫向掃描,按各節(jié)點(diǎn)生成的先后次序,先生成、先檢查、先擴(kuò)展,沿廣度遍歷所有節(jié)點(diǎn)。這種方法只要問(wèn)題有解,即若樹(shù)圖上存在目標(biāo)節(jié)點(diǎn),經(jīng)搜索一定能找到。所以,廣度優(yōu)先搜索法是完備的,是一種推理算法。但是,在問(wèn)題大節(jié)點(diǎn)多,且目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn),搜索效率低,還可能產(chǎn)生組合爆炸。因此,這種方法較適宜問(wèn)題不大的環(huán)境中3.3圖搜索算法3.3.2典型的非啟發(fā)式圖搜索算法分析與改進(jìn)深度優(yōu)先搜索法

該方法從初始節(jié)點(diǎn)開(kāi)始,順序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),放在OPEN表中已有的節(jié)點(diǎn)前面(實(shí)現(xiàn)后生成的子節(jié)點(diǎn)先擴(kuò)展),然后從OPEN表中提取最前的一個(gè)節(jié)點(diǎn)檢查是否是目標(biāo)節(jié)點(diǎn),否則再擴(kuò)展,再重復(fù)上述操作。這種方法每一次擴(kuò)展最晚生成的子節(jié)點(diǎn),沿著最晚生成的子節(jié)點(diǎn)分支,逐級(jí)縱向深入發(fā)展。這種方法搜索一旦進(jìn)入某個(gè)分支,就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上,則可較快地得到解。但是,如果目標(biāo)節(jié)點(diǎn)不在此分支上,不回溯就不可能得到解。所以,深度優(yōu)先搜索是不完備的,只是推理步驟。如果回溯,不難證明其平均效率與廣度優(yōu)先搜索法相同。因此,深度優(yōu)先搜索法如果沒(méi)有啟發(fā)信息,很難有實(shí)用價(jià)值。3.3圖搜索算法3.3.2典型的非啟發(fā)式圖搜索算法分析與改進(jìn)代價(jià)驅(qū)動(dòng)搜索法

該方法考慮了從一個(gè)節(jié)點(diǎn)經(jīng)過(guò)一條支路,轉(zhuǎn)移到另一個(gè)節(jié)點(diǎn)時(shí)所需要支付的代價(jià),如費(fèi)用、時(shí)間等。該方法從初始節(jié)點(diǎn)開(kāi)始,擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),這些子節(jié)點(diǎn)中若沒(méi)有目標(biāo)節(jié)點(diǎn)需再擴(kuò)展搜索。把它們放進(jìn)OPEN表中,依據(jù)初始節(jié)點(diǎn)到它們各自所付出的代價(jià)大小進(jìn)行排序,代價(jià)小的節(jié)點(diǎn)放在前面擴(kuò)展,周而復(fù)始重復(fù)上述操作,直至找到目標(biāo)節(jié)點(diǎn)為止。這種方法根據(jù)各條支路所需支付的代價(jià)有差別,所以具有同樣路徑長(zhǎng)度(所經(jīng)過(guò)的支路數(shù))的搜索過(guò)程,其搜索代價(jià)(所支付的總代價(jià))可能不同,優(yōu)選最小代價(jià)的搜索路徑,進(jìn)行推理求解問(wèn)題。代價(jià)驅(qū)動(dòng)搜索無(wú)論在理論研究方面還是實(shí)際應(yīng)用方面都很有前景,例如最短路徑問(wèn)題。進(jìn)一步的研究認(rèn)為最短路徑問(wèn)題的改進(jìn)應(yīng)為以下幾點(diǎn):3.3圖搜索算法

3.3.2典型的非啟發(fā)式圖搜索算法分析與改進(jìn)代價(jià)驅(qū)動(dòng)搜索法1)OPEN表的節(jié)點(diǎn)排序問(wèn)題,特別是在問(wèn)題節(jié)點(diǎn)多達(dá)成千上萬(wàn)時(shí)尤為重要.這一排序應(yīng)采用映射排序，它是一個(gè)基于地址計(jì)算的排序,在預(yù)置路徑最大代價(jià)dmax后,開(kāi)辟一個(gè)數(shù)組P(dmax),就可把節(jié)點(diǎn)送入其值與P數(shù)組下標(biāo)相等的對(duì)應(yīng)元素中,顯然di=50它對(duì)應(yīng)P(50);dj=500,對(duì)應(yīng)P(500)。相同代價(jià)值的節(jié)點(diǎn)落在同一數(shù)組元素中,用計(jì)數(shù)方式可知有幾個(gè)。由于數(shù)組元素是有序的,500>50,數(shù)組元素的下標(biāo)自然把節(jié)點(diǎn)一次定好了位置,排序即完成。這一排序的時(shí)間復(fù)雜性為O(N),對(duì)于OPEN表面臨的無(wú)數(shù)次排序操作,極大的提高了效率.2)搜索過(guò)程中,如果到達(dá)某一節(jié)點(diǎn)的代價(jià)≥任一初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑代價(jià),這一節(jié)點(diǎn)的路徑刪去。3)搜索過(guò)程中,如果同時(shí)出現(xiàn)了兩條到達(dá)某一節(jié)點(diǎn)的路徑,代價(jià)大的那條路徑即時(shí)刪去。3.3圖搜索算法

3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

搜索過(guò)程中,如果在確定擴(kuò)展那一個(gè)節(jié)點(diǎn)時(shí)能充分利用與問(wèn)題求解有關(guān)的特性信息,就可以估計(jì)出節(jié)點(diǎn)的重要性,就能使搜索選擇重要性較高的節(jié)點(diǎn),以利于求得最優(yōu)解。象這樣就可用于指導(dǎo)搜索過(guò)程,且與具體問(wèn)題求解有關(guān)的控制性信息稱為啟發(fā)性信息。啟發(fā)性信息可以用于估價(jià)節(jié)點(diǎn)重要性,表示為函數(shù)形式:f(x)=g(x)+h(x)其中,g(x)為初始節(jié)點(diǎn)S。到節(jié)點(diǎn)x已經(jīng)付出的代價(jià);h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià),它體現(xiàn)了問(wèn)題的啟發(fā)性信息,其形式根據(jù)問(wèn)題的特性確定。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法如果對(duì)一般性圖搜索算法作以下限制,則它成為A*算法:(1)OPEN表中的節(jié)點(diǎn)按估價(jià)函數(shù)f(x)=g(x)+h(x)的值從小至大進(jìn)行排序.(2)g(x)是到目前為止,從S。到x的一條最小耗散值路徑的耗散值,是作為從S。到x最小耗散值路徑的耗散值g*(x)的估計(jì)值,g(x)>0。(3)h(x)是h*(x)的下界,即對(duì)所有x均有h(x)≤h*(x)。而h*(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià),若有多個(gè)目標(biāo)節(jié)點(diǎn),則為其中最小的一個(gè)。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

A*算法幾個(gè)重要性質(zhì):性質(zhì)1對(duì)于有限圖,A*算法一定會(huì)在有限步內(nèi)終止.證明：對(duì)于有限圖,其節(jié)點(diǎn)個(gè)數(shù)是有限的,A*算法在經(jīng)過(guò)若干次循環(huán)后會(huì)出現(xiàn)兩種情況:或者搜索到目標(biāo)節(jié)點(diǎn)在步驟5結(jié)束;或者OPEN表中的節(jié)點(diǎn)被取完在步驟3結(jié)束。不管那種情況,A*算法都在有限步內(nèi)終止。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法幾個(gè)重要性質(zhì):性質(zhì)2對(duì)于無(wú)限圖,只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在,A*算法也必然終止。證明:分兩步.第一步證明A*算法結(jié)束前,OPEN表中存在節(jié)點(diǎn)x‘,它是最優(yōu)路徑上的一個(gè)節(jié)點(diǎn),且滿足f(x')≤f*(s).。設(shè)最優(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).又因?yàn)锳*算法是廣度代價(jià)擇優(yōu),所以在它結(jié)束之前,OPEN表中一定含有S。x1,x2,…,S*g中的一些節(jié)點(diǎn),設(shè)x'是其中最前面的一個(gè),則它必然滿足f(x')≤f*(S0)至此,第一步證明結(jié)束;3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法幾個(gè)重要性質(zhì):性質(zhì)2對(duì)于無(wú)限圖,只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在,A*算法也必然終止。第二步證明：用反證法,假設(shè)A*算法不終止,并設(shè)e是圖中各條邊的最小代價(jià),d*(xn)是從S。到節(jié)點(diǎn)xn的最短路徑長(zhǎng)度,則顯然有g(shù)*(xn)≥d*(xn)×e又因?yàn)間(xn)≥g*(xn)所以有g(shù)(xn)≥d*(xn)×e再因h(xn)≥0,f(xn)≥g(xn)故得到f(xn)≥d*(xn)×e由于A*算法不終止,隨著搜索的進(jìn)行,d*(xn)會(huì)無(wú)限增大,從而使f(xn)也無(wú)限增大。這與第一步證明得出的結(jié)論矛盾,因?qū)山鉅顟B(tài)空間來(lái)說(shuō),f*(s0)一定是有限值。所以,只要從初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)有路徑存在,即使對(duì)于無(wú)限圖,A*算法也一定會(huì)終止。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

A*算法幾個(gè)重要性質(zhì):

性質(zhì)3A*算法一定終止在最佳路徑上證明:假設(shè)A*算法不是在最優(yōu)路徑上終止,而是在某個(gè)目標(biāo)節(jié)點(diǎn)t處終止,則f(t)=g(t)>f*(s0)。但是由性質(zhì)2證明可知,在A*算法結(jié)束之前,OPEN表中存在著節(jié)點(diǎn)x‘,它應(yīng)該在最優(yōu)路徑上,且滿足f(x')≤f*(s0)此時(shí),A*算法一定會(huì)選擇x'來(lái)擴(kuò)展而不會(huì)選擇t,這就與假設(shè)矛盾,所以,A*算法一定會(huì)終止在最優(yōu)路徑上。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

A*算法幾個(gè)重要性質(zhì):性質(zhì)4A*算法是最優(yōu)的證明:A*算法的搜索效率很大程度上取決h(x),在滿足h(x)≤h*(x)的前提下,h(x)的值越大越好。h(x)值越大,表明它攜帶的啟發(fā)信息越多,搜索時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)越少,搜索的效率越高。設(shè)f1(x)與f2(x)是對(duì)同一問(wèn)題的兩個(gè)估價(jià)函數(shù)f1(x)=g1(x)+h1(x)f2(x)=g2(x)+h2(x)A1*和A2*分別是以f1(x)及f2(x)為估價(jià)函數(shù)的A*算法,且對(duì)于所有的非目標(biāo)節(jié)點(diǎn)x均有h1(x)<h2(x)。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法幾個(gè)重要性質(zhì):性質(zhì)4A*算法是最優(yōu)的證明（接前頁(yè)):

此情況下證明A1*擴(kuò)展的節(jié)點(diǎn)數(shù)不會(huì)比A*2擴(kuò)展的節(jié)點(diǎn)數(shù)少,用歸納法:設(shè)K表示搜索樹(shù)的深度當(dāng)K=0時(shí),結(jié)論顯然成立;設(shè)當(dāng)搜索樹(shù)的深度為K-1時(shí)結(jié)論成立,即A*2擴(kuò)展了的節(jié)點(diǎn),A*1也擴(kuò)展了;現(xiàn)僅證明A*2擴(kuò)展的第K代的任一節(jié)點(diǎn)xk也被A*1擴(kuò)展:3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法幾個(gè)重要性質(zhì):性質(zhì)4A*算法是最優(yōu)的證明（接前頁(yè)):由假設(shè)可知,A*2擴(kuò)展的前K-1代節(jié)點(diǎn)A*1也都擴(kuò)展了,因此A1*搜索樹(shù)中有一條從初始節(jié)點(diǎn)S。到xk的路徑,其費(fèi)用不會(huì)比A*2搜索樹(shù)從S。到xk的費(fèi)用更大。即g1(xk)≤g2(xk)假設(shè)A*1不擴(kuò)展節(jié)點(diǎn)xk,這表示A*1能找到另一個(gè)具有更小估價(jià)值的節(jié)點(diǎn)進(jìn)行擴(kuò)展并找到最優(yōu)解,此時(shí)有f1(xk)≥f*(S0)即g1(xk)+h1(xk)≥f*(S0)應(yīng)用關(guān)系式g1(xk)≤g2(xk)到上列不等式中,得h1(xk)≥f*(S0)-g2(xk),由于h2(xk)=f*(S0)-g2(xk),這就得到h1(xk)≥h2(xk)這與最初的假設(shè)h1(x)<h2(x)相矛盾證畢。3.3圖搜索算法

3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

A*算法的改進(jìn)改進(jìn)1OPEN表中自始至終的排序,采用3.3.2.3節(jié)中介紹的映射方法。改進(jìn)2h(x)單調(diào)限制:A*算法中,每當(dāng)擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)都要檢查其子節(jié)點(diǎn)是否已在OPEN表或CLOSED表中,有時(shí)還需調(diào)整指向父節(jié)點(diǎn)的指針,這就增加了搜索代價(jià)。如果對(duì)啟發(fā)函數(shù)h(x)單調(diào)限制,可減少檢查和調(diào)整的工作量,從而提高搜索效率。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

A*算法的改進(jìn)所謂單調(diào)限制h(x)應(yīng)滿足兩個(gè)條件:(1)h(Sg)=0(2)設(shè)xj是節(jié)點(diǎn)xi的任一子節(jié)點(diǎn),則有h(xi)-h(xj)≤c(xi,xj)其中,Sg是目標(biāo)節(jié)點(diǎn);c(xi,xj)是節(jié)點(diǎn)xi到其子節(jié)點(diǎn)xj的邊代價(jià)。若把上式改寫h(xi)≤h(xj)+c(xi,xj),可看出節(jié)點(diǎn)xi到目標(biāo)節(jié)點(diǎn)的估價(jià)不會(huì)超過(guò)xi到其子節(jié)點(diǎn)xj邊代價(jià)加從xj到目標(biāo)節(jié)點(diǎn)的估價(jià)。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法的改進(jìn)

當(dāng)A*算法的啟發(fā)函數(shù)h(x)滿足單調(diào)限制時(shí),可得出以下兩個(gè)結(jié)論:(1)若A*算法選擇節(jié)點(diǎn)xn進(jìn)行擴(kuò)展,則g(xn)=g*(xn)(2)由A*算法所擴(kuò)展的節(jié)點(diǎn)序列其f值是非遞減的。這兩個(gè)結(jié)論都是在h(x)滿足單調(diào)限制時(shí)才成立.對(duì)于第2個(gè)結(jié)論,當(dāng)h(x)不滿足單調(diào)限制時(shí),有可能某個(gè)要擴(kuò)展的節(jié)點(diǎn)比以前擴(kuò)展的節(jié)點(diǎn)具有較小的f值.3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)A*算法的改進(jìn)改進(jìn)3引入感興趣集的算法:這一改進(jìn)的思路是這樣的,問(wèn)題求解時(shí),人們往往知道最佳路徑上有關(guān)節(jié)點(diǎn)的某些啟發(fā)信息。例如,在求城市A到城市B的最佳路徑時(shí),人們往往憑自己的經(jīng)驗(yàn)斷定所要求的最佳路徑必經(jīng)城市C和城市H,這里我們稱{C,H}是感興趣集合。若知道感興趣集且啟發(fā)式搜索算法恰當(dāng)?shù)貞?yīng)用感興趣集,則肯定可以改善算法的搜索效率。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

A*算法的改進(jìn)算法的改進(jìn)使用OPEN1和OPEN2,CLOSED1和CLOSED2四個(gè)表,對(duì)任一節(jié)點(diǎn)x,若從s到節(jié)點(diǎn)x的當(dāng)前路徑中不含感興趣集中的節(jié)點(diǎn),則x放入OPEN1中;否則放入OPEN2中。選擇節(jié)點(diǎn)擴(kuò)展時(shí),首先擴(kuò)展OPEN2中的節(jié)點(diǎn),因?yàn)镺PEN2中含有感興趣集中的節(jié)點(diǎn),可能比OPEN1中的節(jié)點(diǎn)更有希望在最佳路徑上,而且所擴(kuò)展的節(jié)點(diǎn)數(shù)目總不會(huì)多于原算法。

3.3圖搜索算法

3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

討論(1)啟發(fā)式搜索算法在大問(wèn)題中一般優(yōu)于非啟發(fā)式搜索算法,因此,有效地分析利用啟發(fā)信息尤為重要。含有啟發(fā)信息的評(píng)價(jià)函數(shù)可寫成下列形式:f(x)=v·g(x)+w·h(x)其中,v、w為權(quán)系數(shù)且≥0.當(dāng)w↑,強(qiáng)調(diào)啟發(fā)信息,搜索過(guò)程沿最有希望的方向進(jìn)行,效率肯定高,但降低了完備性;當(dāng)v↑,強(qiáng)調(diào)歷史信息,搜索過(guò)程沿橫向掃描,有利于完備性,但降低了搜索效率。

3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改進(jìn)

討論(2)根據(jù)啟發(fā)信息,可將復(fù)雜的、規(guī)模大的問(wèn)題分解為簡(jiǎn)單的規(guī)模小的若干子問(wèn)題。那么各子問(wèn)題的搜索過(guò)程A1,A2,…,An是完備的,則搜索過(guò)程A也是完備的。A=A1∩A2∩…∩An根據(jù)啟發(fā)信息,可將原始的問(wèn)題進(jìn)行同構(gòu)或同態(tài)的等價(jià)變換,轉(zhuǎn)換為若干等價(jià)問(wèn)題。那么等價(jià)問(wèn)題的搜索過(guò)程A1,A2,…,An是完備的,則搜索過(guò)程A也是完備的。A=A1∪A2∪…∪An.

3.3圖搜索算法3.3.4AND/OR圖搜索算法上節(jié)探討的算法具有重要的意義。但對(duì)于復(fù)雜的問(wèn)題,它們并不是唯一的途徑,若利用它們直接求解往往還比較困難。AND/OR圖算法是用于表示問(wèn)題及其求解過(guò)程的又一種形式化方法。定義1AND圖及AND圖算法把一個(gè)復(fù)雜的問(wèn)題分解成若干個(gè)較為簡(jiǎn)單的子問(wèn)題,每個(gè)子問(wèn)題又可繼續(xù)分解為更為簡(jiǎn)單的子問(wèn)題,重復(fù)此過(guò)程,直到不需要再分解或者不能再分解為止。這個(gè)分解圖是與圖,根據(jù)這個(gè)圖對(duì)每個(gè)子問(wèn)題分別求解,然后把這些解合并起來(lái)得到原問(wèn)題解的過(guò)程是AND圖算法。3.3圖搜索算法3.3.4AND/OR圖搜索算法定義2OR圖及OR圖算法把一個(gè)復(fù)雜問(wèn)題利用同構(gòu)或同態(tài)的等價(jià)變換,使之成為若干個(gè)較容易求解的新問(wèn)題。這個(gè)變換圖是OR圖,根據(jù)這個(gè)圖對(duì)新問(wèn)題求解,當(dāng)且僅當(dāng)新問(wèn)題有一個(gè)可解,就得到原問(wèn)題的解的解過(guò)程是AO圖算法。定義3可解節(jié)點(diǎn)在AND/OR圖中,滿足下列條件之一者為可解節(jié)點(diǎn):(1)它是一個(gè)終止節(jié)點(diǎn).(2)它是一個(gè)OR節(jié)點(diǎn),且子節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn).(3)它是一個(gè)AND節(jié)點(diǎn),且其子節(jié)點(diǎn)全部是可解節(jié)點(diǎn)。3.3圖搜索算法3.3.4AND/OR圖搜索算法定義4不可解節(jié)點(diǎn)定義3中三個(gè)條件全部不滿足的節(jié)點(diǎn)稱為不可解節(jié)點(diǎn)。下面分析AND/OR圖AO*搜索算法,作一些改進(jìn)探討;探討類比搜索方法.為此,我們首先給出AND/OR圖的一般搜索過(guò)程:(1)把原始問(wèn)題作為初始節(jié)點(diǎn),并作為當(dāng)前節(jié)點(diǎn)。(2)應(yīng)用分解或等價(jià)變換算符對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展。(3)為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。(4)選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn),反復(fù)執(zhí)行(2)和(3),直至找到可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。下班可解或不可解的搜索過(guò)程都是至上而下的。如果確定某個(gè)節(jié)點(diǎn)是可解節(jié)點(diǎn),則不可解的后裔節(jié)點(diǎn)不再有用,可從搜索圖中刪去;同樣,如果確定某個(gè)節(jié)點(diǎn)是不可解節(jié)點(diǎn),則全部后裔節(jié)點(diǎn)都不在有用,也可從搜索圖中刪去。3.3圖搜索算法3.3.5AO*搜索算法分析與改進(jìn)定義定義5設(shè)AND/OR圖G,則從節(jié)點(diǎn)n到一立即可解的葉節(jié)點(diǎn)集合N的一解圖G'定義為:(1)G'是G的子圖;(2)若節(jié)點(diǎn)n是集合N中的元素,則G'是由單一節(jié)點(diǎn)n組成的;(3)若節(jié)點(diǎn)n有一個(gè)指向節(jié)點(diǎn){n1,n2,…,nk}的k-連接符,使得從每個(gè)后繼節(jié)點(diǎn)ni到集合N有一個(gè)解圖(i=1,2,…,k),則G'由節(jié)點(diǎn)n、k-連接符、節(jié)點(diǎn){n1,n2,…,nk}以及從{n1,n2,…,nk}中的每個(gè)節(jié)點(diǎn)到集合N的解圖組成。(4)否則,從節(jié)點(diǎn)n到集合N不存在解圖。3.3圖搜索算法3.3.5AO*搜索算法分析與改進(jìn)定義定義6從AND/OR圖任意節(jié)點(diǎn)n到一立即可解的葉節(jié)點(diǎn)集合N的解圖耗散值k(n,N)可遞歸地定義為：(1)若節(jié)點(diǎn)n是集合N中的元素,則k(n,N)=0;(2)否則,節(jié)點(diǎn)n有一個(gè)通到解圖中后繼節(jié)點(diǎn)集合{n1,n2,…,ni}的連接符.令該連接符的耗散值為Cn,則k(n,N)=Cn+k(n1,N)+k(n2,N)+…+k(ni,N)3.3圖搜索算法3.3.5AO*搜索算法分析與改進(jìn)定義定義7AND/OR圖求解中,從起始節(jié)點(diǎn)到一可解葉節(jié)點(diǎn)集合具有最小耗散值的一個(gè)解圖稱為最佳解圖。令函數(shù)h*(n)表示從AND/OR圖中的節(jié)點(diǎn)n到一可解的葉節(jié)點(diǎn)集合的最佳解圖的耗散值;啟發(fā)式估價(jià)函數(shù)h(n)是h*(n)的估計(jì)。定義8若啟發(fā)式估價(jià)函數(shù)h滿足單調(diào)限制,即對(duì)AND/OR圖中任意節(jié)點(diǎn)n及其適用于n的任一k-連接符,有h(n)≤Ck+h(n1)+…+h(nk)其中,Ck為k-連接符的耗散值,n1,n2,…,nk是應(yīng)用k-連接符于節(jié)點(diǎn)n所得的全部后繼節(jié)點(diǎn)。3.3圖搜索算法3.3.5AO*搜索算法分析與改進(jìn)AO*算法A1:建立一個(gè)搜索圖G,G:=s,計(jì)算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED);開(kāi)始時(shí)圖G只包含s,耗散值估計(jì)為h(s),若s是終節(jié)點(diǎn),則標(biāo)記能解.A2:Untils已標(biāo)記上SOLVED,do:A3:beginA4:G':=FIND(G);根據(jù)連接符標(biāo)記(指針)找出一個(gè)待擴(kuò)展的局部解圖G'.A5:n:=G'中的任一非終節(jié)點(diǎn);選一個(gè)非終節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn).A6:EXPAND(n),生成子節(jié)點(diǎn)集{nj},G:=ADD({nj},G),計(jì)算q(nj)=h(nj),其中nj∈G,IFGOAL(nj)THENM(nj,SOLVED);把n的子節(jié)點(diǎn)添加到G中,對(duì)G中未出現(xiàn)的子節(jié)點(diǎn)計(jì)算耗散值,若有終節(jié)點(diǎn)則加能解標(biāo)記.A7:S:={n};建立含n的單一節(jié)點(diǎn)集合S.A8:UntilS為空,do

3.3圖搜索算法3.3.5AO*搜索算法分析與改進(jìn)AO*算法(接前頁(yè))A9:beginA10:REMOVE(m,S),mc∈{S};這個(gè)m的子節(jié)點(diǎn)mc應(yīng)不在S中.A11:(1)修改m的耗散值q(m):對(duì)m指向節(jié)點(diǎn)集{n1i,n2i,…,nki}的每一個(gè)連接符i分別計(jì)算qi,qi(m)=Ci+q(n1i)+…+q(nki),q(m):=minqi(m);對(duì)m個(gè)的i個(gè)連接符,取計(jì)算結(jié)果最小的那個(gè)耗散值為q(m).(2)加指針到minqi(m)的連接符上,或把指針修改到minqi(m)的連接符上,即原來(lái)指針與新確定的不一致時(shí)應(yīng)刪去.(3)IFM(nji,SOLVED)THENM(m,SOLVED);若該連接符的所有子節(jié)點(diǎn)都是能解的,則m也標(biāo)上能解.A12:IFM(m,SOLVED)∨(q(m)≠q0(m))THENADD(ma,S);m能解或修正的耗散值與原先估算q0不同,則把m的所有先輩節(jié)點(diǎn)ma添加到S中.A13:endA14:end3.3圖搜索算法

3.3.5AO*搜索算法分析與改進(jìn)分析與改進(jìn)算法AO*可以理解為兩個(gè)主要運(yùn)算:A1～A6,完成自上而下的圖生成,通過(guò)有標(biāo)記的連接符,尋找最好的局部解圖,然后對(duì)其中一個(gè)非終節(jié)點(diǎn)進(jìn)行擴(kuò)展,并對(duì)其后繼節(jié)點(diǎn)賦給耗散值;A7～A12,完成自下而上的耗散值修正、連接符標(biāo)記和節(jié)點(diǎn)的能解標(biāo)記。(1)耗散值的修正從剛被擴(kuò)展的節(jié)點(diǎn)n開(kāi)始,其修正耗散值q(n)取估計(jì)h*(n)的所有值中最小的一個(gè),然后根據(jù)耗散值遞歸計(jì)算公式逐級(jí)向上修正先輩節(jié)點(diǎn)的耗散值,只有下層節(jié)點(diǎn)耗散值修正后,才可能影響上一層節(jié)點(diǎn)的耗散值,因此必須自底向上一直修正到初始節(jié)點(diǎn)。(2)在A6中擴(kuò)展節(jié)點(diǎn)n時(shí),若不存在后繼節(jié)點(diǎn)(即限入死胡同),則可在A11中對(duì)m(即n)賦一個(gè)高的q值,這個(gè)高的q值會(huì)依次傳遞到s,使得含有節(jié)點(diǎn)n的子圖具有高的q(s),從而排除了被當(dāng)作后選局部解圖的可能性。3.3圖搜索算法3.3.5AO*搜索算法分析與改進(jìn)分析與改進(jìn)(3)A5中怎樣選G'中的一個(gè)非終節(jié)點(diǎn)擴(kuò)展值得研究:一般可以選一個(gè)最可能導(dǎo)致該局部解圖耗散值發(fā)生較大變化的那個(gè)節(jié)點(diǎn)先擴(kuò)展,因?yàn)檫x這個(gè)節(jié)點(diǎn)先擴(kuò)展,會(huì)促使及時(shí)修改局部解圖的標(biāo)記。(4)與3.3.3.2節(jié)A算法類似,應(yīng)讓h(n)滿足單調(diào)限制條件,這樣,當(dāng)h(n)≤h*(n)則AO*一定能找到最佳解圖。當(dāng)h(n)≡0時(shí),AO*成寬度優(yōu)先算法。(5)AO*中評(píng)價(jià)函數(shù)只考慮h(n)分量,計(jì)算g沒(méi)有必要也不可能。其次由于k-連接符連接的有關(guān)子節(jié)點(diǎn),對(duì)于父節(jié)點(diǎn)能解與否以及耗散值都有影響,因而不能象A算法那樣優(yōu)先擴(kuò)展其中具有最小耗散值的節(jié)點(diǎn)。3.3圖搜索算法3.3.6類比搜索方法探討構(gòu)思在AO*和A算法中,所使用的啟發(fā)信息大多是人們依據(jù)具體領(lǐng)域問(wèn)題靠經(jīng)驗(yàn)總結(jié)得來(lái)的,啟發(fā)信息獲取十分困難,且精確性和可靠性也難以保證。此外,搜索算法一般執(zhí)行一次性搜索,將同一問(wèn)題的多次搜索視為彼此獨(dú)立、毫無(wú)相關(guān)的過(guò)程。每次求解問(wèn)題時(shí),面臨的都是全新的搜索圖,即使求解的是相同問(wèn)題,算法仍然從零開(kāi)始,這顯然與人類求解問(wèn)題的方式不符。人類求解問(wèn)題的一個(gè)重要特點(diǎn),就是常常利用以前求解相同或相似問(wèn)題的經(jīng)驗(yàn)來(lái)指導(dǎo)新問(wèn)題的求解。這實(shí)際上是一種類比學(xué)習(xí)機(jī)制,如果將這種機(jī)制引入搜索算法,則多次搜索被看成相互關(guān)聯(lián)的過(guò)程,前面搜索積累的經(jīng)驗(yàn)將有助于提高后面搜索的效率。即,利用類比獲得與新問(wèn)題相似的過(guò)去問(wèn)題的求解過(guò)程,作為啟發(fā)信息來(lái)指導(dǎo)新問(wèn)題的求解,這樣可以縮小搜索范圍,降低問(wèn)題求解的復(fù)雜性。也就是說(shuō),如果算法設(shè)計(jì)恰當(dāng),可以自動(dòng)獲得啟發(fā)信息。3.3圖搜索算法3.3.6類比搜索方法探討方法探討AO*、A及其它算法在問(wèn)題的求解過(guò)程中利用與該問(wèn)題相關(guān)的啟發(fā)信息來(lái)幫助搜索,啟發(fā)信息通常被用于三種情況:(1)幫助確定擴(kuò)展節(jié)點(diǎn)。(2)在擴(kuò)展節(jié)點(diǎn)的過(guò)程中,幫助決定產(chǎn)生后繼節(jié)點(diǎn)。(3)在擴(kuò)展節(jié)點(diǎn)的過(guò)程中,決定那些節(jié)點(diǎn)可從搜索樹(shù)上刪除。值得注意的是,啟發(fā)信息是一種局部信息,只在搜索路徑的每個(gè)節(jié)點(diǎn)上為選擇操作提供參考。3.3圖搜索算法3.3.6類比搜索方法探討方法探討類比搜索方法把類比推理技術(shù)與狀態(tài)空間的啟發(fā)式搜索相結(jié)合,實(shí)際上是對(duì)人類求解問(wèn)題、積累經(jīng)驗(yàn)和增加求解問(wèn)題能力的一種模擬。要實(shí)現(xiàn)它,需要解決如下一些主要問(wèn)題:(1)如何積累問(wèn)題求解的經(jīng)驗(yàn),即在一個(gè)問(wèn)題的求解過(guò)程中,需要記錄那些有用信息。(2)如何定義和判斷兩個(gè)問(wèn)題的求解情況是相似的,如何高效的進(jìn)行檢索。(3)如何有效地使用類比結(jié)論,即相似的過(guò)去問(wèn)題的求解經(jīng)驗(yàn),作為特殊的啟發(fā)信息指導(dǎo)新問(wèn)題的求解。3.3圖搜索算法3.3.6類比搜索方法探討方法探討

基于上述幾點(diǎn),需要建立一個(gè)類比的啟發(fā)式搜索求解模型。它主要包括生成求解事例、檢索及指導(dǎo)求解三個(gè)推理過(guò)程。類比搜索方法在每次求解一個(gè)新問(wèn)題時(shí),不是直接去搜索給定的狀態(tài)空間,而是首先在求解事例庫(kù)中檢索,查找與該問(wèn)題相似的過(guò)去問(wèn)題的求解事例。若存在相似問(wèn)題的求解事例,則以此作為啟發(fā)信息,指導(dǎo)該問(wèn)題的求解。具體地說(shuō),就是在新問(wèn)題的求解過(guò)程中,對(duì)過(guò)去問(wèn)題的求解事例中記錄的成功搜索路徑上每個(gè)操作的依據(jù)條件重新測(cè)試.如果依據(jù)條件仍滿足,則算法根隨成功的求解路徑。否則,對(duì)原求解過(guò)程進(jìn)行改寫,形成的新問(wèn)題求解過(guò)程作為一個(gè)新事例存儲(chǔ)在事例庫(kù)中,以便指導(dǎo)將來(lái)相似問(wèn)題的求解。過(guò)去問(wèn)題與新問(wèn)題的相似性越高,求解過(guò)程需要的搜索就越少。在最理想的情況下,甚至不需要搜索。當(dāng)沒(méi)有檢索到一個(gè)與新問(wèn)題相似的過(guò)去問(wèn)題的求解事例時(shí),則使用A*或AO*等算法進(jìn)行,并在獲得解時(shí)將求解過(guò)程作為一個(gè)求解事例存儲(chǔ)在事例庫(kù)中。3.3圖搜索算法3.3.6類比搜索方法探討方法探討系統(tǒng)最初使用時(shí),由于事例庫(kù)中缺少求解事例,只有使用A*或AO*等算法。隨著求解次數(shù)的增加,求解事例將不斷積累,類比的資料增多(啟發(fā)信息增多),從而使求解問(wèn)題的效率不斷提高。由此可知,類比搜索方法的特點(diǎn)是:類比啟發(fā)信息不僅包含了局部信息,而且提供了指導(dǎo)求解的搜索方向,這樣就可以將一個(gè)龐大空間的搜索壓縮為對(duì)一個(gè)或數(shù)個(gè)很小空間的搜索,極大地提高了求解效率。3.3圖搜索算法3.3.7討論用AND/OR圖算法求解問(wèn)題時(shí),求解過(guò)程就是對(duì)一個(gè)隱含的AND/OR圖進(jìn)行搜索。初始數(shù)據(jù)庫(kù)對(duì)應(yīng)于AND/OR圖的根節(jié)點(diǎn),規(guī)則對(duì)應(yīng)于k-連接符,結(jié)束條件的數(shù)據(jù)庫(kù)對(duì)應(yīng)于一組終節(jié)點(diǎn)集合,搜索算法的任務(wù)就是找到從初始節(jié)點(diǎn)到一組終節(jié)點(diǎn)集的一個(gè)解圖。AND/OR圖的啟發(fā)式搜索算法AO*是通過(guò)評(píng)價(jià)函數(shù)f(n)=h(n)來(lái)引導(dǎo)搜索過(guò)程,適用于分解得到的子問(wèn)題不存在相互作用的情況。若S→N集存在解圖,當(dāng)h(n)≤h*(n)且h(n)滿足單調(diào)限制條件時(shí),AO*算法一定能找到最佳解圖,在這種情況下,AO*具有可采納性。3.3圖搜索算法3.3.7討論

類比搜索方法實(shí)施的關(guān)鍵技術(shù)在于生成求解事例、相似性度量和檢索、以及指導(dǎo)求解。生成求解事例就是積累問(wèn)題的求解經(jīng)驗(yàn),其生成過(guò)程主要解決的問(wèn)題是對(duì)于一個(gè)求解事例需要記錄和保存問(wèn)題求解過(guò)程中的那些特征信息,以及如何進(jìn)行表示、抽取和存儲(chǔ)這些信息。求解一個(gè)復(fù)雜問(wèn)題時(shí),經(jīng)常面臨龐大的搜索。大量被搜索的節(jié)點(diǎn)中,有成功的、也有失敗的。為了給相似問(wèn)題的求解提供有用信息,就要確定保存搜索過(guò)程中的哪些有用特征信息。顯然,走兩個(gè)極端最簡(jiǎn)單:第一是記下整個(gè)搜索過(guò)程;第二是只記問(wèn)題的最終解。這兩個(gè)極端都不圓滿,具體地作法除了保留問(wèn)題的最終解外,還應(yīng)該記錄有關(guān)選擇這些操作的情境和依據(jù)條件。這是一個(gè)很有意義的研究課題。相似性的度量也是類比搜索方法的一個(gè)關(guān)鍵問(wèn)題。相似程度越高,度量方法恰當(dāng),相似問(wèn)題的檢索俞易獲得。關(guān)于這方面,目前還是主要根據(jù)新、老問(wèn)題的特征和關(guān)系來(lái)確定它們之間的相似性。此外,還可設(shè)置相似度閥值，檢索采用直接映射式方法。3.3圖搜索算法3.3.7討論指導(dǎo)求解是類比搜索方法的控制程序,主要考慮靈活的處理策略。一般要考慮以下幾點(diǎn):(1)當(dāng)檢索沒(méi)有類比啟發(fā)信息時(shí),程序能轉(zhuǎn)向常規(guī)搜索方法。(2)當(dāng)檢索到一個(gè)與新問(wèn)題完全相似的過(guò)去問(wèn)題的求解事例時(shí),程序能直接轉(zhuǎn)換解。(3)當(dāng)檢索到一個(gè)與新問(wèn)題部分相似的過(guò)去問(wèn)題的求解事例時(shí),程序能提取相似部分解過(guò)程,還能組織部分搜索、銜接新的解過(guò)程。此外,應(yīng)有裁剪過(guò)去問(wèn)題多余解過(guò)程的功能。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.1規(guī)則不一致原因及解決方法

規(guī)則集中存在的不一致是影響系統(tǒng)性能的重要因素之一。系統(tǒng)建立初期,由于規(guī)則集較小,內(nèi)容也比較簡(jiǎn)單,設(shè)計(jì)人員能對(duì)每一條規(guī)則的條件和結(jié)論部分反復(fù)推敲和精心構(gòu)造,這類問(wèn)題容易防止。但隨著時(shí)間的推移,新的規(guī)則不斷加入,規(guī)則集合越來(lái)越大,內(nèi)容也越來(lái)越豐富,這時(shí)規(guī)則間的相互影響和相互聯(lián)系就隨之變得復(fù)雜。在此情況下,規(guī)則的不一致就將自然產(chǎn)生,當(dāng)然,對(duì)它的認(rèn)識(shí)和解決也就顯得很重要。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.1規(guī)則不一致原因及解決方法主要的不一致規(guī)則種類(1)循環(huán)規(guī)則:由數(shù)個(gè)規(guī)則的前提和結(jié)論形成一個(gè)循環(huán)鏈,最終由末尾規(guī)則的結(jié)果子句推出起始規(guī)則的前提部分;(2)沖突規(guī)則:兩個(gè)規(guī)則的前提條件等價(jià),但一個(gè)或多個(gè)結(jié)果子句有矛盾或者前提子句有矛盾而結(jié)論部分完全等價(jià);也有可能由多條規(guī)則鏈形成沖突規(guī)則集;(3)冗余規(guī)則:兩個(gè)規(guī)則的前提條件等價(jià),一個(gè)或多個(gè)子結(jié)果子句也等價(jià);(4)從屬規(guī)則:兩個(gè)規(guī)則有相同的結(jié)果,但其中一個(gè)包含有多余的約束條件。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.1規(guī)則不一致原因及解決方法不一致規(guī)則的檢查解決方法(1)對(duì)于循環(huán)規(guī)則,可構(gòu)造規(guī)則集的IF---THEN圖,從起始規(guī)則的條件部分開(kāi)始搜索,如果搜索過(guò)程中遇到的THEN部分已在前面出現(xiàn),就可以中斷搜索,規(guī)則集中包含的循環(huán)規(guī)則子集合需設(shè)計(jì)人員檢查,解決;(2)對(duì)于沖突規(guī)則,構(gòu)造IF---IF表,對(duì)規(guī)則集內(nèi)有相同的IF規(guī)則子句構(gòu)造規(guī)則樹(shù),形成推理圖。同時(shí)建立THEN---THEN表用以判斷是否有沖突規(guī)則出現(xiàn)。對(duì)相同IF部分的規(guī)則繼續(xù)用它的各自THEN部分作為其它可以匹配的IF前提條件,遞歸地構(gòu)造,如發(fā)現(xiàn)兩個(gè)推理圖上分別有節(jié)點(diǎn)在THEN---THEN表上是矛盾的,則檢測(cè)出沖突規(guī)則,人工予以解決。(3)對(duì)冗余規(guī)則和從屬規(guī)則的檢查類似于沖突規(guī)則鏈的方法.不同之處是前者在推理圖中的遍歷是試圖發(fā)現(xiàn)有THEN部分等價(jià)的兩條規(guī)則。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法排序算法原則依賴規(guī)則：如果Ri的結(jié)論部份包含有Rj的條件部份，則Rj是一個(gè)依賴規(guī)則，即Rj依賴規(guī)則Ri，或稱Ri是一個(gè)被依賴規(guī)則。優(yōu)先規(guī)則:如果Ri被Pi個(gè)其它規(guī)則所依賴次數(shù)pi越大,Ri被援引的可能性越大。靜態(tài)規(guī)則排列：亦是在原文分析、原文譯文轉(zhuǎn)換、譯文生成之前，對(duì)規(guī)則集中已有的規(guī)則按優(yōu)先次序排列。動(dòng)態(tài)規(guī)則排列：這相當(dāng)于自學(xué)習(xí)能力，即某些句子分析、轉(zhuǎn)換、生成時(shí)，會(huì)增加一條或幾條規(guī)則。這些規(guī)則有可能還與未完成的其它語(yǔ)句有關(guān)。因此，在對(duì)其它語(yǔ)句和完成速度影晌不大的情況下，同時(shí)再排列規(guī)則稱之為動(dòng)態(tài)規(guī)則排列。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法

排序算法原則映射排列：是一個(gè)基于地址計(jì)算的排序。例如，求出上述Pi(i=1，2,...，N）的最大值后，若開(kāi)辟一個(gè)數(shù)組D（Pmax）,就可把數(shù)據(jù)送入數(shù)據(jù)值下標(biāo)相等的對(duì)應(yīng)元素中。顯然Pi=50，對(duì)應(yīng)D(50);Pj=500,對(duì)應(yīng)D(500)。相同數(shù)據(jù)落在同一數(shù)組元素中，用計(jì)數(shù)方式可知有幾個(gè)。由于數(shù)組元素是有序的，500>50，數(shù)組元素的下標(biāo)自然把數(shù)據(jù)一次定好位置，最后只要按規(guī)定的方式調(diào)非零元秦，相同元素按計(jì)數(shù)值次數(shù)調(diào)動(dòng)，排序即完成。枚舉計(jì)數(shù)：如果規(guī)則Ri被規(guī)則Rj依賴(j=1，2,...,N)，則Pi=pi+1（Pi初值賦1)。顯然，對(duì)于N條規(guī)則，每一條都將確定與其它規(guī)則的依賴關(guān)系并計(jì)算，這一過(guò)程稱之為枚舉計(jì)數(shù)。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法

排序算法描述與分析靜態(tài)算法（上）B1:[初始化]，有N條規(guī)則，置P1至PN皆為1。B2:〔對(duì)i循環(huán)〕對(duì)i=N，N—1，N-2，…，2執(zhí)行B3;然后轉(zhuǎn)B5。B3:〔對(duì)j循環(huán)〕對(duì)j=i-1，i-2，…，1執(zhí)行B4;然后轉(zhuǎn)B2。B4:〔尋求Ri被Rj依賴次數(shù)〕若Ri被Rj依賴，Pi←Pi＋1；否則轉(zhuǎn)B3。B5:一遍掃描Pi（i=1，2,...，N)，求Pmax。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法排序算法描述與分析靜態(tài)算法（上）靜態(tài)算法進(jìn)行到這里，求出了任一規(guī)則Ri被依賴次數(shù)Pi。Pi對(duì)應(yīng)于Ri，相當(dāng)于Ri被依賴次數(shù)Pi。Pi對(duì)應(yīng)Ri，相當(dāng)于Ri的關(guān)鍵字。其中，很可能出現(xiàn)Pi=Pj(i≠j),這說(shuō)明Ri和Rj被其它規(guī)則依賴的條數(shù)相同。怎樣快速地按關(guān)鍵字Pi(i=1，2，...,N)大小把規(guī)則快速地排列起來(lái)，并滿足動(dòng)態(tài)需要，我們采用高效算法——映射排序算法初始按關(guān)鍵字值以映射關(guān)系作一次掃描，基本排定規(guī)則位置，Ri→Pi→D（Pi）。對(duì)相同關(guān)鍵字的處理，算法附加了三個(gè)數(shù)組空間：每一記錄的鏈指針空間L（i），鏈?zhǔn)字羔樋臻gQ，鏈當(dāng)前指針空間W。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法排序算法描述與分析靜態(tài)算法（上）關(guān)鍵字值Pi與D數(shù)組元素下標(biāo)映射關(guān)系有一次時(shí),D(Pi)=1；這時(shí)Q(Pi)←1，記錄了具有這唯一對(duì)應(yīng)關(guān)系Pi所在規(guī)則的地址i，并作為最后排序調(diào)整位置的首地址。W（Pi）←i為出現(xiàn)相同關(guān)鍵字提供鏈接地址作準(zhǔn)備。映射時(shí)出現(xiàn)相同關(guān)鍵字，如Pi=Pj，這時(shí)D（Pi）>1，我們把Pi和Pj對(duì)應(yīng)的兩條規(guī)則鏈接起來(lái)，入口地址仍是Q（Pi）=i，但L（W（Pi））←j，相當(dāng)于L(i)=j,此外，W（Pj）←j，為鏈接出現(xiàn)多個(gè)相同關(guān)鍵字作準(zhǔn)備。實(shí)施映射和鏈接處理后，最后再實(shí)施一次掃描，根據(jù)D數(shù)組下標(biāo)值的有序性，D=0不實(shí)施操作，D≥l從相對(duì)應(yīng)的Q數(shù)組下標(biāo)值作為入口地址調(diào)整一次規(guī)則位置即完成排列。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法排序算法描述與分析靜態(tài)算法（下）

B6：[映射初始化，開(kāi)辟鏈指針空間L，容量N;映射計(jì)數(shù)空間D，鏈?zhǔn)字羔樋臻gQ，鏈當(dāng)前指針空間W，容量均為Dmax，賦初值i=1。B7:掃描Pi，讓D（Pi）←D（Pi）＋1；以映射關(guān)系確定Pi的位置，記錄相同Pi的個(gè)數(shù)。B8：若D(Pi)=1，作W(Pi)←i和Q(Pi)←i，轉(zhuǎn)B10。B9:若D（Pi）>1，作L（W（Pi））←i和W(Pi)←i。B10：i←i+1，直至i=N為止，實(shí)施B7～B9。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法

排序算法描述與分析靜態(tài)算法（下）B11:（Z=1)，從J=Dmax開(kāi)始，若D（J）=0轉(zhuǎn)B12;D（J）≠0，作遞減排列。

(1)T←Q（J）；鏈?zhǔn)字羔標(biāo)蚑。(2)輸出RT。(3)z←z＋1，若Z≠D(J)，T←L（T）后轉(zhuǎn)(2)；否則轉(zhuǎn)B12。B12：J←J-1，實(shí)施B11，直至J=0結(jié)束。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題

3.4.2規(guī)則排序算法

排序算法描述與分析動(dòng)態(tài)算法規(guī)則匹配過(guò)程中，如果系統(tǒng)自學(xué)習(xí)新增一條規(guī)則RN+1，將立即置人規(guī)則集適當(dāng)位置，自動(dòng)啟動(dòng)的算法是：C1：對(duì)i=1，2,...，N，若RN+1被Ri依賴，PN+1←PN+1+l（PN+1初值賦1）；反之，若Ri被RN+1依賴，Pi←Pi+1。C2：若PN+1>Pmax，Pmax←PN＋1C3，調(diào)靜態(tài)算法（下），其中修改N←N+1。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題

3.4.2規(guī)則排序算法

排序算法描述與分析算法分析1）靜態(tài)算法（上）時(shí)間復(fù)雜性為O（N2），因?yàn)锽1～B5執(zhí)行步驟共需(N-1)+(N-2)+...+2+1+N=1/2(N2+N)。2）靜態(tài)算法（下）時(shí)間復(fù)雜性為O（N），因?yàn)樗惴ǖ臉?gòu)思來(lái)源于映射排序算法中的一部份，其證明可參閱書(shū)末文獻(xiàn)。由于動(dòng)態(tài)算法僅C1一C2引進(jìn)附加操作，顯然為O(N)，C3為O(N)，所以動(dòng)態(tài)算法時(shí)間復(fù)雜性為O(N)3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法

排序算法描述與分析算法分析3）由于靜態(tài)算法（下）附加存儲(chǔ)空間3Pmax+N，因此，動(dòng)態(tài)算法獲得的高效率是由空間代價(jià)換取的。4）算法假設(shè)了規(guī)則自身依賴，所以Pi的初值賦1。5)算法將規(guī)則優(yōu)先排列，使規(guī)則匹配花費(fèi)平均時(shí)間最小。平均時(shí)間最小亦說(shuō)明，一般狀況下，分折的句子越多，其效率越高；但也可能存在某些狀況，所需規(guī)則恰好排列在最后。所以，這一算法是平均時(shí)間較優(yōu)算法。3.4產(chǎn)生式系統(tǒng)的規(guī)則問(wèn)題3.4.2規(guī)則排序算法

排序算法描述與分析實(shí)驗(yàn)結(jié)果排序算法的實(shí)驗(yàn)是這樣進(jìn)行的，在上述規(guī)則集中，分析4條語(yǔ)句。設(shè)計(jì)第1條語(yǔ)句產(chǎn)生1條規(guī)則，該規(guī)則2、3、4條語(yǔ)句都將涉及。把這條規(guī)則分別放于最后和進(jìn)行動(dòng)態(tài)排列，結(jié)果后者完成2、3、4條語(yǔ)句分析較前者速度提高1倍多。這是一個(gè)目前具有3380條規(guī)則的實(shí)驗(yàn)系統(tǒng)，有如此實(shí)驗(yàn)效果足以說(shuō)明此算法的實(shí)用性。3.5應(yīng)用舉例任何一種自然語(yǔ)言,總是要遵循一定的語(yǔ)法規(guī)則的.計(jì)算機(jī)要理解、翻譯自然語(yǔ)言,就要對(duì)理解和翻譯的語(yǔ)言建立一套規(guī)則,也就是語(yǔ)法,并且提供一種適合計(jì)算機(jī)處理的語(yǔ)法描述形式。上下文無(wú)關(guān)語(yǔ)法是適合描述自然語(yǔ)言的一種體系。作為一個(gè)例子,先來(lái)考察漢語(yǔ)的一個(gè)很小子集,它的上下文無(wú)關(guān)語(yǔ)法由以下一系列重寫規(guī)則組成:(1)<一種句子結(jié)構(gòu)>→<名詞><動(dòng)詞><數(shù)詞><名詞>(2)<名詞>→電腦│學(xué)院│中國(guó)│地圖│衛(wèi)星│…(3)<動(dòng)詞>→購(gòu)買│繪制│發(fā)射│…(4)<數(shù)詞>→一顆│十臺(tái)│一幅│…3.5應(yīng)用舉例

在這些重寫規(guī)則中,尖括號(hào)稱之為非終極符;而電腦、學(xué)院…稱終極符;豎線"│"表示或的意思。這種語(yǔ)法之所以是上下文無(wú)關(guān)的,是因?yàn)樵谶@些重寫規(guī)則中,左邊項(xiàng)都是孤立的非終極符,它們可以被右邊的符號(hào)串所替換,而不管左邊出現(xiàn)的上下文。這種語(yǔ)法既可用于生成語(yǔ)法正確的漢語(yǔ)句子,也可用于分析輸入的漢語(yǔ)句子是否合乎語(yǔ)法。下面三例計(jì)算