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

人工智能與機(jī)器翻譯主講：楊憲澤——產(chǎn)生式系統(tǒng)及其搜索方法第3章產(chǎn)生式系統(tǒng)及其搜索方法3.1產(chǎn)生式系統(tǒng)3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.3圖搜索算法3.4產(chǎn)生式系統(tǒng)的規(guī)那么問(wèn)題3.5運(yùn)用舉例3.6產(chǎn)生式系統(tǒng)的不確定性問(wèn)題3.7系統(tǒng)設(shè)計(jì)技巧3.1產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)運(yùn)用類似于文法的規(guī)那么,對(duì)符號(hào)串作交換運(yùn)算。它是智能軟件中運(yùn)用最普遍、最典型的一種構(gòu)造。為什么要采用產(chǎn)生式系統(tǒng)作為智能軟件的主要構(gòu)造呢?這可以有兩點(diǎn)理由:(1)用產(chǎn)生式系統(tǒng)構(gòu)造求解問(wèn)題的過(guò)程和人類求解問(wèn)題時(shí)的思想過(guò)程很相象,因此可以用它來(lái)模擬人類求解問(wèn)題時(shí)的思想過(guò)程;(2)可以把產(chǎn)生式系統(tǒng)作為智能軟件中的根本構(gòu)造單元或根本方式對(duì)待,就好象是積木世界中的積木塊一樣,因此研討產(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)所運(yùn)用的主要數(shù)據(jù)構(gòu)造,用來(lái)表述問(wèn)題的形狀或有關(guān)現(xià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ùn)用的先決條件;右邊描畫了運(yùn)用這條規(guī)那么所采取的行動(dòng)或得出的結(jié)論。一條產(chǎn)生式規(guī)那么滿足了運(yùn)用的先決條件之后,就可對(duì)綜合數(shù)據(jù)庫(kù)進(jìn)展操作,使其發(fā)生變化。如綜合數(shù)據(jù)庫(kù)代表當(dāng)前形狀,那么運(yùn)用規(guī)那么后就使形狀發(fā)生轉(zhuǎn)換,生成新形狀。3.1產(chǎn)生式系統(tǒng)3.1.1產(chǎn)生式系統(tǒng)的組成部分控制系統(tǒng)是軟件的控制程序,也是規(guī)那么的解釋(推理)程序。它規(guī)定了如何選擇一條可運(yùn)用的規(guī)那么對(duì)數(shù)據(jù)庫(kù)進(jìn)展操作,即確定了求解過(guò)程的推理道路。當(dāng)數(shù)據(jù)庫(kù)滿足終了條件時(shí),系統(tǒng)就應(yīng)停頓運(yùn)轉(zhuǎn);還要使系統(tǒng)在求解過(guò)程中記住運(yùn)用過(guò)的規(guī)那么序列,以便最終能給出解的途徑?？刂葡到y(tǒng)也稱控制戰(zhàn)略,它也可以是從規(guī)那么集中選擇規(guī)那么并作用于形狀的一種廣義選取函數(shù)。確定某一種戰(zhàn)略后,可以算法的方式給出。在建立產(chǎn)生式系統(tǒng)描畫時(shí),還要給出初始形狀和目的條件,詳細(xì)闡明所求解的問(wèn)題。產(chǎn)生式系統(tǒng)中控制戰(zhàn)略的作用就是從初始形狀出發(fā),尋求一個(gè)滿足一定條件的問(wèn)題形狀。目的條件也是產(chǎn)生式系統(tǒng)終了條件的根底。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)的行為就要改動(dò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ī)那么集合及其控制戰(zhàn)略。這種把一個(gè)問(wèn)題的表達(dá)轉(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)描畫之后,經(jīng)過(guò)控制戰(zhàn)略,可求得實(shí)現(xiàn)目的的一個(gè)規(guī)那么序列,這就是所謂問(wèn)題的解,這個(gè)解序列是根據(jù)控制系統(tǒng)記住搜索目的過(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í)引入形狀空間圖。形狀空間圖是一個(gè)有向圖,其節(jié)點(diǎn)可表示問(wèn)題的各種形狀(綜合數(shù)據(jù)庫(kù)),節(jié)點(diǎn)之間的弧線代表一些操作(產(chǎn)生式規(guī)那么),它們可把一種形狀導(dǎo)向另一種形狀。這樣建立起來(lái)的形狀空間圖,描畫了問(wèn)題一切能夠出現(xiàn)的形狀及形狀和操作之間的關(guān)系,因此可以較直觀地看出問(wèn)題的解途徑及其性質(zhì)。當(dāng)然,只需問(wèn)題空間規(guī)模較小才能夠作出形狀空間圖。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)化形狀空間和規(guī)那么集表示,此外,高效率的問(wèn)題求解過(guò)程與控制戰(zhàn)略有關(guān),適宜的控制戰(zhàn)略可減少形狀空間的搜索范圍,提高求解的效率。從以上論述可知,用產(chǎn)生式系統(tǒng)來(lái)描畫和求解問(wèn)題,就是在問(wèn)題空間中搜索一條從初始形狀到達(dá)某一個(gè)目的形狀的途徑。這完全可以模擬人的求解過(guò)程,也就是可以把產(chǎn)生式系統(tǒng)作為求解問(wèn)題思索過(guò)程的一種模擬。3.1產(chǎn)生式系統(tǒng)3.1.2產(chǎn)生式系統(tǒng)的根本算法E1:DATA←初始現(xiàn)實(shí)庫(kù)E2:untilDATA滿足終了條件以前,doE3:beginE4:在規(guī)那么集中,選某一條可用于DATA的規(guī)那么E5:DATA←規(guī)那么運(yùn)用到DATA得到的結(jié)果E6:終了3.1產(chǎn)生式系統(tǒng)3.1.3產(chǎn)生式系統(tǒng)的類型正向、逆向、雙向產(chǎn)生式系統(tǒng)用產(chǎn)生式系統(tǒng)求解某一問(wèn)題時(shí),假設(shè)按照規(guī)那么運(yùn)用的方式或者說(shuō)按推理方向來(lái)劃分的話,有正向、逆向和雙向產(chǎn)生式系統(tǒng)。正向產(chǎn)生式系統(tǒng)是從初始形狀出發(fā)朝著目的形狀這個(gè)方向運(yùn)用規(guī)那么,即正推的方式任務(wù),稱這些規(guī)那么為F規(guī)那么;假設(shè)選目的形狀作為初始數(shù)據(jù)庫(kù)逆向進(jìn)展求解,即逆向運(yùn)用規(guī)那么,產(chǎn)生子目的形狀,反方向一步一步朝著初始形狀方向求解,整個(gè)逆推方式任務(wù),稱逆向產(chǎn)生式系統(tǒng),逆向運(yùn)用的規(guī)那么稱B規(guī)那么;假設(shè)以雙向搜索的方式(即正向和逆向同時(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ùn)用可以恣意交換次序而不影響求解。普通來(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ùn)用于D的規(guī)那么集合,運(yùn)用了其中恣意一條規(guī)那么之后所生成的任何數(shù)據(jù)庫(kù),這樣一個(gè)規(guī)那么集合還適用;(2)滿足目的條件的某個(gè)數(shù)據(jù)庫(kù)D,當(dāng)運(yùn)用任何一個(gè)可運(yùn)用于數(shù)據(jù)庫(kù)D的規(guī)那么之后所生成的任何數(shù)據(jù)庫(kù),任然滿足目的條件;(3)假設(shè)對(duì)D運(yùn)用某一規(guī)那么序列后得到的一個(gè)數(shù)據(jù)庫(kù)D'(并能到達(dá)解),當(dāng)改動(dòng)這些規(guī)那么次序后,任然可求得解,即求得D'與運(yùn)用滿足D的可運(yùn)用規(guī)那么集合中的規(guī)那么次序無(wú)關(guān)。3.1產(chǎn)生式系統(tǒng)3.1.3產(chǎn)生式系統(tǒng)的類型可交換的產(chǎn)生式系統(tǒng)例:給定一個(gè)整數(shù)集合的初始形狀{a,b,c},設(shè)目的形狀為具有a,b,c,ab,bc,ca這六個(gè)元素組成的集合?？蛇\(yùn)用的規(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í)只需搜索其中任一條途徑,只需解存在就一定能找到目的,不用探求多條途徑,因此不可撤回的控制方式(下節(jié)論述)在這種系統(tǒng)中運(yùn)用很適宜,因解與最初可運(yùn)用的規(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)終了條件是生成只包含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í),搜索得到的部分形狀空間圖見圖26。圖中只給出兩條到達(dá)目的的途徑和一條失敗的途徑。實(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ùn)用的條件,如此進(jìn)展下去,直到分量數(shù)據(jù)庫(kù)滿足某種終了條件為止。要留意普通結(jié)束條件應(yīng)是一切分量數(shù)據(jù)庫(kù)都已滿足終了條件。3.1產(chǎn)生式系統(tǒng)3.1.3產(chǎn)生式系統(tǒng)的類型可分解的產(chǎn)生式系統(tǒng)可以分解產(chǎn)生式系統(tǒng)的綜合數(shù)據(jù)庫(kù)和終了條件的產(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}的一切元素都滿足終了條件之前,do:(4)begin(5)從{Di}中選一個(gè)不滿足終了條件的D*(6)從{Di}中刪去D*(7)在規(guī)那么集中選擇一條可運(yùn)用于D*的規(guī)那么R(8){di}:=R運(yùn)用于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↓目的(M,M,M,M,M,M,M,M,M,M)圖263.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略在3.1.2節(jié)的算法中,如何選擇一條可運(yùn)用的規(guī)那么,作用于當(dāng)前的綜合數(shù)據(jù)庫(kù),生成新的形狀以及記住選用的規(guī)那么序列是構(gòu)成控制戰(zhàn)略的主要內(nèi)容。對(duì)大多數(shù)的智能運(yùn)用問(wèn)題,所擁有的控制戰(zhàn)略知識(shí)或信息并缺乏以使每次經(jīng)過(guò)算法E4時(shí),一下子就能選出最適宜的一條規(guī)那么來(lái),因此產(chǎn)生式系統(tǒng)還必需把E4擴(kuò)展成搜索(推理)算法,以致于根本算法的每一循環(huán)中選一條規(guī)那么試用,最終找出某一序列能產(chǎn)生一個(gè)滿足終了條件的數(shù)據(jù)庫(kù)為止。由此可見,高效率的控制戰(zhàn)略需求有關(guān)被求解問(wèn)題的足夠知識(shí),這樣才干在搜索過(guò)程減少盲目性,比較快的找到解途徑。過(guò)去三十多年中,人們研討了許多種搜索算法,歸納起來(lái)主要有兩類:一類是非啟發(fā)式算法;另一類是啟發(fā)式算法。非啟發(fā)式算法是按預(yù)定的控制戰(zhàn)略進(jìn)展搜索,在其過(guò)程中獲得的中間信息不用來(lái)改良控制戰(zhàn)略。由于搜索總是按預(yù)先規(guī)定的道路進(jìn)展,沒(méi)有思索問(wèn)題本身的特性,所以不容易選擇到最優(yōu)的搜索途徑,效率較低,且出現(xiàn)"組合爆炸"的頻率高。啟發(fā)式算法是在搜索中參與了與問(wèn)題有關(guān)的啟發(fā)性信息,用以指點(diǎn)搜索朝著最有希望的方向前進(jìn),加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2.1產(chǎn)生式系統(tǒng)控制戰(zhàn)略分類可分解的產(chǎn)生式系統(tǒng)控制戰(zhàn)略可劃分為兩大類:┌不可撤回方法┌回溯方法└試探性方法─┤└圖搜索方法3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2.2不可撤回方法這種方法相當(dāng)于沿著單獨(dú)一條路搜索下去,利用問(wèn)題給出的部分知識(shí)決議如何選取規(guī)那么,就是說(shuō)根據(jù)當(dāng)前可靠的部分知識(shí)選一條可運(yùn)用規(guī)那么并作用于當(dāng)前綜合數(shù)據(jù)庫(kù)。接著再根據(jù)新形狀繼續(xù)選取規(guī)那么,搜索過(guò)程不斷進(jìn)展,不用思索撤回用過(guò)的規(guī)那么。這是由于在搜索過(guò)程中如能有效利用部分知識(shí),即使運(yùn)用了一條不理想的規(guī)那么,也不妨礙下一步選得另一條更適宜的規(guī)那么。這樣不吊銷用過(guò)的規(guī)那么,并不影響求到解,只是解序列中能夠多了一些不用要的規(guī)那么。顯然這種戰(zhàn)略具有控制簡(jiǎn)單的優(yōu)點(diǎn)。3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2.2不可撤回方法爬山法不僅適用于爬山問(wèn)題,那些目的為極大值,搜索過(guò)程是不斷接近目的的單值問(wèn)題都可運(yùn)用這一方法。運(yùn)用不可撤回戰(zhàn)略,雖然不能夠?qū)θ魏涡螤羁偰苓x得最優(yōu)的規(guī)那么,但是假設(shè)運(yùn)用了一條不適宜的規(guī)那么之后,不去吊銷它并不排除下一步運(yùn)用一條適宜的規(guī)那么,那么只是解序列有些多余的規(guī)那么而已,求得的解不是最優(yōu)解,但控制較簡(jiǎn)單。此外還該當(dāng)指出,普通很難對(duì)給定問(wèn)題構(gòu)造出任何情況下都能通用的爬山函數(shù),因此不可撤回的方法具有一定的局限性。3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2.3回溯方法在問(wèn)題求解過(guò)程中,有時(shí)會(huì)發(fā)現(xiàn)運(yùn)用一條不適宜的規(guī)那么會(huì)阻擾或拖延到達(dá)目的的過(guò)程。在這種情況下,需求有這樣的控制戰(zhàn)略:先試一試某一條規(guī)那么,假設(shè)以后發(fā)現(xiàn)這條規(guī)那么不適宜,那么允許退回去,另選一條規(guī)那么來(lái)試?；厮莘椒ú槐９芡旰玫乃阉鳂錁?gòu)造,只記住當(dāng)前任務(wù)的一條途徑,回溯就是對(duì)這條途徑進(jìn)展修正。運(yùn)用回溯戰(zhàn)略首要的問(wèn)題要研討在什么情況下應(yīng)該回溯,即要確定回溯條件的問(wèn)題。其次就是如何利用有用知識(shí)進(jìn)展規(guī)那么排序,以減少回溯次數(shù)?；厮輵?yīng)發(fā)生在以下三種情況:(1)新生成的形狀在通向初始形狀的途徑上已出現(xiàn)過(guò);(2)從初始形狀開場(chǎng),運(yùn)用的規(guī)那么數(shù)目到達(dá)所規(guī)定的數(shù)目之后還未找到目的形狀(這一組規(guī)那么的數(shù)目實(shí)踐上就是搜索深度范圍所規(guī)定的);(3)對(duì)當(dāng)前形狀,再?zèng)]有可運(yùn)用的規(guī)那么。3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2.3回溯方法搜索深度的設(shè)置是一個(gè)值得留意的問(wèn)題,設(shè)置太淺,有能夠找不到解;設(shè)置太深,有能夠?qū)е禄厮荽螖?shù)巨增。因此應(yīng)根據(jù)實(shí)踐情況來(lái)規(guī)定搜索范圍,先設(shè)置適中的深度搜索,失敗時(shí)再逐漸加深。回溯過(guò)程是一種可試探的方法,從方式上無(wú)論能否存在對(duì)選擇規(guī)那么有用的知識(shí),都可以采用這種戰(zhàn)略。即假設(shè)沒(méi)有有用的知識(shí)來(lái)引導(dǎo)規(guī)那么選取,那么規(guī)那么可按恣意方式(固定排序或隨機(jī))選取;假設(shè)有好的選擇規(guī)那么的知識(shí)可用,那么用這種知識(shí)來(lái)引導(dǎo)規(guī)那么選取,就會(huì)減少盲目性,降低回溯次數(shù),甚至不回溯就能找到解,總之普通來(lái)說(shuō)有利于提高效率。此外由于引入回溯機(jī)理,可以防止墮入部分極大值的情況,繼續(xù)尋覓其他到達(dá)目的的途徑。3.2產(chǎn)生式系統(tǒng)的搜索(控制)戰(zhàn)略3.2.3回溯方法可用遞歸算法描畫回溯戰(zhàn)略:YX0:選擇一條新途徑搜索;YX1:搜索已超出規(guī)定目的(無(wú)新途徑、超時(shí),超深度等),失敗退出;否那么搜索繼續(xù);YX2:搜索的形狀找不到可用規(guī)那么,回溯到Y(jié)X0;YX3:搜索的形狀依某種原那么(恣意陳列或按啟發(fā)式準(zhǔn)那么)取有用規(guī)那么;YX4:假設(shè)規(guī)那么用完未找到目的,回溯YX0;YX5:取頭條可用規(guī)那么Ri;YX6:刪去頭條規(guī)那么,減少搜索中規(guī)那么集長(zhǎng)度(留意,這不動(dòng)原始規(guī)那么集);YX7:規(guī)那么Ri作用于當(dāng)前形狀,生成新形狀;YX8:假設(shè)找到目的,勝利退出;假設(shè)生成的"新形狀"已出現(xiàn)過(guò),回溯到Y(jié)X0;YX9:記錄新形狀,對(duì)新形狀遞規(guī)調(diào)用YX1～YX7;產(chǎn)生式系統(tǒng)求解問(wèn)題時(shí),假設(shè)控制系統(tǒng)保管一切規(guī)那么運(yùn)用后生成并鏈接起來(lái)的形狀記錄圖,那么稱任務(wù)在這種方式下的控制系統(tǒng)運(yùn)用了圖搜索戰(zhàn)略。實(shí)踐上圖搜索戰(zhàn)略是實(shí)現(xiàn)從一個(gè)隱含圖中,生成一部分確實(shí)含有一個(gè)目的節(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)),開場(chǎng)它只含有初始節(jié)點(diǎn)S。步驟2CLOSED←();建立一個(gè)CLOSED表(今后它用于存儲(chǔ)已擴(kuò)展節(jié)點(diǎn)或?qū)⒁獢U(kuò)展的某個(gè)節(jié)點(diǎn)),它的初始形狀為空表。步驟3LOOP:ifOPEN=()thenreturnFAIL;進(jìn)入循環(huán)。假設(shè)OPEN表已空,闡明沒(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ā)式圖搜索算法分析與改良廣度優(yōu)先搜索法該方法從初始節(jié)點(diǎn)開場(chǎng),序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),OPEN表中已有的節(jié)點(diǎn)后面(實(shí)現(xiàn)先生成的子節(jié)點(diǎn)先擴(kuò)展),然后從OPEN表中提取最前的一個(gè)節(jié)點(diǎn)檢查能否是目的節(jié)點(diǎn),否那么再擴(kuò)展,再反復(fù)上述操作。這種方法以為同一級(jí)各節(jié)點(diǎn)對(duì)問(wèn)題求解的價(jià)值是同等的,因此對(duì)全部節(jié)點(diǎn)沿廣度進(jìn)展橫向掃描,按各節(jié)點(diǎn)生成的先后次序,先生成、先檢查、先擴(kuò)展,沿廣度遍歷一切節(jié)點(diǎn)。這種方法只需問(wèn)題有解,即假設(shè)樹圖上存在目的節(jié)點(diǎn),經(jīng)搜索一定能找到。所以,廣度優(yōu)先搜索法是完備的,是一種推理算法。但是,在問(wèn)題大節(jié)點(diǎn)多,且目的節(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ā)式圖搜索算法分析與改良深度優(yōu)先搜索法該方法從初始節(jié)點(diǎn)開場(chǎng),順序擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),放在OPEN表中已有的節(jié)點(diǎn)前面(實(shí)現(xiàn)后生成的子節(jié)點(diǎn)先擴(kuò)展),然后從OPEN表中提取最前的一個(gè)節(jié)點(diǎn)檢查能否是目的節(jié)點(diǎn),否那么再擴(kuò)展,再反復(fù)上述操作。這種方法每一次擴(kuò)展最晚生成的子節(jié)點(diǎn),沿著最晚生成的子節(jié)點(diǎn)分支,逐級(jí)縱向深化開展。這種方法搜索一旦進(jìn)入某個(gè)分支,就將沿著該分支不斷向下搜索。假設(shè)目的節(jié)點(diǎn)恰好在此分支上,那么可較快地得到解。但是,假設(shè)目的節(jié)點(diǎn)不在此分支上,不回溯就不能夠得到解。所以,深度優(yōu)先搜索是不完備的,只是推理步驟。假設(shè)回溯,不難證明其平均效率與廣度優(yōu)先搜索法一樣。因此,深度優(yōu)先搜索法假設(shè)沒(méi)有啟發(fā)信息,很難有適用價(jià)值。3.3圖搜索算法3.3.2典型的非啟發(fā)式圖搜索算法分析與改良代價(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)開場(chǎng),擴(kuò)展生成下一級(jí)各子節(jié)點(diǎn),這些子節(jié)點(diǎn)中假設(shè)沒(méi)有目的節(jié)點(diǎn)需再擴(kuò)展搜索。把它們放進(jìn)OPEN表中,根據(jù)初始節(jié)點(diǎn)到它們各自所付出的代價(jià)大小進(jìn)展排序,代價(jià)小的節(jié)點(diǎn)放在前面擴(kuò)展,周而復(fù)始反復(fù)上述操作,直至找到目的節(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í)際研討方面還是實(shí)踐運(yùn)用方面都很有前景,例如最短途徑問(wèn)題。進(jìn)一步的研討以為最短途徑問(wèn)題的改良應(yīng)為以下幾點(diǎn):3.3圖搜索算法3.3.2典型的非啟發(fā)式圖搜索算法分析與改良代價(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后,開辟一個(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ò)程中,假設(shè)到達(dá)某一節(jié)點(diǎn)的代價(jià)≥任一初始節(jié)點(diǎn)到目的節(jié)點(diǎn)的途徑代價(jià),這一節(jié)點(diǎn)的途徑刪去。3)搜索過(guò)程中,假好像時(shí)出現(xiàn)了兩條到達(dá)某一節(jié)點(diǎn)的途徑,代價(jià)大的那條途徑即時(shí)刪去。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良搜索過(guò)程中,假設(shè)在確定擴(kuò)展那一個(gè)節(jié)點(diǎn)時(shí)能充分利用與問(wèn)題求解有關(guān)的特性信息,就可以估計(jì)出節(jié)點(diǎn)的重要性,就能使搜索選擇重要性較高的節(jié)點(diǎn),以利于求得最優(yōu)解。象這樣就可用于指點(diǎn)搜索過(guò)程,且與詳細(xì)問(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到目的節(jié)點(diǎn)Sg的最優(yōu)途徑的估計(jì)代價(jià),它表達(dá)了問(wèn)題的啟發(fā)性信息,其方式根據(jù)問(wèn)題的特性確定。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法假設(shè)對(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到目的節(jié)點(diǎn)的最小代價(jià),假設(shè)有多個(gè)目的節(jié)點(diǎn),那么為其中最小的一個(gè)。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法幾個(gè)重要性質(zhì):性質(zhì)1對(duì)于有限圖,A*算法一定會(huì)在有限步內(nèi)終止.證明：對(duì)于有限圖,其節(jié)點(diǎn)個(gè)數(shù)是有限的,A*算法在經(jīng)過(guò)假設(shè)干次循環(huán)后會(huì)出現(xiàn)兩種情況:或者搜索到目的節(jié)點(diǎn)在步驟5終了;或者OPEN表中的節(jié)點(diǎn)被取完在步驟3終了。不管那種情況,A*算法都在有限步內(nèi)終止。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法幾個(gè)重要性質(zhì):性質(zhì)2對(duì)于無(wú)限圖,只需從初始節(jié)點(diǎn)到目的節(jié)點(diǎn)有途徑存在,A*算法也必然終止。證明:分兩步.第一步證明A*算法終了前,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).又由于A*算法是廣度代價(jià)擇優(yōu),所以在它終了之前,OPEN表中一定含有S。x1,x2,…,S*g中的一些節(jié)點(diǎn),設(shè)x'是其中最前面的一個(gè),那么它必然滿足f(x')≤f*(S0)至此,第一步證明終了;3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法幾個(gè)重要性質(zhì):性質(zhì)2對(duì)于無(wú)限圖,只需從初始節(jié)點(diǎn)到目的節(jié)點(diǎn)有途徑存在,A*算法也必然終止。第二步證明：用反證法,假設(shè)A*算法不終止,并設(shè)e是圖中各條邊的最小代價(jià),d*(xn)是從S。到節(jié)點(diǎn)xn的最短途徑長(zhǎng)度,那么顯然有g(shù)*(xn)≥d*(xn)×e又由于g(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ū)山庑螤羁臻g來(lái)說(shuō),f*(s0)一定是有限值。所以,只需從初始節(jié)點(diǎn)到目的節(jié)點(diǎn)有途徑存在,即使對(duì)于無(wú)限圖,A*算法也一定會(huì)終止。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法幾個(gè)重要性質(zhì):性質(zhì)3A*算法一定終止在最正確途徑上證明:假設(shè)A*算法不是在最優(yōu)途徑上終止,而是在某個(gè)目的節(jié)點(diǎn)t處終止,那么f(t)=g(t)>f*(s0)。但是由性質(zhì)2證明可知,在A*算法終了之前,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ā)式搜索算法分析與改良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ì)于一切的非目的節(jié)點(diǎn)x均有h1(x)<h2(x)。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法幾個(gè)重要性質(zhì):性質(zhì)4A*算法是最優(yōu)的證明〔接前頁(yè)):此情況下證明A1*擴(kuò)展的節(jié)點(diǎn)數(shù)不會(huì)比A*2擴(kuò)展的節(jié)點(diǎn)數(shù)少,用歸納法:設(shè)K表示搜索樹的深度當(dāng)K=0時(shí),結(jié)論顯然成立;設(shè)當(dāng)搜索樹的深度為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ā)式搜索算法分析與改良A*算法幾個(gè)重要性質(zhì):性質(zhì)4A*算法是最優(yōu)的證明〔接前頁(yè)):由假設(shè)可知,A*2擴(kuò)展的前K-1代節(jié)點(diǎn)A*1也都擴(kuò)展了,因此A1*搜索樹中有一條從初始節(jié)點(diǎn)S。到xk的途徑,其費(fèi)用不會(huì)比A*2搜索樹從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ùn)用關(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ā)式搜索算法分析與改良A*算法的改良改良1OPEN表中自始至終的排序,采用3.3.2.3節(jié)中引見的映射方法。改良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à)。假設(shè)對(duì)啟發(fā)函數(shù)h(x)單調(diào)限制,可減少檢查和調(diào)整的任務(wù)量,從而提高搜索效率。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法的改良所謂單調(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是目的節(jié)點(diǎn);c(xi,xj)是節(jié)點(diǎn)xi到其子節(jié)點(diǎn)xj的邊代價(jià)。假設(shè)把上式改寫h(xi)≤h(xj)+c(xi,xj),可看出節(jié)點(diǎn)xi到目的節(jié)點(diǎn)的估價(jià)不會(huì)超越xi到其子節(jié)點(diǎn)xj邊代價(jià)加從xj到目的節(jié)點(diǎn)的估價(jià)。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法的改良當(dāng)A*算法的啟發(fā)函數(shù)h(x)滿足單調(diào)限制時(shí),可得出以下兩個(gè)結(jié)論:(1)假設(shè)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ā)式搜索算法分析與改良A*算法的改良改良3引入感興趣集的算法:這一改良的思緒是這樣的,問(wèn)題求解時(shí),人們往往知道最正確途徑上有關(guān)節(jié)點(diǎn)的某些啟發(fā)信息。例如,在求城市A到城市B的最正確途徑時(shí),人們往往憑本人的閱歷斷定所要求的最正確途徑必經(jīng)城市C和城市H,這里我們稱{C,H}是感興趣集合。假設(shè)知道感興趣集且啟發(fā)式搜索算法恰當(dāng)?shù)剡\(yùn)用感興趣集,那么一定可以改善算法的搜索效率。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良A*算法的改良算法的改良運(yùn)用OPEN1和OPEN2,CLOSED1和CLOSED2四個(gè)表,對(duì)任一節(jié)點(diǎn)x,假設(shè)從s到節(jié)點(diǎn)x的當(dāng)出途徑中不含感興趣集中的節(jié)點(diǎn),那么x放入OPEN1中;否那么放入OPEN2中。選擇節(jié)點(diǎn)擴(kuò)展時(shí),首先擴(kuò)展OPEN2中的節(jié)點(diǎn),由于OPEN2中含有感興趣集中的節(jié)點(diǎn),能夠比OPEN1中的節(jié)點(diǎn)更有希望在最正確途徑上,而且所擴(kuò)展的節(jié)點(diǎn)數(shù)目總不會(huì)多于原算法。3.3圖搜索算法3.3.3典型的啟發(fā)式搜索算法分析與改良討論(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ā)式搜索算法分析與改良討論(2)根據(jù)啟發(fā)信息,可將復(fù)雜的、規(guī)模大的問(wèn)題分解為簡(jiǎn)單的規(guī)模小的假設(shè)干子問(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)換為假設(shè)干等價(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)題,它們并不是獨(dú)一的途徑,假設(shè)利用它們直接求解往往還比較困難。AND/OR圖算法是用于表示問(wèn)題及其求解過(guò)程的又一種方式化方法。定義1AND圖及AND圖算法把一個(gè)復(fù)雜的問(wèn)題分解成假設(shè)干個(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à)變換,使之成為假設(shè)干個(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*搜索算法,作一些改良討論;討論類比搜索方法.為此,我們首先給出AND/OR圖的普通搜索過(guò)程:(1)把原始問(wèn)題作為初始節(jié)點(diǎn),并作為當(dāng)前節(jié)點(diǎn)。(2)運(yùn)用分解或等價(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ò)程都是至上而下的。假設(shè)確定某個(gè)節(jié)點(diǎn)是可解節(jié)點(diǎn),那么不可解的后裔節(jié)點(diǎn)不再有用,可從搜索圖中刪去;同樣,假設(shè)確定某個(gè)節(jié)點(diǎn)是不可解節(jié)點(diǎn),那么全部后裔節(jié)點(diǎn)都不在有用,也可從搜索圖中刪去。3.3圖搜索算法3.3.5AO*搜索算法分析與改良定義定義5設(shè)AND/OR圖G,那么從節(jié)點(diǎn)n到一立刻可解的葉節(jié)點(diǎn)集合N的一解圖G'定義為:(1)G'是G的子圖;(2)假設(shè)節(jié)點(diǎn)n是集合N中的元素,那么G'是由單一節(jié)點(diǎn)n組成的;(3)假設(shè)節(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*搜索算法分析與改良定義定義6從AND/OR圖恣意節(jié)點(diǎn)n到一立刻可解的葉節(jié)點(diǎn)集合N的解圖耗散值k(n,N)可遞歸地定義為：(1)假設(shè)節(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*搜索算法分析與改良定義定義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假設(shè)啟發(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ùn)用k-銜接符于節(jié)點(diǎn)n所得的全部后繼節(jié)點(diǎn)。3.3圖搜索算法3.3.5AO*搜索算法分析與改良AO*算法A1:建立一個(gè)搜索圖G,G:=s,計(jì)算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED);開場(chǎng)時(shí)圖G只包含s,耗散值估計(jì)為h(s),假設(shè)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ì)算耗散值,假設(shè)有終節(jié)點(diǎn)那么加能解標(biāo)志.A7:S:={n};建立含n的單一節(jié)點(diǎn)集合S.A8:UntilS為空,do3.3圖搜索算法3.3.5AO*搜索算法分析與改良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);假設(shè)該銜接符的一切子節(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*搜索算法分析與改良分析與改良算法AO*可以了解為兩個(gè)主要運(yùn)算:A1～A6,完成自上而下的圖生成,經(jīng)過(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開場(chǎng),其修正耗散值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í),假設(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*搜索算法分析與改良分析與改良(3)A5中怎樣選G'中的一個(gè)非終節(jié)點(diǎn)擴(kuò)展值得研討:普通可以選一個(gè)最能夠?qū)е略摬糠纸鈭D耗散值發(fā)生較大變化的那個(gè)節(jié)點(diǎn)先擴(kuò)展,由于選這個(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算法中,所運(yùn)用的啟發(fā)信息大多是人們根據(jù)詳細(xì)領(lǐng)域問(wèn)題靠閱歷總結(jié)得來(lái)的,啟發(fā)信息獲取非常困難,且準(zhǔn)確性和可靠性也難以保證。此外,搜索算法普通執(zhí)行一次性搜索,將同一問(wèn)題的多次搜索視為彼此獨(dú)立、毫無(wú)相關(guān)的過(guò)程。每次求解問(wèn)題時(shí),面臨的都是全新的搜索圖,即使求解的是一樣問(wèn)題,算法依然從零開場(chǎng),這顯然與人類求解問(wèn)題的方式不符。人類求解問(wèn)題的一個(gè)重要特點(diǎn),就是經(jīng)常利用以前求解一樣或類似問(wèn)題的閱歷來(lái)指點(diǎn)新問(wèn)題的求解。這實(shí)踐上是一種類比學(xué)習(xí)機(jī)制,假設(shè)將這種機(jī)制引入搜索算法,那么多次搜索被看成相互關(guān)聯(lián)的過(guò)程,前面搜索積累的閱歷將有助于提高后面搜索的效率。即,利用類比獲得與新問(wèn)題類似的過(guò)去問(wèn)題的求解過(guò)程,作為啟發(fā)信息來(lái)指點(diǎn)新問(wèn)題的求解,這樣可以減少搜索范圍,降低問(wèn)題求解的復(fù)雜性。也就是說(shuō),假設(shè)算法設(shè)計(jì)恰當(dāng),可以自動(dòng)獲得啟發(fā)信息。3.3圖搜索算法3.3.6類比搜索方法討論方法討論AO*、A及其它算法在問(wèn)題的求解過(guò)程中利用與該問(wèn)題相關(guān)的啟發(fā)信息來(lái)協(xié)助搜索,啟發(fā)信息通常被用于三種情況:(1)協(xié)助確定擴(kuò)展節(jié)點(diǎn)。(2)在擴(kuò)展節(jié)點(diǎn)的過(guò)程中,協(xié)助決議產(chǎn)生后繼節(jié)點(diǎn)。(3)在擴(kuò)展節(jié)點(diǎn)的過(guò)程中,決議那些節(jié)點(diǎn)可從搜索樹上刪除。值得留意的是,啟發(fā)信息是一種部分信息,只在搜索途徑的每個(gè)節(jié)點(diǎn)上為選擇操作提供參考。3.3圖搜索算法3.3.6類比搜索方法討論方法討論類比搜索方法把類比推理技術(shù)與形狀空間的啟發(fā)式搜索相結(jié)合,實(shí)踐上是對(duì)人類求解問(wèn)題、積累閱歷和添加求解問(wèn)題才干的一種模擬。要實(shí)現(xiàn)它,需求處理如下一些主要問(wèn)題:(1)如何積累問(wèn)題求解的閱歷,即在一個(gè)問(wèn)題的求解過(guò)程中,需求記錄那些有用信息。(2)如何定義和判別兩個(gè)問(wèn)題的求解情況是類似的,如何高效的進(jìn)展檢索。(3)如何有效地運(yùn)用類比結(jié)論,即類似的過(guò)去問(wèn)題的求解閱歷,作為特殊的啟發(fā)信息指點(diǎn)新問(wèn)題的求解。3.3圖搜索算法3.3.6類比搜索方法討論方法討論基于上述幾點(diǎn),需求建立一個(gè)類比的啟發(fā)式搜索求解模型。它主要包括生成求解事例、檢索及指點(diǎn)求解三個(gè)推理過(guò)程。類比搜索方法在每次求解一個(gè)新問(wèn)題時(shí),不是直接去搜索給定的形狀空間,而是首先在求解事例庫(kù)中檢索,查找與該問(wèn)題類似的過(guò)去問(wèn)題的求解事例。假設(shè)存在類似問(wèn)題的求解事例,那么以此作為啟發(fā)信息,指點(diǎn)該問(wèn)題的求解。詳細(xì)地說(shuō),就是在新問(wèn)題的求解過(guò)程中,對(duì)過(guò)去問(wèn)題的求解事例中記錄的勝利搜索途徑上每個(gè)操作的根據(jù)條件重新測(cè)試.假設(shè)根據(jù)條件仍滿足,那么算法根隨勝利的求解途徑。否那么,對(duì)原求解過(guò)程進(jìn)展改寫,構(gòu)成的新問(wèn)題求解過(guò)程作為一個(gè)新事例存儲(chǔ)在事例庫(kù)中,以便指點(diǎn)未來(lái)類似問(wèn)題的求解。過(guò)去問(wèn)題與新問(wèn)題的類似性越高,求解過(guò)程需求的搜索就越少。在最理想的情況下,甚至不需求搜索。當(dāng)沒(méi)有檢索到一個(gè)與新問(wèn)題類似的過(guò)去問(wèn)題的求解事例時(shí),那么運(yùn)用A*或AO*等算法進(jìn)展,并在獲得解時(shí)將求解過(guò)程作為一個(gè)求解事例存儲(chǔ)在事例庫(kù)中。3.3圖搜索算法3.3.6類比搜索方法討論方法討論系統(tǒng)最初運(yùn)用時(shí),由于事例庫(kù)中短少求解事例,只需運(yùn)用A*或AO*等算法。隨著求解次數(shù)的添加,求解事例將不斷積累,類比的資料增多(啟發(fā)信息增多),從而使求解問(wèn)題的效率不斷提高。由此可知,類比搜索方法的特點(diǎn)是:類比啟發(fā)信息不僅包含了部分信息,而且提供了指點(diǎn)求解的搜索方向,這樣就可以將一個(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-銜接符,終了條件的數(shù)據(jù)庫(kù)對(duì)應(yīng)于一組終節(jié)點(diǎn)集合,搜索算法的義務(wù)就是找到從初始節(jié)點(diǎn)到一組終節(jié)點(diǎn)集的一個(gè)解圖。AND/OR圖的啟發(fā)式搜索算法AO*是經(jīng)過(guò)評(píng)價(jià)函數(shù)f(n)=h(n)來(lái)引導(dǎo)搜索過(guò)程,適用于分解得到的子問(wèn)題不存在相互作用的情況。假設(shè)S→N集存在解圖,當(dāng)h(n)≤h*(n)且h(n)滿足單調(diào)限制條件時(shí),AO*算法一定能找到最正確解圖,在這種情況下,AO*具有可采用性。3.3圖搜索算法3.3.7討論類比搜索方法實(shí)施的關(guān)鍵技術(shù)在于生成求解事例、類似性度量和檢索、以及指點(diǎn)求解。生成求解事例就是積累問(wè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è)極端都不圓滿,詳細(xì)地作法除了保管問(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討論指點(diǎn)求解是類比搜索方法的控制程序,主要思索靈敏的處置戰(zhàn)略。普通要思索以下幾點(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)絡(luò)就隨之變得復(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òu)成一個(gè)循環(huán)鏈,最終由末尾規(guī)那么的結(jié)果子句推出起始規(guī)那么的前提部分;(2)沖突規(guī)那么:兩個(gè)規(guī)那么的前提條件等價(jià),但一個(gè)或多個(gè)結(jié)果子句有矛盾或者前提子句有矛盾而結(jié)論部分完全等價(jià);也有能夠由多條規(guī)那么鏈構(gòu)成沖突規(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ī)那么的條件部分開場(chǎng)搜索,假設(shè)搜索過(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ī)那么樹,構(gòu)成推理圖。同時(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ī)那么：假設(shè)Ri的結(jié)論部份包含有Rj的條件部份，那么Rj是一個(gè)依賴規(guī)那么，即Rj依賴規(guī)那么Ri，或稱Ri是一個(gè)被依賴規(guī)那么。優(yōu)先規(guī)那么:假設(shè)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〕的最大值后，假設(shè)開辟一個(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ù)：假設(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ù)〕假設(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),這闡明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，記錄了具有這獨(dú)一對(duì)應(yīng)關(guān)系Pi所在規(guī)那么的地址i，并作為最后排序調(diào)整位置的首地址。W〔Pi〕←i為出現(xiàn)一樣關(guān)鍵字提供鏈接地址作預(yù)備。映射時(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)鍵字作預(yù)備。實(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：[映射初始化，開辟鏈指針空間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：假設(shè)D(Pi)=1，作W(Pi)←i和Q(Pi)←i，轉(zhuǎn)B10。B9:假設(shè)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開場(chǎng)，假設(shè)D〔J〕=0轉(zhuǎn)B12;D〔J〕≠0，作遞減陳列。(1)T←Q〔J〕；鏈?zhǔn)字羔標(biāo)蚑。(2)輸出RT。(3)z←z＋1，假設(shè)Z≠D(J)，T←L〔T〕后轉(zhuǎn)(2)；否那么轉(zhuǎn)B12。B12：J←J-1，實(shí)施B11，直至J=0終了。3.4產(chǎn)生式系統(tǒng)的規(guī)那么問(wèn)題3.4.2規(guī)那么排序算法排序算法描畫與分析動(dòng)態(tài)算法規(guī)那么匹配過(guò)程中，假設(shè)系統(tǒng)自學(xué)習(xí)新增一條規(guī)那么RN+1，將立刻置人規(guī)那么集適當(dāng)位置，自動(dòng)啟動(dòng)的算法是：C1：對(duì)i=1，2,...，N，假設(shè)RN+1被Ri依賴，PN+1←PN+1+l〔PN+1初值賦1〕；反之，假設(shè)Ri被RN+1依賴，Pi←Pi+1。C2：假設(shè)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〕，由于B1～B5執(zhí)行步驟共需(N-1)+(N-2)+...+2+1+N=1/2(N2+N)。2〕靜態(tài)算法〔下〕時(shí)間復(fù)雜性為O〔N〕，由于算法的構(gòu)思來(lái)源于映射排序算法中的一部份，其證明可參閱書末文獻(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í)間最小亦闡明，一般情況下，分折的句子越多，其效率越高；但也能夠存在某些情況，所需規(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)效果足以闡明此算法的適用性。3.5運(yùn)用舉例任何一種自然言語(yǔ),總是要遵照一定的語(yǔ)法規(guī)那么的.計(jì)算機(jī)要了解、翻譯自然言語(yǔ),就要對(duì)了解和翻譯的言語(yǔ)建立一套規(guī)那么,也就是語(yǔ)法,并且提供一種適宜計(jì)算機(jī)處置的語(yǔ)法描畫方式。上下文無(wú)關(guān)語(yǔ)法是適宜描畫自然言語(yǔ)的一種體系。作為一個(gè)例子,先來(lái)調(diào)查漢語(yǔ)的一個(gè)很小子集,它的上下文無(wú)關(guān)語(yǔ)法由以下一系列重寫規(guī)那么組成:(1)<一種句子構(gòu)造>→<名詞><動(dòng)詞><數(shù)詞><名詞>(2)<名詞>→電腦│學(xué)院│中國(guó)│地圖│衛(wèi)星│…(3)<動(dòng)詞>→購(gòu)買│繪制│發(fā)射│…(4)<數(shù)詞>→一顆│十臺(tái)│一幅│