智能控制-第三章 搜索推理技術(shù)ppt課件

1、第三章 搜索推理技術(shù)3.6 產(chǎn)生式系統(tǒng)3.7 系統(tǒng)組織技術(shù)3.8 小結(jié)3.1 圖搜索戰(zhàn)略3.2 盲目搜索3.3 啟發(fā)式搜索3.4 消解原理3.5 規(guī)那么演繹系統(tǒng)3.1 圖搜索戰(zhàn)略 v圖搜索控制戰(zhàn)略一種在圖中尋覓途徑的方法。圖中每個節(jié)點對應(yīng)一個形狀，每條連線對應(yīng)一個操作符。這些節(jié)點和連線又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)那么來標(biāo)志。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)那么序列問題就等價于求得圖中的一條途徑問題。v圖搜索過程圖搜索的普經(jīng)過程如下：1建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN 的未擴展節(jié)點表中。2建立一個叫做CLOSED的已擴展節(jié)點表，其初始為空表。3LOOP：假設(shè)OP

2、EN表是空表，那么失敗退出。4選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點n。5假設(shè)n為一目的節(jié)點，那么有解并勝利退出，此解是追蹤圖G中沿著指針從n到S這條途徑而得到的(指針將在第7步中設(shè)置)。3.1 圖搜索戰(zhàn)略6擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。7對那些未曾在G中出現(xiàn)過的M成員設(shè)置一個通向n的指針。把M的這些成員加進OPEN表。對曾經(jīng)在OPEN或CLOSED表上的每一個M成員，確定能否需更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定能否需求更改圖G中通向它的每個后裔節(jié)點

3、的指針方向。8按某一恣意方式或按某個探試值，重排OPEN表。9GO LOOP。3.1 圖搜索戰(zhàn)略開場開場把把S放入放入OPEN表表OPEN表為空表？表為空表？把第一個節(jié)點把第一個節(jié)點(n)從從OPEN表移至表移至CLOSED表表n為目的節(jié)點嗎？為目的節(jié)點嗎？把把n的后繼節(jié)點放入的后繼節(jié)點放入OPEN表的表的末端，提供前往節(jié)點末端，提供前往節(jié)點n的指針的指針修正指針方向修正指針方向重排重排OPEN表表失敗失敗勝利勝利圖圖3.1 3.1 圖搜索過程框圖圖搜索過程框圖是是是是否否否否3.1 圖搜索戰(zhàn)略(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)3.2 盲目搜

4、索 盲目搜索又叫做無信息搜索，普通只適用于求解比較簡單的問題。特點：不需重排OPEN表種類：寬度優(yōu)先、深度優(yōu)先、等代價搜索等。3.2.1 寬度優(yōu)先搜索v 定義 以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。 特點： 一種高代價搜索，但假設(shè)有解存在，那么必能找到它。v算法1把起始節(jié)點放到OPEN表中(假設(shè)該起始節(jié)點為一目的節(jié)點，那么求得一個解答)。2假設(shè)OPEN是個空表，那么沒有解，失敗退出；否那么繼續(xù)。3把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。4擴展節(jié)點n。假設(shè)沒有后繼節(jié)點，那么轉(zhuǎn)向上述第(2)步。5把n的一切后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)

5、點回到n的指針。6假設(shè)n的任一個后繼節(jié)點是個目的節(jié)點，那么找到一個解答，勝利退出；否那么轉(zhuǎn)向第(2)步。3.2 盲目搜索開場開場把把S放入放入OPEN表表OPEN表為空表？表為空表？把第一個節(jié)點把第一個節(jié)點(n)從從OPEN表移至表移至CLOSED表表能否有后繼節(jié)點能否有后繼節(jié)點為目的節(jié)點？為目的節(jié)點？擴展擴展n，把，把n的后繼節(jié)點放入的后繼節(jié)點放入OPEN表的末端，提供前往節(jié)點表的末端，提供前往節(jié)點n的指針的指針失敗失敗勝利勝利圖圖3.2 3.2 寬度優(yōu)先算法框圖寬度優(yōu)先算法框圖是是否否是是否否3.2 盲目搜索v 例子八數(shù)碼難題8-puzzle problem 123845671238456

6、7目的形狀初始形狀規(guī)定：將棋子移入空格的順序為：從空格左邊開場順時針旋轉(zhuǎn)。不許斜向挪動，也不前往先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解目的節(jié)點。3.2 盲目搜索1238456712384123845674123856712 384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹13456123845671238456712384567123845671 238456723242526271236782212

7、384567123845671 238456712 3845671238456712384567123845671415161718192021123845673.2 盲目搜索3.2.2 深度優(yōu)先搜索v 定義 首先擴展最新產(chǎn)生的(即最深的)節(jié)點。v 算法 防止搜索過程沿著無益的途徑擴展下去，往往給出一個節(jié)點擴展的最大深度深度界限。 與寬度優(yōu)先搜索算法最根本的不同在于：將擴展的后繼節(jié)點放在OPEN表的前端。3.2 盲目搜索深度優(yōu)先搜索表示圖SLOMFPQNFFF3.2.3 等代價搜索v 定義 是寬度優(yōu)先搜索的一種推行，不是沿著等長是寬度優(yōu)先搜索的一種推行，不是沿著等長度途徑斷層進展擴展，而是沿著

8、等代價途徑斷層度途徑斷層進展擴展，而是沿著等代價途徑斷層進展擴展。進展擴展。 搜索樹中每條銜接弧線上的有關(guān)代價搜索樹中每條銜接弧線上的有關(guān)代價, ,表表示時間、間隔等破費。示時間、間隔等破費。 v 算法 在等價搜索算法中，把從節(jié)點i到其后續(xù)節(jié)點j的銜接弧線代價記為c(i,j),把從起始節(jié)點S到任一節(jié)點i的途徑代價記為g(i)。在搜索樹上，假設(shè)g(i)也是從起始節(jié)點S到節(jié)點i的最少代價途徑上的代價。等代價搜索方法以g(i)的遞增順序擴展其節(jié)點，其算法如下：3.2 盲目搜索開場把把S S放入放入OPENOPEN表表OPEN表為空表？表為空表？把具有最小g(i)值的節(jié)點i從OPEN表移至CLOSED

9、表能否有后繼節(jié)點為目的節(jié)點？失敗勝利圖圖3.2 3.2 等代價搜索算法框等代價搜索算法框圖圖是是否否是是否否令令g(s)=0S S能否目的節(jié)點？能否目的節(jié)點？是是勝利擴展i，計算其后繼節(jié)點j的g(j)=g(i)+c(i,j)，并把后繼節(jié)點j放入OPEN表否否3.2 盲目搜索圖圖3.2 3.2 等代價搜索算法框等代價搜索算法框圖圖3.3 啟發(fā)式搜索(heuristically search)v特點：重排OPEN表，選擇最有希望的節(jié)點加以擴展v種類：有序搜索、A*算法等3.3.1 啟發(fā)式搜索戰(zhàn)略和估價函數(shù)v盲目搜索能夠帶來“組合爆炸v啟發(fā)式信息 用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。v啟發(fā)式搜

10、索: 利用啟發(fā)信息的搜索方法。v估價函數(shù)估算節(jié)點“希望程度的度量 為獲得某些節(jié)點“希望的啟發(fā)信息，提供一個評定侯選擴展節(jié)點的方法，以便確定哪個節(jié)點最有能夠在通向目的的最正確途徑上 。 f(n)表示節(jié)點n的估價函數(shù)值 v運用節(jié)點“希望程度估價函數(shù)值重排OPEN表3.3.2 有序搜索v本質(zhì) 選擇選擇OPENOPEN表上具有最小表上具有最小f f值的節(jié)點最有希值的節(jié)點最有希望的節(jié)點作為下一個要擴展的節(jié)點。望的節(jié)點作為下一個要擴展的節(jié)點。3.3 啟發(fā)式搜索開場開場把把S放入放入OPEN表，表，計算估價函數(shù)計算估價函數(shù) f (s)OPEN表為空表？表為空表？選取選取OPEN表中表中f值最小的節(jié)點值最小的

11、節(jié)點i放入放入CLOSED表表i為目的節(jié)點嗎？為目的節(jié)點嗎？擴展擴展i，得后繼節(jié)點，得后繼節(jié)點j，計算，計算f(j)，提供前往，提供前往節(jié)點節(jié)點i的指針，利用的指針，利用f(j)對對OPEN表重新排表重新排序，調(diào)整親子關(guān)系及指針序，調(diào)整親子關(guān)系及指針失敗失敗勝利勝利圖圖3.9 3.9 有序搜索算法框圖有序搜索算法框圖是是否否是是否否v算法3.3 啟發(fā)式搜索v 例子八數(shù)碼難題8-puzzle problem12384567目的形狀12384567初始形狀八數(shù)碼難題的有序搜索樹見以下圖： f(n) = d(n)+W(n) d(n): 搜索樹中節(jié)點n的深度； W(n): 對應(yīng)于節(jié)點n的數(shù)據(jù)庫中錯放的

12、棋子個數(shù)3.3 啟發(fā)式搜索564312384567123845671238456765561238456712 3845675712384567123845677813245671 238456712384567557圖3.10 八數(shù)碼難題的有序搜索樹123845671238456712384567466257112384647 5 3.3 啟發(fā)式搜索3.3.3 A*算法v估價函數(shù)的定義：對節(jié)點n定義f*(n)=g*(n)+h*(n) ,表示從S開場約束經(jīng)過節(jié)點n的一條最正確途徑的代價。希望估價函數(shù)f 定義為：f(n)=g(n)+h(n) g是g*的估計 ，h是h*的估計vA*算法的定義：定義

13、1 在GRAPHSEARCH過程中，假設(shè)第8步的重排OPEN表是根據(jù)f(x)=g(x)+h(x)進展的，那么稱該過程為A算法。v 定義2 在A算法中，假設(shè)對一切的x存在h(x)h*(x),那么稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。v 定義3 采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?.3 啟發(fā)式搜索(1) 把S放入OPEN表，記 f=h ，令CLOSED為空表。(2) 反復(fù)以下過程，直至找到目的節(jié)點止。假設(shè)OPEN為空表，那么宣告失敗。(3) 選取OPEN表中未設(shè)置過的具有最小f值的節(jié)點為最正確節(jié)點BESTNODE

14、，并 把它放入CLOSED表。(4) 假設(shè)BESTNODE為一目的節(jié)點，那么勝利求得一解。(5) 假設(shè)BESTNODE不是目的節(jié)點，那么擴展之，產(chǎn)生后繼節(jié)點SUCCSSOR。(6) 對每個SUCCSSOR進展以下過程： (a) 建立從SUCCSSOR前往BESTNODE的指針。 (b) 計算g(SUC)=g(BES)+k(BES,SUC)。 (c) 假設(shè)SUCCSSOROPEN，那么稱此節(jié)點為OLD，并把它添至BESTNODE 的后繼節(jié)點表中。 (d) 比較新舊途徑代價。假設(shè)g(SUC)g(OLD),那么重新確定OLD的父輩節(jié)點 為BESTNODE，記下較小代價g(OLD),并修正f(OLD)

15、值。 (e) 假設(shè)至OLD節(jié)點的代價較低或一樣，那么停頓擴展節(jié)點。 (f) 假設(shè)SUCCSSOR不在OPEN表中，那么看其能否在CLOSED表中。 (g) 假設(shè)SUCCSSOR在CLOSED表中，那么轉(zhuǎn)向c。 (h) 假設(shè)SUCCSSOR既不在OPEN表中，又不在CLOSED表中，那么把它放入 OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向(7)(7) 計算 f 值。(8) GO LOOPA*算法步驟：A*算法參考框圖開場開場把把S放入放入OPEN表，記表，記f=hOPEN=NIL?失敗失敗選取選取OPEN表上未設(shè)置過的具有最小表上未設(shè)置過的具有最小f值值的節(jié)點的節(jié)點BESTNODE,放

16、入放入CLOSED表中表中BESTNODE是是目的節(jié)目的節(jié)點？點？勝利勝利擴展擴展BESTNODE，產(chǎn)生，產(chǎn)生后續(xù)節(jié)點后續(xù)節(jié)點SUCCESSOR建立從建立從SUCCESSOR前往前往BESTNODE的指針的指針計算計算g(SUC)=g(BES)+k(BES,SUC)SUC屬于屬于OPEN？SUC屬于屬于CLOSED？SUC=OLD，把它添加到，把它添加到BESTNODE的后續(xù)節(jié)點表中的后續(xù)節(jié)點表中g(shù)(SUC) Q)消解式消解式 Q Q (2) 合并父輩子句父輩子句 P QP Q消解式消解式 QQ = Q(3) 重言式 父輩子句 P Q P Q P P消解式消解式 Q QP Q P Q(4) 空

17、子句(矛盾)P PNIL3.4.3 含有變量的消解式 要把消解推理規(guī)那么推行到含有變量的子句，必需找到要把消解推理規(guī)那么推行到含有變量的子句，必需找到一個作用于父輩子句的置換，使父輩子句含有互補文字。一個作用于父輩子句的置換，使父輩子句含有互補文字。v 含有變量的子句之消解式v 例子Px,f(y)Q(x)Rf(a),y Pf (f(a),zR(z，w)Q f (f(a) R(f(a)，y) R(f(y)，w) =f(f(a)/x,f(y)/z3.4 消解原理父輩子句父輩子句 消解式消解式P和和 PQ (即即PQ)QPQ和和 PQ QPQ 和和 PQQQ 和和PPP PNILPQ 和和 QR(即

18、即PQ 和和 QR) PR(即即PR)B(x) 和和 B(x)C(x)C(x)P(x)Q(x) 和和 Q(f(y)P(f(y),=f(y)/xP(x,f(y)Q(x)R(f(a),y)和和 Q(f(f(a)R(f(a),y )R(f(y),w)P(f(f(a),z)R(z,w) =f(f(a)/x,f(y)/z表 3.1 子句和消解式3.4.4 消解反演求解過程v消解反演v 給出公式集：S，目的公式：Lv否認(rèn)L，得L；v把L添加到S中去；v把新產(chǎn)生的集合L，S化成子句集；v運用消解原理，力圖推導(dǎo)出一個表示矛盾的空子句NILv 例子儲蓄問題v 前提：每個儲蓄錢的人都獲得利息。v 結(jié)論：假設(shè)沒有利

19、息，那么就沒有人去儲蓄錢3.4 消解原理(1規(guī)定原子公式：規(guī)定原子公式： S(x,y) 表示表示 “x儲蓄儲蓄y M(x) 表示表示 “x是錢是錢 I(x) 表示表示 “x是利息是利息 E(x，y) 表示表示 “x獲得獲得y(2用謂詞公式表示前提和結(jié)論：前提：(x)(y)(S(x,y)M(y)(y)(I(y)E(x,y)結(jié)論：(x)I(x) (x)(y)(M(y) S(x,y)證明：證明：3.4 消解原理把前提化為子句形：1) S(x,y)M(y)I(f(x)2) S(x,y)M(y)E(x,f(x)把結(jié)論的否認(rèn)化為子句形： 3) I(z) 4) S(a,b) 5) M(b)(3) 化為子句形

20、3.4 消解原理(4) 消解反演求空子句NIL3.4 消解原理圖3.12 儲蓄問題反演樹子句1子句3f (x)/zM(b)NIL子句5子句7子句4a/x,b/yS(x,y)M(y)子句子句6S(x,y)M(y)I(f(x)I(z)S(a,b)M(b)v反演求解過程v從反演樹求取答案步驟：v把由目的公式的否認(rèn)產(chǎn)生的每個子句添加到目的公式否認(rèn)之否認(rèn)的子句中去。v按照反演樹，執(zhí)行和以前一樣的消解，直至在根部得到某個子句止。v用根部的子句作為一個回答語句。v本質(zhì)v把一棵根部有NIL的反演樹變換為根部帶有回 答語句的一棵證明樹。3.4 消解原理“假設(shè)無論約翰假設(shè)無論約翰(John)(John)到哪里去，

21、菲多到哪里去，菲多(Fido)(Fido)也就去那里，也就去那里，那么假設(shè)約翰在學(xué)校里，菲多在哪里呢那么假設(shè)約翰在學(xué)校里，菲多在哪里呢? ? 這兩個現(xiàn)實可以解釋為以下公式集這兩個現(xiàn)實可以解釋為以下公式集S S：( (x)AT(JOHN,X)=AT(FIDO,X)x)AT(JOHN,X)=AT(FIDO,X) AT(JOHN,SCHOOL) AT(JOHN,SCHOOL) 假設(shè)我們首先證明公式(x)AT(FIDO,X)在邏輯上遵照S，然后尋求一個存在x的例，那么就能處理“菲多在哪里的問題消解反演求解方法：首先對被證明的公式加以否認(rèn)，再把這消解反演求解方法：首先對被證明的公式加以否認(rèn)，再把這個否認(rèn)

22、式附加到集個否認(rèn)式附加到集S S中去，化這個擴展集的一切成員為子句中去，化這個擴展集的一切成員為子句形，然后用消解證明這個子句集是不可滿足的。形，然后用消解證明這個子句集是不可滿足的。例子：這里要留意的是：目的公式這里要留意的是：目的公式 ( (x) AT(FIDO,x) x) AT(FIDO,x) 的否認(rèn)產(chǎn)生的否認(rèn)產(chǎn)生 ( (x)x)AT(FIDO,x)AT(FIDO,x)， 其子句方式為其子句方式為: : AT(FIDO,x) AT(FIDO,x) 目的公式否認(rèn)的子句方式為目的公式否認(rèn)的子句方式為 : : AT(FIDO,x) AT(FIDO,x) 把它添加至目的公式的否認(rèn)把它添加至目的公

23、式的否認(rèn)之否認(rèn)的子句中去，得重言式之否認(rèn)的子句中去，得重言式 AT(FIDO,x)AT(FIDO,x)AT(FIDO,x)AT(FIDO,x)；(2) 用以下圖所示的反演樹進展消解，并在根部得到子句: AT (FIDO，SCHOOL)；(3) (3) 從根部求得答案從根部求得答案AT(FIDOAT(FIDO，SCHOOL)SCHOOL)，用此子句作為回答語句。，用此子句作為回答語句。消解反演求解過程：圖 3.14 從消解求取答案例題的反演樹3.5 規(guī)那么演繹系統(tǒng)v 定義v 基于規(guī)那么的問題求解系統(tǒng)運用IfThen規(guī)那么來建立，每個if能夠與某斷言(assertion)集中的一個或多個斷言匹配。

24、有時把該斷言集稱為任務(wù)內(nèi)存，then部分用于規(guī)定放入任務(wù)內(nèi)存的新斷言。這種基于規(guī)那么的系統(tǒng)叫做規(guī)那么演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項。 3.5.1 規(guī)那么正向演繹系統(tǒng)v定義v 正向規(guī)那么演繹系統(tǒng)是從現(xiàn)實到目的進展操作的，即從情況條件到動作進展推理的，也就是從if到then的方向進展推理的。 v求解過程v現(xiàn)實表達式的與或形變換v 在基于規(guī)那么的正向演繹系統(tǒng)中，把現(xiàn)實表示為非蘊涵方式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。 不把這些現(xiàn)實化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換為叫做與或形的非蘊涵方式。3.5 規(guī)那么演繹系統(tǒng)例如，有現(xiàn)實表達式： (u

25、)(v)Q(v，u)(R(v)P(v)S(u，v)把它化為： Q(v,A)R(v)P(v)S(A,v)對變量更名規(guī)范化，使得同一變量不出如今現(xiàn)實表達式的不同主要合取式中。更名后得表達式： Q(w,A)R(v)P(v)S(A,v) 必需留意到Q(v，A)中的變量v可用新變量w替代，而合取式R(v)P(v)中的變量v卻不可更名，由于后者也出如今析取式S(A,v)中。與或形表達式是由符號和銜接的一些文字的子表達式組成的。呈與或形的表達式并不是子句形，而是接近于原始表達式方式，特別是它的子表達式不是復(fù)合產(chǎn)生的。3.5 規(guī)那么演繹系統(tǒng)v現(xiàn)實表達式的與或圖表示Q(w,A)R(v)P(v)S(A,v)Q(w

26、,A)R(v)P(v)S(A,v)R(v)P(v)S(A,v)R(v)P(v)圖3.15 一個現(xiàn)實表達式的與或樹表示 與或形的現(xiàn)實表達式可用與或圖來表示。以下圖的與或樹表示出上述例子的與或形現(xiàn)實表達式。圖中，每個節(jié)點表示該現(xiàn)實表達式的一個子表達式。 3.5 規(guī)那么演繹系統(tǒng) 表示某個現(xiàn)實表達式的與或圖的葉節(jié)點均由表達式中的文字來標(biāo)志。圖中標(biāo)志有整個現(xiàn)實表達式的節(jié)點，稱為根節(jié)點，它在圖中沒有祖先。公式的與或圖表示有個有趣的性質(zhì)，即由變換該公式得到的子句集可作為此與或圖的解圖的集合(終止于葉節(jié)點)讀出；也就是說，所得到的每個子句是作為解圖的各個葉節(jié)點上文字的析取。這樣，由表達式 Q(w,A)R(v)

27、P(v)S(A,v) 得到的子句為Q(w,A),S(A,v)R(v),S(A,v)P(v)對應(yīng)動態(tài)圖示： 3.5 規(guī)那么演繹系統(tǒng)v與或圖的F規(guī)那么前向推理規(guī)那么變換v 這些規(guī)那么是建立在某個問題轄域中普通陳說性知識的蘊涵公式根底上的。我們把允許用作規(guī)那么的公式類型限制為以下方式： v L W v 式中：L是單文字；W為與或形的獨一公式。 舉例闡明如下：公式 (x)( y)( z)P(x,y,z) ( u)Q(x,u可以經(jīng)過以下步驟加以變換： (1) 暫時消去蘊涵符號 ( x)( y)( z)P(x,y,z)( u)Q(x,u)(2) 把否認(rèn)符號移進第一個析取式內(nèi)，互換變量的量詞( x)( y)

28、( z)P(x,y,z)( u)Q(x,u)(3) 進展Skolem化 ( x)( y)P(x,y,f(x,y)( u)Q(x,u)(4) 把一切全稱量詞移至前面然后消去 P(x,y,f(x,y)Q(x,u)(5) 恢復(fù)蘊涵式 P(x,y,f(x,y) Q(x,u)3.5 規(guī)那么演繹系統(tǒng)上述變換的動態(tài)演示如下： 3.5 規(guī)那么演繹系統(tǒng)3.5.2 規(guī)那么逆向演繹系統(tǒng)v定義：v 逆向規(guī)那么演繹系統(tǒng)是從then向if進展推理的，即從目的或動作向現(xiàn)實或情況條件進展推理的。 v求解過程：v目的表達式的與或方式 逆向演繹系統(tǒng)可以處置恣意方式的目的表達式。首先，采用與變換現(xiàn)實表達式同樣的過程，把目的公式化成

29、與或形，即消去蘊涵符號，把否認(rèn)符號移進括號內(nèi)，對全稱量詞Skolem化并刪去存在量詞。留在目的表達式與或形中的變量假定都已存在量詞量化。 3.5 規(guī)那么演繹系統(tǒng)例如，目的表達式例如，目的表達式( (y)(y)( x) x)P(x) P(x) (x,y)(x,y)P(x)S(y)P(x)S(y)被化成與或形：被化成與或形：P(f(y)P(f(y)Q(f(y),y)Q(f(y),y)R(f(y)R(f(y)S(y)S(y)式中，式中，f(y)f(y)為一為一SkolemSkolem函數(shù)。函數(shù)。對目的的主要析取式中的變量分別規(guī)范化可得對目的的主要析取式中的變量分別規(guī)范化可得P(f(z)P(f(z)Q

30、(f(y),y)Q(f(y),y)R(f(y)R(f(y)S(y)S(y) 應(yīng)留意不能對析取的子表達式內(nèi)的變量應(yīng)留意不能對析取的子表達式內(nèi)的變量y y改名而使每個析改名而使每個析取式具有不同的變量。取式具有不同的變量。3.5 規(guī)那么演繹系統(tǒng) 與或形的目的公式也可以表示為與或圖。不過，與現(xiàn)實表達式的與或圖不同的是，對于目的表達式，與或圖中的k線銜接符用來分開合取關(guān)系的子表達式。在目的公式的與或圖中，我們把根節(jié)點的任一后裔叫做子目的節(jié)點，而標(biāo)在這些后裔節(jié)點中的表達式叫做子目的。 相應(yīng)的動態(tài)圖： 3.5 規(guī)那么演繹系統(tǒng)v與或圖的B規(guī)那么逆向推理規(guī)那么變換 如今運用B規(guī)那么即逆向推理規(guī)那么來變換逆向演

31、繹系統(tǒng)的與或圖構(gòu)造，這個B規(guī)那么是建立在確定的蘊涵式根底上的，正如正向系統(tǒng)的F規(guī)那么一樣。不過，如今把這些B規(guī)那么限制為 W L方式的表達式。其中，W為任一與或形公式，L為文字，而且蘊涵式中任何變量的量詞轄域為整個蘊涵式。 v 作為終止條件的現(xiàn)實節(jié)點的一致解圖3.5 規(guī)那么演繹系統(tǒng) 正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的根底上的。此正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的根底上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目的和表示現(xiàn)實的兩個與或圖構(gòu)造組成。組合系統(tǒng)的總數(shù)據(jù)庫由表示目的和表示現(xiàn)實的兩個與或圖構(gòu)造組成。這些與或圖構(gòu)造分別用正向系統(tǒng)的這些與或圖構(gòu)造分別用正向系統(tǒng)的F F規(guī)那么和逆向系統(tǒng)的規(guī)那

32、么和逆向系統(tǒng)的B B規(guī)那么來修規(guī)那么來修正。正。3.5.3 規(guī)那么雙向演繹系統(tǒng)3.5 規(guī)那么演繹系統(tǒng)3.6 產(chǎn)生式系統(tǒng)(production system)v定義：用來描畫假設(shè)干個不同的以一個根定義：用來描畫假設(shè)干個不同的以一個根本概念為根底的系統(tǒng)。這個根本概念就是本概念為根底的系統(tǒng)。這個根本概念就是產(chǎn)生式規(guī)那么或產(chǎn)生式條件和操作對的概產(chǎn)生式規(guī)那么或產(chǎn)生式條件和操作對的概念。念。v本質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識分為本質(zhì)：在產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：用現(xiàn)實表示靜態(tài)知識，如事物、兩部分：用現(xiàn)實表示靜態(tài)知識，如事物、事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)那么事件和它們之間的關(guān)系；用產(chǎn)生式規(guī)那么

33、表示推理過程和行為。由于這類系統(tǒng)的知表示推理過程和行為。由于這類系統(tǒng)的知識庫主要用于存儲規(guī)那么，因此又把此類識庫主要用于存儲規(guī)那么，因此又把此類系統(tǒng)稱為基于規(guī)那么的系統(tǒng)系統(tǒng)稱為基于規(guī)那么的系統(tǒng)(rule-based (rule-based system) system) 。3.6.1 產(chǎn)生式系統(tǒng)的組成控制戰(zhàn)略圖3.22 產(chǎn)生式系統(tǒng)的主要組成總數(shù)據(jù)庫產(chǎn)生式規(guī)那么3.6 產(chǎn)生式系統(tǒng) 總數(shù)據(jù)庫又叫綜合數(shù)據(jù)庫、上下文、黑板等，用于存放求解過程中各種當(dāng)前信息的數(shù)據(jù)構(gòu)造，如問題的初始形狀、現(xiàn)實或證據(jù)、中間推理結(jié)論和最后結(jié)果等。 產(chǎn)生式規(guī)那么是一個規(guī)那么庫，用于存放與求解問題有關(guān)的某個領(lǐng)域知識的規(guī)那么之集合

34、及其交換規(guī)那么。 控制戰(zhàn)略為一推理機構(gòu)，由一組程序組成，用來控制產(chǎn)生式系統(tǒng)的運轉(zhuǎn)，決議問題求解過程的推理線路，實現(xiàn)對問題的求解。 v選擇規(guī)那么到執(zhí)行操作的步驟v 1 匹配v 把當(dāng)前數(shù)據(jù)庫與規(guī)那么的條件部分相匹配。v 2 沖突處理v 當(dāng)有一條以上規(guī)那么的條件部分和當(dāng)前數(shù)據(jù)庫相匹配時，就需求決議首先運用哪一條規(guī)那么，這稱為沖突處理。v 3 操作v 操作就是執(zhí)行規(guī)那么的操作部分。經(jīng)過操作以后，當(dāng)前數(shù)據(jù)庫將被修正 3.6 產(chǎn)生式系統(tǒng)3.6.2 產(chǎn)生式系統(tǒng)的推理 v正向推理：從一組表示現(xiàn)實的謂詞或命題出發(fā)，運用一組產(chǎn)生式規(guī)那么，用以證明該謂詞公式或命題能否成立。 實現(xiàn)正向推理的普通戰(zhàn)略是：先提供一批數(shù)據(jù)(現(xiàn)實)到總數(shù)據(jù)庫中，系統(tǒng)利用這些現(xiàn)實與規(guī)那么的前提匹配，觸發(fā)匹配勝利的規(guī)那么(即啟用規(guī)那么)，把其結(jié)論作為新的現(xiàn)實添加到總數(shù)據(jù)庫中。繼續(xù)上述過程，用更新過的總數(shù)據(jù)庫中的一切現(xiàn)實再與規(guī)那么庫中另一條規(guī)那么匹配，用其結(jié)論再修正總數(shù)據(jù)庫的內(nèi)容，直到?jīng)]有可匹配的新規(guī)那么，不再有新的現(xiàn)實加到總數(shù)據(jù)庫為止。 3.6 產(chǎn)生式系統(tǒng)例如，有規(guī)那么集如下:規(guī)那么1: IF P1 THEN P2 規(guī)那么2: IF P2 THEN P3 規(guī)那么3: IF