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

1、第第6 6章章 基于產(chǎn)生式規(guī)則的機(jī)器推理基于產(chǎn)生式規(guī)則的機(jī)器推理2022-3-6人工智能2第第6章基于產(chǎn)生式規(guī)則的機(jī)器推理章基于產(chǎn)生式規(guī)則的機(jī)器推理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）一詞從波斯特機(jī)中借用來的。）一詞從波斯特機(jī)中借用來的。波斯特機(jī)是一種自動(dòng)機(jī)，它是根

2、據(jù)串替換規(guī)則提出波斯特機(jī)是一種自動(dòng)機(jī)，它是根據(jù)串替換規(guī)則提出的一種計(jì)算模型。其中的每一條規(guī)則就叫一個(gè)產(chǎn)生的一種計(jì)算模型。其中的每一條規(guī)則就叫一個(gè)產(chǎn)生式。也稱產(chǎn)生式規(guī)則，簡(jiǎn)稱規(guī)則。式。也稱產(chǎn)生式規(guī)則，簡(jiǎn)稱規(guī)則。這里產(chǎn)生式就是前面討論過的操作（二階梵塔問題，這里產(chǎn)生式就是前面討論過的操作（二階梵塔問題，猴子摘香蕉問題等）、邏輯蘊(yùn)含式、推理規(guī)則以及猴子摘香蕉問題等）、邏輯蘊(yùn)含式、推理規(guī)則以及各種關(guān)系（包含經(jīng)驗(yàn)性聯(lián)想）的一種邏輯抽象。各種關(guān)系（包含經(jīng)驗(yàn)性聯(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é)論或動(dòng)作，規(guī)則體。后件是結(jié)論或動(dòng)作，規(guī)則體。產(chǎn)生式規(guī)則的語(yǔ)義：如果前提滿足，則可得結(jié)論或產(chǎn)生式規(guī)則的語(yǔ)義：如果前提滿足，則可得結(jié)論或者執(zhí)行相應(yīng)的動(dòng)作，即后件由前件觸發(fā)。者執(zhí)行相應(yīng)的動(dòng)作，即后件由前件觸發(fā)。一個(gè)產(chǎn)生式規(guī)則就是一條知識(shí)，用產(chǎn)生式不僅可以進(jìn)一個(gè)產(chǎn)生式規(guī)則就是一條知識(shí)，用產(chǎn)生式不僅可以進(jìn)行推理，也可以實(shí)現(xiàn)操作。行推理，也可以實(shí)現(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)，那么股票價(jià)格上漲。如果銀行存款利率下調(diào)，那

4、么股票價(jià)格上漲。如果爐溫超過上限，則立即關(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ī)則（例）（例）例例 三個(gè)聰明人問題。古代有個(gè)國(guó)王想知道他的三個(gè)聰明人問題。古代有個(gè)國(guó)王想知道他的三個(gè)大三個(gè)大臣臣中誰(shuí)最聰明，就在他們每個(gè)人前額上中誰(shuí)最聰明，就在他們每個(gè)人前額上都畫了一個(gè)點(diǎn)，他們都能看到別人點(diǎn)的顏色，都畫了一個(gè)點(diǎn)，他們都能看到別人點(diǎn)的顏色

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

6、問題都只有部分了解，無法直接求解。但在推理過程中每個(gè)人又可以從別人那里獲得新在推理過程中每個(gè)人又可以從別人那里獲得新的知識(shí)，重新進(jìn)行推理?？梢杂卯a(chǎn)生式來表達(dá)的知識(shí)，重新進(jìn)行推理?？梢杂卯a(chǎn)生式來表達(dá)推理過程中所用到的各種知識(shí)。推理過程中所用到的各種知識(shí)。2022-3-6人工智能96.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）狀態(tài)集合表示：狀態(tài)集合表示： 用用x1,x2,x3表示三個(gè)人點(diǎn)的顏色，表示三個(gè)人點(diǎn)的顏色，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) 實(shí)際給定的狀態(tài)為實(shí)際給定的狀態(tài)為現(xiàn)實(shí)界現(xiàn)實(shí)界X0 (x10,x20,x30) 用排除法找到用排除法找到X0 。2022-3-6人工智能106.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）排除過程：排除過程：第一次，大臣只知道至少有一個(gè)人是白點(diǎn)，排除第一次，大臣只知道至少有一個(gè)人是白點(diǎn)，排除X0=(0,0,0)狀態(tài)。狀態(tài)。這時(shí)如果有人看到兩個(gè)非白點(diǎn)，根這時(shí)如果有人看到兩個(gè)非白點(diǎn)，根據(jù)排除的狀態(tài)可推知自己是白點(diǎn)。據(jù)排除的狀態(tài)可推知自己是白點(diǎn)。第二次大臣根據(jù)沒有一個(gè)人知道自己點(diǎn)顏

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

9、例）（例）引入中介狀態(tài)并定義下述符號(hào)：引入中介狀態(tài)并定義下述符號(hào)： Si i大臣看到的非白點(diǎn)數(shù)；大臣看到的非白點(diǎn)數(shù)； Wi i大臣猜出自己點(diǎn)的顏色否。如果他宣布已大臣猜出自己點(diǎn)的顏色否。如果他宣布已知道自己點(diǎn)的顏色，為知道自己點(diǎn)的顏色，為1，否則為，否則為0； nX0中白點(diǎn)的個(gè)數(shù)。中白點(diǎn)的個(gè)數(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個(gè)大個(gè)大臣，國(guó)王說至少有臣，國(guó)王說至少有l(wèi) l個(gè)人的點(diǎn)是白色的，則有下個(gè)人的點(diǎn)是白色的，則有下述產(chǎn)生式：述產(chǎn)生式： (1) (n=l) X0 x|x中的白點(diǎn)數(shù)中的白點(diǎn)數(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運(yùn)行過程運(yùn)行過程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ī)則庫(kù)推理機(jī)全局?jǐn)?shù)據(jù)庫(kù)2022-3-6人工智能176.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（2 2）組成組成產(chǎn)生式規(guī)則庫(kù)產(chǎn)生式規(guī)則庫(kù)作用在全局?jǐn)?shù)據(jù)庫(kù)上的一些規(guī)則作用在全局?jǐn)?shù)據(jù)庫(kù)上的一些規(guī)則的集合。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫(kù)的集合。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫(kù)中內(nèi)容滿足這些條件

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

16、構(gòu)，用來存放初始事實(shí)數(shù)據(jù)、中間結(jié)果和最后結(jié)果。對(duì)應(yīng)敘述性知識(shí)。結(jié)果和最后結(jié)果。對(duì)應(yīng)敘述性知識(shí)。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城的最小費(fèi)用路線。城市之間的城的最小費(fèi)用路線。城市之間的交通費(fèi)用標(biāo)在相應(yīng)的聯(lián)線上。建立產(chǎn)生式系統(tǒng)。交通費(fèi)用標(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ù)庫(kù)全局?jǐn)?shù)據(jù)庫(kù)（已訪問過的城鎮(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)一次，且費(fèi)用最少。他所有城鎮(zhèn)一次，且費(fèi)用最少。（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ī)則動(dòng)作動(dòng)作條件條件R1下一步到下一步到A系列中包含所有城鎮(zhèn)時(shí)可用系列中包含所有城鎮(zhèn)時(shí)可用R2下一步到下一步到B每條規(guī)則只能使用一次，即每條規(guī)則只能使用一次，即序列中已有某城鎮(zhèn)時(shí)，不能序列中已有某城鎮(zhèn)時(shí)，不能再使用相應(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í)組織的計(jì)算機(jī)軟件相比具有特點(diǎn)：與一般分級(jí)組織的計(jì)算機(jī)軟件相比具有特點(diǎn)：全局?jǐn)?shù)據(jù)庫(kù)的內(nèi)容可以為所有規(guī)則所訪問，沒有任全局?jǐn)?shù)據(jù)庫(kù)

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

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

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

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

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

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

25、則推理成功，結(jié)束。步步3 取出目標(biāo)鏈中第一個(gè)目標(biāo)，用動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí)取出目標(biāo)鏈中第一個(gè)目標(biāo)，用動(dòng)態(tài)數(shù)據(jù)庫(kù)中的事實(shí)同其匹配，若匹配成功，轉(zhuǎn)步同其匹配，若匹配成功，轉(zhuǎn)步2。步步4 用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配用規(guī)則集中的各規(guī)則的結(jié)論同該目標(biāo)匹配，若匹配成功，則將第一個(gè)匹配成功且未用過的規(guī)則的前提作成功，則將第一個(gè)匹配成功且未用過的規(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é)點(diǎn)：一個(gè)產(chǎn)生式的前提包含了幾個(gè)事實(shí)，合取，與節(jié)點(diǎn)：一個(gè)產(chǎn)生式的前提包含了幾個(gè)事實(shí)，那么它的結(jié)論對(duì)應(yīng)這些事實(shí)的合取。那么它的結(jié)論對(duì)應(yīng)這些事實(shí)的合取。析取，或節(jié)點(diǎn)：一個(gè)結(jié)論可以由多個(gè)產(chǎn)生式得到，析取，或節(jié)點(diǎn)：一個(gè)結(jié)論可以由多個(gè)產(chǎn)生式得到，則這個(gè)結(jié)論對(duì)應(yīng)這些產(chǎn)生式的析取。則這個(gè)結(jié)論對(duì)應(yīng)這些產(chǎn)生式的析取。每個(gè)產(chǎn)生式系統(tǒng)都

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

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

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

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

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

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

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

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

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