人工智能(北郵)

第三章搜索推理技術(shù)

教學內(nèi)容早期搜索推理技術(shù)，如圖搜索策略和消解原理；高級搜索推理技術(shù)，如規(guī)則演繹系統(tǒng)、產(chǎn)生式系統(tǒng)、系統(tǒng)組織技術(shù)、不確定性推理和非單調(diào)推理。

13.1圖搜索策略1、圖搜索策略的定義

圖搜索策略可看作一種在圖中尋找路徑的方法。初始節(jié)點和目標節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。研究圖搜索的一般策略，能夠給出圖搜索過程的一般步驟。

22、圖搜索算法中的幾個重要名詞術(shù)語

（1）OPEN表與CLOSE表

（2）搜索圖與搜索樹

狀態(tài)節(jié)點父節(jié)點狀態(tài)節(jié)點父節(jié)點編號OPEN表CLOSE表343、圖搜索(GRAPHSEARCH)的一般過程

(1)建立一個只含有起始節(jié)點S的搜索圖G，把S放到一個叫做OPEN的未擴展節(jié)點表中。

(2)建立一個叫做CLOSED的已擴展節(jié)點表，其初始為空表。

(3)LOOP：若OPEN表是空表，則失敗退出。

(4)選擇OPEN表上的第一個節(jié)點，把它從OPEN表移出并放進CLOSED表中。稱此節(jié)點為節(jié)點n。

(5)若n為一目標節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。5

(6)擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。

(7)對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設(shè)置一個通向n的指針。把M的這些成員加進OPEN表。對已經(jīng)在OPEN或CLOSED表上的每一個M成員，確定是否需要更改通到n的指針方向。對已在CLOSED表上的每個M成員，確定是否需要更改圖G中通向它的每個后裔節(jié)點的指針方向。

(8)按某一任意方式或按某個探試值，重排OPEN表。

(9)GOLOOP。

64、圖搜索方法分析：

圖搜索過程的第8步對OPEN表上的節(jié)點進行排序，以便能夠從中選出一個“最好”的節(jié)點作為第4步擴展用。這種排序可以是任意的即盲目的(屬于盲目搜索)，也可以用以后要討論的各種啟發(fā)思想或其它準則為依據(jù)(屬于啟發(fā)式搜索)。每當被選作擴展的節(jié)點為目標節(jié)點時，這一過程就宣告成功結(jié)束。這時，能夠重現(xiàn)從起始節(jié)點到目標節(jié)點的這條成功路徑，其辦法是從目標節(jié)點按指針向S返回追溯。當搜索樹不再剩有未被擴展的端節(jié)點時，過程就以失敗告終(某些節(jié)點最終可能沒有后繼節(jié)點，所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點出發(fā)，一定達不到目標節(jié)點。

73.2盲目搜索

教學內(nèi)容：介紹三種盲目搜索方法，即寬度優(yōu)先搜索、深度優(yōu)先搜索和等代價搜索。

教學重點：盲目搜索的特點，寬度優(yōu)先搜索。

教學難點：等代價搜索中代價的概念。

教學方法：以實例強化內(nèi)容的學習，通過提問引導學生對三種方法的特點進行比較。

教學要求：掌握盲目搜索的特點，比較三種盲目搜索方法的優(yōu)缺點。

83.2.1寬度優(yōu)先搜索1、定義

如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-firstsearch)。

92、特點

這種搜索是逐層進行的；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。

103、寬度優(yōu)先搜索算法

(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。

(2)如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。

(3)把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。

(4)擴展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第(2)步。

(5)把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。

(6)如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。

114、寬度優(yōu)先搜索方法分析：

寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第8步具體化為本算法中的第6步，這實際是將OPEN表作為“先進先出”的隊列進行操作。

寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對有限圖來說，我們就說該法失敗退出；對于無限圖來說，則永遠不會終止)。12

5、例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹，這個問題就是要把初始棋局變?yōu)槿缦履繕似寰值膯栴}：

1314

3.2.2深度優(yōu)先搜索1、定義

在此搜索中，首先擴展最新產(chǎn)生的(即最深的)節(jié)點。深度相等的節(jié)點可以任意排列。

這種盲目(無信息)搜索叫做深度優(yōu)先搜索(depth-firstsearch)。

152、特點

首先，擴展最深的節(jié)點的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；只有當搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。

16173、深度界限

為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴展下去)，往往給出一個節(jié)點擴展的最大深度界限。任何節(jié)點如果達到了深度界限，那么都將把它們作為沒有后繼節(jié)點處理。

18194、含有深度界限的深度優(yōu)先搜索算法

請同學們課后自學，并回答課后思考題。

思考題：有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的最短途徑嗎？

203.2.3等代價搜索

1、定義

寬度優(yōu)先搜索可被推廣用來解決尋找從起始狀態(tài)至目標狀態(tài)的具有最小代價的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價搜索算法。

212、等代價搜索中的幾個記號

起始節(jié)點記為S；

從節(jié)點i到它的后繼節(jié)點j的連接弧線代價記為c(i，j)；

從起始節(jié)點S到任一節(jié)點i的路徑代價記為g(i)。

22233、等代價搜索算法

（請同學們課后認真閱讀本算法，指出與寬度優(yōu)先、深度優(yōu)先算法有何特別之處。）

244、等代價搜索方法分析

如果所有的連接弧線具有相等的代價，那么等代價算法就簡化為寬度優(yōu)先搜索算法。

思考：試比較各種盲目搜索搜索方法的效率，找出影響算法效率的原因。

253.3啟發(fā)式搜索教學內(nèi)容：啟發(fā)式搜索策略概述和有序搜索。啟發(fā)式搜索彌補盲目搜索的不足，提高搜索效率。

教學重點：啟發(fā)式搜索策略、啟發(fā)信息和有序搜索。

教學難點：估價函數(shù)的設(shè)計、A*算法原理。

教學方法：通過實例加深對原理的理解，鼓勵同學擴大閱讀范圍。

教學要求：掌握啟發(fā)式搜索策略和估價函數(shù)的設(shè)計方法，了解A*算法原理。

263.3.1啟發(fā)式搜索策略和估價函數(shù)

1、為什么需要啟發(fā)式搜索

盲目搜索效率低，耗費過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)形式。27

2、定義

進行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。利用啟發(fā)信息的搜索方法叫做啟發(fā)式搜索方法。

283、啟發(fā)式搜索策略

有關(guān)具體問題領(lǐng)域的信息常?？梢杂脕砗喕阉?。一個比較靈活(但代價也較大)的利用啟發(fā)信息的方法是應(yīng)用某些準則來重新排列每一步OPEN表中所有節(jié)點的順序。然后，搜索就可能沿著某個被認為是最有希望的邊緣區(qū)段向外擴展。應(yīng)用這種排序過程，需要某些估算節(jié)點“希望”的量度，這種量度叫做估價函數(shù)(evalutionfunction)。294、估價函數(shù)

為獲得某些節(jié)點“希望”的啟發(fā)信息，提供一個評定侯選擴展節(jié)點的方法，以便確定哪個節(jié)點最有可能在通向目標的最佳路徑上。

f(n)——表示節(jié)點n的估價函數(shù)值

建立估價函數(shù)的一般方法：試圖確定一個處在最佳路徑上的節(jié)點的概率；提出任意節(jié)點與目標集之間的距離量度或差別量度；或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點來決定棋局的得分數(shù)。這些特點被認為與向目標節(jié)點前進一步的希望程度有關(guān)。303.3.2有序搜索1、定義

用估價函數(shù)f來排列GRAPHSEARCH第8步中OPEN表上的節(jié)點。應(yīng)用某個算法(例如等代價算法)選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。這種搜索方法叫做有序搜索(orderedsearch)或最佳優(yōu)先搜索(best-firstsearch)，而其算法就叫做有序搜索算法或最佳優(yōu)先算法。

尼爾遜(Nilsson)曾提出一個有序搜索的基本算法。估價函數(shù)f是這樣確定的：一個節(jié)點的希望程序越大，其f值就越小。被選為擴展的節(jié)點，是估價函數(shù)最小的節(jié)點。

312、實質(zhì)

選擇OPEN表上具有最小f值的節(jié)點作為下一個要擴展的節(jié)點，即總是選擇最有希望的節(jié)點作為下一個要擴展的節(jié)點。

323、有序狀態(tài)空間搜索算法

(1)把起始節(jié)點S放到OPEN表中，計算f(S)并把其值與節(jié)點S聯(lián)系起來。

(2)如果OPEN是個空表，則失敗退出，無解。

(3)從OPEN表中選擇一個f值最小的節(jié)點i。結(jié)果有幾個節(jié)點合格，當其中有一個為目標節(jié)點時，則選擇此目標節(jié)點，否則就選擇其中任一個節(jié)點作為節(jié)點i。

(4)把節(jié)點i從OPEN表中移出，并把它放入CLOSED的擴展節(jié)點表中。

(5)如果i是個目標節(jié)點，則成功退出，求得一個解。

33(6)擴展節(jié)點i，生成其全部后繼節(jié)點。對于i的每一個后繼節(jié)點j：

(a)計算f(j)。

(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標節(jié)點時記住一個解答路徑。

(c)如果j已在OPEN表上或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值。如果新的f值較小，則

(i)以此新值取代舊值。

(ii)從j指向i，而不是指向它的父輩節(jié)點。

(iii)如果節(jié)點j在CLOSED表中，則把它移回OPEN表。(7)轉(zhuǎn)向(2)，即GOTO(2)。

344、有序搜索方法分析

寬度優(yōu)先搜索、等代價搜索和深度優(yōu)先搜索統(tǒng)統(tǒng)是有序搜索技術(shù)的特例。對于寬度優(yōu)先搜索，選擇f(i)作為節(jié)點i的深度。對于等代價搜索，f(i)是從起始節(jié)點至節(jié)點i這段路徑的代價。

有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準確的希望量度，那么f的選擇將涉及兩個方面的內(nèi)容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優(yōu)的解或任意解。35

5、例：八數(shù)碼難題

采用了簡單的估價函數(shù)

f(n)=d(n)+W(n)

其中：d(n)是搜索樹中節(jié)點n的深度；W(n)用來計算對應(yīng)于節(jié)點n的數(shù)據(jù)庫中錯放的棋子個數(shù)。因此，起始節(jié)點棋局

283

14

765

的f值等于0+4=4。

363.3.3A*算法A*算法是一種有序搜索算法，其特點在于對估價函數(shù)的定義上。

1、幾個記號

令k(ni，nj)表示任意兩個節(jié)點ni和nj之間最小代價路徑的實際代價(對于兩節(jié)點間沒有通路的節(jié)點，函數(shù)k沒有定義)。于是，從節(jié)點n到某個具體的目標節(jié)點ti，某一條最小代價路徑的代價可由k(n,ti)給出。令h*(n)表示整個目標節(jié)點集合｛ti｝上所有k(n,ti)中最小的一個，因此，h*(n)就是從n到目標節(jié)點最小代價路徑的代價，而且從n到目標節(jié)點能夠獲得h*(n)的任一路徑就是一條從n到某個目標節(jié)點的最佳路徑(對于任何不能到達目標節(jié)點的節(jié)點n，函數(shù)h*沒有定義)。372、估價函數(shù)的定義

定義g*為:g*(n)=k(S,n)

定義函數(shù)f*，使得在任一節(jié)點n上其函數(shù)值f*(n)就是從節(jié)點S到節(jié)點n的一條最佳路徑的實際代價加上從節(jié)點n到某目標節(jié)點的一條最佳路徑的代價之和，即

f*(n)=g*(n)+h*(n)

38希望估價函數(shù)f是f*的一個估計，此估計可由下式給出：

f(n)=g(n)+h(n)

其中：g是g*的估計；h是h*的估計。對于g(n)來說，一個明顯的選擇就是搜索樹中從S到n這段路徑的代價，這一代價可以由從n到S尋找指針時，把所遇到的各段弧線的代價加起來給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價路徑)。這個定義包含了g(n)≥g*(n)。h*(n)的估計h(n)依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。這種信息可能與八數(shù)碼難題中的函數(shù)W(n)所用的那種信息相似。把h叫做啟發(fā)函數(shù)。

393、A*算法定義

定義1在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進行的，則稱該過程為A算法。

定義2在A算法中，如果對所有的x存在h(x)≤h*(x),則稱h(x)為h*(x)的下界，它表示某種偏于保守的估計。

定義3采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?/p>

404、A*算法

A*算法描述參考教材。

提問：由g*(n)和g(n)的定義知g*(n)≤g(n)

A．對B．錯

思考：試比較寬度優(yōu)先搜索、有界深度優(yōu)先搜索及有序搜索的搜索效率，并以實例數(shù)據(jù)加以說明

413.4消解原理

教學內(nèi)容：消解原理是針對謂詞邏輯知識表示的問題求解方法。本節(jié)內(nèi)容主要包括子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。

教學重點：子句集的求取、消解推理的規(guī)則和消解反演問題求解方法。

教學難點：消解反演的思想。

教學方法：實例講解，注重課堂練習。

教學要求：重點掌握子句集的求解步驟和消解反演過程，掌握消解推理的規(guī)則。

42

消解原理的基礎(chǔ)知識：

（1）謂詞公式、某些推理規(guī)則以及置換合一等概念。

（2）子句：由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。

（3）消解：當消解可使用時，消解過程被應(yīng)用于母體子句對，以便產(chǎn)生一個導出子句。例如，如果存在某個公理E1∨E2和另一公理～E2∨E3，那么E1∨E3在邏輯上成立。這就是消解，而稱E1∧E3為E1∨E2和～E2∨E3的消解式(resolvent)。

433.4.1子句集的求取1、步驟

(1)消去蘊涵符號

只應(yīng)用∨和～符號，以～A∨B替換A→B。

提問：現(xiàn)有公式[(A→B)→B]∨C，在消去蘊涵符號后得到公式：

A．[～(A→B)∨B]∨CB．[～(A∨B)∧B]∨C

C．[～(～A∨B)∨B]∨CD．[(A∨B)∨B]∨C

44(2)減少否定符號的轄域

每個否定符號～最多只用到一個謂詞符號上，

并反復應(yīng)用狄·摩根定律。例如：

以～A∨～B代替～(A∧B)

以～A∧～B代替～(A∨B)

以A代替～(～A)

以(?)｛～A｝代替～(?x)A

以(?x)｛～A｝代替～(?x)A

45提問：設(shè)有公式(?

x)(?

y)｛(?

y)P(x,y)→(?

x)Q(x,y)｝，在經(jīng)過對變量標準化后得到公式為：

A．(?x)(?y)｛(?y)P(x,y)→(?y)Q(y,y)｝

B．(?x)(?y)｛(?x)P(x,x)→(?x)Q(x,y)｝

C．(?x)(?y)｛(?z)P(x,z)→(?q)Q(q,y)｝

D．(?x)(?y)｛(?z)P(x,z)→(?q)Q(q,z)｝

E．(?x)(?y)｛(?z)P(q,z)→(?q)Q(q,z)｝46

(3)對變量標準化

在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元(虛構(gòu)變量)，它可以在該轄域內(nèi)處處統(tǒng)一地被另一個沒有出現(xiàn)過的任意變量所代替，而不改變公式的真值。合適公式中變量的標準化意味著對啞元改名以保證每個量詞有其自己唯一的啞元。47

(4)消去存在量詞

用Skolem函數(shù)代替存在的x,就可以消去全部存在量詞，并寫成：

(?y)P［g(y),y］

從一個公式消去一個存在量詞的一般規(guī)則是以一個Skolem函數(shù)代替每個出現(xiàn)的存在量詞的量化變量，而這個Skolem函數(shù)的變量就是由那些全稱量詞所約束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所使用的函數(shù)符號必須是新的，即不允許是公式中已經(jīng)出現(xiàn)過的函數(shù)符號。例如：

(?y)(?x)P(x,y)被〔(?y)P(g(y),y)〕代替，其中g(shù)(y)為一Skolem函數(shù)。

48

如果要消去的存在量詞不在任何一個全稱量詞的轄域內(nèi)，則用不含變量的Skolem函數(shù)即常量。例如，(?x)P(x)化為P(A)，其中常量符號A用來表示人們知道的存在實體。A必須是個新的常量符號，它未曾在公式中其它地方使用過。49

(5)化為前束形

把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。所得公式稱為前束形。(6)把母式化為合取范式

任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。(7)消去全稱量詞

消去明顯出現(xiàn)的全稱量詞。50

提問：對于公式(?z)(?y){(?x)P(x,y,z)∨(?q)(?)(?e)Q(q,w,e,z)，在經(jīng)過消去存在量詞后，正確的公式為：

A．(?y){P(B,y,A)∨(?w)Q(C,w,D,A)

B．(?y){P(B,y,A)∨(??w)Q(C,w,g(w),A),g(w)為一Skolem函數(shù)

C．(?y){P(g1(y),y,A)∨(?w)Q(g２(y),w,g３(w),A)

式中，(g1(y)，g２(y)和g３(w)為Skolem函數(shù)

D．(?y){P(g1(y),y,A)∨(?w)Q(g２(y),w,g３(y,w),A)

式中，(g1(y)，g２(y)和g３(y,w)為Skolem函數(shù)51

(8)消去連詞符號∧

用｛A，B｝代替(A∧B)，以消去明顯的符號∧。反復代替的結(jié)果，最后得到一個有限集，其中每個公式是文字的析取。任一個只由文字的析取構(gòu)成的合適公式叫做一個子句。(9)更換變量名稱

可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。522、例

將下列謂詞演算公式化為一個子句集

(?x)｛P(x)→｛(?y)［P(y)→P(f(x,y))］∧～(?y)［Q(x,y)→P(y)］｝｝

533、說明

并不是所有問題的謂詞公式化為子句集都需要上述9個步驟。對于某些問題，可能不需要其中的一些步驟。

543.4.2消解推理規(guī)則1、消解式

令L1為任一原子公式，L2為另一原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β,如果L1和L2具有最一般合一者σ，那么通過消解可以從這兩個父輩子句推導出一個新子句(α∨β)σ。這個新子句叫做消解式。它是由取這兩個子句的析取，然后消去互補對而得到的。

552、消解式求法

(1)假言推理

父輩子句P～P∨Q(即P→Q)

\

/

\

/

消解式Q

56(2)合并(3)重言式(4)空子句(矛盾)

～P

P

\

/

\

/

NIL(5)鏈式(三段論)

即取各子句的析取，然后消去互補對。

說明：對合并、重言式、鏈式(三段論)請同學們自行閱讀。

57

3.4.3含有變量的消解式

1、消解式求法

為了對含有變量的子句使用消解規(guī)則，必須找到一個置換，作用于父輩子句使其含有互補文字。582、例子

P(x)∨Q(x)～Q［f(y)］

置換σ=｛f(y)/x｝

P［f(y)］

593.4.4消解反演求解過程1、基本思想

把要解決的問題作為一個要證明的命題，其目標公式被否定并化成子句形，然后添加到命題公式集中去，把消解反演系統(tǒng)應(yīng)用于聯(lián)合集，并推導出一個空子句(NIL)，產(chǎn)生一個矛盾，這說明目標公式的否定式不成立，即有目標公式成立，定理得證，問題得到解決，與數(shù)學中反證法的思想十分相似。

602、消解反演

反演求解的步驟

給出一個公式集S和目標公式L，通過反證或反演來求證目標公式L，其證明步驟如下：

(1)否定L，得～L；

(2)把～L添加到S中去；

(3)把新產(chǎn)生的集合｛～L，S｝化成子句集；

(4)應(yīng)用消解原理，力圖推導出一個表示矛盾的空子句NIL。

61反演求解的正確性

設(shè)公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足～L的，所以不存在能夠滿足并集S∪｛～L｝的解釋。如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。因此，如果L在邏輯上遵循S，那么S∪｛～L｝是不可滿足的?？梢宰C明，如果消解反演反復應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集S∪｛～L｝消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從S∪｛～L｝的子句消解得到空子句，那么L在邏輯上遵循S。

623、反演求解過程

步驟：

(1)把由目標公式的否定產(chǎn)生的每個子句添加到目標公式否定之否定的子句中去。

(2)按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。

(3)用根部的子句作為一個回答語句。

63分析：

答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個語句的一顆證明樹。由于變換關(guān)系涉及到把由目標公式的否定產(chǎn)生的每個子句變換為一個重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語句在邏輯上遵循公理加上重言式，因而也單獨地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。

64例：儲蓄問題

前提：每個儲蓄錢的人都獲得利息。

結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢

思考：應(yīng)用消解反演求解如下問題：

“如果無論約翰(John)到哪里去，菲多(Fido)也就去那里，那么如果約翰在學校里，菲多在哪里呢?”

653.5規(guī)則演繹系統(tǒng)

教學內(nèi)容：規(guī)則演繹系統(tǒng)屬于高級搜索推理技術(shù)，用于解決比較復雜的系統(tǒng)和問題。本節(jié)介紹規(guī)則演繹系統(tǒng)的定義及其三種推理方法：規(guī)則正向演繹系統(tǒng)、規(guī)則逆向演繹系統(tǒng)和規(guī)則雙向演繹系統(tǒng)。

教學重點：規(guī)則演繹系統(tǒng)的定義、正向推理和逆向推理過程。

教學難點：雙向演繹的匹配問題等。

教學方法：課堂教學為主。通過比較揭示正向推理、逆向推理和雙向推理的特點。

教學要求：掌握規(guī)則演繹系統(tǒng)的定義和正向推理、逆向推理的過程，了解規(guī)則雙向演繹系統(tǒng)。66

規(guī)則演繹系統(tǒng)的定義：

基于規(guī)則的問題求解系統(tǒng)運用下述規(guī)則來建立：

If→Then

其中，If部分可能由幾個if組成，而Then部分可能由一個或一個以上的then組成。

在所有基于規(guī)則系統(tǒng)中，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rulebaseddeductionsystem)。在這種系統(tǒng)中，通常稱每個if部分為前項(antecedent)，稱每個then部分為后項(consequent)。

673.5.1規(guī)則正向演繹系統(tǒng)

1、定義

正向規(guī)則演繹系統(tǒng)是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。

682、正向推理過程

（1）事實表達式的與或形變換

把事實表示為非蘊涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。具體變換步驟與前述化為子句形類似。

注意：我們不想把這些事實化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換為叫做與或形的非蘊涵形式。

69

例：有事實表達式

(?u)(?v)｛Q(v，u)∧～［(R(v)∨P(v))∧S(u，v)］｝把它化為

Q(v,A)∧｛［～R(v)∧～P(v)］∨～S(A,v)｝

對變量更名標準化，使得同一變量不出現(xiàn)在事實表達式的不同主要合取式中，得：

Q(w,A)∧｛［～R(v)∧～P(v)］∨～S(A,v)｝

70（2）事實表達式的與或圖表示

將上例與或形的事實表達式用與或圖來表示，見圖3.1。

71

一般把事實表達式的與或圖表示倒過來畫，即把根節(jié)點畫在最下面，而把其后繼節(jié)點往上畫。上節(jié)的與或圖表示，就是按通常方式畫出的，即目標在上面。

72（3）與或圖的F規(guī)則變換

這些規(guī)則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎(chǔ)上的。把允許用作規(guī)則的公式類型限制為下列形式：

L→W

式中：L是單文字；W為與或形的唯一公式。

73

將這類規(guī)則應(yīng)用于與或圖進行推演。假設(shè)有一條規(guī)則L=>W，根據(jù)此規(guī)則及事實表達式F(L)，可以推出表達式F(W)。F(W)是用W代替F中的所有L而得到的。當用規(guī)則L=>W來變換以上述方式描述的F(L)的與或圖表示時，就產(chǎn)生一個含有F(W)表示的新圖；也就是說，它的以葉節(jié)點終止的解圖集以F(W)子句形式代表該子句集。這個子句集包括在F(L)的子句形和L=>W的子句形間對L進行所有可能的消解而得到的整集。該過程以極其有效的方式達到了用其它方法要進行多次消解才能達到的目的。

74

（4）作為終止條件的目標公式

應(yīng)用F規(guī)則的目的在于從某個事實公式和某個規(guī)則集出發(fā)來證明某個目標公式。在正向推理系統(tǒng)中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式。用文字集表示此目標公式，并設(shè)該集各元都為析取關(guān)系。

結(jié)論：

當正向演繹系統(tǒng)產(chǎn)生一個含有以目標節(jié)點作為終止的解圖時，此系統(tǒng)就成功地終止。753.5.2規(guī)則逆向演繹系統(tǒng)

1、定義

基于規(guī)則的逆向演繹系統(tǒng)，其操作過程與正向演繹系統(tǒng)相反，即為從目標到事實的操作過程，從then到if的推理過程。

762、逆向推理過程

（1）目標表達式的與或形式

逆向演繹系統(tǒng)能夠處理任意形式的目標表達式。首先，采用與變換事實表達式同樣的過程，把目標公式化成與或形。

（2）與或圖的B規(guī)則變換

B規(guī)則是建立在確定的蘊涵式基礎(chǔ)上的，正如正向系統(tǒng)的F規(guī)則一樣。不過，我們現(xiàn)在把這些B規(guī)則限制為

W→L(3.4)

形式的表達式。其中，W為任一與或形公式，L為文字，而且蘊涵式中任何變量的量詞轄域為整個蘊涵式。

（3）作為終止條件的事實節(jié)點的一致解圖

逆向系統(tǒng)成功的終止條件是與或圖包含有某個終止在事實節(jié)點上的一致解圖。

773.5.3規(guī)則雙向演繹系統(tǒng)

1.基于規(guī)則的正向演繹系統(tǒng)和逆向演繹系統(tǒng)的特點和局限性

正向演繹系統(tǒng)能夠處理任意形式的if表達式，但被限制在then表達式為由文字析取組成的一些表達式。逆向演繹系統(tǒng)能夠處理任意形式的then表達式，但被限制在if表達式為文字合取組成的一些表達式。雙向(正向和逆向)組合演繹系統(tǒng)具有正向和逆向兩系統(tǒng)的優(yōu)點，克服各自的缺點。

782.雙向(正向和逆向)組合演繹系統(tǒng)的構(gòu)成

正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標和表示事實的兩個與或圖結(jié)構(gòu)組成，并分別用F規(guī)則和B規(guī)則來修正。79

3.終止條件

組合演繹系統(tǒng)的主要復雜之處在于其終止條件，終止涉及兩個圖結(jié)構(gòu)之間的適當交接處。當用F規(guī)則和B規(guī)則對圖進行擴展之后，匹配就可以出現(xiàn)在任何文字節(jié)點上。

在完成兩個圖間的所有可能匹配之后，目標圖中根節(jié)點上的表達式是否已經(jīng)根據(jù)事實圖中根節(jié)點上的表達式和規(guī)則得到證明的問題仍然需要判定。只有當求得這樣的一個證明時，證明過程才算成功地終止。若能夠斷定在給定方法限度內(nèi)找不到證明時過程則以失敗告終。

803.6產(chǎn)生式系統(tǒng)

教學內(nèi)容：本節(jié)介紹產(chǎn)生式系統(tǒng)的定義、組成和推理技術(shù)。

教學重點：產(chǎn)生式系統(tǒng)與規(guī)則演繹系統(tǒng)的差別和產(chǎn)生式系統(tǒng)的組成。

教學難點：產(chǎn)生式系統(tǒng)的控制策略等。

教學方法：課堂教學和實驗相結(jié)合。重點講解原理，通過實驗進一步領(lǐng)會系統(tǒng)的精髓。充分利用網(wǎng)絡(luò)課程中的多媒體素材來表示抽象概念。

教學要求：掌握產(chǎn)生式系統(tǒng)的組成結(jié)構(gòu)，通過實踐掌握產(chǎn)生式系統(tǒng)的設(shè)計和工作過程。81

定義：

在基于規(guī)則系統(tǒng)中，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配，then部分用于規(guī)定放入工作內(nèi)存的新斷言。當then部分用于規(guī)定動作時，稱這種基于規(guī)則的系統(tǒng)為反應(yīng)式系統(tǒng)(reactionsystem)或產(chǎn)生式系統(tǒng)(productionsystem)。

823.6.1產(chǎn)生式系統(tǒng)的組成

1.產(chǎn)生式系統(tǒng)的組成

產(chǎn)生式系統(tǒng)由3個部分組成，即總數(shù)據(jù)庫(或全局數(shù)據(jù)庫)、產(chǎn)生式規(guī)則和控制策略，如圖3.2所示。

圖3.2產(chǎn)生式系統(tǒng)的主要組成

83

總數(shù)據(jù)庫有時也被稱作上下文，當前數(shù)據(jù)庫或暫時存儲器?？倲?shù)據(jù)庫是產(chǎn)生式規(guī)則的注意中心。產(chǎn)生式規(guī)則的左邊表示在啟用這一規(guī)則之前總數(shù)據(jù)庫內(nèi)必須準備好的條件。例如在上述例子中，在得出該動物是食肉動物的結(jié)論之前，必須在總數(shù)據(jù)庫中存有“該動物是哺乳動物”和“該動物吃肉”這兩個事實。執(zhí)行產(chǎn)生式規(guī)則的操作會引起總數(shù)據(jù)庫的變化，這就使其他產(chǎn)生式規(guī)則的條件可能被滿足。84

產(chǎn)生式規(guī)則是一個規(guī)則庫，用于存放與求解問題有關(guān)的某個領(lǐng)域知識的規(guī)則之集合及其交換規(guī)則。規(guī)則庫知識的完整性、一致性、準確性、靈活性和知識組織的合理性，將對產(chǎn)生式系統(tǒng)的運行效率和工作性能產(chǎn)生重要影響。

85

控制策略為一推理機構(gòu)，由一組程序組成，用來控制產(chǎn)生式系統(tǒng)的運行，決定問題求解過程的推理線路，實現(xiàn)對問題的求解。產(chǎn)生式系統(tǒng)的控制策略隨搜索方式的不同可分為可撤回策略、回溯策略、圖搜索策略等。

86

2.產(chǎn)生式系統(tǒng)的控制策略控制策略的作用是說明下一步應(yīng)該選用什么規(guī)則，也就是如何應(yīng)用規(guī)則。通常從選擇規(guī)則到執(zhí)行操作分3步：匹配、沖突解決和操作。

87

（1）匹配

在這一步，把當前數(shù)據(jù)庫與規(guī)則的條件部分相匹配。如果兩者完全匹配，則把這條規(guī)則稱為觸發(fā)規(guī)則。當按規(guī)則的操作部分去執(zhí)行時，稱這條規(guī)則為啟用規(guī)則。被觸發(fā)的規(guī)則不一定總是啟用規(guī)則，因為可能同時有幾條規(guī)則的條件部分被滿足，這就要在解決沖突步驟中來解決這個問題。在復雜的情況下，在數(shù)據(jù)庫和規(guī)則的條件部分之間可能要進行近似匹配。

88

（2）沖突解決

當有一條以上規(guī)則的條件部分和當前數(shù)據(jù)庫相匹配時，就需要決定首先使用哪一條規(guī)則，這稱為沖突解決。

89

（3）操作

操作就是執(zhí)行規(guī)則的操作部分，經(jīng)過操作以后，當前數(shù)據(jù)庫將被修改。然后，其他的規(guī)則有可能被使用。

903.6.2產(chǎn)生式系統(tǒng)的推理1.正向推理

從一組表示事實的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則，用以證明該謂詞公式或命題是否成立。

一般策略：先提供一批事實（數(shù)據(jù)）到總數(shù)據(jù)庫中。系統(tǒng)利用這些事實與規(guī)則的前提相匹配，觸發(fā)匹配成功的規(guī)則，把其結(jié)論作為新的事實添加到總數(shù)據(jù)庫中。繼續(xù)上述過程，用更新過的總數(shù)據(jù)庫的所有事實再與規(guī)則庫中另一條規(guī)則匹配，用其結(jié)論再次修改總數(shù)據(jù)庫的內(nèi)容，直到?jīng)]有可匹配的新規(guī)則，不再有新的事實加到總數(shù)據(jù)庫中。

912.逆向推理

從表示目標的謂詞或命題出發(fā)，使用一組產(chǎn)生式規(guī)則證明事實謂詞或命題成立，即首先提出一批假設(shè)目標，然后逐一驗證這些假設(shè)。

一般策略：首先假設(shè)一個可能的目標，然后由產(chǎn)生式系統(tǒng)試圖證明此假設(shè)目標是否在總數(shù)據(jù)庫中。若在總數(shù)據(jù)庫中，則該假設(shè)目標成立；否則，若該假設(shè)為終葉（證據(jù)）節(jié)點，則詢問用戶。若不是，則再假定另一個目標，即尋找結(jié)論部分包含該假設(shè)的那些規(guī)則，把它們的前提作為新的假設(shè)，并力圖證明其成立。這樣反復進行推理，直到所有目標均獲證明或者所有路徑都得到測試為止。

923.雙向推理

雙向推理的推理策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現(xiàn)事實與目標的匹配。

933.6.3產(chǎn)生式系統(tǒng)舉例

說明：請同學們課后認真閱讀本部分內(nèi)容，并以此為參考進行實驗準備！

思考：規(guī)則演繹系統(tǒng)和產(chǎn)生式系統(tǒng)有哪幾種推理方式?各自的特點為何?

943.7系統(tǒng)組織技術(shù)

教學內(nèi)容：系統(tǒng)組織技術(shù)屬于高級搜索推理技術(shù)，能夠用于求解比較復雜的系統(tǒng)。本節(jié)簡要介紹三種系統(tǒng)組織技術(shù)：議程表法、黑板法和△極小搜索法。

教學重點：系統(tǒng)組織技術(shù)如何實現(xiàn)模塊之間的合作。

教學難點：無要求。

教學方法：課堂教學。

教學要求：了解系統(tǒng)組織技術(shù)的基本原理。

953.7.1議程表1.定義

議程表(agenda)是一個系統(tǒng)能夠執(zhí)行的任務(wù)表列。與每個任務(wù)有關(guān)的有兩件事，即提出該任務(wù)的理由和表示對該任務(wù)是有用的證據(jù)總權(quán)的評價。

962.模塊間的合作

從組織大系統(tǒng)的觀點看，議程表方法的意義在于它允許幾個獨立模塊進行通訊。其通訊方法是每個模塊可將支持(或反對)某個具體任務(wù)的證據(jù)，加到一個證明選擇該任務(wù)是正確的表中。這樣就使系統(tǒng)能夠選出從各方面都有充分證據(jù)的任務(wù)。雖然各模塊共同使用關(guān)于為什么要執(zhí)行各項任務(wù)的證據(jù)，但一個模塊并不需要了解其它模塊如何工作，以及它們所包含的知識。這樣，議程表方法便具有大系統(tǒng)中模塊化的一切優(yōu)點，而無相互隔離的缺點。

973.7.2黑板法1.定義

黑板法(theBlackboardApproach)首先是在HEARSAY-Ⅱ語音理解系統(tǒng)中發(fā)展起來的。它的思想比較簡單。整個系統(tǒng)由一組稱為知識資源(KS)的獨立模塊和一塊黑板組成。這里，知識資源含有系統(tǒng)中專門領(lǐng)域的知識，而黑板則是一切KS可以訪問的公用數(shù)據(jù)結(jié)構(gòu)。

982.模塊間的合作

當一個KS被激發(fā)時，它檢查當時黑板上的內(nèi)容，并應(yīng)用其知識產(chǎn)生一個新的假設(shè)寫到黑板上，直到完成任務(wù)為止。當時間表沒有發(fā)現(xiàn)未解決的活動記錄時，系統(tǒng)便停止執(zhí)行。

993.7.3Δ-極小搜索法

1、定義

Δ值表示一假設(shè)的級別與參加競爭的最佳假設(shè)的級別之差，提供了一種選擇最有希望假設(shè)的技術(shù)。

1002、工作過程

一次接受一串輸入，順序地處理，使其形成一個關(guān)于輸入的統(tǒng)一而相容的解釋。Δ-極小法是這樣來解決這類問題的：在適當?shù)臅r刻，觸發(fā)某KS，然后為它生成所有它認為是可能的假設(shè)，并賦給某個假設(shè)一種級別。由這些級別計算出的Δ值，表示一假設(shè)的級別與參加競爭的最佳假設(shè)的級別之差。而在該假設(shè)最后導致不相容時，再考慮參加競爭的另一假設(shè)。

1013.8不確定性推理

教學內(nèi)容：本節(jié)介紹兩種不確定性(uncertainty)，即關(guān)于證據(jù)的不確定性和關(guān)于結(jié)論的不確定性。

教學要點：不確定性如何表示和推理。

教學難點：不確定性的推理。

教學方法：課堂教學為主。

教學要求：了解不確定性的表示和推理方法。

1023.8.1關(guān)于證據(jù)的不確定性

1.不確定性的表示

一般通過對事實賦于一個介于0和1之間的系數(shù)來表示事實的不確定性。1代表完全確定，0代表完全不確定。這個系數(shù)被稱為可信度(也有一些專家系統(tǒng)，如MYCIN和EXPERT等，取可信度的范圍為-1到+1)。

1032.不確定性的處理

當規(guī)則具有一個以上的條件時，就需要根據(jù)各條件的可信度來求得總條件部分的可信度。已有的方法有兩類：

（1）以模糊集理論為基礎(chǔ)的方法

按這種方法，把所有條件中最小的可信度作為總條件的可信度。這種方法類似于當把幾根繩子連接起來使用時，總的繩子強度與強度最差的繩子的相同。

（2）以概率為基礎(chǔ)的方法

這種方法同樣賦予每個證據(jù)以可信度。但當把單獨條件的可信度結(jié)合起來求取總的可信度時，它取