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

3.1

圖搜索策略3.2

盲目搜索3.3

啟發(fā)式搜索3.4

消解原理3.5

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

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

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

不確定性推理3.9

非單調(diào)推理3.10小結(jié)第3章搜索推理技術(shù)3.1圖搜索策略圖搜索控制策略一種在圖中尋找路的方法。圖中每個節(jié)點對應(yīng)一個狀態(tài)，每條連線對應(yīng)一個操作符。節(jié)點和連線（即狀態(tài)與操作）又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標記。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。圖搜索過程1.

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

建立一個叫做CLOSED的已擴展節(jié)點表（簡稱CLOSED表），其初始為空表。3.

LOOP：若OPEN表是空表，則失敗退出。4.

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

若n為一目標節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到（指針將在第7步中設(shè)置）。圖搜索過程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。圖搜索過程框圖3.2盲目搜索概念沒有啟發(fā)信息的一種搜索形式一般只適用于求解比較簡單的問題特點不需重排OPEN表種類寬度優(yōu)先深度優(yōu)先等代價搜索3.2.1寬度優(yōu)先搜索1)定義以接近起始節(jié)點的程度為依據(jù)，進行逐層擴展的節(jié)點搜索方法。2)特點搜索是逐層進行的，即在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。一種高代價搜索，但若有解存在，則必能找到它。寬度優(yōu)先搜索示意圖寬度優(yōu)先算法框圖寬度優(yōu)先搜索算法描述1.

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

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

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

擴展節(jié)點n。如果沒有后繼節(jié)點，則轉(zhuǎn)向上述第2步。寬度優(yōu)先搜索算法描述5.

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

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

擴展當前節(jié)點后生成的子節(jié)點總是置于OPEN表的后端，即OPEN表作為排隊表使用，先進先出，使搜索優(yōu)先向橫方向發(fā)展。

寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，這實際是將OPEN表作為“先進先出”的隊列進行操作。搜索樹:搜索過程產(chǎn)生的節(jié)點和指針構(gòu)成一棵隱式定義的狀態(tài)空間圖的子樹,稱為搜索樹。如果問題有解,寬度優(yōu)先算法能夠保證找到一條通向目標節(jié)點的最短路徑(即找到最優(yōu)解).如要問題無解,對于有限圖,該算法會失敗退出，對于無限圖,則永遠不會終止。寬度優(yōu)先搜索算法說明八數(shù)碼難題將牌移入空格的順序：從空格左邊開始順時針旋轉(zhuǎn)。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，才求得解（目標節(jié)點）。八數(shù)碼難題的寬度優(yōu)先搜索樹3.2.2深度優(yōu)先搜索1定義首先擴展最新產(chǎn)生（即最深的）節(jié)點。深度相等的節(jié)點可以任意排列。2)特點首先，擴展最深的節(jié)點的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下去；僅當搜索到達一個沒有后裔的狀態(tài)時，才考慮另一條替代的路徑。3)節(jié)點深度定義:起始節(jié)點(即根節(jié)點)的深度為0.任何其他節(jié)點的深度等于其父輩節(jié)點的深度加1.4)深度界限:–為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴展下去),往往給出一個節(jié)點擴展的最大深度,稱為深度界限.–任何節(jié)點如果達到了深度界限,那么都將把它們作為沒有后繼節(jié)點來處理.–即使應(yīng)用了深度界限,深度優(yōu)先搜索所求得的解答路徑也不一定就是最短路徑.3.2.2深度優(yōu)先搜索深度優(yōu)先搜索示意圖深度優(yōu)先搜索算法描述1.

把起始節(jié)點S放到未擴展節(jié)點OPEN表中。如果此節(jié)點為一目標節(jié)點，則得到一個解。2.

如果OPEN為一空表，則失敗退出。3.

把第一個節(jié)點（節(jié)點n）從OPEN表移到CLOSED表。4.

如果節(jié)點n的深度等于最大深度，則轉(zhuǎn)向(2)。5.

擴展節(jié)點n，產(chǎn)生其全部后裔，并把它們放入OPEN表的前頭。如果沒有后裔，則轉(zhuǎn)向(2)。6.

如果后繼節(jié)點中有任一個為目標節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向(2)。深度優(yōu)先搜索算法描述起始把S放入OPEN表OPEN表是否為空?把OPEN表中的第一個節(jié)點n移入CLOSED表擴展節(jié)點n,把其后裔n放入OPEN表的前端,提供返回節(jié)點n的指針失敗是否是否有任何后繼節(jié)點為目標節(jié)點?成功是否S是否為目標節(jié)點?成功是節(jié)點n的深度是否等于深度界限?是否否八數(shù)碼難題的深度優(yōu)先搜索樹

思考題：有界深度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標節(jié)點的最短途徑嗎？一般不能保證找到最優(yōu)解。當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制。最壞情況時，搜索空間等同于窮舉。與回溯法的差別：圖搜索。是一個通用的與問題無關(guān)的方法。深度優(yōu)先搜索的性質(zhì)為什么需要啟發(fā)式搜索

效率低，耗費過多的計算空間與時間。可能帶來組合爆炸。分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價搜索算法,其主要的差別是OPEN表中待擴展節(jié)點的順序問題。人們就試圖找到一種方法用于排列待擴展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴展，那么，搜索效率將會大為提高。3.3啟發(fā)式搜索定義進行搜索技術(shù)一般需要某些有關(guān)具體問題的領(lǐng)域的特性信息，把此種信息叫做啟發(fā)信息。把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。特點重排OPEN表，選擇最有希望的節(jié)點加以擴展種類有序搜索、A*算法等3.3啟發(fā)式搜索啟發(fā)式搜索策略

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

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

為獲得某些節(jié)點“希望”的啟發(fā)信息，提供一個評定侯選擴展節(jié)點的方法，以便確定哪個節(jié)點最有可能在通向目標的最佳路徑上。一個節(jié)點的“希望”有幾種定義方法一種方法是估算目標節(jié)點到此節(jié)點的距離；另一種方法認為，解答路徑包括被估價過的節(jié)點，并計算全條路徑的長度或難度。每個不同的衡量標準只能考慮該問題中這個節(jié)點的某些決定性特性，或者對給定節(jié)點與目標節(jié)點進行比較，以決定相關(guān)特性。表示方法f(n)——表示節(jié)點n的估價函數(shù)值3.3.1啟發(fā)式搜索策略和估價函數(shù)建立估價函數(shù)的一般方法1.

試圖確定一個處在最佳路徑上的節(jié)點的概率；2.

提出任意節(jié)點與目標集之間的距離量度或差別量度；3.或者在棋盤式的博弈和難題中根據(jù)棋局的某些特點來決定棋局的得分數(shù)。這些特點被認為與向目標節(jié)點前進一步的希望程度有關(guān)。3.3.1啟發(fā)式搜索策略和估價函數(shù)評價函數(shù)的格式

應(yīng)用這種評價函數(shù)來實現(xiàn)啟發(fā)式搜索的典型是算法A，其將評價函數(shù)f設(shè)計為：

f(n)=g(n)+h(n)n--搜索圖中的某個當前被擴展的節(jié)點；f(n)--從初始狀態(tài)節(jié)點s,經(jīng)由節(jié)點n到達目標狀節(jié)點ng，估計的最小路徑代價；g(n)--從s到n,估計的最小路徑代價；h(n)--從n到ng,估計的最小路徑代價；

3.3.1啟發(fā)式搜索策略和估價函數(shù)啟發(fā)式搜索算法框圖啟發(fā)式搜索算法描述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é)點,則成功退出,求得一個解。啟發(fā)式搜索算法描述6.

擴展節(jié)點i,生成其全部后繼節(jié)點.對于i的每一個后繼節(jié)點j:計算f(j)。如果j既不在OPEN表中,也不在CLOSED表中,則用估價函數(shù)f把它添入OPEN表。從j加一指向父輩節(jié)點i的指針(以便找到目標節(jié)點時記住一個解答路徑)。如果j已在OPEN表或CLOSED表上,則比較剛剛對j計算過的f值和前面計算過的該節(jié)點在表中的f值.如果新的f值較小,則：以此新值取代舊值。從j指向i,而不是指向它的父輩節(jié)點。如果節(jié)點j在CLOSED表中,則把它移回OPEN表。7.

轉(zhuǎn)向(2),即GOTO(2)。

啟發(fā)式搜索—A算法例子定義評價函數(shù)：

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

g(n)為從初始節(jié)點到當前節(jié)點的耗散值

h(n)為當前節(jié)點“不在位”的將牌數(shù)

啟發(fā)式搜索—A算法例子

1)記號:g*(n)：從s到n的最短路徑的耗散值h*(n)：從n到g的最短路徑的耗散值f*(n)=g*(n)+h*(n)：從s經(jīng)過n到g的最短路徑的耗散值

2)估價函數(shù)f是f*的一個估計:f(n)=g(n)+h(n)，其中g(shù)(n)是g*(n)的估計,h(n)是h*(n)的估計.g(n)：通常為從s到n這段路徑的實際代價，則有g(shù)(n)≥g*(n);h(n)：是從節(jié)點n到目標節(jié)點Sg的最優(yōu)路徑的估計代價.它的選擇依賴于有關(guān)問題領(lǐng)域的啟發(fā)信息,叫做啟發(fā)函數(shù).例如八數(shù)碼中的h(n)。最佳圖搜索算法A*（A*算法）

3)定義

在A算法中，如果滿足條件：

h(n)≤h*(n)

則A算法稱為A*算法。

4)A*算法的特點若存在從初始節(jié)點S0到目標節(jié)點Sg的路徑,則A*算法必能結(jié)束在最佳路徑上。使用啟發(fā)函數(shù)h(n)的A*算法，比不使用h(n)(h(n)≡0)的算法,求得最佳路徑時擴展的節(jié)點數(shù)要少。一般來說,在滿足h(n)≤h*(n)的條件下,h(n)的值越大,說明它攜帶的啟發(fā)性信息越多,搜索時擴展的節(jié)點就越少,搜索效率就越高,當h(n)=h*(n)時,則不會去擴展多余的節(jié)點就可找到解。最佳圖搜索算法A*（A*算法）思考題：八數(shù)碼難題g:實際走的步數(shù)(節(jié)點深度)。w(n):當前節(jié)點“不在位”的將牌數(shù)。h(n)=p(n):移動到目標狀態(tài)相應(yīng)位置所需走步的總和.（在不設(shè)阻的情況下)思考題：八數(shù)碼難題基礎(chǔ)知識謂詞公式、某些推理規(guī)則以及置換合一等概念。子句：由文字的析取組成的公式；一個原子公式和原子公式的否定都叫做文字。消解：當消解可使用時，消解過程被應(yīng)用于母體子句對，以便產(chǎn)生一個導(dǎo)出子句。例如，如果存在某個公理E1∨E2和另一公理～E2∨E3，那么，E1∨E3在邏輯上成立。這就是消解，而稱E1∧E3為E1∨E2和～E2∨E3的消解式。3.4消解原理子句集的求取

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

3.4消解原理(?x){P(x)?{(?y)[P(y)?P(f(x,y))]∧～(?y)[Q(x,y)?

P(y)]}}1.消去蘊涵符號只應(yīng)用∨和～符號，以～A∨B替換A→B。(?x)｛～P(x)∨{(?y)［~P(y)∨P(f(x,y))］∧～(?y)［~Q(x,y)∨P(y)］}}2.減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上，并反復(fù)應(yīng)用狄·摩根定律。

(?x)｛～P(x)∨｛(?y)［～P(y)∨P(f(x,y))］∧(?y)［Q(x,y)∧～P(y)］｝｝3.4.1子句集的求取3.對變量標準化

對啞元（虛構(gòu)變量）改名，以保證每個量詞有其自己唯一的啞元。

(?x){～P(x)∨{(?y)［～P(y)∨P(f(x,y))］

∧(?w)［Q(x,w)∧～P(w)］}}4.消去存在量詞

以Skolem函數(shù)代替存在量詞內(nèi)的約束變量，然后消去存在量詞

(?x)｛～P(x)∨{(?y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝式中，w=g(x)為一Skolem函數(shù)。3.4.1子句集的求取5.化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形=

{前綴}{母式}

全稱量詞串無量詞公式

(?x)(?y){～P(x)∨{[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}6.把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。

(?x)(?y){[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}3.4.1子句集的求取7.消去全稱量詞

所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。

{[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}8.消去連詞符號∧用{A,B}代替(A∧B)，消去符號，∧。最后得到一個有限集，其中每個公式是文字的析取?！玃(x))∨～P(y)∨P(f(x,y))

～P(x)∨Q(x,g(x))

～P(x)∨～P(g(x))3.4.1子句集的求取9.更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中?！玃(x1)∨～P(y)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］說明：并不是所有問題的謂詞公式化為子句集都需要上述9個步驟。對于某些問題，可能不需要其中的一些步驟。3.4.1子句集的求取消解式的定義令L1，L2為兩任意原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β，如果L1和L2具有最一般合一σ，那么通過消解可以從這兩個父輩子句推導(dǎo)出一個新子句(α∨β)σ。這個新子句叫做消解式。3.4.2消解推理規(guī)則消解式求法3.4.2消解推理規(guī)則含有變量的子句之消解式要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個作用于父輩子句的置換，使父輩子句含有互補文字。3.4.3含有變量的消解式基本思想把要解決的問題作為一個要證明的命題，其目標公式被否定并化成子句形，然后添加到命題公式集中去,把消解反演系統(tǒng)應(yīng)用于聯(lián)合集，并推導(dǎo)出一個空子句(NIL)，產(chǎn)生一個矛盾，這說明目標公式的否定式不成立，即有目標公式成立，定理得證，問題得到解決。這與數(shù)學中反證法的思想十分相似。反演求解步驟給出一個公式集{S}

和自標公式L，通過反證或反演來求證目標公式L，其證明步驟如下：

1.

否定L，得～；

2.

把～L添加到S中去；

3.

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

4.

應(yīng)用消解原理，力圖推導(dǎo)出一個表示矛盾的空子句3.4.4消解反演求解過程反演求解的正確性設(shè)公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足～L的，所以不存在能夠滿足并集S∪{～L}的解釋。如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。因此，如果L在邏輯上遵循S，那么S∪{～L}是不可滿足的?？梢宰C明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生是不可滿足的?？梢宰C明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集S∪{～L}消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從S∪{～L}的子句消解得到空子句，那么L在邏輯上遵循S。3.4.4消解反演求解過程消解推理的常用規(guī)則3.4.4消解反演求解過程例子—儲蓄問題前提：每個儲蓄錢的人都獲得利息。結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢消解反演求解過程—儲蓄問題(1）規(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)

化為子句形證明：消解反演求解過程—儲蓄問題把前提化為子句形：1)

～S(x,y)∨～M(y)∨I(f(x))2)

～S(x,y)∨～M(y)∨E(x,f(x))把結(jié)論化為子句形：3)

～I(z)4)S(a,b)5)M(b)(4)

消解反演求NIL設(shè)已知：(1)能閱讀者是識字的；(2)海豚不識字；(3)有些海豚是很聰明的。試證明：有些聰明者并不能閱讀。思考題：思考題：然后把上述各語句翻譯為謂詞公式：(1)

x(R(x)→L(x))(2)

x(D(x)→乛L(x))已知條件(3)

x(D(x)∧I(x))(4)

x(I(x)∧乛R(x))需證結(jié)論證：首先，定義如下謂詞：R(x)：x能閱讀。L(x)：x識字。I(x)：x是聰明的。D(x)：x是海豚。求題設(shè)與結(jié)論否定的子句集，得(1)乛R(x)∨L(x)(2)乛D(y)∨乛L(y)(3)D(a)(4)I(a)(5)乛I(z)∨R(z)思考題：歸結(jié)得(6)R(a)(5)，(4)，{a/z}(7)L(a)(6)，(1)，{a/x}(8)乛D(a)(7),(2),{a/y}(9)□(8),(3)歸結(jié)過程演繹樹如圖所示。思考題：從反演樹求取答案步驟把問題的已知條件用謂詞公式表示出來，并化為相應(yīng)的子句集；把問題的目標的否定用謂詞公式表示出來，并化為子句集；對目標否定子句集中的每個子句，構(gòu)造該子句的重言式（即把該目標否定子句和此目標否定子句的否定之間再進行析取所得到的子句），用這些重言式代替相應(yīng)的目標否定子句，并把這些重言式加入到前提子句集中，得到一個新的子句集。對這個新的子句集，應(yīng)用消解原理求出其反演證明樹，這時證明樹的根子句不為空，稱這個證明樹為修改證明樹；用修改證明樹的根子句作為回答語句，則答案就在此根子句中。反演求解過程

如果無論約翰(JOHN)到哪里去,菲多(FIDO)也就去那里,那么如果約翰在學校里,菲多在哪里呢?

解：定義謂詞：

AT（x,y）:表示x在y處

1.已知的謂詞表示:{(?x)[AT(JOHN,x)→AT(FIDO,x)],AT(JOHN,SCHOOL)}

化為子句集:{~AT(JOHN,y)∨AT(FIDO,y),AT(JOHN,SCHOOL)}反演求解過程2.目標否定的謂詞表示：

~(?x)AT(FIDO,x)=>(?x)~AT(FIDO,x)

化為子句集:{~AT(FIDO,x)}3.構(gòu)造目標否定子句的重言式,并代替原子句

{~AT(FIDO,x)∨AT(FIDO,x)}4.將3得到的子句集加入前提子句集中:G={~AT(JOHN,y)∨AT(FIDO,y),AT(JOHN,SCHOOL),~AT(FIDO,x)∨AT(FIDO,x)}反演求解過程5.對新子句集G應(yīng)用消解原理求出反演樹:G={~AT(JOHN,y)∨AT(FIDO,y),AT(JOHN,SCHOOL),~AT(FIDO,x)∨AT(FIDO,x)}反演求解過程定義基于規(guī)則的問題求解系統(tǒng)運用If→Then規(guī)則來建立，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內(nèi)存，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)。在這種系統(tǒng)中，通常稱每個if部分為前項，稱每個then部分為后項。3.5規(guī)則演繹系統(tǒng)規(guī)則正向演繹系統(tǒng):是從已知事實出發(fā),正向使用規(guī)則對事實表達式的與或樹進行變換，直到找到一個含有目標節(jié)點的一致解樹為止。已知事實:事實表達式的與或樹。目標表達式：限制為文字的析取式。F規(guī)則:L→W,其中L為單文字,W為與或。結(jié)束條件:目標表達式是析取式.得到結(jié)束于目標節(jié)點的一致解樹。3.5.1規(guī)則正向演繹系統(tǒng)1.事實表達式的與或形變換2.事實表達式的與或樹表示3.規(guī)則的與或形變換4.目標公式的表示形式5.規(guī)則正向演繹推理過程3.5.1規(guī)則正向演繹系統(tǒng)1.事實表達式的與或形變換

–規(guī)則正向演繹系統(tǒng)中要求事實表達式化簡為與

或形。(1)消去”蘊含”和”雙條件”符號;(2)減小否定符號的轄域,使否定符號只作用于原子公式;(3)利用Skolem函數(shù)消去存在量詞;(4)對變量進行換名，使得不同的主合取元，具有不同的變量名;(5)隱去全稱量詞，默認公式中的變量受全稱量詞約束。3.5.1規(guī)則正向演繹系統(tǒng)1.

事實表達式的與或形變換把事實表示為非蘊涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫。例如有事實表達式：

(?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)｝

規(guī)則正向演繹系統(tǒng)的求解過程2.

事實表達式的與或圖表示將上例與或形的事實表達式用與或圖來表示，如下圖所示：規(guī)則正向演繹系統(tǒng)的求解過程3.

與或圖的F規(guī)則變換

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

L?W

式中：L是單文字；W為與或形的唯一公式。規(guī)則正向演繹系統(tǒng)的求解過程4.

作為終止條件的目標公式

應(yīng)用F規(guī)則的目的在于從某個事實公式和某個規(guī)則集出發(fā)來證明某個目標公式。在正向推理系統(tǒng)中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式。用文字集表示此目標公式，并設(shè)該集各元都為析取關(guān)系。結(jié)論：當正向演繹系統(tǒng)產(chǎn)生一個含有以目標節(jié)點作為終止的解圖時，此系統(tǒng)就成功地終止。

規(guī)則正向演繹系統(tǒng)的求解過程①命題邏輯的規(guī)則正向演繹過程

F規(guī)則變換:如果在與或樹中有一個葉節(jié)點剛好與某F規(guī)則L→W的前件L匹配，則將該葉節(jié)點與L用一個匹配弧連接起來，將規(guī)則后件W添加到與或樹中。這樣,就對與或樹用規(guī)則L→W實施了一次變換,得到了一個“更新”了的與或樹。規(guī)則正向演繹系統(tǒng)的求解過程規(guī)則正向演繹系統(tǒng)的求解過程例:事實表達式的與或為:((P∨Q)∧R)∨(S∧(T∨U))

規(guī)則:S→(X∧Y)∨Z規(guī)則正向演繹系統(tǒng)的求解過程②謂詞邏輯的規(guī)則正向演繹過程a)事實表達式進行與或樹表示;b)規(guī)則轉(zhuǎn)換成F規(guī)則L→W,其中L為單文字,W為與或形;c)目標表達式變換成子句形;d)對與或樹進行F規(guī)則變換;e)結(jié)束條件:找到所有葉節(jié)點都與目標節(jié)點匹配的一致解樹.規(guī)則正向演繹系統(tǒng)的求解過程F規(guī)則變換:

設(shè)與或樹中有一個端節(jié)點的文字L′和L可合一,mgu是u，則這條規(guī)則可應(yīng)用,這時用匹配弧連接的后裔節(jié)點是L，它是規(guī)則后項Wu對應(yīng)的與或樹表示的根節(jié)點,在匹配弧上標記有u,表示用u置換后可與規(guī)則匹配。規(guī)則正向演繹系統(tǒng)的求解過程例:事實與或形表示:P(A,y)∨(Q(x,A)∧R(B,y))

規(guī)則蘊涵式:P(z,B)→(S(z)∨X(B))圖應(yīng)用規(guī)則變換后得到的與或樹有兩個解樹,對應(yīng)的兩個子句是:S(A)∨X(B)∨Q(x,A)S(A)∨X(B)∨R(B,B)事實和規(guī)則組成的子句集,對文字P進行歸結(jié):①P(A,y)∨Q(x,A)②P(A,y)∨R(B,y)③￢P(z,B)∨S(z)∨X(B)④R(B,B)∨S(B)∨X(B)②③歸結(jié)σ={A/z,B/y}⑤Q(x,A)∨S(A)∨X(B)①③歸結(jié)σ={A/z,B/y}規(guī)則正向演繹系統(tǒng)的求解過程定義逆向規(guī)則演繹系統(tǒng)是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。逆向推理過程1.

目標表達式的與或形式

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

3.5.2規(guī)則逆向演繹系統(tǒng)2.

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

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

WL

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

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

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

3.5.3規(guī)則雙向演繹系統(tǒng)雙向(正向和逆向)組合演繹系統(tǒng)的構(gòu)成正向和逆向組合系統(tǒng)是建立在兩個系統(tǒng)相結(jié)合的基礎(chǔ)上的。此組合系統(tǒng)的總數(shù)據(jù)庫由表示目標和表示事實的兩個與或圖結(jié)構(gòu)組成，并分別用F規(guī)則和B規(guī)則來修正。終止條件組合演繹系統(tǒng)的主要復(fù)雜之處在于其終止條件，終止涉及兩個圖結(jié)構(gòu)之間的適當交接處。當用F規(guī)則和B規(guī)則對圖進行擴展之后，匹配就可以出現(xiàn)在任何文字節(jié)點上。

3.5.3規(guī)則雙向演繹系統(tǒng)3.6產(chǎn)生式系統(tǒng)產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)的推理產(chǎn)生式系統(tǒng)的控制策略產(chǎn)生式系統(tǒng)中的知識表示1.事實的表示：

–確定性的知識：命題、謂詞、三元組

(對象,屬性,值)或(關(guān)系,對象1,對象2)

老李和老張是朋友:

（Friend,Li,zhang）

–不確定性的知識：四元組

(對象，屬性，值，可信度因子)

極少數(shù)花的顏色是黑的產(chǎn)生式系統(tǒng)的組成2.推理過程和行為(規(guī)則)的表示產(chǎn)生式或規(guī)則：P→QIFPTHENQ–P是產(chǎn)生式的前提，或稱為前件

–Q是一組結(jié)論或操作，或稱為后件

IF(動物,本領(lǐng),會下蛋)AND(動物,本領(lǐng),會飛)THEN(動物,類別,鳥)IF(病人,癥狀,咳嗽)AND(病人,癥狀,流涕)THEN(病人,疾病,感冒,0.85)產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)的組成產(chǎn)生式系統(tǒng)由3個部分組成，即總數(shù)據(jù)庫(或全局數(shù)據(jù)庫)、產(chǎn)生式規(guī)則和控制策略。

產(chǎn)生式系統(tǒng)的組成1.綜合數(shù)據(jù)庫

–是一個用來存放與求解問題有關(guān)的各種當前信息的數(shù)據(jù)結(jié)構(gòu)。

–問題的初始狀態(tài)、事實、證據(jù)、中間推理結(jié)論及最后結(jié)果等。2.產(chǎn)生式規(guī)則庫

–是用來存放與求解問題有關(guān)的某個領(lǐng)域知識的規(guī)則的集合及其交換規(guī)則。3.控制系統(tǒng)：一組程序，用來控制系統(tǒng)的運行，決定推理方式和控制策略。

–從規(guī)則庫中選擇規(guī)則與綜合數(shù)據(jù)庫中的已知事實進行匹配。

–當匹配成功的規(guī)則多于一條時，按照某種策略從中選出一條規(guī)則去執(zhí)行。

–匹配成功時，如果規(guī)則的后件是結(jié)論則加入綜合數(shù)據(jù)庫中，如果是操作則執(zhí)行這些操作。

–如果當前執(zhí)行規(guī)則的后件滿足結(jié)束條件，則停止推理。

–記住應(yīng)用過的規(guī)則序列，便于最終給出問題的解路徑。產(chǎn)生式系統(tǒng)的組成圖產(chǎn)生式系統(tǒng)推理流程

產(chǎn)生式系統(tǒng)的組成用于動物識別的產(chǎn)生式系統(tǒng)：

②r3,r4,r5,r6匹配失敗有暗斑點長脖子長腿有奶有蹄初始綜合數(shù)據(jù)庫：長頸鹿，斑馬目標集合：順序選擇規(guī)則試與事實匹配，將匹配成功的規(guī)則執(zhí)行并做標記：有暗斑點長脖子長腿有奶有蹄哺乳動物綜合數(shù)據(jù)庫：①r1匹配失敗，r2匹配成功:④r8,r9,r10匹配失?、輗11匹配成功③r7匹配成功：有暗斑點長脖子長腿有奶有蹄哺乳動物有蹄類綜合數(shù)據(jù)庫：綜合數(shù)據(jù)庫：有暗斑點長脖子長腿有奶有蹄哺乳動物有蹄類

長頸鹿長頸鹿已在目標集合中，故推理成功結(jié)束．用于動物識別的產(chǎn)生式系統(tǒng)：控制策略與常用算法產(chǎn)生式系統(tǒng)的控制策略：當有多條規(guī)則可用時，對規(guī)則的選擇和處理方式。1.不可撤回方式思想：無論所使用過的規(guī)則是否有效，都不再撤回它的應(yīng)用。優(yōu)點：控制過程簡單。缺點：不一定能找到最優(yōu)解。2.回溯方式思想：如果確定某條規(guī)則的應(yīng)用不利于問題求解則撤回此規(guī)則的應(yīng)用。兩個問題：如何確定回溯條件和減少回溯次數(shù)。優(yōu)點：容易實現(xiàn)且空間代價小。3.圖搜索方式思想：用圖或樹把應(yīng)用規(guī)則路徑記錄下來，從中選取最優(yōu)路徑。優(yōu)點：有利于尋找最優(yōu)解?？刂撇呗耘c常用算法產(chǎn)生式系統(tǒng)的推理策略可分為：正向推理和反向推理兩種基本方式。正向推理反向推理產(chǎn)生式系統(tǒng)的推理方式事實(數(shù)據(jù))驅(qū)動、前向鏈接推理目標驅(qū)動、逆向鏈接推理控制策略與常用算法1.正向推理正向推理算法：步1將初始事實/數(shù)據(jù)置入動態(tài)數(shù)據(jù)庫；步2用動態(tài)數(shù)據(jù)庫中的事實/數(shù)據(jù)，匹配/測試目標條件，若目標條件滿足，則推理成功，結(jié)束。步3用規(guī)則庫中各規(guī)則的前提匹配動態(tài)數(shù)據(jù)庫中的事實/

數(shù)據(jù)，將匹配成功的規(guī)則組成待用規(guī)則集；步4若待用規(guī)則集為空，則運行失敗，退出。步5將待用規(guī)則集中各規(guī)則的結(jié)論加入動態(tài)數(shù)據(jù)庫，或者執(zhí)行其動作，轉(zhuǎn)步2；可以看出，隨著推理的進行，動態(tài)數(shù)