基于產(chǎn)生式規(guī)則的機器推理

1、第第6 6章章 基于產(chǎn)生式規(guī)則的機器推理基于產(chǎn)生式規(guī)則的機器推理2022-3-6人工智能2第第6章基于產(chǎn)生式規(guī)則的機器推理章基于產(chǎn)生式規(guī)則的機器推理6.1 6.1 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則6.2 6.2 產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)2022-3-6人工智能36.1 6.1 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則6.1.1 產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則6.1.2 基于產(chǎn)生式規(guī)則的推理模式基于產(chǎn)生式規(guī)則的推理模式2022-3-6人工智能46.1.16.1.1產(chǎn)生式規(guī)則（產(chǎn)生式規(guī)則（1）產(chǎn)生式產(chǎn)生式產(chǎn)生式（產(chǎn)生式（ProductionProduction）一詞從波斯特機中借用來的。）一詞從波斯特機中借用來的。波斯特機是一種自動機，它是根

2、據(jù)串替換規(guī)則提出波斯特機是一種自動機，它是根據(jù)串替換規(guī)則提出的一種計算模型。其中的每一條規(guī)則就叫一個產(chǎn)生的一種計算模型。其中的每一條規(guī)則就叫一個產(chǎn)生式。也稱產(chǎn)生式規(guī)則，簡稱規(guī)則。式。也稱產(chǎn)生式規(guī)則，簡稱規(guī)則。這里產(chǎn)生式就是前面討論過的操作（二階梵塔問題，這里產(chǎn)生式就是前面討論過的操作（二階梵塔問題，猴子摘香蕉問題等）、邏輯蘊含式、推理規(guī)則以及猴子摘香蕉問題等）、邏輯蘊含式、推理規(guī)則以及各種關(guān)系（包含經(jīng)驗性聯(lián)想）的一種邏輯抽象。各種關(guān)系（包含經(jīng)驗性聯(lián)想）的一種邏輯抽象。 2022-3-6人工智能56.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（2）產(chǎn)生式的一般形式為：產(chǎn)生式的一般形式為：前件前件后件（

3、情況后件（情況行為）行為）前件是前提，規(guī)則的執(zhí)行條件。前件是前提，規(guī)則的執(zhí)行條件。 后件是結(jié)論或動作，規(guī)則體。后件是結(jié)論或動作，規(guī)則體。產(chǎn)生式規(guī)則的語義：如果前提滿足，則可得結(jié)論或產(chǎn)生式規(guī)則的語義：如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動作，即后件由前件觸發(fā)。者執(zhí)行相應(yīng)的動作，即后件由前件觸發(fā)。一個產(chǎn)生式規(guī)則就是一條知識，用產(chǎn)生式不僅可以進一個產(chǎn)生式規(guī)則就是一條知識，用產(chǎn)生式不僅可以進行推理，也可以實現(xiàn)操作。行推理，也可以實現(xiàn)操作。2022-3-6人工智能66.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（3）產(chǎn)生式規(guī)則例子產(chǎn)生式規(guī)則例子如果銀行存款利率下調(diào)，那么股票價格上漲。如果銀行存款利率下調(diào)，那

4、么股票價格上漲。如果爐溫超過上限，則立即關(guān)閉風(fēng)門。如果爐溫超過上限，則立即關(guān)閉風(fēng)門。如果發(fā)燒、嘔吐并且出現(xiàn)黃疸，那么得了肝炎。如果發(fā)燒、嘔吐并且出現(xiàn)黃疸，那么得了肝炎。（0.7）如果鍵盤突然失靈，且屏幕上出現(xiàn)怪字符，則是病如果鍵盤突然失靈，且屏幕上出現(xiàn)怪字符，則是病毒發(fā)作。毒發(fā)作。2022-3-6人工智能76.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）例例 三個聰明人問題。古代有個國王想知道他的三個聰明人問題。古代有個國王想知道他的三個大三個大臣臣中誰最聰明，就在他們每個人前額上中誰最聰明，就在他們每個人前額上都畫了一個點，他們都能看到別人點的顏色，都畫了一個點，他們都能看到別人點的顏色

5、，但看不到自己點的顏色。國王說，你們中間至但看不到自己點的顏色。國王說，你們中間至少有一個人的點是白色的。于是重復(fù)地問他們：少有一個人的點是白色的。于是重復(fù)地問他們：“誰知道自己點的顏色？誰知道自己點的顏色？”三位大臣們頭兩次三位大臣們頭兩次都回答說不知道。題目要求證明下一次他們?nèi)蓟卮鹫f不知道。題目要求證明下一次他們?nèi)紩f都會說“知道知道”，并且所有的點都是白色。，并且所有的點都是白色。2022-3-6人工智能86.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）分析分析： 這類問題的特點是有有限個受試者，每個這類問題的特點是有有限個受試者，每個人對問題都只有部分了解，無法直接求解。但人對

6、問題都只有部分了解，無法直接求解。但在推理過程中每個人又可以從別人那里獲得新在推理過程中每個人又可以從別人那里獲得新的知識，重新進行推理?？梢杂卯a(chǎn)生式來表達的知識，重新進行推理?？梢杂卯a(chǎn)生式來表達推理過程中所用到的各種知識。推理過程中所用到的各種知識。2022-3-6人工智能96.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）狀態(tài)集合表示：狀態(tài)集合表示： 用用x1,x2,x3表示三個人點的顏色，表示三個人點的顏色，1表示白色，表示白色，0表示非白色。表示非白色。 X(x1,x2,x3)表示顏色分布狀態(tài)。表示顏色分布狀態(tài)。 全部可能的狀態(tài)集合全部可能的狀態(tài)集合(可能界可能界PW0)：(0,0,

7、0),(0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) 實際給定的狀態(tài)為實際給定的狀態(tài)為現(xiàn)實界現(xiàn)實界X0 (x10,x20,x30) 用排除法找到用排除法找到X0 。2022-3-6人工智能106.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）排除過程：排除過程：第一次，大臣只知道至少有一個人是白點，排除第一次，大臣只知道至少有一個人是白點，排除X0=(0,0,0)狀態(tài)。狀態(tài)。這時如果有人看到兩個非白點，根這時如果有人看到兩個非白點，根據(jù)排除的狀態(tài)可推知自己是白點。據(jù)排除的狀態(tài)可推知自己是白點。第二次大臣根據(jù)沒有一個人知道自己點顏

8、色的事實第二次大臣根據(jù)沒有一個人知道自己點顏色的事實推知至少兩人為白點。排除推知至少兩人為白點。排除(0,0,1)(0,1,0)(1,0,0)狀態(tài)。狀態(tài)。這時如果有人看到一個非白點，根據(jù)排除后得到的這時如果有人看到一個非白點，根據(jù)排除后得到的狀態(tài)可推知自己的點是白的。狀態(tài)可推知自己的點是白的。第三次，大臣們根據(jù)仍無人知道自己點顏色的新事第三次，大臣們根據(jù)仍無人知道自己點顏色的新事實推知沒有一個非白點出現(xiàn)，即實推知沒有一個非白點出現(xiàn)，即X0=(1,1,1)。于是三。于是三人都知道自己點的顏色是白的。人都知道自己點的顏色是白的。2022-3-6人工智能116.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（

9、例）（例）引入中介狀態(tài)并定義下述符號：引入中介狀態(tài)并定義下述符號： Si i大臣看到的非白點數(shù)；大臣看到的非白點數(shù)； Wi i大臣猜出自己點的顏色否。如果他宣布已大臣猜出自己點的顏色否。如果他宣布已知道自己點的顏色，為知道自己點的顏色，為1，否則為，否則為0； nX0中白點的個數(shù)。中白點的個數(shù)。 2022-3-6人工智能126.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）(1) (n=1) X(n=1) X0 0 (0,0,1),(0,1,0),(0,1,1),(1,0,0),(1,0,1),(1,1,0),(1,1,1) (0,0,1),(0,1,0),(0,1,1),(1,0,0),(

10、1,0,1),(1,1,0),(1,1,1)；(2) (n=1) (2) (n=1) (S(Si i=2) =2) =(W=(Wi i=1),(i=1,2,3,=1),(i=1,2,3,下同下同) )；(3)( (3)( i ) i ) (W(Wi i=1) =1) (n=1) = (n=1) (n=1) = (n=1) ；(4) (n=1) = (4) (n=1) = ( i ) i ) (W(Wi i=1) =1) ；(5) (5) ( i ) i ) (W(Wi i=0) =0) (n=1) = (n=2) ; (n=1) = (n=2) ;(6) (n=2) X(6) (n=2) X0

11、 0 (0,1,1),(1,0,1),(1,1,0),(1,1,1) (0,1,1),(1,0,1),(1,1,0),(1,1,1)；(7) (n=2) (7) (n=2) (S(Si i=1) =1) =(W=(Wi i=1);=1);(8) ( (8) ( i ) i ) (W(Wi i=1) =1) (n=2) = (n=2) ;(n=2) = (n=2) ;(9) (n=2) = (9) (n=2) = ( i ) i ) (W(Wi i=1);=1);(10) (10) ( i ) i ) (W(Wi i=0) =0) (n=2) = (n=3); (n=2) = (n=3);(11

12、) (n=3) X(11) (n=3) X0 0 (1,1,1) (1,1,1)；(12) (n=3) = (12) (n=3) = ( i ) i ) (W(Wi i=1).=1).2022-3-6人工智能136.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）上述結(jié)果可以推廣到更一般的情況：設(shè)有上述結(jié)果可以推廣到更一般的情況：設(shè)有m個大個大臣，國王說至少有臣，國王說至少有l(wèi) l個人的點是白色的，則有下個人的點是白色的，則有下述產(chǎn)生式：述產(chǎn)生式： (1) (n=l) X0 x|x中的白點數(shù)中的白點數(shù)=l； (2) (n=l) (Si=2) =(Wi=1),(i=1,2,m,下同下同)； (3

13、)( i ) (Wi=1) (n=l) = (n=l) ； (4) (n=l) = ( i ) (Wi=l) ； (5)( i ) (Wi=0) (n=l) (l (n=l1) ; (6)( i ) (Wi=0) (n=l) (lm-1)= (nm)。 2022-3-6人工智能146.1.26.1.2基于產(chǎn)生式規(guī)則的推理模式基于產(chǎn)生式規(guī)則的推理模式 A B B A B 把有前提的操作和邏輯推理統(tǒng)稱為推理，把有前提的操作和邏輯推理統(tǒng)稱為推理，產(chǎn)生式系統(tǒng)中的推理是更廣義的推理。產(chǎn)生式系統(tǒng)中的推理是更廣義的推理。2022-3-6人工智能156.26.2產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)6.2.16.2.1系統(tǒng)結(jié)構(gòu)

14、系統(tǒng)結(jié)構(gòu)6.2.26.2.2運行過程運行過程6.2.36.2.3控制策略常用算法控制策略常用算法6.2.46.2.4程序?qū)崿F(xiàn)程序?qū)崿F(xiàn)* *6.2.56.2.5產(chǎn)生式系統(tǒng)與問題求解產(chǎn)生式系統(tǒng)與問題求解2022-3-6人工智能166.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（1 1）產(chǎn)生式系統(tǒng)結(jié)構(gòu)產(chǎn)生式系統(tǒng)結(jié)構(gòu)產(chǎn)生式規(guī)則庫推理機全局?jǐn)?shù)據(jù)庫2022-3-6人工智能176.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（2 2）組成組成產(chǎn)生式規(guī)則庫產(chǎn)生式規(guī)則庫作用在全局?jǐn)?shù)據(jù)庫上的一些規(guī)則作用在全局?jǐn)?shù)據(jù)庫上的一些規(guī)則的集合。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫的集合。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫中內(nèi)容滿足這些條件

15、可調(diào)用這條規(guī)則。一般可形成中內(nèi)容滿足這些條件可調(diào)用這條規(guī)則。一般可形成一個稱為推理網(wǎng)絡(luò)的結(jié)構(gòu)圖。對應(yīng)過程性知識。一個稱為推理網(wǎng)絡(luò)的結(jié)構(gòu)圖。對應(yīng)過程性知識。推理機推理機負(fù)責(zé)產(chǎn)生式規(guī)則的前提條件測試或匹配，負(fù)責(zé)產(chǎn)生式規(guī)則的前提條件測試或匹配，規(guī)則的調(diào)度和選取，規(guī)則體的解釋和執(zhí)行。即推理規(guī)則的調(diào)度和選取，規(guī)則體的解釋和執(zhí)行。即推理機實施推理，并對推理進行控制，它也是規(guī)則的解機實施推理，并對推理進行控制，它也是規(guī)則的解釋程序。對應(yīng)控制性知識。釋程序。對應(yīng)控制性知識。全局?jǐn)?shù)據(jù)庫全局?jǐn)?shù)據(jù)庫人工智能系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中心。是人工智能系統(tǒng)的數(shù)據(jù)結(jié)構(gòu)中心。是一個動態(tài)數(shù)據(jù)結(jié)構(gòu)，用來存放初始事實數(shù)據(jù)、中間一個動態(tài)數(shù)據(jù)結(jié)

16、構(gòu)，用來存放初始事實數(shù)據(jù)、中間結(jié)果和最后結(jié)果。對應(yīng)敘述性知識。結(jié)果和最后結(jié)果。對應(yīng)敘述性知識。2022-3-6人工智能186.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（3 3）例例 旅行推銷員問題。求從旅行推銷員問題。求從A城出發(fā)，經(jīng)過其他城市一次城出發(fā)，經(jīng)過其他城市一次且僅一次，最后回到且僅一次，最后回到A城的最小費用路線。城市之間的城的最小費用路線。城市之間的交通費用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。交通費用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。BCADE713109656710102022-3-6人工智能196.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（4 4）（1）全局?jǐn)?shù)據(jù)庫全局?jǐn)?shù)據(jù)庫（已訪問過的城鎮(zhèn)

17、名稱序列）。（已訪問過的城鎮(zhèn)名稱序列）。約約束條件是除城鎮(zhèn)束條件是除城鎮(zhèn)A之外其他名稱不得在序列中重復(fù)出現(xiàn)；之外其他名稱不得在序列中重復(fù)出現(xiàn)；只有所有的名稱都在序列中出現(xiàn)后，城鎮(zhèn)只有所有的名稱都在序列中出現(xiàn)后，城鎮(zhèn)A才能重復(fù)出才能重復(fù)出現(xiàn)。現(xiàn)。（2）規(guī)則集規(guī)則集如下表所示如下表所示。（3）推理推理： （A） （AB） （ABE） （4）終止條件終止條件序列始于序列始于A，終止于，終止于A，其中包含其，其中包含其他所有城鎮(zhèn)一次，且費用最少。他所有城鎮(zhèn)一次，且費用最少。（5）各種各種搜索策略搜索策略選擇規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)選擇規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)先搜索等。先搜索等。 R2R5202

18、2-3-6人工智能206.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（5 5）規(guī)則集規(guī)則集 規(guī)則規(guī)則動作動作條件條件R1下一步到下一步到A系列中包含所有城鎮(zhèn)時可用系列中包含所有城鎮(zhèn)時可用R2下一步到下一步到B每條規(guī)則只能使用一次，即每條規(guī)則只能使用一次，即序列中已有某城鎮(zhèn)時，不能序列中已有某城鎮(zhèn)時，不能再使用相應(yīng)規(guī)則再使用相應(yīng)規(guī)則R3下一步到下一步到CR4下一步到下一步到DR5下一步到下一步到E2022-3-6人工智能216.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（6 6）與一般分級組織的計算機軟件相比具有特點：與一般分級組織的計算機軟件相比具有特點：全局?jǐn)?shù)據(jù)庫的內(nèi)容可以為所有規(guī)則所訪問，沒有任全局?jǐn)?shù)據(jù)庫

19、的內(nèi)容可以為所有規(guī)則所訪問，沒有任何部分是專為某一規(guī)則建立的，這種特性便于模仿何部分是專為某一規(guī)則建立的，這種特性便于模仿智能行為中的強數(shù)據(jù)驅(qū)動。智能行為中的強數(shù)據(jù)驅(qū)動。規(guī)則本身不調(diào)用其他規(guī)則。規(guī)則之間的聯(lián)系必須通規(guī)則本身不調(diào)用其他規(guī)則。規(guī)則之間的聯(lián)系必須通過全局?jǐn)?shù)據(jù)庫聯(lián)系。過全局?jǐn)?shù)據(jù)庫聯(lián)系。全局?jǐn)?shù)據(jù)庫、規(guī)則和推理機之間相對獨立，這種積全局?jǐn)?shù)據(jù)庫、規(guī)則和推理機之間相對獨立，這種積木式結(jié)構(gòu)便于整個系統(tǒng)增加和修改知識。木式結(jié)構(gòu)便于整個系統(tǒng)增加和修改知識。2022-3-6人工智能226.2.26.2.2產(chǎn)生式系統(tǒng)的產(chǎn)生式系統(tǒng)的運行過程（運行過程（1）推理機一次運行過程推理機一次運行過程從規(guī)則庫中取出

20、一條規(guī)則，將其前提同從規(guī)則庫中取出一條規(guī)則，將其前提同當(dāng)前動態(tài)數(shù)據(jù)庫中的事實進行模式匹配當(dāng)前動態(tài)數(shù)據(jù)庫中的事實進行模式匹配匹配成功否？匹配成功否？把該規(guī)則的結(jié)論放入當(dāng)前動態(tài)數(shù)據(jù)庫；把該規(guī)則的結(jié)論放入當(dāng)前動態(tài)數(shù)據(jù)庫；或執(zhí)行規(guī)則所規(guī)定的動作或執(zhí)行規(guī)則所規(guī)定的動作YN2022-3-6人工智能236.2.26.2.2產(chǎn)生式系統(tǒng)的產(chǎn)生式系統(tǒng)的運行過程運行過程（2 2）產(chǎn)生式系統(tǒng)運行過程產(chǎn)生式系統(tǒng)運行過程實際的產(chǎn)生式系統(tǒng)，目標(biāo)條件往往要經(jīng)過多步推理實際的產(chǎn)生式系統(tǒng)，目標(biāo)條件往往要經(jīng)過多步推理才能滿足或者證明問題無解。才能滿足或者證明問題無解。產(chǎn)生式系統(tǒng)的運行過程就是推理機不斷的運用規(guī)則產(chǎn)生式系統(tǒng)的運行過程

21、就是推理機不斷的運用規(guī)則庫中的規(guī)則，作用于動態(tài)數(shù)據(jù)庫，不斷進行推理并庫中的規(guī)則，作用于動態(tài)數(shù)據(jù)庫，不斷進行推理并不斷檢測目標(biāo)條件是否被滿足的過程。不斷檢測目標(biāo)條件是否被滿足的過程。產(chǎn)生式系統(tǒng)運行過程是從初始事實出發(fā)，尋求到達產(chǎn)生式系統(tǒng)運行過程是從初始事實出發(fā)，尋求到達目標(biāo)條件的通路的過程。所以也是一個目標(biāo)條件的通路的過程。所以也是一個搜索搜索的過程。的過程。2022-3-6人工智能246.2.36.2.3控制策略與常用算法控制策略與常用算法（1 1）推理方式推理方式正向推理正向推理 從初始事實數(shù)據(jù)出發(fā)，正向使用規(guī)則從初始事實數(shù)據(jù)出發(fā)，正向使用規(guī)則進行推理，朝目標(biāo)方向前進。又稱為前向推理、正進行

22、推理，朝目標(biāo)方向前進。又稱為前向推理、正向鏈、數(shù)據(jù)驅(qū)動的推理。向鏈、數(shù)據(jù)驅(qū)動的推理。反向推理反向推理從目標(biāo)出發(fā)，反向使用規(guī)則進行推理，從目標(biāo)出發(fā)，反向使用規(guī)則進行推理，朝初始事實或數(shù)據(jù)方向前進。又稱反向推理、反向朝初始事實或數(shù)據(jù)方向前進。又稱反向推理、反向鏈、目標(biāo)驅(qū)動的推理。鏈、目標(biāo)驅(qū)動的推理。2022-3-6人工智能256.2.36.2.3控制策略與常用算法控制策略與常用算法（2 2）正向推理算法一正向推理算法一步步1 將初始事實將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；步步2 用動態(tài)數(shù)據(jù)庫中的事實匹配目標(biāo)條件，若目標(biāo)條件用動態(tài)數(shù)據(jù)庫中的事實匹配目標(biāo)條件，若目標(biāo)條件滿足，推理成功，

23、結(jié)束。滿足，推理成功，結(jié)束。步步3 用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實，用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實，將匹配成功的規(guī)則組成待用規(guī)則集。將匹配成功的規(guī)則組成待用規(guī)則集。步步4 若待用規(guī)則集為空，則運行失敗，退出。若待用規(guī)則集為空，則運行失敗，退出。步步5 將待用規(guī)則集中各規(guī)則的結(jié)論加入動態(tài)數(shù)據(jù)庫，或?qū)⒋靡?guī)則集中各規(guī)則的結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，轉(zhuǎn)步者執(zhí)行其動作，轉(zhuǎn)步2。2022-3-6人工智能266.2.36.2.3控制策略與常用算法（控制策略與常用算法（3 3）若把若把動態(tài)數(shù)據(jù)庫動態(tài)數(shù)據(jù)庫的的每一個狀態(tài)每一個狀態(tài)作為一個作為一個節(jié)點節(jié)點的話，則的話，則上述

24、推理過程就是一個從初始狀態(tài)到目標(biāo)狀態(tài)的上述推理過程就是一個從初始狀態(tài)到目標(biāo)狀態(tài)的狀態(tài)狀態(tài)圖搜索圖搜索過程。過程。如果把動態(tài)數(shù)據(jù)庫中的如果把動態(tài)數(shù)據(jù)庫中的每一個事實每一個事實/數(shù)據(jù)數(shù)據(jù)作為一個作為一個節(jié)點節(jié)點的話，則上述推理過程就是一個自底向上的的話，則上述推理過程就是一個自底向上的與或樹搜與或樹搜索索過程。過程。2022-3-6人工智能276.2.36.2.3控制策略與常用算法控制策略與常用算法（4 4）反向推理算法反向推理算法步步1 將初始事實將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫，數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫，將目標(biāo)條件置入將目標(biāo)條件置入目標(biāo)鏈；目標(biāo)鏈；步步2 若目標(biāo)鏈為空，則推理成功，結(jié)束。若目標(biāo)鏈為空，

25、則推理成功，結(jié)束。步步3 取出目標(biāo)鏈中第一個目標(biāo)，用動態(tài)數(shù)據(jù)庫中的事實取出目標(biāo)鏈中第一個目標(biāo)，用動態(tài)數(shù)據(jù)庫中的事實同其匹配，若匹配成功，轉(zhuǎn)步同其匹配，若匹配成功，轉(zhuǎn)步2。步步4 用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配成功，則將第一個匹配成功且未用過的規(guī)則的前提作成功，則將第一個匹配成功且未用過的規(guī)則的前提作為新的目標(biāo)，并取代原來的父目標(biāo)加入目標(biāo)鏈，轉(zhuǎn)步為新的目標(biāo)，并取代原來的父目標(biāo)加入目標(biāo)鏈，轉(zhuǎn)步3。步步5 若該目標(biāo)是初始目標(biāo)，則推理失敗，退出。若該目標(biāo)是初始目標(biāo)，則推理失敗，退出。步步6 將該目標(biāo)的父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄將該目標(biāo)的

26、父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄弟目標(biāo)，轉(zhuǎn)步弟目標(biāo)，轉(zhuǎn)步3。2022-3-6人工智能286.2.36.2.3控制策略與常用算法控制策略與常用算法（5 5）在產(chǎn)生式系統(tǒng)中，從前提到結(jié)論的產(chǎn)生式規(guī)則在產(chǎn)生式系統(tǒng)中，從前提到結(jié)論的產(chǎn)生式規(guī)則通常也是一棵與或樹。通常也是一棵與或樹。合取，與節(jié)點：一個產(chǎn)生式的前提包含了幾個事實，合取，與節(jié)點：一個產(chǎn)生式的前提包含了幾個事實，那么它的結(jié)論對應(yīng)這些事實的合取。那么它的結(jié)論對應(yīng)這些事實的合取。析取，或節(jié)點：一個結(jié)論可以由多個產(chǎn)生式得到，析取，或節(jié)點：一個結(jié)論可以由多個產(chǎn)生式得到，則這個結(jié)論對應(yīng)這些產(chǎn)生式的析取。則這個結(jié)論對應(yīng)這些產(chǎn)生式的析取。每個產(chǎn)生式系統(tǒng)都

27、隱含著許多這樣的與或樹。每個產(chǎn)生式系統(tǒng)都隱含著許多這樣的與或樹。2022-3-6人工智能296.2.36.2.3控制策略與常用算法控制策略與常用算法（6 6）F1P1F3F4F5F6BCDAP2P3P4P5F2事實中介事實B、C、D產(chǎn)生式規(guī)則P1、P2、P3、P4、P5結(jié)論2022-3-6人工智能306.2.36.2.3控制策略與常用算法控制策略與常用算法（7 7）例例6.1：動物分類問題的產(chǎn)生式系統(tǒng)描述及求解。：動物分類問題的產(chǎn)生式系統(tǒng)描述及求解。 規(guī)則規(guī)則：r1 r1： IF IF 該動物有毛發(fā)該動物有毛發(fā) THEN THEN 該動物是哺乳動物該動物是哺乳動物r2r2： IF IF 該動物

28、有奶該動物有奶 THEN THEN 該動物是哺乳動物該動物是哺乳動物r3r3： IF IF 該動物有羽毛該動物有羽毛 THEN THEN 該動物是鳥該動物是鳥r4r4： IF IF 該動物會飛該動物會飛 AND AND 會下蛋會下蛋 THEN THEN 該動物是鳥該動物是鳥r5r5： IF IF 該動物吃肉該動物吃肉 THEN THEN 該動物是食肉動物該動物是食肉動物r6r6： IF IF 該動物有犬齒該動物有犬齒 AND AND 有爪有爪 AND AND 眼盯前方眼盯前方 THEN THEN 該動物是食肉動物動物該動物是食肉動物動物2022-3-6人工智能316.2.36.2.3控制策略與

29、常用算法控制策略與常用算法（8 8）r7r7： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 有蹄有蹄 THEN THEN 該動物是有蹄類動物該動物是有蹄類動物r8r8： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 是嚼反芻動物是嚼反芻動物 THEN THEN 該動物是有蹄動物該動物是有蹄動物r9r9： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 是食肉動物是食肉動物 AND AND 是黃褐色是黃褐色 AND AND 身上有暗斑點身上有暗斑點 THEN THEN 該動物是該動物是金錢豹金錢豹 r10r10： IF IF 該動物是哺乳動物該動物

30、是哺乳動物 AND AND 是食肉動物是食肉動物 AND AND 是黃褐色是黃褐色 AND AND 身上有黑色條紋身上有黑色條紋 THEN THEN 該動物是該動物是虎虎2022-3-6人工智能326.2.36.2.3控制策略與常用算法控制策略與常用算法（9 9）r11r11： IF IF 該動物是有蹄類動物該動物是有蹄類動物 AND AND 有長脖子有長脖子 AND AND 有長腿有長腿 AND AND 身上有暗斑點身上有暗斑點 THEN THEN 該動物是該動物是長頸鹿長頸鹿 r12r12： IF IF 該動物有蹄類動物該動物有蹄類動物 AND AND 身上有黑色條紋身上有黑色條紋 THE

31、N THEN 該動物是該動物是斑馬斑馬r13r13： IF IF 該動物是鳥該動物是鳥 AND AND 有長脖子有長脖子 AND AND 有長腿有長腿 AND AND 不會飛不會飛 AND AND 有黑白二色有黑白二色 THEN THEN 該動物是該動物是鴕鳥鴕鳥2022-3-6人工智能336.2.36.2.3控制策略與常用算法控制策略與常用算法（1010）r14r14： IF IF 該動物是鳥該動物是鳥 AND AND 會游泳會游泳 AND AND 不會飛不會飛 AND AND 有黑白二色有黑白二色 THEN THEN 該動物是該動物是企鵝企鵝r15r15：IF IF 該動物是鳥該動物是鳥

32、AND AND 善飛善飛 AND AND 不怕風(fēng)浪不怕風(fēng)浪 THEN THEN 該動物是該動物是海燕海燕老虎老虎黃褐色黃褐色有黑色條紋有黑色條紋食肉動物食肉動物哺乳動物哺乳動物有毛發(fā)有毛發(fā)有奶有奶吃肉吃肉有爪有爪有犬齒有犬齒目 盯 前目 盯 前方方金錢豹金錢豹有 黑 色 斑有 黑 色 斑點點長頸鹿長頸鹿有蹄動物有蹄動物有蹄有蹄長腿長腿長脖子長脖子有 暗 斑有 暗 斑點點圖圖6-4 6-4 動物分類產(chǎn)生式規(guī)則集所形成的部分推理網(wǎng)絡(luò)動物分類產(chǎn)生式規(guī)則集所形成的部分推理網(wǎng)絡(luò)2022-3-6人工智能356.2.36.2.3控制策略與常用算法控制策略與常用算法（1212）初始事實：初始事實： f1 f1

33、：某動物有毛發(fā)。：某動物有毛發(fā)。 f2f2：吃肉。：吃肉。 f3f3：黃褐色。：黃褐色。 f4f4：有黑色條紋：有黑色條紋目標(biāo)條件為：該動物為什么？目標(biāo)條件為：該動物為什么？2022-3-6人工智能366.2.36.2.3控制策略與常用算法控制策略與常用算法（1313）哺乳類食肉動物有毛發(fā)食肉黃褐色有黑色條紋老虎正向推理推理樹r2r6r102022-3-6人工智能376.2.36.2.3控制策略與常用算法控制策略與常用算法（1414）哺乳類食肉動物有毛發(fā)有奶黃褐色有黑色條紋老虎反向推理推理樹目盯前方有毛發(fā)有爪吃肉r10r5r1r2r6例例6.2 使用反向推理算法使用反向推理算法2022-3-6

34、人工智能386.2.36.2.3控制策略與常用算法（控制策略與常用算法（1515）3 沖突消解策略沖突消解策略給定一組事實之后可用匹配技術(shù)尋找可用產(chǎn)生式，其給定一組事實之后可用匹配技術(shù)尋找可用產(chǎn)生式，其基本思想是將已知事實代入產(chǎn)生式的前件，若前件為基本思想是將已知事實代入產(chǎn)生式的前件，若前件為真，則該產(chǎn)生式是可用的。真，則該產(chǎn)生式是可用的。提高匹配效率的方法提高匹配效率的方法索引匹配。為狀態(tài)建立可用產(chǎn)生式索引表，減少可用產(chǎn)生式索引匹配。為狀態(tài)建立可用產(chǎn)生式索引表，減少可用產(chǎn)生式搜索范圍。搜索范圍。分層匹配。將產(chǎn)生式分成若干層或組，按一定特征進行分層分層匹配。將產(chǎn)生式分成若干層或組，按一定特征進

35、行分層搜索。搜索。過濾匹配。邊匹配邊過濾匹配。邊匹配邊 按某些附加特征或參數(shù)對可用產(chǎn)生式進按某些附加特征或參數(shù)對可用產(chǎn)生式進行精選。行精選。2022-3-6人工智能396.2.36.2.3控制策略與常用算法控制策略與常用算法（2 2）正向推理算法二正向推理算法二步步1 將初始事實將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；步步2 用動態(tài)數(shù)據(jù)庫中的事實匹配目標(biāo)條件，若目標(biāo)條件用動態(tài)數(shù)據(jù)庫中的事實匹配目標(biāo)條件，若目標(biāo)條件滿足，推理成功，結(jié)束。滿足，推理成功，結(jié)束。步步3 用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實，用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實，將匹配成功的規(guī)則組成待用規(guī)則集。將匹配成功的規(guī)則組成待用規(guī)則集。步步4 若待用規(guī)則集為空，則運行失敗，退出。若待用規(guī)則集為空，則運行失敗，退出。步步5 用某種策略，從待用規(guī)則集中選取一條規(guī)則，用某種策略，從待用規(guī)則集中選取一條規(guī)則，將其將其結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，撤消待用規(guī)結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，撤消待用規(guī)則集，轉(zhuǎn)步則集，轉(zhuǎn)步2。2022-3-6人工智能406.2.36.2.3控制策略與常用算法（控制策略與常用算法（1616）如果一組事實可以同時使幾個產(chǎn)生式前提為真，常用如果一組事實可以同時使幾個產(chǎn)生式前提為真，常用以下方法進行選擇（沖突消解策