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

1、第第6 6章章 基于產(chǎn)生式規(guī)則的機器推理基于產(chǎn)生式規(guī)則的機器推理2022-4-22人工智能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-4-22人工智能36.1.16.1.1產(chǎn)生式規(guī)則（產(chǎn)生式規(guī)則（1）產(chǎn)生式（產(chǎn)生式（ProductionProduction）-1943-1943年美國數(shù)學(xué)家年美國數(shù)學(xué)家PostPost在計算在計算形式體系中提出的術(shù)語形式體系中提出的術(shù)語產(chǎn)生式產(chǎn)生式一詞從波斯特機中借用來的。波斯特機是一一詞從波斯特機中借用來的。波斯特機是一種自動機，它是根據(jù)串替換規(guī)則提出的一種計算模

2、種自動機，它是根據(jù)串替換規(guī)則提出的一種計算模型。型。產(chǎn)生式就是邏輯蘊含式、推理規(guī)則以及各種關(guān)系產(chǎn)生式就是邏輯蘊含式、推理規(guī)則以及各種關(guān)系（包含經(jīng)驗性聯(lián)想）的一種邏輯抽象。（包含經(jīng)驗性聯(lián)想）的一種邏輯抽象。 產(chǎn)生式系統(tǒng)在形式上很簡單，但在一定意義上模仿產(chǎn)生式系統(tǒng)在形式上很簡單，但在一定意義上模仿了人類思考的過程。了人類思考的過程。人工智能使用產(chǎn)生式的理由人工智能使用產(chǎn)生式的理由為什么要采用產(chǎn)生式系統(tǒng)作為人工智能系統(tǒng)的為什么要采用產(chǎn)生式系統(tǒng)作為人工智能系統(tǒng)的主要結(jié)構(gòu)呢？兩點理由：主要結(jié)構(gòu)呢？兩點理由：用產(chǎn)生式系統(tǒng)結(jié)構(gòu)求解問題的過程用產(chǎn)生式系統(tǒng)結(jié)構(gòu)求解問題的過程和人類求解問題和人類求解問題時的思維過

3、程相似時的思維過程相似，因而可以用來模擬人類求解問，因而可以用來模擬人類求解問題時的思維過程。題時的思維過程?？砂旬a(chǎn)生式系統(tǒng)可把產(chǎn)生式系統(tǒng)作為人工智能系統(tǒng)的基本結(jié)構(gòu)單元作為人工智能系統(tǒng)的基本結(jié)構(gòu)單元或基本模式看待或基本模式看待，就像積木中的積木塊一樣，因而，就像積木中的積木塊一樣，因而研究產(chǎn)生式系統(tǒng)的基本問題就具有一般意義。研究產(chǎn)生式系統(tǒng)的基本問題就具有一般意義。2022-4-22人工智能4產(chǎn)生式規(guī)則的界定及內(nèi)容產(chǎn)生式規(guī)則的界定及內(nèi)容產(chǎn)生式規(guī)則是產(chǎn)生式系統(tǒng)的主體，是產(chǎn)生式系統(tǒng)知識產(chǎn)生式規(guī)則是產(chǎn)生式系統(tǒng)的主體，是產(chǎn)生式系統(tǒng)知識表示的核心。故直接將產(chǎn)生式稱為表示的核心。故直接將產(chǎn)生式稱為產(chǎn)生式規(guī)則

4、產(chǎn)生式規(guī)則。一般產(chǎn)生式的結(jié)構(gòu)可表示為自然語言形式，一般產(chǎn)生式的結(jié)構(gòu)可表示為自然語言形式，“原因原因-結(jié)結(jié)果果”，“條件條件-結(jié)論結(jié)論”，“前提前提-操作操作”，“事實事實-進展進展”，“情況情況-行為行為”等結(jié)構(gòu)都可歸結(jié)為產(chǎn)生式的知識表等結(jié)構(gòu)都可歸結(jié)為產(chǎn)生式的知識表達形式。達形式。2022-4-22人工智能5可歸結(jié)為產(chǎn)生式的表達形式可歸結(jié)為產(chǎn)生式的表達形式例：例：（1）天下雨，地上濕。（）天下雨，地上濕。（“原因原因-結(jié)果結(jié)果”）（2）如果把冰加熱到零攝氏度以上，冰會融化為水。（）如果把冰加熱到零攝氏度以上，冰會融化為水。（“條件條件-結(jié)論結(jié)論”）（3）夜來風(fēng)雨聲，花落知多少。（）夜來風(fēng)雨聲，

5、花落知多少。（“事實事實-進展進展”）（4）若能找到一根合適的杠桿，就能撬超那座山。（）若能找到一根合適的杠桿，就能撬超那座山。（“前提前提-操作操作”）（5）剛才開機了，意味著發(fā)出了捕獲目標(biāo)圖像的信號。（）剛才開機了，意味著發(fā)出了捕獲目標(biāo)圖像的信號。（“情況情況-行為行為”）2022-4-22人工智能62022-4-22人工智能76.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（2）產(chǎn)生式的一般形式為：產(chǎn)生式的一般形式為：A A B B（或（或 IF IF A A ThenThen B B）A A是產(chǎn)生式的前提（前件），用于指出該產(chǎn)生式是是產(chǎn)生式的前提（前件），用于指出該產(chǎn)生式是否可用的條件否可用的

6、條件B B是一組結(jié)論或操作（后件），用于指出當(dāng)前提是一組結(jié)論或操作（后件），用于指出當(dāng)前提A A指指示的條件滿足時，應(yīng)得出的結(jié)論或應(yīng)執(zhí)行的操作。示的條件滿足時，應(yīng)得出的結(jié)論或應(yīng)執(zhí)行的操作。一個產(chǎn)生式規(guī)則就是一條知識，用產(chǎn)生式不僅可以進一個產(chǎn)生式規(guī)則就是一條知識，用產(chǎn)生式不僅可以進行推理，也可以實現(xiàn)操作。行推理，也可以實現(xiàn)操作。2022-4-22人工智能86.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）例例三個聰明人問題。古代有個國王想知道他的三三個聰明人問題。古代有個國王想知道他的三個大臣中誰最聰明，就在他們每個人前額上都個大臣中誰最聰明，就在他們每個人前額上都畫了一個點，他們都能看到別人

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

8、每個人對人對問題問題都都只有部分了解，無法直接求解只有部分了解，無法直接求解。但。但在推理過程中每個人又可以從別人那里獲得新在推理過程中每個人又可以從別人那里獲得新的知識，重新進行推理。可以用產(chǎn)生式來表達的知識，重新進行推理?？梢杂卯a(chǎn)生式來表達推理過程中所用到的各種知識。推理過程中所用到的各種知識。2022-4-22人工智能106.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)集合

9、全部可能的狀態(tài)集合(可能界可能界PW0)：(0,0,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-4-22人工智能116.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）排除過程：排除過程：第一次，大臣只知道至少有一個人是白點，排除第一次，大臣只知道至少有一個人是白點，排除X0=(0,0,0)狀態(tài)。狀態(tài)。這時如果有人看到兩個非白點，根這時如果有人看到兩個非白點，根據(jù)排除的狀態(tài)可推知自己是白點。據(jù)排除的狀態(tài)

10、可推知自己是白點。第二次大臣根據(jù)沒有一個人知道自己點顏色的事實第二次大臣根據(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-4-2

11、2人工智能126.1.16.1.1產(chǎn)生式規(guī)則產(chǎn)生式規(guī)則（例）（例）引入中介狀態(tài)并定義下述符號：引入中介狀態(tài)并定義下述符號： Si i大臣看到的大臣看到的非白點數(shù)非白點數(shù)； Wi i大臣猜出自己點的顏色否。如果他宣布大臣猜出自己點的顏色否。如果他宣布已已知道自己點的顏色，為知道自己點的顏色，為1，否則為，否則為0； nX0中中白點的個數(shù)白點的個數(shù)。 2022-4-22人工智能136.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

12、),(0,1,0),(0,1,1),(1,0,0),(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=

13、2) ;(6) (n=2) X(6) (n=2) X0 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)

14、 = (n=3); (n=2) = (n=3);(11) (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-4-22人工智能146.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

15、) =(Wi=1),(i=1,2,m,下同下同)； (3)( 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-4-22人工智能156.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-4-22人工智能16

16、6.26.2產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)6.2.16.2.1系統(tǒng)結(jié)構(gòu)系統(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-4-22人工智能176.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-4-22人工智能186.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ù)庫上的一些作用在全局?jǐn)?shù)據(jù)庫上的一些規(guī)則規(guī)則的集合的集合。每條規(guī)則都有一定的條件，若全

17、局?jǐn)?shù)據(jù)庫。每條規(guī)則都有一定的條件，若全局?jǐn)?shù)據(jù)庫中內(nèi)容滿足這些條件可調(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)中心

18、。是一個動態(tài)數(shù)據(jù)結(jié)構(gòu)，用來存放初始一個動態(tài)數(shù)據(jù)結(jié)構(gòu)，用來存放初始事實數(shù)據(jù)、中間事實數(shù)據(jù)、中間結(jié)果和最后結(jié)果結(jié)果和最后結(jié)果。對應(yīng)敘述性知識。對應(yīng)敘述性知識。2022-4-22人工智能196.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-4-22人工智能206.2.16.2.1系統(tǒng)結(jié)

19、構(gòu)（系統(tǒng)結(jié)構(gòu)（4 4）（1）全局?jǐn)?shù)據(jù)庫全局?jǐn)?shù)據(jù)庫（已訪問過的城鎮(zhèn)名稱序列）。（已訪問過的城鎮(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)?，F(xiàn)。（2）規(guī)則集規(guī)則集如下表所示如下表所示。（3）推理推理： （A） （AB） （ABE） （4）終止條件終止條件序列始于序列始于A，終止于，終止于A，其中包含其，其中包含其他所有城鎮(zhèn)一次，且費用最少。他所有城鎮(zhèn)一次，且費用最少。（5）各種各種搜索策略搜索策略選擇規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)選擇

20、規(guī)則，如廣度優(yōu)先搜索，最好優(yōu)先搜索等。先搜索等。 R2R52022-4-22人工智能216.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-4-22人工智能226.2.16.2.1系統(tǒng)結(jié)構(gòu)（系統(tǒng)結(jié)構(gòu)（6 6）與一般分級組織的計算機軟件相比具有特點：與一般分級組織的計算機軟件

21、相比具有特點：全局?jǐn)?shù)據(jù)庫的內(nèi)容可以為所有規(guī)則所訪問，沒有任全局?jǐn)?shù)據(jù)庫的內(nèi)容可以為所有規(guī)則所訪問，沒有任何部分是專為某一規(guī)則建立的，這種特性便于模仿何部分是專為某一規(guī)則建立的，這種特性便于模仿智能行為中的智能行為中的強數(shù)據(jù)驅(qū)動強數(shù)據(jù)驅(qū)動。規(guī)則本身規(guī)則本身不調(diào)用其他規(guī)則不調(diào)用其他規(guī)則。規(guī)則之間的聯(lián)系必須通。規(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-4-22人工智能236.2.26.2.2產(chǎn)生式系統(tǒng)的產(chǎn)生式系統(tǒng)的運行過程

22、（運行過程（1）推理機一次運行過程推理機一次運行過程從規(guī)則庫中取出一條規(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-4-22人工智能246.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)條件往往要實際的產(chǎn)生式系統(tǒng)，目標(biāo)條件往往要經(jīng)過多步推理經(jīng)過多步推理才能滿足或者證明問題無解。才能滿足或者證明問題無

23、解。產(chǎn)生式系統(tǒng)的運行過程就是產(chǎn)生式系統(tǒng)的運行過程就是推理機不斷的運用規(guī)則推理機不斷的運用規(guī)則庫中的規(guī)則庫中的規(guī)則，作用于動態(tài)數(shù)據(jù)庫作用于動態(tài)數(shù)據(jù)庫，不斷進行推理并，不斷進行推理并不斷檢測目標(biāo)條件是否被滿足的過程。不斷檢測目標(biāo)條件是否被滿足的過程。產(chǎn)生式系統(tǒng)運行過程是從初始事實出發(fā)，尋求到達產(chǎn)生式系統(tǒng)運行過程是從初始事實出發(fā)，尋求到達目標(biāo)條件的通路的過程。所以也是一個目標(biāo)條件的通路的過程。所以也是一個搜索搜索的過程。的過程。例例1 一個簡單的例子一個簡單的例子問題：設(shè)字符轉(zhuǎn)換規(guī)則ABCACDBCGBEFDE已知：A，B求：F2022-4-22人工智能25例例1 一個簡單的例子（一個簡單的例子（1

24、）一、綜合數(shù)據(jù)庫x，其中x為字符二、規(guī)則集1，IFABTHENC2，IFACTHEND3，IFBCTHENG4，IFBETHENF5，IFDTHENE2022-4-22人工智能26三、控制策略順序排隊四、初始條件A，B五、結(jié)束條件Fx例例1 一個簡單的例子（一個簡單的例子（2）2022-4-22人工智能27綜合數(shù)據(jù)庫可觸發(fā)規(guī)則 被觸發(fā)規(guī)則A，B（1）（1）A，B，C（2）（3） （2）A，B，C，D（3）（5） （3）A，B，C，D，G（5）（5）A，B，C，D，G，E（4）（4）A，B，C，D，G，E，F(xiàn)求解過程28問題：問題：N個傳教士，個傳教士，N個野人，一條船，可同時乘坐個野人，一條船

25、，可同時乘坐 k 個人，要求在任何時刻，在河的兩岸及船上，傳教個人，要求在任何時刻，在河的兩岸及船上，傳教士人數(shù)不能少于野人的人數(shù)。士人數(shù)不能少于野人的人數(shù)。問：問：如何過河。（給出綜合數(shù)據(jù)庫、初始狀態(tài)和如何過河。（給出綜合數(shù)據(jù)庫、初始狀態(tài)和目標(biāo)狀態(tài)、規(guī)則集合的形式化描述）目標(biāo)狀態(tài)、規(guī)則集合的形式化描述）以以N=3，k=2為例求解。為例求解。例例2：傳教士與野人問題（：傳教士與野人問題（M-C問題）問題）29例例2：M-C問題（續(xù)問題（續(xù)1） L R L R m 3 0 m 0 3 c 3 0 c 0 3 B 1 0 B 0 1nL 左岸 R 右岸 B 1（有船）、0（無船）30例例2：M-C

26、問題（續(xù)問題（續(xù)2）1，綜合數(shù)據(jù)庫，綜合數(shù)據(jù)庫 （m, c, b)，其中：其中：0m, c3, b 0, 12，初始狀態(tài)，初始狀態(tài) （3，3，1） ( 簡化，只描述左岸的情況即可簡化，只描述左岸的情況即可 )3，目標(biāo)狀態(tài)（結(jié)束狀態(tài)），目標(biāo)狀態(tài)（結(jié)束狀態(tài)） （0，0，0）31例例2：M-C問題（續(xù)問題（續(xù)3 ）4，規(guī)則集，規(guī)則集IF (m, c, 1) THEN (m-1, c, 0)IF (m, c, 1) THEN (m, c-1, 0) IF (m, c, 1) THEN (m-1, c-1, 0)IF (m, c, 1) THEN (m-2, c, 0)IF (m, c, 1) THEN

27、 (m, c-2, 0)32IF (m, c, 0) THEN (m+1, c, 1)IF (m, c, 0) THEN (m, c+1, 1)IF (m, c, 0) THEN (m+1, c+1, 1)IF (m, c, 0) THEN (m+2, c, 1)IF (m, c, 0) THEN (m, c+2, 1)例例2：M-C問題（續(xù)問題（續(xù)4）例例2：N=5，k=3為例為例2022-4-22人工智能33例例3：猴子摘香蕉問題：猴子摘香蕉問題一個房間里，天花板上掛有一串香蕉，有一只猴子可在房間里任意活動（到一個房間里，天花板上掛有一串香蕉，有一只猴子可在房間里任意活動（到處走動，推移箱

28、子，攀登箱子等）。設(shè)房間里還有一只可被猴子移動的箱子處走動，推移箱子，攀登箱子等）。設(shè)房間里還有一只可被猴子移動的箱子，且猴子登上箱子時才能摘到香蕉，問猴子在某一狀態(tài)下（設(shè)猴子位置為，且猴子登上箱子時才能摘到香蕉，問猴子在某一狀態(tài)下（設(shè)猴子位置為c，箱子位置為，箱子位置為b，香蕉位置為，香蕉位置為a），如何行動可摘取到香蕉。），如何行動可摘取到香蕉。2022-4-22人工智能34nanbnc例例3：猴子摘香蕉問題：猴子摘香蕉問題2022-4-22人工智能351，綜合數(shù)據(jù)庫，綜合數(shù)據(jù)庫定義定義5元組（元組（M, B, Box, On, H）M：猴子的位置：猴子的位置B：香蕉的位置：香蕉的位置Bo

29、x：箱子的位置：箱子的位置On=0：猴子在地板上：猴子在地板上On=1：猴子在箱子上：猴子在箱子上H=0：猴子沒有抓到香蕉：猴子沒有抓到香蕉H=1：猴子抓到了香蕉：猴子抓到了香蕉例例4：量水問題：量水問題對量水問題給出產(chǎn)生式系統(tǒng)描述，并畫出狀態(tài)對量水問題給出產(chǎn)生式系統(tǒng)描述，并畫出狀態(tài)空間圖?？臻g圖。 有兩個無刻度標(biāo)志的水壺，分別可有兩個無刻度標(biāo)志的水壺，分別可裝裝5升和升和2升的水。設(shè)另有一水缸，可用來向水升的水。設(shè)另有一水缸，可用來向水壺灌水或倒出水，兩個水壺之間，水也可以相壺灌水或倒出水，兩個水壺之間，水也可以相互傾灌。已知互傾灌。已知5升壺為滿壺，升壺為滿壺，2升壺為空壺，問升壺為空壺，

30、問如何通過倒水或灌水操作，使能在如何通過倒水或灌水操作，使能在2升的壺中升的壺中量出一升的水來。量出一升的水來。2022-4-22人工智能36例例4：量水問題：量水問題2022-4-22人工智能372022-4-22人工智能386.2.36.2.3控制策略與常用算法控制策略與常用算法（1 1）推理方式推理方式正向推理正向推理 從初始事實數(shù)據(jù)出發(fā)，正向使用規(guī)則從初始事實數(shù)據(jù)出發(fā)，正向使用規(guī)則進行推理，朝目標(biāo)方向前進。又稱為前向推理、正進行推理，朝目標(biāo)方向前進。又稱為前向推理、正向鏈、數(shù)據(jù)驅(qū)動的推理。向鏈、數(shù)據(jù)驅(qū)動的推理。反向推理反向推理從目標(biāo)出發(fā)，反向使用規(guī)則進行推理，從目標(biāo)出發(fā)，反向使用規(guī)則進

31、行推理，朝初始事實或數(shù)據(jù)方向前進。又稱反向推理、反向朝初始事實或數(shù)據(jù)方向前進。又稱反向推理、反向鏈、目標(biāo)驅(qū)動的推理。鏈、目標(biāo)驅(qū)動的推理。2022-4-22人工智能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ī)則集

32、。將匹配成功的規(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-4-22人工智能406.2.36.2.3控制策略與常用算法（控制策略與常用算法（3 3）若把若把動態(tài)數(shù)據(jù)庫動態(tài)數(shù)據(jù)庫的的每一個狀態(tài)每一個狀態(tài)作為一個作為一個節(jié)點節(jié)點的話，則的話，則上述推理過程就是一個從初始狀態(tài)到目標(biāo)狀態(tài)的上述推理過程就是一個從初始狀態(tài)到目標(biāo)狀態(tài)的狀態(tài)狀態(tài)圖搜索圖搜索過程。過程。如果把動態(tài)數(shù)據(jù)庫中的如果把動態(tài)數(shù)據(jù)庫中的每一

33、個事實每一個事實/數(shù)據(jù)數(shù)據(jù)作為一個作為一個節(jié)點節(jié)點的話，則上述推理過程就是一個自底向上的的話，則上述推理過程就是一個自底向上的與或樹搜與或樹搜索索過程。過程。2022-4-22人工智能416.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)鏈為空，則推理成功，結(jié)束。步步3 取出目標(biāo)鏈中第一個目標(biāo)，用動態(tài)數(shù)據(jù)庫中的事實取出目標(biāo)鏈中第一個目標(biāo)，用動態(tài)數(shù)據(jù)庫中的事實同其匹配，若匹配成功，轉(zhuǎn)步同其匹配，若匹

34、配成功，轉(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)的父目標(biāo)移回目標(biāo)鏈，取代該目標(biāo)及其兄弟目標(biāo)，轉(zhuǎn)步弟目標(biāo)，轉(zhuǎn)步3。2022-4-22人工智能426.2.36.2.3控制策略與常用算法控制策略與常用算法（5

35、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)都隱含著許多這樣的與或樹。每個產(chǎn)生式系統(tǒng)都隱含著許多這樣的與或樹。2022-4-22人工智能436.2.36.2.3控制策略與常用算法控制策略與常用算法（

36、6 6）F1P1F3F4F5F6BCDAP2P3P4P5F2事實中介事實B、C、D產(chǎn)生式規(guī)則P1、P2、P3、P4、P5結(jié)論2022-4-22人工智能446.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 該動物有奶該動物有奶 THEN THEN 該動物是哺乳動物該動物是哺乳動物r3r3： IF IF 該動物有羽毛該動物有羽毛 THEN THEN 該動物是鳥

37、該動物是鳥r4r4： IF IF 該動物會飛該動物會飛 AND AND 會下蛋會下蛋 THEN THEN 該動物是鳥該動物是鳥r5r5： IF IF 該動物吃肉該動物吃肉 THEN THEN 該動物是食肉動物該動物是食肉動物r6r6： IF IF 該動物有犬齒該動物有犬齒 AND AND 有爪有爪 AND AND 眼盯前方眼盯前方 THEN THEN 該動物是食肉動物動物該動物是食肉動物動物2022-4-22人工智能456.2.36.2.3控制策略與常用算法控制策略與常用算法（8 8）r7r7： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 有蹄有蹄 THEN THEN 該動物

38、是有蹄類動物該動物是有蹄類動物r8r8： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 是嚼反芻動物是嚼反芻動物 THEN THEN 該動物是有蹄動物該動物是有蹄動物r9r9： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 是食肉動物是食肉動物 AND AND 是黃褐色是黃褐色 AND AND 身上有暗斑點身上有暗斑點 THEN THEN 該動物是該動物是金錢豹金錢豹 r10r10： IF IF 該動物是哺乳動物該動物是哺乳動物 AND AND 是食肉動物是食肉動物 AND AND 是黃褐色是黃褐色 AND AND 身上有黑色條紋身上有黑色條紋 THEN THE

39、N 該動物是該動物是虎虎2022-4-22人工智能466.2.36.2.3控制策略與常用算法控制策略與常用算法（9 9）r11r11： IF IF 該動物是有蹄類動物該動物是有蹄類動物 AND AND 有長脖子有長脖子 AND AND 有長腿有長腿 AND AND 身上有暗斑點身上有暗斑點 THEN THEN 該動物是該動物是長頸鹿長頸鹿 r12r12： IF IF 該動物有蹄類動物該動物有蹄類動物 AND AND 身上有黑色條紋身上有黑色條紋 THEN THEN 該動物是該動物是斑馬斑馬r13r13： IF IF 該動物是鳥該動物是鳥 AND AND 有長脖子有長脖子 AND AND 有長腿

40、有長腿 AND AND 不會飛不會飛 AND AND 有黑白二色有黑白二色 THEN THEN 該動物是該動物是鴕鳥鴕鳥2022-4-22人工智能476.2.36.2.3控制策略與常用算法控制策略與常用算法（1010）r14r14： IF IF 該動物是鳥該動物是鳥 AND AND 會游泳會游泳 AND AND 不會飛不會飛 AND AND 有黑白二色有黑白二色 THEN THEN 該動物是該動物是企鵝企鵝r15r15：IF IF 該動物是鳥該動物是鳥 AND AND 善飛善飛 AND AND 不怕風(fēng)浪不怕風(fēng)浪 THEN THEN 該動物是該動物是海燕海燕老虎老虎黃褐色黃褐色有黑色條紋有黑色條

41、紋食肉動物食肉動物哺乳動物哺乳動物有毛發(fā)有毛發(fā)有奶有奶吃肉吃肉有爪有爪有犬齒有犬齒目 盯 前目 盯 前方方金錢豹金錢豹有 黑 色 斑有 黑 色 斑點點長頸鹿長頸鹿有蹄動物有蹄動物有蹄有蹄長腿長腿長脖子長脖子有 暗 斑有 暗 斑點點圖圖6-4 6-4 動物分類產(chǎn)生式規(guī)則集所形成的部分推理網(wǎng)絡(luò)動物分類產(chǎn)生式規(guī)則集所形成的部分推理網(wǎng)絡(luò)2022-4-22人工智能496.2.36.2.3控制策略與常用算法控制策略與常用算法（1212）初始事實：初始事實： f1 f1：某動物有毛發(fā)。：某動物有毛發(fā)。 f2f2：吃肉。：吃肉。 f3f3：黃褐色。：黃褐色。 f4f4：有黑色條紋：有黑色條紋目標(biāo)條件為：該動物

42、為什么？目標(biāo)條件為：該動物為什么？2022-4-22人工智能506.2.36.2.3控制策略與常用算法控制策略與常用算法（1313）哺乳類食肉動物有毛發(fā)食肉黃褐色有黑色條紋老虎正向推理推理樹r2r6r102022-4-22人工智能516.2.36.2.3控制策略與常用算法控制策略與常用算法（1414）哺乳類食肉動物有毛發(fā)有奶黃褐色有黑色條紋老虎反向推理推理樹目盯前方有毛發(fā)有爪吃肉r10r5r1r2r6例例6.2 使用反向推理算法使用反向推理算法2022-4-22人工智能526.2.36.2.3控制策略與常用算法（控制策略與常用算法（1515）3 沖突消解策略沖突消解策略給定一組事實之后可用匹配

43、技術(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)生式分成若干層或組，按一定特征進行分層搜索。搜索。過濾匹配。邊匹配邊過濾匹配。邊匹配邊 按某些附加特征或參數(shù)對可用產(chǎn)生式進按某些附加特征或參數(shù)對可用產(chǎn)生式進行精選。行

44、精選。2022-4-22人工智能536.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。