知識(shí)表示知識(shí)是一切智能行為的基礎(chǔ)，也是軟件智能化的重要研究對(duì)象。要使軟件具有智能，就必須使它具有知識(shí)，而要使軟件具有知識(shí)，首先必須解決知識(shí)的表示問(wèn)題。所謂知識(shí)表示實(shí)際上就是對(duì)知識(shí)的一種描述，即用一些約定的符號(hào)把知識(shí)編碼成一組計(jì)算機(jī)可以接受的數(shù)據(jù)結(jié)構(gòu)。所謂知識(shí)表示過(guò)程就是把知識(shí)編碼成某種數(shù)據(jù)結(jié)構(gòu)的過(guò)程。一般來(lái)說(shuō)，同一知識(shí)可以有多種不同的表示形式，而不同表示形式所產(chǎn)生的效果又可能不一樣。12/9/20221知識(shí)表示知識(shí)是一切智能行為的基礎(chǔ)，也是軟件智能化的重要研究對(duì)常用的知識(shí)表示方法非結(jié)構(gòu)化方法邏輯表示法QA3,STRIPS,DART,MOMO產(chǎn)生式系統(tǒng)DENDRAL，MYCIN結(jié)構(gòu)化方法框架語(yǔ)義網(wǎng)絡(luò)過(guò)程式知識(shí)表示法12/9/20222常用的知識(shí)表示方法12/7/20222第二章產(chǎn)生式系統(tǒng)

2.1產(chǎn)生式系統(tǒng)概述

一、產(chǎn)生式系統(tǒng)的定義產(chǎn)生式系統(tǒng)是人工智能系統(tǒng)中常用的一種程序結(jié)構(gòu)，是一種知識(shí)表示系統(tǒng)。

通常由以下三部分組成：綜合數(shù)據(jù)庫(kù)產(chǎn)生式規(guī)則集控制系統(tǒng)12/9/20223第二章產(chǎn)生式系統(tǒng)2.1產(chǎn)生式系統(tǒng)概述12/7/20綜合數(shù)據(jù)庫(kù)：存放問(wèn)題的狀態(tài)描述的數(shù)據(jù)結(jié)構(gòu)。Note:綜合數(shù)據(jù)庫(kù)不是常規(guī)意義的數(shù)據(jù)庫(kù)，是一種數(shù)據(jù)結(jié)構(gòu)。一般數(shù)據(jù)庫(kù)所存數(shù)據(jù)的結(jié)構(gòu)很簡(jiǎn)單，通常只有數(shù)值與字符串；綜合數(shù)據(jù)庫(kù)的數(shù)據(jù)可以很復(fù)雜，其中狀態(tài)描述可以為常規(guī)的各種數(shù)據(jù)結(jié)構(gòu)，如表、數(shù)組、字符串、集合、矩陣、樹(shù)、圖等等。綜合數(shù)據(jù)庫(kù)是動(dòng)態(tài)變化的。一、產(chǎn)生式系統(tǒng)的定義12/9/20224綜合數(shù)據(jù)庫(kù)：存放問(wèn)題的狀態(tài)描述的數(shù)據(jù)結(jié)構(gòu)。一、產(chǎn)生式系統(tǒng)的定產(chǎn)生式規(guī)則形式：

IF前提條件THEN操作當(dāng)規(guī)則的前提條件被某一狀態(tài)描述滿足時(shí)，就對(duì)該狀態(tài)施行規(guī)則所指出的操作。一、產(chǎn)生式系統(tǒng)的定義12/9/20225產(chǎn)生式規(guī)則形式：一、產(chǎn)生式系統(tǒng)的定義12/7/20225控制系統(tǒng)：

（1）選擇規(guī)則：對(duì)同一個(gè)狀態(tài)的多個(gè)可用規(guī)則排序。（2）檢驗(yàn)狀態(tài)描述是否滿足終止條件。如果滿足終止條件，則終止產(chǎn)生式系統(tǒng)的運(yùn)行，并用使用過(guò)的規(guī)則序列構(gòu)造出問(wèn)題的解。一、產(chǎn)生式系統(tǒng)的定義12/9/20226控制系統(tǒng)：一、產(chǎn)生式系統(tǒng)的定義12/7/202二、產(chǎn)生式系統(tǒng)的例

八數(shù)碼難題由8個(gè)標(biāo)有1－8的棋子和一個(gè)3×3的棋盤組成。把8個(gè)棋子放在棋盤里，形成一個(gè)初始狀態(tài)，然后移動(dòng)棋子，想辦法達(dá)到規(guī)定的目標(biāo)狀態(tài)。在移動(dòng)棋子時(shí)，只能把棋子移進(jìn)相鄰的空格中。圖2.1八數(shù)碼難題的初始狀態(tài)與目標(biāo)狀態(tài)283164751238476512/9/20227二、產(chǎn)生式系統(tǒng)的例八數(shù)碼難題由8個(gè)標(biāo)有1－8的棋八數(shù)碼難題的產(chǎn)生式系統(tǒng)表示綜合數(shù)據(jù)庫(kù)：以狀態(tài)為節(jié)點(diǎn)的有向圖。狀態(tài)描述：3×3矩陣產(chǎn)生式規(guī)則：IF<空格不在最左邊>Then<左移空格>；IF<空格不在最上邊>Then<上移空格>；IF<空格不在最右邊>Then<右移空格>；IF<空格不在最下邊>Then<下移空格>。控制系統(tǒng)：

選擇規(guī)則:按左、上、右、下的順序移動(dòng)空格。終止條件：匹配成功。12/9/20228八數(shù)碼難題的產(chǎn)生式系統(tǒng)表示綜合數(shù)據(jù)庫(kù)：以狀態(tài)為節(jié)點(diǎn)的有向圖。三、產(chǎn)生式系統(tǒng)的基本過(guò)程ProcedurePRODUCTIONDATA←初始狀態(tài)描述untilDATA滿足終止條件，do：begin在規(guī)則集合中，選出一條可用于DATA的規(guī)則RDATA←把R應(yīng)用于DATA所得的結(jié)果End12/9/20229三、產(chǎn)生式系統(tǒng)的基本過(guò)程ProcedurePRODUCTI

步驟4是不確定的，只要求選出一條可用的規(guī)則R，至于這條規(guī)則如何選取，卻沒(méi)有具體說(shuō)明。

選取規(guī)則所依據(jù)的原則稱為控制策略。多數(shù)人工智能系統(tǒng)控制策略的信息并不足以在第4步選出最合用的規(guī)則，因此，控制策略便成了一個(gè)搜索過(guò)程。

高效的系統(tǒng)需要被求解問(wèn)題足夠的知識(shí)，以便在步驟4選出一條最合用的規(guī)則。第三章，第四章三、產(chǎn)生式系統(tǒng)的基本過(guò)程12/9/202210步驟4是不確定的，只要求選出一條可用的規(guī)則三、產(chǎn)生式系統(tǒng)的特點(diǎn)一、模塊性強(qiáng)。綜合數(shù)據(jù)庫(kù)、規(guī)則集和控制系統(tǒng)相對(duì)獨(dú)立，程序的修改更加容易。二、各產(chǎn)生式規(guī)則相互獨(dú)立，不能互相調(diào)用，增加一些或刪去一些產(chǎn)生式規(guī)則都十分方便。三、產(chǎn)生式規(guī)則的形式與人們推理所用的邏輯形式十分接近，人們具有的知識(shí)轉(zhuǎn)換成產(chǎn)生式規(guī)則很容易，產(chǎn)生式規(guī)則也容易被人們讀懂。DENDRAL和MYCIN都采用了產(chǎn)生式系統(tǒng)的結(jié)構(gòu)。12/9/202211產(chǎn)生式系統(tǒng)的特點(diǎn)一、模塊性強(qiáng)。綜合數(shù)據(jù)庫(kù)、規(guī)則集和控制系統(tǒng)相2.2控制策略

產(chǎn)生式系統(tǒng)的控制策略分為兩類：不可撤回的控制策略試探性控制策略：回溯方式和圖搜索方式12/9/2022122.2控制策略產(chǎn)生式系統(tǒng)的控制策略分為兩類：12一、不可撤回的控制策略（瞎子爬山法）基本思想采用不可撤回控制方式的解題過(guò)程類似于盲人爬山過(guò)程，是利用關(guān)于每一個(gè)狀態(tài)的局部知識(shí)構(gòu)造全局性解的過(guò)程。在盲人爬山過(guò)程中，無(wú)論爬到哪一點(diǎn)，他總沿著坡度最陡的方向向上爬，這是局部性的知識(shí)，盡管他事先對(duì)爬山路線并不了解，但只要按照這個(gè)原則向上爬，就一定能爬到某一山頂，于是確定了一條從山腳到山頂?shù)呐郎铰肪€，也可以說(shuō)構(gòu)造出一個(gè)具有某種意義下全局性的解。12/9/202213一、不可撤回的控制策略（瞎子爬山法）基本思想12/7/202一、不可撤回的控制策略爬山函數(shù)：定義在整個(gè)綜合數(shù)據(jù)庫(kù)上的實(shí)數(shù)值函數(shù)，目標(biāo)狀態(tài)有最大的函數(shù)值。目標(biāo)：爬到山頂?？刂撇呗裕簯?yīng)用爬山函數(shù)選一規(guī)則，使得所選下一狀態(tài)的爬山函數(shù)值不減少且最大（有兩個(gè)相同的最大值時(shí)任選一個(gè)；若無(wú)這樣的規(guī)則，則終止爬山過(guò)程）。12/9/202214一、不可撤回的控制策略爬山函數(shù)：定義在整個(gè)綜合數(shù)據(jù)庫(kù)上的實(shí)數(shù)設(shè)爬山函數(shù)CF(S)：不在目標(biāo)位的數(shù)碼個(gè)數(shù)的負(fù)值。

初始狀態(tài)S0目標(biāo)狀態(tài)Sg

CF(S0)＝-4CF(Sg)＝0狀態(tài)描述S：3階方陣4條產(chǎn)生式規(guī)則使用順序：空格左、上、右、下移。2831647512384765例：八數(shù)碼難題，不可撤回式控制12/9/202215設(shè)爬山函數(shù)CF(S)：不在目標(biāo)位的數(shù)碼個(gè)數(shù)的負(fù)值。283控制策略：處于任一狀態(tài)S，系統(tǒng)根據(jù)爬山函數(shù)選擇一條規(guī)則使得這條規(guī)則作用于S時(shí)，獲得的下一狀態(tài)爬山函數(shù)不減少且最大（亦即距離目標(biāo)狀態(tài)最少）。例：八數(shù)碼難題，不可撤回式控制12/9/202216控制策略：處于任一狀態(tài)S，系統(tǒng)根據(jù)爬山函數(shù)選擇一條規(guī)則使得這

283164752831476523184765231847651238476512384765例：八數(shù)碼難題不可撤回式控制-4-3-3-1-2012/9/2022172831647528314765231847652318不可撤回控制策略的優(yōu)點(diǎn)1.只記錄當(dāng)前一個(gè)節(jié)點(diǎn)，空間復(fù)雜性很低。2.若能找到解，則速度很快。12/9/202218不可撤回控制策略的優(yōu)點(diǎn)1.只記錄當(dāng)前一個(gè)節(jié)點(diǎn)，空間復(fù)雜性很不可撤回控制策略的局限性多數(shù)情況下找不到解。原因：(a)爬山函數(shù)有多個(gè)局部極大值例如：目標(biāo)0初始-2(b)爬山函數(shù)具有“平頂值”解決方法：設(shè)計(jì)更好的爬山函數(shù)；選多余規(guī)則123748651257486312/9/202219不可撤回控制策略的局限性多數(shù)情況下找不到解。原因：12374二、回溯控制策略回溯方式是一種試探性的控制策略。（類似深度優(yōu)先）基本思想控制系統(tǒng)先選用一條規(guī)則，如果發(fā)現(xiàn)這條規(guī)則的選用不能導(dǎo)致產(chǎn)生解，則系統(tǒng)“忘掉”選用規(guī)則所涉及的步驟和產(chǎn)生的狀態(tài)，然后選用另外一條規(guī)則，重新進(jìn)行試探。

12/9/202220二、回溯控制策略回溯方式是一種試探性的控制策略。（類似深度回溯方法特點(diǎn)1.只存儲(chǔ)初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，占用空間較小。2.總的時(shí)間復(fù)雜性無(wú)法定論:最好情況復(fù)雜性很低：當(dāng)控制系統(tǒng)掌握較多的有關(guān)解的知識(shí)時(shí)，則回溯次數(shù)大為減少，效率高。最壞情況復(fù)雜性很高：當(dāng)控制系統(tǒng)一點(diǎn)也沒(méi)掌握有關(guān)解的知識(shí)時(shí)，則規(guī)則選取是任意的，回溯次數(shù)高，效率低。為了避免進(jìn)入無(wú)限的境地，設(shè)置回溯深度限制強(qiáng)行回溯，問(wèn)題：太深：效率低；太淺：可能找不到解。3.當(dāng)深度限制可變時(shí)，通常能找到解，是實(shí)際用得多、應(yīng)用最廣的一種搜索策略。

12/9/202221回溯方法特點(diǎn)1.只存儲(chǔ)初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，占用空間較小四條規(guī)則使用順序：左、上、右、下（可加入啟發(fā)式信息，如使用爬山函數(shù)安排規(guī)則的順序）

深度：6

控制策略：回溯式

回溯條件：

⑴產(chǎn)生了一個(gè)上溯到初始狀態(tài)的路徑上出現(xiàn)過(guò)的狀態(tài)時(shí)（產(chǎn)生了祖先節(jié)點(diǎn)）。

⑵無(wú)可用的規(guī)則。

⑶達(dá)深度未得解。2831647512384765八數(shù)碼難題的初始狀態(tài)與目標(biāo)狀態(tài)例：八數(shù)碼難題回溯式12/9/202222四條規(guī)則使用順序：左、上、右、下（可加入啟發(fā)式信息，如使用爬2831647583264175832641752831647583264175834261758326417586324175283641758326417586324175

8326417583264175八數(shù)碼問(wèn)題回溯控制

83264175

（1）（5）（6）（5）（2）（6）（7）（6）

（3）（7）（7）

（4）（5）

（6）

12/9/202223283838328383三、圖搜索控制策略基本思想：從初始狀態(tài)開(kāi)始，使用全部可用規(guī)則序列。對(duì)所有的下一步狀態(tài)每一個(gè)再用全部可用的規(guī)則，直到目標(biāo)狀態(tài)為止。（類似廣度優(yōu)先搜索策略）搜索樹(shù)：記錄規(guī)則的應(yīng)用和所產(chǎn)生的狀態(tài)的樹(shù)結(jié)構(gòu)。樹(shù)根：初始狀態(tài)有向?。阂?guī)則的使用除根以外的其它各節(jié)點(diǎn)：規(guī)則應(yīng)用的結(jié)果圖搜索控制方式不斷地?cái)U(kuò)展搜索樹(shù)，直到它包括了滿足終止條件的節(jié)點(diǎn)為止。

12/9/202224三、圖搜索控制策略基本思想：從初始狀態(tài)開(kāi)始，使用全部可用規(guī)則圖搜索控制策略的特點(diǎn)1.不再選擇規(guī)則，而是使用所有可用的規(guī)則，下一步選擇節(jié)點(diǎn)來(lái)擴(kuò)展。2.存儲(chǔ)所有產(chǎn)生的節(jié)點(diǎn)，占用空間大。3.有解一定能找到（相當(dāng)于窮舉）。4.平均時(shí)間復(fù)雜性高，系統(tǒng)效率低。12/9/202225圖搜索控制策略的特點(diǎn)1.不再選擇規(guī)則，而是使用所有可用的規(guī)則

例：八數(shù)碼難題圖搜索式2831647512384765八數(shù)碼難題的初始狀態(tài)與目標(biāo)狀態(tài)書中圖：按照深度小的排在前面、優(yōu)先選擇左節(jié)點(diǎn)。12/9/202226

例：八數(shù)碼難題圖搜索式283164751238476四、產(chǎn)生式系統(tǒng)的工作方式1.正向產(chǎn)生式系統(tǒng)（數(shù)據(jù)驅(qū)動(dòng)控制）：綜合數(shù)據(jù)庫(kù)：用狀態(tài)描述產(chǎn)生式規(guī)則：F規(guī)則--狀態(tài)產(chǎn)生新?tīng)顟B(tài)

從初始狀態(tài)出發(fā)，不斷地應(yīng)用F規(guī)則，直到產(chǎn)生目標(biāo)狀態(tài)為止。適用條件：初始節(jié)點(diǎn)數(shù)≤目標(biāo)節(jié)點(diǎn)數(shù)12/9/202227四、產(chǎn)生式系統(tǒng)的工作方式1.正向產(chǎn)生式系統(tǒng)（數(shù)據(jù)驅(qū)動(dòng)控2.反（逆）向產(chǎn)生式系統(tǒng)（目標(biāo)驅(qū)動(dòng)控制）：綜合數(shù)據(jù)庫(kù)：用目標(biāo)描述產(chǎn)生式規(guī)則：B規(guī)則目標(biāo)產(chǎn)生子目標(biāo)從目標(biāo)狀態(tài)出發(fā)，利用反向的產(chǎn)生式規(guī)則（B規(guī)則）不斷地產(chǎn)生子目標(biāo)，直到產(chǎn)生出與初始狀態(tài)相同的子目標(biāo)為止。適用條件：初始節(jié)點(diǎn)數(shù)≥目標(biāo)節(jié)點(diǎn)數(shù)12/9/2022282.反（逆）向產(chǎn)生式系統(tǒng)（目標(biāo)驅(qū)動(dòng)控制）：12/7/203.雙向產(chǎn)生式系統(tǒng)：正向產(chǎn)生式系統(tǒng)和反向產(chǎn)生式系統(tǒng)結(jié)合.綜合數(shù)據(jù)庫(kù)：既有初始狀態(tài)描述，又有目標(biāo)狀態(tài)描述。產(chǎn)生式規(guī)則集：既有F規(guī)則，又有B規(guī)則。

正向產(chǎn)生式規(guī)則用在初始方向的狀態(tài)描述上，反向產(chǎn)生式規(guī)則用在目標(biāo)描述上。控制系統(tǒng):判斷選F規(guī)則還是B規(guī)則；判斷已經(jīng)產(chǎn)生的狀態(tài)和目標(biāo)是否能以某種方式匹配，從而滿足結(jié)束條件。結(jié)束條件：中間匯合時(shí)的狀態(tài)。適用條件：初始節(jié)點(diǎn)數(shù)與目標(biāo)節(jié)點(diǎn)數(shù)都很多。特點(diǎn)：效率高；復(fù)雜。12/9/2022293.雙向產(chǎn)生式系統(tǒng)：正向產(chǎn)生式系統(tǒng)和反向產(chǎn)生式系統(tǒng)結(jié)合.12.3特殊的產(chǎn)生式系統(tǒng)一、可交換產(chǎn)生式系統(tǒng)在某些產(chǎn)生式系統(tǒng)中。規(guī)則應(yīng)用的次序?qū)Ξa(chǎn)生的狀態(tài)無(wú)影響，即從初始狀態(tài)到目標(biāo)狀態(tài)不依賴規(guī)則次序，因此可應(yīng)用不可撤回式控制策略，從而提高了產(chǎn)生式系統(tǒng)的效率，這類產(chǎn)生式系統(tǒng)就是可交換的產(chǎn)生式系統(tǒng)。例：基于歸結(jié)方法的產(chǎn)生式系統(tǒng)12/9/2022302.3特殊的產(chǎn)生式系統(tǒng)一、可交換產(chǎn)生式系統(tǒng)12/7/202

一個(gè)產(chǎn)生式系統(tǒng)稱為可交換的，如果對(duì)任意狀態(tài)描述D具有如下性質(zhì)：(a)設(shè)RD是可應(yīng)用于D的規(guī)則集，任取r

∈RD，r作用于D得D’，設(shè)為D’=r

(D)，則r對(duì)D’可用(即：設(shè)D’的可用規(guī)則集為RD’，則r∈RD’，即RDRD’)；（每一條對(duì)D可應(yīng)用的規(guī)則，對(duì)于對(duì)D應(yīng)用一條可應(yīng)用的規(guī)則后所產(chǎn)生的狀態(tài)描述仍是可應(yīng)用的）（可應(yīng)用性）可交換產(chǎn)生式系統(tǒng)定義12/9/202231一個(gè)產(chǎn)生式系統(tǒng)稱為可交換的，如果對(duì)任意狀態(tài)描述D具有(b)設(shè)D滿足目標(biāo)條件，D的可用規(guī)則集為RD，任取r∈RD，用r作用到D產(chǎn)生狀態(tài)D’，D’滿足目標(biāo)條件。（如果D滿足目標(biāo)條件，則對(duì)D應(yīng)用任何一條可應(yīng)用的規(guī)則所產(chǎn)生的狀態(tài)描述也滿足目標(biāo)條件）

（可滿足性）。12/9/202232(b)設(shè)D滿足目標(biāo)條件，D的可用規(guī)則集為RD，任取r∈R（c）設(shè)D的可用規(guī)則集為RD，任取r1,r2,…,rn

∈RD，依據(jù)（a）將r1,r2,…,rn依次作用到D及產(chǎn)生的狀態(tài)上，得狀態(tài)Dn；設(shè)r1’,r2’,…,rn’是r1,r2,…,rn的任意一個(gè)排列，用r1’,r2’,…,rn’依次作用到D及產(chǎn)生的狀態(tài)上，得狀態(tài)Dn’，則Dn’=Dn

（對(duì)D應(yīng)用一個(gè)由可應(yīng)用于D的規(guī)則所構(gòu)成的規(guī)則序列所產(chǎn)生的狀態(tài)描述不因序列的次序不同而改變）(無(wú)次序性）。

12/9/202233（c）設(shè)D的可用規(guī)則集為RD，任取r1,r2,…,rR1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交換的產(chǎn)生式系統(tǒng)例R2R3R2R112/9/202234R1R3R1S12S11S0S13S3S2SGS1R3R2R可交換產(chǎn)生式系統(tǒng)優(yōu)點(diǎn)：從初始狀態(tài)到目標(biāo)狀態(tài)不依賴規(guī)則次序，不必探查等價(jià)路徑，可以使用不可撤回策略。Note：產(chǎn)生式系統(tǒng)的可交換性并不意味著整個(gè)規(guī)則序列的次序可以改變。只是最初作用于給定狀態(tài)的那些規(guī)則使用起來(lái)與次序無(wú)關(guān)。12/9/202235可交換產(chǎn)生式系統(tǒng)優(yōu)點(diǎn)：從初始狀態(tài)到目標(biāo)狀態(tài)不依賴規(guī)則次序，不設(shè)產(chǎn)生式系統(tǒng)P：綜合數(shù)據(jù)庫(kù)，一組規(guī)則，圖搜索策略造另一可交換的產(chǎn)生式系轉(zhuǎn)換P’如下：綜合數(shù)據(jù)庫(kù)：初始狀態(tài)：P的整個(gè)搜索樹(shù)目標(biāo)狀態(tài)：只剩解路轉(zhuǎn)換

可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：12/9/202236設(shè)產(chǎn)生式系統(tǒng)P：綜合數(shù)據(jù)庫(kù)，一組規(guī)則，圖搜索策略轉(zhuǎn)換可用如轉(zhuǎn)換可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：規(guī)則Ri：若綜合數(shù)據(jù)庫(kù)中第i層節(jié)點(diǎn)n不是解路P上的點(diǎn)，則從綜合數(shù)據(jù)庫(kù)中刪除節(jié)點(diǎn)n?？刂撇呗裕翰豢沙坊厥綄轉(zhuǎn)換為P’，P’是可交換的產(chǎn)生式系統(tǒng)

綜合數(shù)據(jù)庫(kù)變復(fù)雜；規(guī)則數(shù)目少，但操作復(fù)雜（如何判斷n不是解路P上的點(diǎn)）；控制策略簡(jiǎn)單。12/9/202237轉(zhuǎn)換可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：規(guī)則Ri：若綜二、可分解的產(chǎn)生式系統(tǒng)

可交換產(chǎn)生式系統(tǒng)可以避免搜索多余路徑，可以使用不可撤回策略。避免搜索多余路徑的另一種方法是可分解的產(chǎn)生式系統(tǒng)。12/9/202238二、可分解的產(chǎn)生式系統(tǒng)可交換產(chǎn)生式系統(tǒng)可以避免搜索多可分解的產(chǎn)生式系統(tǒng)例:字符串重寫綜合數(shù)據(jù)庫(kù)：串節(jié)點(diǎn)的有向圖狀態(tài)：字符串（或用表）初始狀態(tài)：(C,B,Z)產(chǎn)生式規(guī)則：R1:IF<(*1,C,*2)>THEN<(*1,D,L,*2)>

（重寫規(guī)則）R2:IF<(*1,C,*2)>THEN<(*1,B,M,*2)>R3:IF<(*1,B,*2)>THEN<(*1,M,M,*2)>R4:IF<(*1,Z,*2)>THEN<(*1,B,B,M,*2)>控制系統(tǒng)：

選擇規(guī)則：用圖搜索控制策略終止條件：狀態(tài)描述僅有M組成的符號(hào)串。

12/9/202239可分解的產(chǎn)生式系統(tǒng)例:字符串重寫綜合數(shù)據(jù)庫(kù)：串節(jié)點(diǎn)的有向圖1重寫問(wèn)題的解序列（不完整）R3R3R3R3R3R4R4R3R3R3R2R1R4（C，B，Z）(M,M,M,B,Z)(M,M,M,M,M,Z)(M,M,M,M,M,B,B,M)(M,M,M,M,M,M,M,B,M)(M,M,M,M,M,M,M,M,M,M)(C,B,B,B,M)(B,M,B,B,B,M)(M,M,M,B,B,B,M)(D,L,B,Z)(D,L,M,M,Z)(D,L,M,M,B,B,M)(D,L,M,M,M,M,B,M)(D,L,M,M,M,M,M,M,M)R2R3(B,M,B,Z)12/9/202240重寫問(wèn)題的解序列（不完整）R3R3R3R3R3R4R4R3Note:按照?qǐng)D搜索控制方式在產(chǎn)生終止?fàn)顟B(tài)時(shí)可能會(huì)探索許多完全等價(jià)的路徑,導(dǎo)致系統(tǒng)的低效。從失敗路徑上浪費(fèi)很多工作。節(jié)點(diǎn)的內(nèi)容之間存在著大量的符號(hào)冗余。12/9/202241Note:12/7/202241觀察：該產(chǎn)生式系統(tǒng)的初始狀態(tài)可以分解成C,B和Z，然后把產(chǎn)生式規(guī)則分解使得可應(yīng)用于這些組成部分：R1:(C)→(D,L)R2:(C)→(B,M)R3:(B)→(M,M)R4:(Z)→(B,B,M)應(yīng)用規(guī)則后所得的結(jié)果狀態(tài)又可以進(jìn)一步分裂，這樣不斷地分解，不斷地應(yīng)用規(guī)則，直到所產(chǎn)生的狀態(tài)是M字符為止，即終止條件分解為一個(gè)M字符作成的狀態(tài)。12/9/202242觀察：12/7/202242重寫問(wèn)題的與/或樹(shù)(C,B,Z)CBZ(D,L)(B,M)(M,M)(B,B,M)DLBM(M,M)MMMMBMB(M,M)(M,M)MMMM

R1R2R3R4

R3R3R312/9/202243重寫問(wèn)題的與/或樹(shù)(C,B,Z)CBZ(D,L)(B,M

定義

能夠把產(chǎn)生式系統(tǒng)綜合數(shù)據(jù)庫(kù)的狀態(tài)描述分解為若干組成部分，產(chǎn)生式規(guī)則可以分別用在各組成部分上，并且整個(gè)系統(tǒng)的終止條件可以用在各組成部分的終止條件表示出來(lái)的產(chǎn)生式系統(tǒng)，稱為可分解的產(chǎn)生式系統(tǒng)。可分解的產(chǎn)生式系統(tǒng)12/9/202244定義能夠把產(chǎn)生式系統(tǒng)綜合數(shù)據(jù)庫(kù)的狀態(tài)描述分解Note:對(duì)分解出的獨(dú)立分量的處理方式：可并行處理也可串行處理（一般情況下）：（1）按產(chǎn)生的時(shí)間排序；（2）在處理過(guò)程中動(dòng)態(tài)排序。12/9/202245Note:對(duì)分解出的獨(dú)立分量的處理方式：12/7/2022可分解的產(chǎn)生式系統(tǒng)的基本過(guò)程ProcedureSPLITDATA←初始狀態(tài)描述{Di}←DATA的分解結(jié)果；每個(gè)Di看成是獨(dú)立的狀態(tài)描述until對(duì)所有的Di{Di}，Di都滿足終止條件，do:begin在{Di}中選擇一個(gè)不滿足終止條件的D*從{Di}中刪除D*

從規(guī)則集合中選出一個(gè)可應(yīng)用于D*的規(guī)則RD←把R應(yīng)用于D*的結(jié)果{di}←D的分解結(jié)果把{di}加入{Di}中end12/9/202246可分解的產(chǎn)生式系統(tǒng)的基本過(guò)程ProcedureSPLIT1

SPLIT的控制策略：在步驟5中如何選取D*，在步驟7如何選取R。Note：PRODUCTION和SPLIT是兩個(gè)比較重要的算法，本課的重點(diǎn)之一。PRODUCTION的步驟4：控制策略

可分解的產(chǎn)生式系統(tǒng)的基本過(guò)程12/9/202247SPLIT的控制策略：在步驟5中如何選取D*，在可分解產(chǎn)生式系統(tǒng)的例子－－符號(hào)積分SAINT系統(tǒng)，1961年Slagle提出，1963年對(duì)SAINT進(jìn)行改進(jìn)，達(dá)到優(yōu)秀大學(xué)生水平，是一個(gè)可分解產(chǎn)生式系統(tǒng)。輸入：不定積分題目；輸出：積分的結(jié)果函數(shù)

綜合數(shù)據(jù)庫(kù)：以字符串為節(jié)點(diǎn)的與或圖狀態(tài)：字符串初始狀態(tài)：用字符串表示的不定積分題目（被積函數(shù)）產(chǎn)生式規(guī)則：分步積分規(guī)則、代數(shù)替換、三角替換等等例如：IF<∫udv>THEN<u∫dv-∫vdu>控制系統(tǒng)：選擇規(guī)則：圖搜索

終止條件：與系統(tǒng)內(nèi)部保存的基本積分表中的函數(shù)具有相同的形式。如：∫udu=u2/2

12/9/202248可分解產(chǎn)生式系統(tǒng)的例子－－符號(hào)積分SAINT系統(tǒng)，1961三角恒等式三角恒等式z=z=z=用分母除分子-z=12/9/202249三角恒等式三角恒等式z=z=z=用分母除分子-z=12/知識(shí)表示知識(shí)是一切智能行為的基礎(chǔ)，也是軟件智能化的重要研究對(duì)象。要使軟件具有智能，就必須使它具有知識(shí)，而要使軟件具有知識(shí)，首先必須解決知識(shí)的表示問(wèn)題。所謂知識(shí)表示實(shí)際上就是對(duì)知識(shí)的一種描述，即用一些約定的符號(hào)把知識(shí)編碼成一組計(jì)算機(jī)可以接受的數(shù)據(jù)結(jié)構(gòu)。所謂知識(shí)表示過(guò)程就是把知識(shí)編碼成某種數(shù)據(jù)結(jié)構(gòu)的過(guò)程。一般來(lái)說(shuō)，同一知識(shí)可以有多種不同的表示形式，而不同表示形式所產(chǎn)生的效果又可能不一樣。12/9/202250知識(shí)表示知識(shí)是一切智能行為的基礎(chǔ)，也是軟件智能化的重要研究對(duì)常用的知識(shí)表示方法非結(jié)構(gòu)化方法邏輯表示法QA3,STRIPS,DART,MOMO產(chǎn)生式系統(tǒng)DENDRAL，MYCIN結(jié)構(gòu)化方法框架語(yǔ)義網(wǎng)絡(luò)過(guò)程式知識(shí)表示法12/9/202251常用的知識(shí)表示方法12/7/20222第二章產(chǎn)生式系統(tǒng)

2.1產(chǎn)生式系統(tǒng)概述

一、產(chǎn)生式系統(tǒng)的定義產(chǎn)生式系統(tǒng)是人工智能系統(tǒng)中常用的一種程序結(jié)構(gòu)，是一種知識(shí)表示系統(tǒng)。

通常由以下三部分組成：綜合數(shù)據(jù)庫(kù)產(chǎn)生式規(guī)則集控制系統(tǒng)12/9/202252第二章產(chǎn)生式系統(tǒng)2.1產(chǎn)生式系統(tǒng)概述12/7/20綜合數(shù)據(jù)庫(kù)：存放問(wèn)題的狀態(tài)描述的數(shù)據(jù)結(jié)構(gòu)。Note:綜合數(shù)據(jù)庫(kù)不是常規(guī)意義的數(shù)據(jù)庫(kù)，是一種數(shù)據(jù)結(jié)構(gòu)。一般數(shù)據(jù)庫(kù)所存數(shù)據(jù)的結(jié)構(gòu)很簡(jiǎn)單，通常只有數(shù)值與字符串；綜合數(shù)據(jù)庫(kù)的數(shù)據(jù)可以很復(fù)雜，其中狀態(tài)描述可以為常規(guī)的各種數(shù)據(jù)結(jié)構(gòu)，如表、數(shù)組、字符串、集合、矩陣、樹(shù)、圖等等。綜合數(shù)據(jù)庫(kù)是動(dòng)態(tài)變化的。一、產(chǎn)生式系統(tǒng)的定義12/9/202253綜合數(shù)據(jù)庫(kù)：存放問(wèn)題的狀態(tài)描述的數(shù)據(jù)結(jié)構(gòu)。一、產(chǎn)生式系統(tǒng)的定產(chǎn)生式規(guī)則形式：

IF前提條件THEN操作當(dāng)規(guī)則的前提條件被某一狀態(tài)描述滿足時(shí)，就對(duì)該狀態(tài)施行規(guī)則所指出的操作。一、產(chǎn)生式系統(tǒng)的定義12/9/202254產(chǎn)生式規(guī)則形式：一、產(chǎn)生式系統(tǒng)的定義12/7/20225控制系統(tǒng)：

（1）選擇規(guī)則：對(duì)同一個(gè)狀態(tài)的多個(gè)可用規(guī)則排序。（2）檢驗(yàn)狀態(tài)描述是否滿足終止條件。如果滿足終止條件，則終止產(chǎn)生式系統(tǒng)的運(yùn)行，并用使用過(guò)的規(guī)則序列構(gòu)造出問(wèn)題的解。一、產(chǎn)生式系統(tǒng)的定義12/9/202255控制系統(tǒng)：一、產(chǎn)生式系統(tǒng)的定義12/7/202二、產(chǎn)生式系統(tǒng)的例

八數(shù)碼難題由8個(gè)標(biāo)有1－8的棋子和一個(gè)3×3的棋盤組成。把8個(gè)棋子放在棋盤里，形成一個(gè)初始狀態(tài)，然后移動(dòng)棋子，想辦法達(dá)到規(guī)定的目標(biāo)狀態(tài)。在移動(dòng)棋子時(shí)，只能把棋子移進(jìn)相鄰的空格中。圖2.1八數(shù)碼難題的初始狀態(tài)與目標(biāo)狀態(tài)283164751238476512/9/202256二、產(chǎn)生式系統(tǒng)的例八數(shù)碼難題由8個(gè)標(biāo)有1－8的棋八數(shù)碼難題的產(chǎn)生式系統(tǒng)表示綜合數(shù)據(jù)庫(kù)：以狀態(tài)為節(jié)點(diǎn)的有向圖。狀態(tài)描述：3×3矩陣產(chǎn)生式規(guī)則：IF<空格不在最左邊>Then<左移空格>；IF<空格不在最上邊>Then<上移空格>；IF<空格不在最右邊>Then<右移空格>；IF<空格不在最下邊>Then<下移空格>。控制系統(tǒng)：

選擇規(guī)則:按左、上、右、下的順序移動(dòng)空格。終止條件：匹配成功。12/9/202257八數(shù)碼難題的產(chǎn)生式系統(tǒng)表示綜合數(shù)據(jù)庫(kù)：以狀態(tài)為節(jié)點(diǎn)的有向圖。三、產(chǎn)生式系統(tǒng)的基本過(guò)程ProcedurePRODUCTIONDATA←初始狀態(tài)描述untilDATA滿足終止條件，do：begin在規(guī)則集合中，選出一條可用于DATA的規(guī)則RDATA←把R應(yīng)用于DATA所得的結(jié)果End12/9/202258三、產(chǎn)生式系統(tǒng)的基本過(guò)程ProcedurePRODUCTI

步驟4是不確定的，只要求選出一條可用的規(guī)則R，至于這條規(guī)則如何選取，卻沒(méi)有具體說(shuō)明。

選取規(guī)則所依據(jù)的原則稱為控制策略。多數(shù)人工智能系統(tǒng)控制策略的信息并不足以在第4步選出最合用的規(guī)則，因此，控制策略便成了一個(gè)搜索過(guò)程。

高效的系統(tǒng)需要被求解問(wèn)題足夠的知識(shí)，以便在步驟4選出一條最合用的規(guī)則。第三章，第四章三、產(chǎn)生式系統(tǒng)的基本過(guò)程12/9/202259步驟4是不確定的，只要求選出一條可用的規(guī)則三、產(chǎn)生式系統(tǒng)的特點(diǎn)一、模塊性強(qiáng)。綜合數(shù)據(jù)庫(kù)、規(guī)則集和控制系統(tǒng)相對(duì)獨(dú)立，程序的修改更加容易。二、各產(chǎn)生式規(guī)則相互獨(dú)立，不能互相調(diào)用，增加一些或刪去一些產(chǎn)生式規(guī)則都十分方便。三、產(chǎn)生式規(guī)則的形式與人們推理所用的邏輯形式十分接近，人們具有的知識(shí)轉(zhuǎn)換成產(chǎn)生式規(guī)則很容易，產(chǎn)生式規(guī)則也容易被人們讀懂。DENDRAL和MYCIN都采用了產(chǎn)生式系統(tǒng)的結(jié)構(gòu)。12/9/202260產(chǎn)生式系統(tǒng)的特點(diǎn)一、模塊性強(qiáng)。綜合數(shù)據(jù)庫(kù)、規(guī)則集和控制系統(tǒng)相2.2控制策略

產(chǎn)生式系統(tǒng)的控制策略分為兩類：不可撤回的控制策略試探性控制策略：回溯方式和圖搜索方式12/9/2022612.2控制策略產(chǎn)生式系統(tǒng)的控制策略分為兩類：12一、不可撤回的控制策略（瞎子爬山法）基本思想采用不可撤回控制方式的解題過(guò)程類似于盲人爬山過(guò)程，是利用關(guān)于每一個(gè)狀態(tài)的局部知識(shí)構(gòu)造全局性解的過(guò)程。在盲人爬山過(guò)程中，無(wú)論爬到哪一點(diǎn)，他總沿著坡度最陡的方向向上爬，這是局部性的知識(shí)，盡管他事先對(duì)爬山路線并不了解，但只要按照這個(gè)原則向上爬，就一定能爬到某一山頂，于是確定了一條從山腳到山頂?shù)呐郎铰肪€，也可以說(shuō)構(gòu)造出一個(gè)具有某種意義下全局性的解。12/9/202262一、不可撤回的控制策略（瞎子爬山法）基本思想12/7/202一、不可撤回的控制策略爬山函數(shù)：定義在整個(gè)綜合數(shù)據(jù)庫(kù)上的實(shí)數(shù)值函數(shù)，目標(biāo)狀態(tài)有最大的函數(shù)值。目標(biāo)：爬到山頂?？刂撇呗裕簯?yīng)用爬山函數(shù)選一規(guī)則，使得所選下一狀態(tài)的爬山函數(shù)值不減少且最大（有兩個(gè)相同的最大值時(shí)任選一個(gè)；若無(wú)這樣的規(guī)則，則終止爬山過(guò)程）。12/9/202263一、不可撤回的控制策略爬山函數(shù)：定義在整個(gè)綜合數(shù)據(jù)庫(kù)上的實(shí)數(shù)設(shè)爬山函數(shù)CF(S)：不在目標(biāo)位的數(shù)碼個(gè)數(shù)的負(fù)值。

初始狀態(tài)S0目標(biāo)狀態(tài)Sg

CF(S0)＝-4CF(Sg)＝0狀態(tài)描述S：3階方陣4條產(chǎn)生式規(guī)則使用順序：空格左、上、右、下移。2831647512384765例：八數(shù)碼難題，不可撤回式控制12/9/202264設(shè)爬山函數(shù)CF(S)：不在目標(biāo)位的數(shù)碼個(gè)數(shù)的負(fù)值。283控制策略：處于任一狀態(tài)S，系統(tǒng)根據(jù)爬山函數(shù)選擇一條規(guī)則使得這條規(guī)則作用于S時(shí)，獲得的下一狀態(tài)爬山函數(shù)不減少且最大（亦即距離目標(biāo)狀態(tài)最少）。例：八數(shù)碼難題，不可撤回式控制12/9/202265控制策略：處于任一狀態(tài)S，系統(tǒng)根據(jù)爬山函數(shù)選擇一條規(guī)則使得這

283164752831476523184765231847651238476512384765例：八數(shù)碼難題不可撤回式控制-4-3-3-1-2012/9/2022662831647528314765231847652318不可撤回控制策略的優(yōu)點(diǎn)1.只記錄當(dāng)前一個(gè)節(jié)點(diǎn)，空間復(fù)雜性很低。2.若能找到解，則速度很快。12/9/202267不可撤回控制策略的優(yōu)點(diǎn)1.只記錄當(dāng)前一個(gè)節(jié)點(diǎn)，空間復(fù)雜性很不可撤回控制策略的局限性多數(shù)情況下找不到解。原因：(a)爬山函數(shù)有多個(gè)局部極大值例如：目標(biāo)0初始-2(b)爬山函數(shù)具有“平頂值”解決方法：設(shè)計(jì)更好的爬山函數(shù)；選多余規(guī)則123748651257486312/9/202268不可撤回控制策略的局限性多數(shù)情況下找不到解。原因：12374二、回溯控制策略回溯方式是一種試探性的控制策略。（類似深度優(yōu)先）基本思想控制系統(tǒng)先選用一條規(guī)則，如果發(fā)現(xiàn)這條規(guī)則的選用不能導(dǎo)致產(chǎn)生解，則系統(tǒng)“忘掉”選用規(guī)則所涉及的步驟和產(chǎn)生的狀態(tài)，然后選用另外一條規(guī)則，重新進(jìn)行試探。

12/9/202269二、回溯控制策略回溯方式是一種試探性的控制策略。（類似深度回溯方法特點(diǎn)1.只存儲(chǔ)初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，占用空間較小。2.總的時(shí)間復(fù)雜性無(wú)法定論:最好情況復(fù)雜性很低：當(dāng)控制系統(tǒng)掌握較多的有關(guān)解的知識(shí)時(shí)，則回溯次數(shù)大為減少，效率高。最壞情況復(fù)雜性很高：當(dāng)控制系統(tǒng)一點(diǎn)也沒(méi)掌握有關(guān)解的知識(shí)時(shí)，則規(guī)則選取是任意的，回溯次數(shù)高，效率低。為了避免進(jìn)入無(wú)限的境地，設(shè)置回溯深度限制強(qiáng)行回溯，問(wèn)題：太深：效率低；太淺：可能找不到解。3.當(dāng)深度限制可變時(shí)，通常能找到解，是實(shí)際用得多、應(yīng)用最廣的一種搜索策略。

12/9/202270回溯方法特點(diǎn)1.只存儲(chǔ)初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的路徑，占用空間較小四條規(guī)則使用順序：左、上、右、下（可加入啟發(fā)式信息，如使用爬山函數(shù)安排規(guī)則的順序）

深度：6

控制策略：回溯式

回溯條件：

⑴產(chǎn)生了一個(gè)上溯到初始狀態(tài)的路徑上出現(xiàn)過(guò)的狀態(tài)時(shí)（產(chǎn)生了祖先節(jié)點(diǎn)）。

⑵無(wú)可用的規(guī)則。

⑶達(dá)深度未得解。2831647512384765八數(shù)碼難題的初始狀態(tài)與目標(biāo)狀態(tài)例：八數(shù)碼難題回溯式12/9/202271四條規(guī)則使用順序：左、上、右、下（可加入啟發(fā)式信息，如使用爬2831647583264175832641752831647583264175834261758326417586324175283641758326417586324175

8326417583264175八數(shù)碼問(wèn)題回溯控制

83264175

（1）（5）（6）（5）（2）（6）（7）（6）

（3）（7）（7）

（4）（5）

（6）

12/9/202272283838328383三、圖搜索控制策略基本思想：從初始狀態(tài)開(kāi)始，使用全部可用規(guī)則序列。對(duì)所有的下一步狀態(tài)每一個(gè)再用全部可用的規(guī)則，直到目標(biāo)狀態(tài)為止。（類似廣度優(yōu)先搜索策略）搜索樹(shù)：記錄規(guī)則的應(yīng)用和所產(chǎn)生的狀態(tài)的樹(shù)結(jié)構(gòu)。樹(shù)根：初始狀態(tài)有向?。阂?guī)則的使用除根以外的其它各節(jié)點(diǎn)：規(guī)則應(yīng)用的結(jié)果圖搜索控制方式不斷地?cái)U(kuò)展搜索樹(shù)，直到它包括了滿足終止條件的節(jié)點(diǎn)為止。

12/9/202273三、圖搜索控制策略基本思想：從初始狀態(tài)開(kāi)始，使用全部可用規(guī)則圖搜索控制策略的特點(diǎn)1.不再選擇規(guī)則，而是使用所有可用的規(guī)則，下一步選擇節(jié)點(diǎn)來(lái)擴(kuò)展。2.存儲(chǔ)所有產(chǎn)生的節(jié)點(diǎn)，占用空間大。3.有解一定能找到（相當(dāng)于窮舉）。4.平均時(shí)間復(fù)雜性高，系統(tǒng)效率低。12/9/202274圖搜索控制策略的特點(diǎn)1.不再選擇規(guī)則，而是使用所有可用的規(guī)則

例：八數(shù)碼難題圖搜索式2831647512384765八數(shù)碼難題的初始狀態(tài)與目標(biāo)狀態(tài)書中圖：按照深度小的排在前面、優(yōu)先選擇左節(jié)點(diǎn)。12/9/202275

例：八數(shù)碼難題圖搜索式283164751238476四、產(chǎn)生式系統(tǒng)的工作方式1.正向產(chǎn)生式系統(tǒng)（數(shù)據(jù)驅(qū)動(dòng)控制）：綜合數(shù)據(jù)庫(kù)：用狀態(tài)描述產(chǎn)生式規(guī)則：F規(guī)則--狀態(tài)產(chǎn)生新?tīng)顟B(tài)

從初始狀態(tài)出發(fā)，不斷地應(yīng)用F規(guī)則，直到產(chǎn)生目標(biāo)狀態(tài)為止。適用條件：初始節(jié)點(diǎn)數(shù)≤目標(biāo)節(jié)點(diǎn)數(shù)12/9/202276四、產(chǎn)生式系統(tǒng)的工作方式1.正向產(chǎn)生式系統(tǒng)（數(shù)據(jù)驅(qū)動(dòng)控2.反（逆）向產(chǎn)生式系統(tǒng)（目標(biāo)驅(qū)動(dòng)控制）：綜合數(shù)據(jù)庫(kù)：用目標(biāo)描述產(chǎn)生式規(guī)則：B規(guī)則目標(biāo)產(chǎn)生子目標(biāo)從目標(biāo)狀態(tài)出發(fā)，利用反向的產(chǎn)生式規(guī)則（B規(guī)則）不斷地產(chǎn)生子目標(biāo)，直到產(chǎn)生出與初始狀態(tài)相同的子目標(biāo)為止。適用條件：初始節(jié)點(diǎn)數(shù)≥目標(biāo)節(jié)點(diǎn)數(shù)12/9/2022772.反（逆）向產(chǎn)生式系統(tǒng)（目標(biāo)驅(qū)動(dòng)控制）：12/7/203.雙向產(chǎn)生式系統(tǒng)：正向產(chǎn)生式系統(tǒng)和反向產(chǎn)生式系統(tǒng)結(jié)合.綜合數(shù)據(jù)庫(kù)：既有初始狀態(tài)描述，又有目標(biāo)狀態(tài)描述。產(chǎn)生式規(guī)則集：既有F規(guī)則，又有B規(guī)則。

正向產(chǎn)生式規(guī)則用在初始方向的狀態(tài)描述上，反向產(chǎn)生式規(guī)則用在目標(biāo)描述上。控制系統(tǒng):判斷選F規(guī)則還是B規(guī)則；判斷已經(jīng)產(chǎn)生的狀態(tài)和目標(biāo)是否能以某種方式匹配，從而滿足結(jié)束條件。結(jié)束條件：中間匯合時(shí)的狀態(tài)。適用條件：初始節(jié)點(diǎn)數(shù)與目標(biāo)節(jié)點(diǎn)數(shù)都很多。特點(diǎn)：效率高；復(fù)雜。12/9/2022783.雙向產(chǎn)生式系統(tǒng)：正向產(chǎn)生式系統(tǒng)和反向產(chǎn)生式系統(tǒng)結(jié)合.12.3特殊的產(chǎn)生式系統(tǒng)一、可交換產(chǎn)生式系統(tǒng)在某些產(chǎn)生式系統(tǒng)中。規(guī)則應(yīng)用的次序?qū)Ξa(chǎn)生的狀態(tài)無(wú)影響，即從初始狀態(tài)到目標(biāo)狀態(tài)不依賴規(guī)則次序，因此可應(yīng)用不可撤回式控制策略，從而提高了產(chǎn)生式系統(tǒng)的效率，這類產(chǎn)生式系統(tǒng)就是可交換的產(chǎn)生式系統(tǒng)。例：基于歸結(jié)方法的產(chǎn)生式系統(tǒng)12/9/2022792.3特殊的產(chǎn)生式系統(tǒng)一、可交換產(chǎn)生式系統(tǒng)12/7/202

一個(gè)產(chǎn)生式系統(tǒng)稱為可交換的，如果對(duì)任意狀態(tài)描述D具有如下性質(zhì)：(a)設(shè)RD是可應(yīng)用于D的規(guī)則集，任取r

∈RD，r作用于D得D’，設(shè)為D’=r

(D)，則r對(duì)D’可用(即：設(shè)D’的可用規(guī)則集為RD’，則r∈RD’，即RDRD’)；（每一條對(duì)D可應(yīng)用的規(guī)則，對(duì)于對(duì)D應(yīng)用一條可應(yīng)用的規(guī)則后所產(chǎn)生的狀態(tài)描述仍是可應(yīng)用的）（可應(yīng)用性）可交換產(chǎn)生式系統(tǒng)定義12/9/202280一個(gè)產(chǎn)生式系統(tǒng)稱為可交換的，如果對(duì)任意狀態(tài)描述D具有(b)設(shè)D滿足目標(biāo)條件，D的可用規(guī)則集為RD，任取r∈RD，用r作用到D產(chǎn)生狀態(tài)D’，D’滿足目標(biāo)條件。（如果D滿足目標(biāo)條件，則對(duì)D應(yīng)用任何一條可應(yīng)用的規(guī)則所產(chǎn)生的狀態(tài)描述也滿足目標(biāo)條件）

（可滿足性）。12/9/202281(b)設(shè)D滿足目標(biāo)條件，D的可用規(guī)則集為RD，任取r∈R（c）設(shè)D的可用規(guī)則集為RD，任取r1,r2,…,rn

∈RD，依據(jù)（a）將r1,r2,…,rn依次作用到D及產(chǎn)生的狀態(tài)上，得狀態(tài)Dn；設(shè)r1’,r2’,…,rn’是r1,r2,…,rn的任意一個(gè)排列，用r1’,r2’,…,rn’依次作用到D及產(chǎn)生的狀態(tài)上，得狀態(tài)Dn’，則Dn’=Dn

（對(duì)D應(yīng)用一個(gè)由可應(yīng)用于D的規(guī)則所構(gòu)成的規(guī)則序列所產(chǎn)生的狀態(tài)描述不因序列的次序不同而改變）(無(wú)次序性）。

12/9/202282（c）設(shè)D的可用規(guī)則集為RD，任取r1,r2,…,rR1R3R1S12S11S0S13S3S2SGS1R3R2R1R2R3R1R2R3R2R1R3R3R2R1R2R3R1可交換的產(chǎn)生式系統(tǒng)例R2R3R2R112/9/202283R1R3R1S12S11S0S13S3S2SGS1R3R2R可交換產(chǎn)生式系統(tǒng)優(yōu)點(diǎn)：從初始狀態(tài)到目標(biāo)狀態(tài)不依賴規(guī)則次序，不必探查等價(jià)路徑，可以使用不可撤回策略。Note：產(chǎn)生式系統(tǒng)的可交換性并不意味著整個(gè)規(guī)則序列的次序可以改變。只是最初作用于給定狀態(tài)的那些規(guī)則使用起來(lái)與次序無(wú)關(guān)。12/9/202284可交換產(chǎn)生式系統(tǒng)優(yōu)點(diǎn)：從初始狀態(tài)到目標(biāo)狀態(tài)不依賴規(guī)則次序，不設(shè)產(chǎn)生式系統(tǒng)P：綜合數(shù)據(jù)庫(kù)，一組規(guī)則，圖搜索策略造另一可交換的產(chǎn)生式系轉(zhuǎn)換P’如下：綜合數(shù)據(jù)庫(kù)：初始狀態(tài)：P的整個(gè)搜索樹(shù)目標(biāo)狀態(tài)：只剩解路轉(zhuǎn)換

可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：12/9/202285設(shè)產(chǎn)生式系統(tǒng)P：綜合數(shù)據(jù)庫(kù)，一組規(guī)則，圖搜索策略轉(zhuǎn)換可用如轉(zhuǎn)換可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：規(guī)則Ri：若綜合數(shù)據(jù)庫(kù)中第i層節(jié)點(diǎn)n不是解路P上的點(diǎn)，則從綜合數(shù)據(jù)庫(kù)中刪除節(jié)點(diǎn)n?？刂撇呗裕翰豢沙坊厥綄轉(zhuǎn)換為P’，P’是可交換的產(chǎn)生式系統(tǒng)

綜合數(shù)據(jù)庫(kù)變復(fù)雜；規(guī)則數(shù)目少，但操作復(fù)雜（如何判斷n不是解路P上的點(diǎn)）；控制策略簡(jiǎn)單。12/9/202286轉(zhuǎn)換可用如下方法將一產(chǎn)生式系轉(zhuǎn)換為可交換的：規(guī)則Ri：若綜二、可分解的產(chǎn)生式系統(tǒng)

可交換產(chǎn)生式系統(tǒng)可以避免搜索多余路徑，可以使用不可撤回策略。避免搜索多余路徑的另一種方法是可分解的產(chǎn)生式系統(tǒng)。12/9/202287二、可分解的產(chǎn)生式系統(tǒng)可交換產(chǎn)生式系統(tǒng)可以避免搜索多可分解的產(chǎn)生式系統(tǒng)例:字符串重寫綜合數(shù)據(jù)庫(kù)：串節(jié)點(diǎn)的有向圖狀態(tài)：字符串（或用表）初始狀態(tài)：(C,B,Z)產(chǎn)生式規(guī)則：R1:IF<(*1,C,*2)>THEN<(*1,D,L,*2)>

（重寫規(guī)則）R2:IF<(*1,C,*2)>THEN<(*1,B,M,*2)>R3:IF<(*1,B,*2)>THEN<(*1,M,M,*2)>R4:IF<(*1,Z,*2)>THEN<(*1,B,B,M,*2)>控制系統(tǒng)：

選擇規(guī)則：用圖搜索控制策略終止條件：狀態(tài)描述僅有M組成的符號(hào)串。

12/9/202288可分解的產(chǎn)生式系統(tǒng)例:字符串重寫綜合數(shù)據(jù)庫(kù)：串節(jié)點(diǎn)的有向圖1重寫問(wèn)題的解序列（不完整）R3R3R3R3R3R4R4R3R3R3R2R1R4（C，B，Z）(M,M,M,B,Z)(M,M,M,M,M,Z)(M,M,M,M,M,B,B,M)(M,M,M,M,M,M,M,B,M)(M,M,M,M,M,M,M