产生式系统及其搜索方法课件

產生式系統及其搜索方法

3.1產生式系統

產生式系統使用類似於文法的規則,對符號串作替換運算。它是智能軟體中使用最普遍、最典型的一種結構。為什麼要採用產生式系統作為智能軟體的主要結構呢?這可以有兩點理由:

(1)用產生式系統結構求解問題的過程和人類求解問題時的思維過程很相象,因而可以用它來模擬人類求解問題時的思維過程;(2)可以把產生式系統作為智能軟體中的基本結構單元或基本模式看待,就好像是積木世界中的積木塊一樣,因而研究產生式系統的基本問題就具有一般意義。3.1產生式系統

3.1.1產生式系統的組成部分一個智能軟體用產生式系統設計的基本組成是:一個綜合資料庫;一組產生式規則;一個控制系統。綜合資料庫是產生式系統所使用的主要數據結構,用來表述問題的狀態或有關事實。它包含求解問題的資訊,其中有些部分可以是不變的,有些部分可能只與當前問題的解有關。人們可以根據問題的性質,用適當的方法來構造綜合資料庫的資訊。3.1產生式系統

3.1.1產生式系統的組成部分產生式規則的一般形式為:

條件─→行動或前提─→結論即表示成為:if┄┄then┄┄的形式。其中,左邊確定了該規則可應用的先決條件;右邊描述了應用這條規則所採取的行動或得出的結論。一條產生式規則滿足了應用的先決條件之後,就可對綜合資料庫進行操作,使其發生變化。如綜合資料庫代表當前狀態,則應用規則後就使狀態發生轉換,生成新狀態。3.1產生式系統

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

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

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

3.1.1產生式系統的組成部分

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

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

3.1.1產生式系統的組成部分

建立產生式系統描述的過程,就是所謂問題的表示。對問題表示的好壞,往往對求解過程的效率有很大的影響。一種較好的表示法會簡化狀態空間和規則集表示,此外,高效率的問題求解過程與控制策略有關,合適的控制策略可縮小狀態空間的搜索範圍,提高求解的效率。從以上論述可知,用產生式系統來描述和求解問題,就是在問題空間中搜索一條從初始狀態到達某一個目標狀態的路徑。這完全可以模擬人的求解過程,也就是可以把產生式系統作為求解問題思考過程的一種模擬。3.1產生式系統

3.1.2產生式系統的基本演算法E1:DATA←初始事實庫E2:untilDATA滿足結束條件以前,doE3:beginE4:在規則集中,選某一條可用於DATA的規則E5:DATA←規則應用到DATA得到的結果E6:結束3.1產生式系統

3.1.3產生式系統的類型正向、逆向、雙向產生式系統

用產生式系統求解某一問題時,如果按照規則使用的方式或者說按推理方向來劃分的話,有正向、逆向和雙向產生式系統。正向產生式系統是從初始狀態出發朝著目標狀態這個方向使用規則,即正推的方式工作,稱這些規則為F規則;若選目標狀態作為初始資料庫逆向進行求解,即逆向使用規則,產生子目標狀態,反方向一步一步朝著初始狀態方向求解,整個逆推方式工作,稱逆向產生式系統,逆向應用的規則稱B規則;若以雙向搜索的方式(即正向和逆向同時進行)去求解問題,則稱為雙向產生式系統。3.1產生式系統

3.1.3產生式系統的類型可交換的產生式系統可交換式產生式系統的可交換性指幾條規則的應用可以任意交換次序而不影響求解。一般來說,當一個產生式系統對任何一個資料庫D都具有如下性質時,這樣一個產生式系統是可交換的。

(1)可應用於D的規則集合,使用了其中任意一條規則之後所生成的任何資料庫,這樣一個規則集合還適用;(2)滿足目標條件的某個資料庫D,當應用任何一個可應用於資料庫D的規則之後所生成的任何資料庫,任然滿足目標條件;(3)若對D應用某一規則序列後得到的一個資料庫D'(並能達到解),當改變這些規則次序後,任然可求得解,即求得D'與使用滿足D的可應用規則集合中的規則次序無關。3.1產生式系統

3.1.3產生式系統的類型可交換的產生式系統

例:給定一個整數集合的初始狀態{a,b,c},設目標狀態為具有a,b,c,ab,bc,ca這六個元素組成的集合。可應用的規則集合為

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}

顯然,這個產生式實例具有可交換性。一個產生式系統具有可交換性,求解時只需搜索其中任一條途徑,只要解存在就一定能找到目標,不必探索多條途徑,因此不可撤回的控制方式(下節論述)在這種系統中使用很合適,因解與最初可應用的規則系列的次序無關,系統不必提供特殊選擇規則的機理。3.1產生式系統

3.1.3產生式系統的類型可分解的產生式系統先研究一個重寫問題的產生式系統,初始資料庫為(C,B,Z),產生式規則如下:R1:C→(D,L)R2:C→(B,M)R3:B→(M,M)R4:Z→(B,B,M)

結束條件是生成只包含M組成的資料庫,即(M,…,M)。3.1產生式系統

3.1.3產生式系統的類型可分解的產生式系統用圖搜索方式求解這個問題時,搜索得到的部分狀態空間圖見圖26。圖中只給出兩條達到目標的路徑和一條失敗的路徑。實際搜索時有可能去探索更多的路徑,往往導致效率降低。對於個問題,為了避免搜索多餘的路徑,可以將初始資料庫分解成幾個可以獨立加以處理的分量,分別對它們進行求解。即可以分別對每一個分量資料庫,測試產生式規則可以應用的條件,如此進行下去,直到分量資料庫滿足某種結束條件為止。要注意一般結束條件應是所有分量資料庫都已滿足結束條件。3.1產生式系統

3.1.3產生式系統的類型可分解的產生式系統能夠分解產生式系統的綜合資料庫和結束條件的產生式系統稱為可分解的產生式系統。一個可分解的產生式系統,其基本演算法描述如下:

(1)DATA:=初始資料庫

(2){Di}:=DATA的分解式;每個Di元素都看成單獨的資料庫

(3)Until{Di}的所有元素都滿足結束條件之前,do:(4)begin(5)從{Di}中選一個不滿足結束條件的D*(6)從{Di}中刪去D*(7)在規則集中選擇一條可應用於D*的規則R(8){di}:=R應用於D*的結果

(9)在{Di}上添加di(10)end下圖為分解方式

(C,B,Z)初態

┌──────┼──────┐↓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產生式系統的搜索(控制)策略

在3.1.2節的演算法中,如何選擇一條可應用的規則,作用於當前的綜合資料庫,生成新的狀態以及記住選用的規則序列是構成控制策略的主要內容。對大多數的智能應用問題,所擁有的控制策略知識或資訊並不足以使每次通過演算法E4時,一下子就能選出最合適的一條規則來,因而產生式系統還必須把E4擴大成搜索(推理)演算法,以至於基本演算法的每一迴圈中選一條規則試用,最終找出某一序列能產生一個滿足結束條件的資料庫為止。由此可見,高效率的控制策略需要有關被求解問題的足夠知識,這樣才能在搜索過程減少盲目性,比較快的找到解路徑。

過去三十多年中,人們研究了許多種搜索演算法,歸納起來主要有兩類:一類是非啟發式演算法;另一類是啟發式演算法。非啟發式演算法是按預定的控制策略進行搜索,在其過程中獲得的中間資訊不用來改進控制策略。由於搜索總是按預先規定的路線進行,沒有考慮問題本身的特性,所以不容易選擇到最優的搜索途徑,效率較低,且出現"組合爆炸"的頻率高。啟發式演算法是在搜索中加入了與問題有關的啟發性資訊,用以指導搜索朝著最有希望的方向前進,加速問題的求解過程並找到最優解。

3.2產生式系統的搜索(控制)策略3.2產生式系統的搜索(控制)策略

3.2.1產生式系統控制策略分類可分解的產生式系統控制策略可劃分為兩大類:┌不可撤回方法┌回溯方法

└試探性方法─┤└圖搜索方法3.2產生式系統的搜索(控制)策略

3.2.2不可撤回方法

這種方法相當於沿著單獨一條路搜索下去,利用問題給出的局部知識決定如何選取規則,就是說根據當前可靠的局部知識選一條可應用規則並作用於當前綜合資料庫。接著再根據新狀態繼續選取規則,搜索過程一直進行,不必考慮撤回用過的規則。這是由於在搜索過程中如能有效利用局部知識,即使使用了一條不理想的規則,也不妨礙下一步選得另一條更合適的規則。這樣不撤銷用過的規則,並不影響求到解,只是解序列中可能多了一些不必要的規則。顯然這種策略具有控制簡單的優點。3.2產生式系統的搜索(控制)策略

3.2.2不可撤回方法

爬山法不僅適用於爬山問題,那些目標為極大值,搜索過程是不斷接近目標的單值問題都可應用這一方法。使用不可撤回策略,雖然不可能對任何狀態總能選得最優的規則,但是如果應用了一條不合適的規則之後,不去撤銷它並不排除下一步應用一條合適的規則,那麼只是解序列有些多餘的規則而已,求得的解不是最優解,但控制較簡單。此外還應當指出,一般很難對給定問題構造出任何情況下都能通用的爬山函數,因而不可撤回的方法具有一定的局限性。3.2產生式系統的搜索(控制)策略

3.2.3回溯方法

在問題求解過程中,有時會發現應用一條不合適的規則會阻擾或拖延達到目標的過程。在這種情況下,需要有這樣的控制策略:先試一試某一條規則,如果以後發現這條規則不合適,則允許退回去,另選一條規則來試。回溯方法不保留完整的搜索樹結構,只記住當前工作的一條路徑,回溯就是對這條路徑進行修正。使用回溯策略首要的問題要研究在什麼情況下應該回溯,即要確定回溯條件的問題。其次就是如何利用有用知識進行規則排序,以減少回溯次數。回溯應發生在以下三種情況:

(1)新生成的狀態在通向初始狀態的路徑上已出現過;(2)從初始狀態開始,應用的規則數目達到所規定的數目之後還未找到目標狀態(這一組規則的數目實際上就是搜索深度範圍所規定的);(3)對當前狀態,再沒有可應用的規則。3.2產生式系統的搜索(控制)策略

3.2.3回溯方法搜索深度的設置是一個值得注意的問題,設置太淺,有可能找不到解;設置太深,有可能導致回溯次數巨增。因而應根據實際情況來規定搜索範圍,先設置適中的深度搜索,失敗時再逐步加深。回溯過程是一種可試探的方法,從形式上無論是否存在對選擇規則有用的知識,都可以採用這種策略。即如果沒有有用的知識來引導規則選取,那麼規則可按任意方式(固定排序或隨機)選取;如果有好的選擇規則的知識可用,那麼用這種知識來引導規則選取,就會減少盲目性,降低回溯次數,甚至不回溯就能找到解,總之一般來說有利於提高效率。此外由於引入回溯機理,可以避免陷入局部極大值的情況,繼續尋找其他達到目標的路徑。3.2產生式系統的搜索(控制)策略

3.2.3回溯方法可用遞歸演算法描述回溯策略:YX0:選擇一條新路徑搜索;YX1:搜索已超出規定指標(無新路徑、超時,超深度等),失敗退出;否則搜索繼續;YX2:搜索的狀態找不到可用規則,回溯到YX0;YX3:搜索的狀態依某種原則(任意排列或按啟發式準則)取有用規則;YX4:若規則用完未找到目標,回溯YX0;YX5:取頭條可用規則Ri;YX6:刪去頭條規則,減少搜索中規則集長度(注意,這不動原始規則集);YX7:規則Ri作用於當前狀態,生成新狀態;YX8:若找到目標,成功退出;若生成的"新狀態"已出現過,回溯到YX0;YX9:記錄新狀態,對新狀態遞規調用YX1～YX7;

產生式系統求解問題時,如果控制系統保留所有規則應用後生成並鏈接起來的狀態記錄圖,則稱工作在這種方式下的控制系統使用了圖搜索策略。實際上圖搜索策略是實現從一個隱含圖中,生成一部分確實含有一個目標節點的顯式表示的子圖搜索過程。3.3圖搜索演算法3.3圖搜索演算法

3.3.1一般性圖搜索演算法步驟1G←S,OPEN←(S);建立一個搜索圖G,它只含有初始節點S,建立一個OPEN表(今後它用於存儲生成的節點),開始它只含有初始節點S。

步驟2CLOSED←();建立一個CLOSED表(今後它用於存儲已擴展節點或將要擴展的某個節點),它的初始狀態為空表。步驟3LOOP:ifOPEN=()thenreturnFAIL;進入迴圈。如果OPEN表已空,說明沒有節點可擴展,就返回FAIL,即失敗。步驟4n←FIRST(OPEN),CLOSED←(n,CLOSED);從OPEN表中取出一個節點n,將其放入CLOSED表中。3.3圖搜索演算法

3.3.2典型的非啟發式圖搜索演算法分析與改進廣度優先搜索法

該方法從初始節點開始,序擴展生成下一級各子節點,OPEN表中已有的節點後面(實現先生成的子節點先擴展),然後從OPEN表中提取最前的一個節點檢查是否是目標節點,否則再擴展,再重複上述操作。這種方法認為同一級各節點對問題求解的價值是同等的,因而對全部節點沿廣度進行橫向掃描,按各節點生成的先後次序,先生成、先檢查、先擴展,沿廣度遍曆所有節點。這種方法只要問題有解,即若樹圖上存在目標節點,經搜索一定能找到。所以,廣度優先搜索法是完備的,是一種推理演算法。但是,在問題大節點多,且目標節點距離初始節點較遠時將會產生許多無用節點,搜索效率低,還可能產生組合爆炸。因此,這種方法較適宜問題不大的環境中3.3圖搜索演算法

3.3.2典型的非啟發式圖搜索演算法分析與改進深度優先搜索法

該方法從初始節點開始,順序擴展生成下一級各子節點,放在OPEN表中已有的節點前面(實現後生成的子節點先擴展),然後從OPEN表中提取最前的一個節點檢查是否是目標節點,否則再擴展,再重複上述操作。這種方法每一次擴展最晚生成的子節點,沿著最晚生成的子節點分支,逐級縱向深入發展。這種方法搜索一旦進入某個分支,就將沿著該分支一直向下搜索。如果目標節點恰好在此分支上,則可較快地得到解。但是,如果目標節點不在此分支上,不回溯就不可能得到解。所以,深度優先搜索是不完備的,只是推理步驟。如果回溯,不難證明其平均效率與廣度優先搜索法相同。因此,深度優先搜索法如果沒有啟發資訊,很難有實用價值。3.3圖搜索演算法

3.3.2典型的非啟發式圖搜索演算法分析與改進代價驅動搜索法

該方法考慮了從一個節點經過一條支路,轉移到另一個節點時所需要支付的代價,如費用、時間等。該方法從初始節點開始,擴展生成下一級各子節點,這些子節點中若沒有目標節點需再擴展搜索。把它們放進OPEN表中,依據初始節點到它們各自所付出的代價大小進行排序,代價小的節點放在前面擴展,周而復始重複上述操作,直至找到目標節點為止。這種方法根據各條支路所需支付的代價有差別,所以具有同樣路徑長度(所經過的支路數)的搜索過程,其搜索代價(所支付的總代價)可能不同,優選最小代價的搜索路徑,進行推理求解問題。代價驅動搜索無論在理論研究方面還是實際應用方面都很有前景,例如最短路徑問題。進一步的研究認為最短路徑問題的改進應為以下幾點:3.3圖搜索演算法

3.3.2典型的非啟發式圖搜索演算法分析與改進代價驅動搜索法1)OPEN表的節點排序問題,特別是在問題節點多達成千上萬時尤為重要.這一排序應採用映射排序，它是一個基於地址計算的排序,在預置路徑最大代價dmax後,開闢一個數組P(dmax),就可把節點送入其值與P數組下標相等的對應元素中,顯然di=50它對應P(50);dj=500,對應P(500)。相同代價值的節點落在同一數組元素中,用計數方式可知有幾個。由於數組元素是有序的,500>50,數組元素的下標自然把節點一次定好了位置,排序即完成。這一排序的時間複雜性為O(N),對於OPEN表面臨的無數次排序操作,極大的提高了效率.2)搜索過程中,如果到達某一節點的代價≥任一初始節點到目標節點的路徑代價,這一節點的路徑刪去。3)搜索過程中,如果同時出現了兩條到達某一節點的路徑,代價大的那條路徑即時刪去。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

搜索過程中,如果在確定擴展那一個節點時能充分利用與問題求解有關的特性資訊,就可以估計出節點的重要性,就能使搜索選擇重要性較高的節點,以利於求得最優解。象這樣就可用於指導搜索過程,且與具體問題求解有關的控制性資訊稱為啟發性資訊。啟發性資訊可以用於估價節點重要性,表示為函數形式:f(x)=g(x)+h(x)

其中,g(x)為初始節點S。到節點x已經付出的代價;h(x)是從節點x到目標節點Sg的最優路徑的估計代價,它體現了問題的啟發性資訊,其形式根據問題的特性確定。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法如果對一般性圖搜索演算法作以下限制,則它成為A*演算法:(1)OPEN表中的節點按估價函數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)是從節點x到目標節點的最小代價,若有多個目標節點,則為其中最小的一個。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:

性質1對於有限圖,A*演算法一定會在有限步內終止.

證明：對於有限圖,其節點個數是有限的,A*演算法在經過若干次迴圈後會出現兩種情況:或者搜索到目標節點在步驟5結束;或者OPEN表中的節點被取完在步驟3結束。不管那種情況,A*演算法都在有限步內終止。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:性質2對於無限圖,只要從初始節點到目標節點有路徑存在,A*演算法也必然終止。證明:分兩步.第一步證明A*演算法結束前,OPEN表中存在節點x‘,它是最優路徑上的一個節點,且滿足f(x')≤f*(s).。

設最優路徑是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*演算法是廣度代價擇優,所以在它結束之前,OPEN表中一定含有S。x1,x2,…,S*g中的一些節點,設x'是其中最前面的一個,則它必然滿足f(x')≤f*(S0)

至此,第一步證明結束;3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:性質2對於無限圖,只要從初始節點到目標節點有路徑存在,A*演算法也必然終止。第二步證明：用反證法,假設A*演算法不終止,並設e是圖中各條邊的最小代價,d*(xn)是從S。到節點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)也無限增大。這與第一步證明得出的結論矛盾,因對可解狀態空間來說,f*(s0)一定是有限值。所以,只要從初始節點到目標節點有路徑存在,即使對於無限圖,A*演算法也一定會終止。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:

性質3A*演算法一定終止在最佳路徑上證明:假設A*演算法不是在最優路徑上終止,而是在某個目標節點t處終止,則f(t)=g(t)>f*(s0)。但是由性質2證明可知,在A*演算法結束之前,OPEN表中存在著節點x‘,它應該在最優路徑上,且滿足f(x')≤f*(s0)此時,A*演算法一定會選擇x'來擴展而不會選擇t,這就與假設矛盾,所以,A*演算法一定會終止在最優路徑上。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:性質4A*演算法是最優的證明:A*演算法的搜索效率很大程度上取決h(x),在滿足h(x)≤h*(x)的前提下,h(x)的值越大越好。h(x)值越大,表明它攜帶的啟發資訊越多,搜索時擴展的節點數越少,搜索的效率越高。設f1(x)與f2(x)是對同一問題的兩個估價函數

f1(x)=g1(x)+h1(x)f2(x)=g2(x)+h2(x)A1*和A2*分別是以f1(x)及f2(x)為估價函數的A*演算法,且對於所有的非目標節點x均有h1(x)<h2(x)。3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:性質4A*演算法是最優的證明（接前頁):

此情況下證明A1*擴展的節點數不會比A*2擴展的節點數少,用歸納法:設K表示搜索樹的深度當K=0時,結論顯然成立;設當搜索樹的深度為K-1時結論成立,即A*2擴展了的節點,A*1也擴展了;現僅證明A*2擴展的第K代的任一節點xk也被A*1擴展:3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

A*演算法幾個重要性質:性質4A*演算法是最優的證明（接前頁):由假設可知,A*2擴展的前K-1代節點A*1也都擴展了,因此A1*搜索樹中有一條從初始節點S。到xk的路徑,其費用不會比A*2搜索樹從S。到xk的費用更大。即g1(xk)≤g2(xk)假設A*1不擴展節點xk,這表示A*1能找到另一個具有更小估價值的節點進行擴展並找到最優解,此時有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典型的啟發式搜索演算法分析與改進

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

A*演算法的改進所謂單調限制h(x)應滿足兩個條件:(1)h(Sg)=0(2)設xj是節點xi的任一子節點,則有h(xi)-h(xj)≤c(xi,xj)

其中,Sg是目標節點;c(xi,xj)是節點xi到其子節點xj的邊代價。若把上式改寫h(xi)≤h(xj)+c(xi,xj),可看出節點xi到目標節點的估價不會超過xi到其子節點xj邊代價加從xj到目標節點的估價。3.3圖搜索演算法3.3.3典型的啟發式搜索演算法分析與改進

A*演算法的改進

當A*演算法的啟發函數h(x)滿足單調限制時,可得出以下兩個結論:(1)若A*演算法選擇節點xn進行擴展,則g(xn)=g*(xn)(2)由A*演算法所擴展的節點序列其f值是非遞減的。這兩個結論都是在h(x)滿足單調限制時才成立.對於第2個結論,當h(x)不滿足單調限制時,有可能某個要擴展的節點比以前擴展的節點具有較小的f值.3.3圖搜索演算法3.3.3典型的啟發式搜索演算法分析與改進

A*演算法的改進改進3引入感興趣集的演算法:這一改進的思路是這樣的,問題求解時,人們往往知道最佳路徑上有關節點的某些啟發資訊。例如,在求城市A到城市B的最佳路徑時,人們往往憑自己的經驗斷定所要求的最佳路徑必經城市C和城市H,這裏我們稱{C,H}是感興趣集合。若知道感興趣集且啟發式搜索演算法恰當地應用感興趣集,則肯定可以改善演算法的搜索效率。3.3圖搜索演算法3.3.3典型的啟發式搜索演算法分析與改進

A*演算法的改進演算法的改進使用OPEN1和OPEN2,CLOSED1和CLOSED2四個表,對任一節點x,若從s到節點x的當前路徑中不含感興趣集中的節點,則x放入OPEN1中;否則放入OPEN2中。選擇節點擴展時,首先擴展OPEN2中的節點,因為OPEN2中含有感興趣集中的節點,可能比OPEN1中的節點更有希望在最佳路徑上,而且所擴展的節點數目總不會多於原演算法。

3.3圖搜索演算法

3.3.3典型的啟發式搜索演算法分析與改進

討論(1)

啟發式搜索演算法在大問題中一般優於非啟發式搜索演算法,因此,有效地分析利用啟發資訊尤為重要。含有啟發資訊的評價函數可寫成下列形式:f(x)=v·g(x)+w·h(x)

其中,v、w為權係數且≥0.當w↑,強調啟發資訊,搜索過程沿最有希望的方向進行,效率肯定高,但降低了完備性;當v↑,強調歷史資訊,搜索過程沿橫向掃描,有利於完備性,但降低了搜索效率。

3.3圖搜索演算法3.3.3典型的啟發式搜索演算法分析與改進

討論(2)

根據啟發資訊,可將複雜的、規模大的問題分解為簡單的規模小的若干子問題。那麼各子問題的搜索過程A1,A2,…,An是完備的,則搜索過程A也是完備的。

A=A1∩A2∩…∩An根據啟發資訊,可將原始的問題進行同構或同態的等價變換,轉換為若干等價問題。那麼等價問題的搜索過程A1,A2,…,An是完備的,則搜索過程A也是完備的。

A=A1∪A2∪…∪An.

3.3圖搜索演算法3.3.4AND/OR圖搜索演算法上節探討的演算法具有重要的意義。但對於複雜的問題,它們並不是唯一的途徑,若利用它們直接求解往往還比較困難。AND/OR圖演算法是用於表示問題及其求解過程的又一種形式化方法。定義1AND圖及AND圖演算法把一個複雜的問題分解成若干個較為簡單的子問題,每個子問題又可繼續分解為更為簡單的子問題,重複此過程,直到不需要再分解或者不能再分解為止。這個分解圖是與圖,根據這個圖對每個子問題分別求解,然後把這些解合併起來得到原問題解的過程是AND圖演算法。3.3圖搜索演算法3.3.4AND/OR圖搜索演算法定義2OR圖及OR圖演算法把一個複雜問題利用同構或同態的等價變換,使之成為若干個較容易求解的新問題。這個變換圖是OR圖,根據這個圖對新問題求解,當且僅當新問題有一個可解,就得到原問題的解的解過程是AO圖演算法。定義3可解節點在AND/OR圖中,滿足下列條件之一者為可解節點:(1)它是一個終止節點.(2)它是一個OR節點,且子節點中至少有一個是可解節點.(3)它是一個AND節點,且其子節點全部是可解節點。3.3圖搜索演算法3.3.4AND/OR圖搜索演算法定義4不可解節點定義3中三個條件全部不滿足的節點稱為不可解節點。下麵分析AND/OR圖AO*搜索演算法,作一些改進探討;探討類比搜索方法.為此,我們首先給出AND/OR圖的一般搜索過程:(1)把原始問題作為初始節點,並作為當前節點。

(2)應用分解或等價變換算符對當前節點進行擴展。

(3)為每個子節點設置指向父節點的指針。

(4)選擇合適的子節點作為當前節點,反復執行(2)和(3),直至找到可解節點或不可解節點為止。下班可解或不可解的搜索過程都是至上而下的。如果確定某個節點是可解節點,則不可解的後裔節點不再有用,可從搜索圖中刪去;同樣,如果確定某個節點是不可解節點,則全部後裔節點都不在有用,也可從搜索圖中刪去。3.3圖搜索演算法3.3.5AO*搜索演算法分析與改進定義定義5設AND/OR圖G,則從節點n到一立即可解的葉節點集合N的一解圖G'定義為:(1)G'是G的子圖;(2)若節點n是集合N中的元素,則G'是由單一節點n組成的;(3)若節點n有一個指向節點{n1,n2,…,nk}的k-連接符,使得從每個後繼節點ni到集合N有一個解圖(i=1,2,…,k),則G'由節點n、k-連接符、節點{n1,n2,…,nk}以及從{n1,n2,…,nk}中的每個節點到集合N的解圖組成。

(4)否則,從節點n到集合N不存在解圖。3.3圖搜索演算法3.3.5AO*搜索演算法分析與改進定義定義6從AND/OR圖任意節點n到一立即可解的葉節點集合N的解圖耗散值k(n,N)可遞歸地定義為：(1)若節點n是集合N中的元素,則k(n,N)=0;(2)否則,節點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圖求解中,從起始節點到一可解葉節點集合具有最小耗散值的一個解圖稱為最佳解圖。令函數h*(n)表示從AND/OR圖中的節點n到一可解的葉節點集合的最佳解圖的耗散值;啟發式估價函數h(n)是h*(n)的估計。定義8若啟發式估價函數h滿足單調限制,即對AND/OR圖中任意節點n及其適用於n的任一k-連接符,有

h(n)≤Ck+h(n1)+…+h(nk)其中,Ck為k-連接符的耗散值,n1,n2,…,nk是應用k-連接符於節點n所得的全部後繼節點。3.3圖搜索演算法3.3.5AO*搜索演算法分析與改進AO*演算法A1:建立一個搜索圖G,G:=s,計算q(s)=h(s),IFGOAL(s)THENM(s,SOLVED);開始時圖G只包含s,耗散值估計為h(s),若s是終節點,則標記能解.A2:Untils已標記上SOLVED,do:A3:beginA4:G':=FIND(G);根據連接符標記(指針)找出一個待擴展的局部解圖G'.A5:n:=G'中的任一非終節點;選一個非終節點作為當前節點.A6:EXPAND(n),生成子節點集{nj},G:=ADD({nj},G),計算q(nj)=h(nj),其中nj∈G,IFGOAL(nj)THENM(nj,SOLVED);把n的子節點添加到G中,對G中未出現的子節點計算耗散值,若有終節點則加能解標記.A7:S:={n};建立含n的單一節點集合S.A8:UntilS為空,do

3.3圖搜索演算法3.3.5AO*搜索演算法分析與改進AO*演算法(接前頁)A9:beginA10:REMOVE(m,S),mc∈{S};這個m的子節點mc應不在S中.A11:(1)修改m的耗散值q(m):

對m指向節點集{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);若該連接符的所有子節點都是能解的,則m也標上能解.A12:IFM(m,SOLVED)∨(q(m)≠q0(m))THENADD(ma,S);m能解或修正的耗散值與原先估算q0不同,則把m的所有先輩節點ma添加到S中.A13:endA14:end3.3圖搜索演算法

3.3.5AO*搜索演算法分析與改進分析與改進演算法AO*可以理解為兩個主要運算:A1～A6,完成自上而下的圖生成,通過有標記的連接符,尋找最好的局部解圖,然後對其中一個非終節點進行擴展,並對其後繼節點賦給耗散值;A7～A12,完成自下而上的耗散值修正、連接符標記和節點的能解標記。

(1)耗散值的修正從剛被擴展的節點n開始,其修正耗散值q(n)取估計h*(n)的所有值中最小的一個,然後根據耗散值遞歸計算公式逐級向上修正先輩節點的耗散值,只有下層節點耗散值修正後,才可能影響上一層節點的耗散值,因此必須自底向上一直修正到初始節點。

(2)在A6中擴展節點n時,若不存在後繼節點(即限入死胡同),則可在A11中對m(即n)賦一個高的q值,這個高的q值會依次傳遞到s,使得含有節點n的子圖具有高的q(s),從而排除了被當作後選局部解圖的可能性。3.3圖搜索演算法3.3.5AO*搜索演算法分析與改進分析與改進(3)A5中怎樣選G'中的一個非終節點擴展值得研究:一般可以選一個最可能導致該局部解圖耗散值發生較大變化的那個節點先擴展,因為選這個節點先擴展,會促使及時修改局部解圖的標記。(4)與3.3.3.2節A演算法類似,應讓h(n)滿足單調限制條件,這樣,當h(n)≤h*(n)則AO*一定能找到最佳解圖。當h(n)≡0時,AO*成寬度優先演算法。(5)AO*中評價函數只考慮h(n)分量,計算g沒有必要也不可能。其次由於k-連接符連接的有關子節點,對於父節點能解與否以及耗散值都有影響,因而不能象A演算法那樣優先擴展其中具有最小耗散值的節點。3.3圖搜索演算法3.3.6類比搜索方法探討構思在AO*和A演算法中,所使用的啟發資訊大多是人們依據具體領域問題靠經驗總結得來的,啟發資訊獲取十分困難,且精確性和可靠性也難以保證。此外,搜索演算法一般執行一次性搜索,將同一問題的多次搜索視為彼此獨立、毫無相關的過程。每次求解問題時,面臨的都是全新的搜索圖,即使求解的是相同問題,演算法仍然從零開始,這顯然與人類求解問題的方式不符。人類求解問題的一個重要特點,就是常常利用以前求解相同或相似問題的經驗來指導新問題的求解。這實際上是一種類比學習機制,如果將這種機制引入搜索演算法,則多次搜索被看成相互關聯的過程,前面搜索積累的經驗將有助於提高後面搜索的效率。即,利用類比獲得與新問題相似的過去問題的求解過程,作為啟發資訊來指導新問題的求解,這樣可以縮小搜索範圍,降低問題求解的複雜性。也就是說,如果演算法設計恰當,可以自動獲得啟發資訊。3.3圖搜索演算法3.3.6類比搜索方法探討方法探討

AO*、A及其它演算法在問題的求解過程中利用與該問題相關的啟發資訊來幫助搜索,啟發資訊通常被用於三種情況:(1)幫助確定擴展節點。

(2)在擴展節點的過程中,幫助決定產生後繼節點。

(3)在擴展節點的過程中,決定那些節點可從搜索樹上刪除。值得注意的是,啟發資訊是一種局部資訊,只在搜索路徑的每個節點上為選擇操作提供參考。3.3圖搜索演算法3.3.6類比搜索方法探討方法探討類比搜索方法把類比推理技術與狀態空間的啟發式搜索相結合,實際上是對人類求解問題、積累經驗和增加求解問題能力的一種模擬。要實現它,需要解決如下一些主要問題:(1)如何積累問題求解的經驗,即在一個問題的求解過程中,需要記錄那些有用資訊。

(2)如何定義和判斷兩個問題的求解情況是相似的,如何高效的進行檢索。

(3)如何有效地使用類比結論,即相似的過去問題的求解經驗,作為特殊的啟發資訊指導新問題的求解。3.3圖搜索演算法3.3.6類比搜索方法探討方法探討

基於上述幾點,需要建立一個類比的啟發式搜索求解模型。它主要包括生成求解事例、檢索及指導求解三個推理過程。類比搜索方法在每次求解一個新問題時,不是直接去搜索給定的狀態空間,而是首先在求解事例庫中檢索,查找與該問題相似的過去問題的求解事例。若存在相似問題的求解事例,則以此作為啟發資訊,指導該問題的求解。具體地說,就是在新問題的求解過程中,對過去問題的求解事例中記錄的成功搜索路徑上每個操作的依據條件重新測試.如果依據條件仍滿足,則演算法根隨成功的求解路徑。否則,對原求解過程進行改寫,形成的新問題求解過程作為一個新事例存儲在事例庫中,以便指導將來相似問題的求解。過去問題與新問題的相似性越高,求解過程需要的搜索就越少。在最理想的情況下,甚至不需要搜索。當沒有檢索到一個與新問題相似的過去問題的求解事例時,則使用A*或AO*等演算法進行,並在獲得解時將求解過程作為一個求解事例存儲在事例庫中。3.3圖搜索演算法3.3.6類比搜索方法探討方法探討系統最初使用時,由於事例庫中缺少求解事例,只有使用A*或AO*等演算法。隨著求解次數的增加,求解事例將不斷積累,類比的資料增多(啟發資訊增多),從而使求解問題的效率不斷提高。由此可知,類比搜索方法的特點是:類比啟發資訊不僅包含了局部資訊,而且提供了指導求解的搜索方向,這樣就可以將一個龐大空間的搜索壓縮為對一個或數個很小空間的搜索,極大地提高了求解效率。3.3圖搜索演算法3.3.7討論用AND/OR圖演算法求解問題時,求解過程就是對一個隱含的AND/OR圖進行搜索。初始資料庫對應於AND/OR圖的根節點,規則對應於k-連接符,結束條件的資料庫對應於一組終節點集合,搜索演算法的任務就是找到從初始節點到一組終節點集的一個解圖。

AND/OR圖的啟發式搜索演算法AO*是通過評價函數f(n)=h(n)來引導搜索過程,適用於分解得到的子問題不存在相互作用的情況。若S→N集存在解圖,當h(n)≤h*(n)且h(n)滿足單調限制條件時,AO*演算法一定能找到最佳解圖,在這種情況下,AO*具有可採納性。3.3圖搜索演算法3.3.7討論

類比搜索方法實施的關鍵技術在於生成求解事例、相似性度量和檢索、以及指導求解。生成求解事例就是積累問題的求解經驗,其生成過程主要解決的問題是對於一個求解事例需要記錄和保存問題求解過程中的那些特徵資訊,以及如何進行表示、抽取和存儲這些資訊。求解一個複雜問題時,經常面臨龐大的搜索。大量被搜索的節點中,有成功的、也有失敗的。為了給相似問題的求解提供有用資訊,就要確定保存搜索過程中的哪些有用特徵資訊。顯然,走兩個極端最簡單:第一是記下整個搜索過程;第二是只記問題的最終解。這兩個極端都不圓滿,具體地作法除了保留問題的最終解外,還應該記錄有關選擇這些操作的情境和依據條件。這是一個很有意義的研究課題。相似性的度量也是類比搜索方法的一個關鍵問題。相似程度越高,度量方法恰當,相似問題的檢索俞易獲得。關於這方面,目前還是主要根據新、老問題的特徵和關係來確定它們之間的相似性。此外,還可設置相似度閥值，檢索採用直接映射式方法。3.3圖搜索演算法3.3.7討論指導求解是類比搜索方法的控制程式,主要考慮靈活的處理策略。一般要考慮以下幾點:(1)當檢索沒有類比啟發資訊時,程式能轉向常規搜索方法。

(2)當檢索到一個與新問題完全相似的過去問題的求解事例時,程式能直接轉換解。

(3)當檢索到一個與新問題部分相似的過去問題的求解事例時,程式能提取相似部分解過程,還能組織部分搜索、銜接新的解過程。此外,應有裁剪過去問題多餘解過程的功能。3.4產生式系統的規則問題3.4.1規則不一致原因及解決方法

規則集中存在的不一致是影響系統性能的重要因素之一。系統建立初期,由於規則集較小,內容也比較簡單,設計人員能對每一條規則的條件和結論部分反復推敲和精心構造,這類問題容易防止。但隨著時間的推移,新的規則不斷加入,規則集合越來越大,內容也越來越豐富,這時規則間的相互影響和相互聯繫就隨之變得複雜。在此情況下,規則的不一致就將自然產生,當然,對它的認識和解決也就顯得很重要。3.4產生式系統的規則問題3.4.1規則不一致原因及解決方法主要的不一致規則種類(1)迴圈規則:由數個規則的前提和結論形成一個迴圈鏈,最終由末尾規則的結果子句推出起始規則的前提部分;(2)衝突規則:兩個規則的前提條件等價,但一個或多個結果子句有矛盾或者前提子句有矛盾而結論部分完全等價;也有可能由多條規則鏈形成衝突規則集;(3)冗餘規則:兩個規則的前提條件等價,一個或多個子結果子句也等價;(4)從屬規則:兩個規則有相同的結果,但其中一個包含有多餘的約束條件。3.4產生式系統的規則問題3.4.1規則不一致原因及解決方法不一致規則的檢查解決方法(1)對於迴圈規則,可構造規則集的IF---THEN圖,從起始規則的條件部分開始搜索,如果搜索過程中遇到的THEN部分已在前面出現,就可以中斷搜索,規則集中包含的迴圈規則子集合需設計人員檢查,解決;(2)對於衝突規則,構造IF---IF表,對規則集內有相同的IF規則子句構造規則樹,形成推理圖。同時建立THEN---THEN表用以判斷是否有衝突規則出現。對相同IF部分的規則繼續用它的各自THEN部分作為其他可以匹配的IF前提條件,遞歸地構造,如發現兩個推理圖上分別有節點在THEN---THEN表上是矛盾的,則檢測出衝突規則,人工予以解決。

(3)對冗餘規則和從屬規則的檢查類似於衝突規則鏈的方法.不同之處是前者在推理圖中的遍曆是試圖發現有THEN部分等價的兩條規則。3.4產生式系統的規則問題3.4.2規則排序演算法排序演算法原則依賴規則：如果Ri的結論部份包含有Rj的條件部份，則Rj是一個依賴規則，即Rj

依賴規則Ri，或稱Ri是一個被依賴規則。優先規則:如果Ri被Pi個其他規則所依賴次數pi越大,Ri被援引的可能性越大。靜態規則排列：亦是在原文分析、原文譯文轉換、譯文生成之前，對規則集中已有的規則按優先次序排列。動態規則排列：這相當於自學習能力，即某些句子分析、轉換、生成時，會增加一條或幾條規則。這些規則有可能還與未完成的其他語句有關。因此，在對其他語句和完成速度影晌不大的情況下，同時再排列規則稱之為動態規則排列。3.4產生式系統的規則問題3.4.2規則排序演算法

排序演算法原則映射排列：是一個基於地址計算的排序。例如，求出上述Pi(i=1，2,...，N）的最大值後，若開闢一個數組D（Pmax）,就可把數據送入數據值下標相等的對應元素中。顯然Pi=50，對應D(50);Pj=500,對應D(500)。相同數據落在同一數組元素中，用計數方式可知有幾個。由於數組元素是有序的，500>50，數組元素的下標自然把數據一次定好位置，最後只要按規定的方式調非零元秦，相同元素按計數值次數調動，排序即完成。枚舉計數：如果規則Ri被規則Rj依賴(j=1，2,...,N)，則Pi=pi+1（Pi初值賦1)。顯然，對於N條規則，每一條都將確定與其它規則的依賴關係並計算，這一過程稱之為枚舉計數。3.4產生式系統的規則問題3.4.2規則排序演算法

排序演算法描述與分析靜態演算法（上）

B1:[初始化]，有N條規則，置P1至PN皆為1。

B2:〔對i迴圈〕對i=N，N—1，N-2，…，2執行B3;然後轉B5。

B3:〔對j迴圈〕對j=i-1，i-2，…，1執行B4;然後轉B2。

B4:〔尋求Ri被Rj依賴次數〕若Ri被Rj依賴，Pi←Pi＋1；否則轉B3。

B5:一遍掃描Pi（i=1，2,...，N)，求Pmax。3.