3.1圖搜索策略圖搜索控制策略

一種在圖中尋找路徑的方法。

圖中每個節點對應一個狀態，每條連線對應一個操作符。這些節點和連線(即狀態與操作符)又分別由產生式系統的數據庫和規則來標記。求得把一個數據庫變換為另一數據庫的規則序列問題就等價于求得圖中的一條路徑問題。一般圖搜索過程

狀態空間搜索的基本思想是：先把問題的初始狀態作為當前擴展節點對其進行擴展，生成一組子節點，然后檢查問題的目標狀態是否出現在這些子節點中。若出現，則搜索成功，找到了該問題的解；若沒出現，則再按照某種搜索策略從已生成的子節點中選擇一個節點作為當前擴展節點。重復上述過程，直到目標狀態出現在子節點中或沒有可供擴展的節點為止。搜索術語（用圖來描述狀態空間）節點：對應于狀態描述節點深度：根節點的深度為0,其他節點的深度規定為父節點深度加1,即dn+1=dn+1。擴展節點：應用操作符將上一狀態（節點ni）變遷到下一狀態（節點nj），ni表示被擴展節點，nj

即是由ni

擴展出的子節點。路徑：從節點ni到nk的路徑是由相鄰節點間的弧線構成的折線，通常要求路徑是無環的，否則會導致搜索過程進入死循環。搜索圖：在搜索解答路徑的過程中只畫出搜索時直接涉及到的節點和弧線，構成所謂的搜索圖。Open表：存放已經生成但未擴展節點Close表：存放已擴展或將要擴展的節點S0表示問題的初始狀態G表示搜索過程所得到的搜索圖M表示當前擴展節點新生成的且不為自己先輩的子節點集。開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表n為目標節點嗎？把n的后繼節點放入OPEN表的末端，提供返回節點n的指針修改指針方向重排OPEN表失敗成功圖3.1

圖搜索過程框圖是是否否圖搜索過程圖樹/不修改指針;圖/修改指針;修改指針:找最優解3.2

盲目搜索特點：不需重排OPEN表種類：寬度優先、深度優先、等代價搜索等。3.2.1

寬度優先搜索定義以接近起始節點的程度逐層擴展節點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它。算法開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的末端，提供返回節點n的指針失敗成功圖3.2寬度優先算法框圖是否是否3.2盲目搜索例：八數碼難題

3×3九宮棋盤，放置數碼為1-8的8個棋牌，剩下一個空格，只能通過棋牌向空格的移動來改變棋盤的布局。求解的問題——給定初始布局（即初始狀態）和目標布局（即目標狀態），如何移動棋牌才能從初始布局到達目標布局解答路徑——就是一個合法的走步序列用寬度優先搜索方法解決該問題：

為問題狀態的表示建立數據結構：3×3的一個矩陣，*矩陣元素Sij∈{0,1,…,8}；其中1≤i,j≤3，*數字0指示空格，*數字1-8指示相應棋牌。制定操作算子集：*直觀方法——為每個棋牌制定一套可能的走步：左、上、右、下四種移動。這樣就需32個操作算子。*簡易方法——僅為空格制定這4種走步，因為只有緊靠空格的棋牌才能移動。*空格移動的唯一約束是不能移出棋盤。初始狀態S0：23目標狀態Sg：123 184 804 76576523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654寬度優先搜索91011121314151617從圖中得，解的路徑是：S0→→→38173.2.2

深度優先搜索定義首先擴展最新產生的(即最深的)節點。算法防止搜索過程沿著無益的路徑擴展下去，往往給出一個節點擴展的最大深度——深度界限。與寬度優先搜索算法最根本的不同在于：將擴展的后繼節點放在OPEN表的前端。（算法框圖見教材）3.2盲目搜索例：八數碼難題

231847652318476528314765231847652831476528316475283147652831647528316475123784651238476528364175123412384765目標深度優先搜索…………2318476523184765283147652318476528314765283164752831476528316475283164752837146583214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目標設深度界限dm=4例：八數碼難題

3.2.3

等代價搜索定義

是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。算法若所有連接弧線具有相等代價，則簡化為寬度優先搜索算法。3.2盲目搜索3.3

啟發式搜索特點：重排OPEN表，選擇最有希望的節點加以擴展種類：有序搜索(A算法)、A*算法等3.3.1啟發式搜索策略和估價函數盲目搜索可能帶來組合爆炸啟發式信息

用來加速搜索過程的有關問題領域的特征信息。包括：用于決定要擴展的下一個節點的信息；在擴展一個節點時，用于決定要生成哪一個或哪幾個后繼節點的信息；用于決定某些應該從搜索樹中拋棄或修剪的節點的信息；啟發式搜索使用啟發式信息指導的搜索過程稱為啟發式搜索.

估價函數用來估算節點處于最佳求解路徑上的希望程度的函數f(n)=g(n)+h(n)n——搜索圖中的某個當前被擴展的節點；f(n)——從初始狀態節點s,經由節點n到達目標節點ng，估計的最小路徑代價；g(n)——從s到n的實際路徑代價；h(n)——從n到ng,估計的最小路徑代價。例——八數碼難題估價函數：f(n)=d(n)+w(n) 其中：d(n)為n的深度 w(n)為不在位的棋子數

如起始節點 283 164 705 則起始節點S0的估價函數值為：f( S0)=0+4=4

3.3.2

有序搜索實質

選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點。3.3啟發式搜索(1)全局擇優搜索：選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點，即總是選擇最有希望的節點作為下一個要擴展的節點。(2)局部擇優搜索：從剛生成的子節點中選擇具有最小f值的節點作為下一個要擴展的節點。開始把S放入OPEN表，計算估價函數f(s)OPEN表為空表？選取OPEN表中f值最小的節點i放入CLOSED表i為目標節點嗎？擴展i，得后繼節點j，計算f(j)，提供返回節點i的指針，利用f(j)對OPEN表重新排序，調整親子關系及指針失敗成功圖3.9有序搜索算法框圖是否是否3.3啟發式搜索算法例子八數碼難題（8-puzzleproblem）12384567（目標狀態）12384567（初始狀態）八數碼難題的有序搜索樹見下圖：3.3啟發式搜索5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖3.10八數碼難題的有序搜索樹123846（4）73.3啟發式搜索53.3.3A*算法估價函數的定義：

對節點n定義f*(n)=g*(n)+h*(n),表示從S開始約束通過節點n的一條最佳路徑的代價。

希望估價函數f定義為：f(n)=g(n)+h(n)

——g是g*的估計，h是h*的估計3.3啟發式搜索g*(n)：從s到n的最小路徑代價值h*(n)：從n到g的最小路徑代價值f*(n)=g*(n)+h*(n)：從s經過n到g的最小路徑的總代價值g(n)、h(n)、f(n)分別是g*(n)、h*(n)、f*(n)的估計值g(n)通常選擇為當前所找到的從初始節點S到節點n的“最佳”路徑的代價值，顯然有g(n)g*(n)在A算法中，如果滿足條件：

(1)

g(n)是對g*(n)的估計，且g(n)>0；(2)h(n)是h*(n)的下界，即對任意節點n均有 0≤h(n)≤h*(n)

則A算法稱為A*算法A*算法的定義：

定義1在GRAPHSEARCH過程中，如果第8步的重排OPEN表是依據f(n)=g(n)+h(n)進行的，則稱該過程為A算法。定義2在A算法中，如果對所有的n存在h(n)≤h*(n),則稱h(n)為h*(n)的下界，它表示某種偏于保守的估計。定義3采用h*(n)的下界h(n)為啟發函數的A算法，稱為A*算法。當h=0時，A*算法就變為有序搜索算法。

A*算法的可納性

對任一個圖，存在從S到目標的路徑，如果一個搜索算法總是結束在一條從S到目標的最佳路徑上，則稱此算法是可采納的。算法A*保證只要最短路徑存在，就一定能找出這條路徑，所以算法A*是可納的。

A*算法應用舉例八數碼難題估價函數：f(n)=d(n)+w(n) 其中：d(n)為n的深度 w(n)為不在位的棋子數取h(n)=w(n),則有w(n)≤h*(n),h(n)滿足A*算法的限制條件。1238476528316475初始狀態目標狀態

在八數碼難題中,令估價函數

f(n)=d(n)+p(n)啟發函數h(n)=p(n),p(n)為不在位的棋子與其目標位置的距離之和，則有p(n)≤h*(n),滿足A*算法的限制條件。283164752831476528316475283164752318476528314765283147652318476523184765123847651238476512378465目標12345h=5,g=0,f=5h=6,g=1,f=7h=4,g=1,f=5h=6,g=1,f=7h=5,g=2,f=7h=3,g=2,f=5h=5,g=2,f=7h=2,g=3,f=5h=4,g=3,f=7h=1,g=4,f=5h=0,g=5,f=5w(n)——不在位的棋子數，不夠貼切，錯誤選用節點加以擴展。p(n)——更接近于h*(n)的h(n)，其值是節點n與目標狀態節點相比較，每個錯位棋子在假設不受阻攔的情況下，移動到目標狀態相應位置所需走步的總和。p(n)比w(n)更接近于h*(n)，因為p(n)不僅考慮了錯位因素，還考慮了錯位的距離（移動次數）。說明h值越大,啟發功能越強,搜索效率越高.特別地(1)h(n)=h*(n)

搜索僅沿最佳路徑進行,效率最高.(2)h(n)=0

無啟發信息,盲目搜索,效率低.(3)h(n)>h*(n)

是一般的A算法,效率高,但不能保證找到最佳路徑.有時為求解難題取h(n)>h*(n),以提高效率.3.4博弈樹的啟發式搜索參與搜索的不只是一個主體，而包括對抗的多方(對弈)任何一方在選擇自己的行為時，都要將對方可能采取的對策考慮在內由此而產生的搜索樹稱為博弈樹(博弈圖)博奕:兩棋手按一定規則輪流走步,雙方都知道對方的走步,當滿足一定條件時,走步結束,這時,或一方取勝,或為和局.1.博弈問題

我方（指程序方，叫MAX）每走一著棋（半回合），都力圖使自己通向取勝的目標。輪到MAX走棋時，由于它掌握著出棋的主動權，只要此時的各種走法中有一個能通向勝局，它就會毫不客氣地出這一著。因此由MAX方出棋的結點具有或結點的性質。對手（叫MIN，是一個回合的對棋者）每走一著棋（半回合），都力圖干擾MAX的選擇，使其偏離取勝的目標。輪到MIN走棋時，由于它掌握著對棋的主動權，因此只要此時的全部著法中有一個能導致敗局，它就會毫不客氣地出這一著。因此由MIN對棋的結點具有與終點的性質。所以-博弈樹一般都是與／或樹。博弈樹的特點：（1）初始格局是初始節點（2）博弈樹中或節點和與節點逐層交替出現（3）所有能使自己一方獲勝的終局都是本原問題，而相應使對方獲勝的棋局均為不可解節點。例分火柴游戲

設一堆火柴有7根，由MAX（我方）和MIN（對手）兩人輪流來分它們，要求每次都要把某一堆火柴分成不相等的兩部分，最后不能分下去的人為負，對方為勝。如果MIN先走，可以有三種選擇：（6，1）、（5，2）、（4，3）在每一種選擇下，MAX又可以有兩種走法，整個博弈過程的狀態空間如圖所示。結點中的數字表示各堆火柴的根數分布，名字表示輪到他繼續向下走棋。(5,1,1,MIN)(6,1,MAX)(5,2,MAX)(4,3,MAX)(3,2,2,MIN)(4,2,1,MIN)(7,MIN)(3,3,1,MIN)(4,1,1,1,MAX)(3,2,1,1,MAX)(2,2,2,1,MAX)(2,1,1,1,1,MAX)(3,1,1,1,1,MIN)(2,2,1,1,1,MIN)2.極大極小過程

極大極小搜索策略是考慮雙方對弈若干步之后,從可能的走步中選一步相對好棋的走法來走,即在有限的搜索深度范圍內進行求解。定義一個靜態估計函數f,以便對棋局的勢態(節點)作出優劣估值。一般規定有利于MAX的勢態,f(p)取正值,有利于MIN的勢態,f(p)取負值,勢均力敵的勢態,f(p)取0值,若f(o)=+∞,則表示MAX贏,若f(o)=-∞,則表示MIN贏。在輪到MAX走時,選擇f(p)大的節點走;而輪到MIN走時,應考慮對方會選f(p)最小的節點走.因此,在博奕圖搜索時,可采用一步走f(p)值極大的節點(MAX走),一步走f(p)值極小的節點(MIN走),這樣交替前進的方法.這種搜索過程稱為極大極小過程.例:一字棋 棋局中,我方(MAX)棋子用表示,對方(MIN)棋子用°表示.開始由我方先走,估價函數:

我方獲勝e(p)=- 對方獲勝

e(+p)-e(-p)其他情況

空格視為時我方三連子數-空格視為°時對方三連子數°e(p)=6-4=2為了計算非葉節點的值，必須從葉節點向上倒推，叫倒推值。MAX的倒推值是其后繼節點估值的最大值。MIN的倒推值是其后繼節點估值的最小值。

°°°°°°°°°°°°1-1-211010-1-10-10-2

12°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°11213121010201112231221100°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°°111212-101001122111-------ABCD3.

-剪枝

極大極小過程是把搜索樹的生成和格局估值這兩個過程分開來進行,即先生成全部搜索樹,然后再進行端節點靜態估值和倒推值計算,這顯然會導致低效率。如果把生成和倒推估值結合起來進行,再根據一定條件判定,有可能盡早修剪掉一些無用的分枝,即α-β剪枝過程的思想。α-β剪枝方法：（1）MAX節點的值為當前子節點的最大倒推值；MAX節點的值在搜索過程中永不減少（2）MIN節點的值為當前子節點的最小倒推值；MIN節點的值在搜索過程中永不增加

（3）α-β剪枝規則：①任何MAX節點n的值大于或等于它的任一先輩節點MIN的值,則可終止該MAX節點以下的搜索,并可將其最終倒推值設為它的值.這種剪枝稱為β剪枝②任何MIN節點n的值小于或等于它的任一先輩節點MAX的值,則可終止該MIN節點以下的搜索,并可將其最終倒推值設為它的值。這種剪枝稱為α剪枝。

α剪枝：α（先輩節點）≥β（后繼節點）β剪枝：α（后繼節點）≥β（先輩節點）05-333-302-23523α≥0β≤0α≥00-303α≥330β≤52α≥2β≤-5-5-522ααββα剪枝：α（先輩節點）≥β（后繼節點）β剪枝：α（后繼節點）≥β（先輩節點）β≤-3α剪枝β剪枝2α剪枝481*5P80**α≥4β≤4α≥4414α≥554β≤00α≥0β≤-6-6-6004ααβββ≤1α剪枝β剪枝S0KLM6FNGQ5HD*ABRISJEα剪枝α剪枝C3.5消解原理回顧：

原子公式（atomicformulas）

文字—一個原子公式及其否定。P(x),

P(x)

子句—由文字的析取組成的合適公式。P(x)Q(x)

空子句---不包含任何子句的文字。用NIL表示

子句集---由子句或空子句所構成的集合.

消解—對謂詞演算公式進行分解和化簡，消去一些符號，以求得導出子句。3.5.1

子句集的求取步驟：共9步。例子:將下列謂詞演算公式化為一個子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝開始：消去蘊涵符號只應用∨和～符號，以～A∨B替換AB。(1)(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}3.5消解原理(2)減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上，并反復應用狄·摩根定律。(3)對變量標準化對啞元（虛構變量）改名，以保證每個量詞有其自己唯一的啞元。3.5消解原理(2)(x)｛～P(x)∨｛(y)［～P(y)∨P(f(x,y))］∧(y)［Q(x,y)∧～P(y)］｝｝(3)(x)｛～P(x)∨｛(y)［～P(y)∨P(f(x,y))］∧(w)［Q(x,w)∧～P(w)］｝｝(4)消去存在量詞以Skolem函數代替存在量詞內的約束變量，然后消去存在量詞化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形={前綴}{母式}

全稱量詞串無量詞公式(4)(x)｛～P(x)∨{(y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x)）∧～P(g(x))］｝｝式中，w=g(x)為一Skolem函數。(5)(x)(y)｛～P(x)∨｛［～P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝3.5消解原理把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(7)消去全稱量詞所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現的全稱量詞。3.5消解原理(6)(x)(y)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝(7)｛［～P(x)∨～P(y)∨P(f(x,y))］∧［～P(x)∨Q(x,g(x))］∧［～P(x)∨～P(g(x))］｝(8)消去連詞符號∧用{A,B}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現在一個以上的子句中。3.5消解原理(8)

～P(x)∨～P(y)∨P(f(x,y))

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

～P(x)∨～P(g(x))(9)

～P(x1)∨～P(y)∨P［f(x1,y)］～P(x2)∨Q［x2,g(x2)］～P(x3)∨～P［g(x3)］3.5.2

消解推理規則消解式的定義

令L1，L2為兩任意原子公式；L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通過消解可以從這兩個父輩子句推導出一個新子句(α∨β)σ。這個新子句叫做消解式。

消解式求法取各子句的析取，然后消去互補對。3.5消解原理幾種從父輩子句求消解式的例子假言推理AAB則B合并P∨QPQ則Q重言式P∨Q～

P∨

～

Q空子句～PP鏈式PQQR則PR3.5.3含有變量的消解式

要把消解推理規則推廣到含有變量的子句，必須找到一個作用于父輩子句的置換，使父輩子句含有互補文字。

含有變量的子句之消解式例子P[x,f(y)]∨Q(x)∨R[f(a),y] ～P[f(f(a)),z]∨R(z，w)Q[f(f(a))]∨R(f(a)，y)∨R(f(y)，w)σ={f(f(a))/x,f(y)/z}3.5消解原理3.5.4

消解反演求解過程消解反演

給出{S}，L否定L，得～L；把～L添加到S中去；把新產生的集合｛～L，S｝化成子句集；應用消解原理，力圖推導出一個表示矛盾的空子句例1—儲蓄問題前提：每個儲蓄錢的人都獲得利息。結論：如果沒有利息，那么就沒有人去儲蓄錢3.5消解原理(1）規定原子公式：

S(x,y)表示“x儲蓄y”

M(x)表示“x是錢”

I(x)表示“x是利息”

E(x，y)表示“x獲得y”(2）用謂詞公式表示前提和結論：前提：(x)[(y)(S(x,y))∧M(y)][(y)(I(y)∧E(x,y))]結論：～(x)I(x)(x)(y)(M(y)→～S(x,y))(3)

化為子句形證明：3.5消解原理把前提化為子句形：1)

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

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

～I(z)4)

S(a,b)5)

M(b)(4)

消解反演求NIL圖3.12儲蓄問題反演樹子句（1）子句（3）f(x)/z～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}～S(x,y)∨～M(y)子句（6）3.5消解原理例2：“快樂學生”問題

假設：任何通過計算機考試并獲獎的人都是快樂的。任何肯學習或幸運的人都可以通過所有考試，張不肯學習但他是幸運的，任何幸運的人都能獲獎。求證：張是快樂的。解：將問題用謂詞表示如下：“任何通過計算機考試并獲獎的人都是快樂的”

(x)(Pass(x,computer)

Win(x,prize))Happy(x))“任何肯學習或幸運的人都可以通過所有考試”(x)(

y)(Study(x)

Lucky(x)Pass(x,y))“張不肯學習但他是幸運的”Study(zhang)

Lucky(zhang)“任何幸運的人都能獲獎”(x)(Lucky(x)Win(x,prize))

結論“張是快樂的”的否定Happy(zhang)將謂詞轉化為子句集：

P1:

Pass(x,computer)

Win(x,prize)Happy(x)P2:

Study(y)

Pass(y,z)P3:

Lucky(u)

Pass(u,v)P4:Study(zhang)P5:

Lucky(zhang)P6:

Lucky(w)Win(w,prize)

Q:Happy(zhang)所以：S’={P1,

P2,

P3,

P4,

P5,

P6},S’’=

{P1,

P2,

P3,

P4,

P5,

P6,

Q}對S’’進行歸結操作，直至推出NIL。歸結反演過程如下：P6

Pass(x,computer)

Win(x,prize)Happy(x)

Lucky(w)Win(w,prize)

Pass(w,computer)

Happy(w)

Lucky(w)置換{w/x}

P1Happy(zhang)

Q

Pass(zhang,computer)

Lucky(zhang)置換{zhang/w}Lucky(zhang)

P5

Pass(zhang,computer)

Lucky(u)

Pass(u,v)

P3

Lucky(zhang)置換{zhang/u,computer/v}Lucky(zhang)

P5NIL

歸結出NIL，證明結論為真。從反演樹求取問題的答案步驟1.把問題的已知條件用謂詞公式表達出來，并轉換成子句集S’；2.把問題的目標的否定用謂詞公式表達出來，并轉換成子句集Q；3.對Q中的每個子句，構造其重言式（包含互補文字對的子句），代替相應的目標否定子句，加入到S’中，得到S’’；4.對S’’應用消解原理求出消解樹，該消解樹的根子句為所求答案。實質把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。例3：已知：李和張是同班同學，如果x和y是同班同學，則x的教室也是y的教室，現在張在302教室上課，問：李現在在哪里上課？解：定義謂詞：

C(x,y)x和y是同班同學

At(x,u)x在u教室上課已知前提謂詞公式表示如下：

C(zhang,li)(x)(

y)(u)(C(x,y)

At(x,u)At(y,u))At(zhang,302)目標的否定用謂詞公式表示如下：(v)At(li,v)將謂詞轉化為子句集：

P1:C(zhang,li)P2:C(x,y)

At(x,u)

At(y,u)P3:

At(zhang,302)把目標的否定化為子句，用重言式Q:

At(li,z)

At(li,z)代替所以：S’={P1,

P2,

P3,

},S’’=

{P1,

P2,

P3,

Q}對S’’進行歸結操作，歸結反演過程如下：

P3

C(x,y)

At(x,u)

At(y,u)

At(li,z)

At(li,z)

QAt(li,z)

C(x,li)At(x,z)C(zhang,li)

P1At(li,z)

At(zhang,z)置換{li/y,z/u}At(zhang,302)

P2At(li,302)置換{zhang/x}置換{302/z}答案：李在302教室。正向演繹系統的基本思想邏輯蘊涵式與子句的區別：上面二個表達式在邏輯上是等價的，但所表達的概念有區別：：強調推理性(即：前件為真時后件為真)

：只是表示了A、B、C中有一個為真，則公式為真可見：將蘊涵式寫成與其等價的子句形式會損失一些邏輯信息。直接利用蘊涵式所做的證明系統就是基于規則的演繹系統。3.6規則演繹系統

定義

基于規則的問題求解系統運用If→Then規則來建立，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內存，then部分用于規定放入工作內存的新斷言。這種基于規則的系統叫做規則演繹系統。在這種系統中，通常稱每個if部分為前項，稱每個then部分為后項。IFATHENBIFBTHENCIFCTHEND已知A

3.6.1規則正向演繹系統定義正向規則演繹系統是從事實到目標進行操作的，即從狀況條件到動作進行推理的，也就是從if到then的方向進行推理的。

3.6規則演繹系統正向規則演繹的求解過程事實表達式的與或形變換

在基于規則的正向演繹系統中，我們把事實表示為非蘊涵形式的與或形，作為系統的總數據庫。方法：將規則前件的事實表達式從規則中分離出來，單獨變換成與或形式的表達式，但是不必化簡成子句。例如：一個事實表達式：消去存在量詞，由常量代替變元x，得到一個與或表達式：利用等價變換，得到：對第一個合取項進行變量換名(w/y)，目的是保證每個合取項的變量名都不相同得到公式：上式不是子句，但是一個與或表達式，可以直接用于正向推理系統。2.用與或圖表示一個與或表達式：與或圖中的節點代表子表達式當表達式為析取式(E1∨E2∨

…∨Ek)時，則每個子表達式表示為原表達式的一個后繼節點，且用一個K連接符連接每個Ei

，表示為與關系。當表達式為合取式(E1∧E2∧

…∧Ek)時，則每個子表達式單獨作為原表達式的一個子節點，用1連接符連接，表示為或關系。上例的事實表達式用與或圖表示如下：可以看出，每個端節點都是一個文字，所以與或圖相當于把一個表達式按照與或關系拆分成文字表示。討論：利用與或圖求解圖：方法與可分解系統中的解圖求法相同。不同的是與或圖中的節點之間的合取、析取關系是相反的。因此，求解圖是按照K連接方式求解，而不是按照真值求解。上圖中的三個解圖分別構成三個子句：

Q(w,A),~R(y)∨~S(A,y),~P(y)∨~S(A,y)基于規則正向推理系統中的與或圖是一種知識表達方式；可分解系統中的與或圖是一種圖搜索方式，二者是不同的。3.與或圖的F規則變換

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

LW 式中：L是單文字；W為與或形的唯一公式。3.6規則演繹系統如果規則為(L1∨L2)→W形式，即前提是析取形式，則將其分解成二條規則

L1→W，L2→W如果規則為(L1∧L2)→W形式，即前提是合取形式，不予討論。例：初始數據庫的與或表達式為：

[(P∨Q)∧R]∨[S∧(T∨U)]

規則：S→(X∧Y)∨Z推理過程：①用與或圖表示初始條件表達式②尋找與規則前提匹配的文字③用匹配弧連接上述兩個文字④將規則結論的與或圖連接到前提上，擴充與或圖⑤正向系統的推理樹根節點在下部上面例題的推理樹見下頁。從上圖的事實表達式部分可以得到四個子句：(1)(P∨Q)∨S(2)(P∨Q)∨(T∨U)(3)(R∨S)(4)R∨(T∨U)[(P∨Q)∧R]∨[S∧(T∨U)]X∧YXYZSSTUT∨US∧(T∨U)(P∨Q)∧RP∨QRPQ規則：S→(X∧Y)∨Z從上圖的規則結論部分可以得到二個子句：(1)X∨Z(2)Y∨Z用這二個子句代替前提中的S，得到四個新子句(1)(P∨Q)∨(X∨Z)(2)(P∨Q)∨(Y∨Z)(3)R∨(X∨Z)(4)R∨(Y∨Z)下面說明這四個子句就是用事實表達式和規則構成的子句集進行歸結所得到的全部歸結式。X∧YXYZS首先將事實表達式和規則寫成子句形式：事實表達式[(P∨Q)∧R]∨[S∧(T∨U)](P∨Q∨S)∧(P∨Q∨T∨U)∧(R∨S)∧(R∨T∨U)規則S→(X∧Y)∨Z~S∨(X∧Y)∨Z(~S∨X∨Z)∧(~S∨Y∨Z)得到子句集：{P∨Q∨S,P∨Q∨T∨U,R∨S,R∨T∨U,~S∨X∨Z,~S∨Y∨Z}①②③④⑤⑥由上面的子句集求出歸結式：①與⑤式：P∨Q∨X∨Z①與⑥式：P∨Q∨Y∨Z③與⑤式：R∨X∨Z③與⑥式：R∨Y∨Z由此可見，用歸結方法與用與或樹方法得到的歸結式是相同的。例：事實表達式A∨B

規則R1：A→(C∧D)R2：B→(E∧G)

目標C∨G推理樹：由此解圖得到子句集：{C∨E,C∨G,D∨E,D∨G}其中：C∨G是目標A∨BCGCDEGABABR1R23.6.2規則逆向演繹系統定義

逆向規則演繹系統是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。

求解過程目標表達式的與或形式與或圖的B規則變換作為終止條件的事實節點的一致解圖3.6規則演繹系統1目標表達式的與或表示逆向推理系統從目標開始，與正向系統相反，規則的使用是反向的。目標表達式的與或形式：(1)利用skolem函數對目標公式進行標準化（同以前講的標準化過程相同）(2)各析取項之間變元要各不相同（變量換名）(3)子表達式之間為析取關系時，使用1連接符連接子表達式之間為合取關系時，使用K連接符連接(4)與或圖的根節點在上面例：目標公式：標準化，得到：變量換名，得到：2逆向推理系統關于規則的限制：B規則的形式：W→L其中：W：任何與或公式L：單文字結論①規則中的變元全部是全稱量詞約束②如果規則為W→(L1∧L2)形式，則分解為兩條規則：

W→L1

和W→L2推理過程：(1)用與或圖表示目標表達式(2)尋找與規則結論匹配的文字(3)用匹配弧連接上述的二個匹配文字(4)將規則的結論與前提連接，擴充與或圖，直至出現事實表達式的文字(5)反向推理樹的根節點在上面反向推理例題：P83事實表達式：F1：D(FIDO)F2：~B(FIDO)F3：W(FIDO)F4：M(MR)規則：R1：（W(x1)∧D(x1))→F(x1)R2：(F(x2)∧~B(x2))→~A(y2,x2)R3：M(x3)→C(x3)目標公式：()()（C(x)∧D(y)∧~A(x,y)）得到一個解圖：M(MR)∧D(FIDO)∧W(FIDO)∧D(FIDO)∧~B(FIDO)判斷是否是一致解圖：C(x)~A(x,y)D(y)~A(y2,x2)M(x3)F(x2)~B(x2){x3/x}{y2/x,x2/y}{FIDO/y}逆向推理樹C(x)∧D(y)∧~A(x,y)C(x3)D(FIDO)M(MR){MR/x3}F(x1)~B(FIDO){FIDO/x2}{x1/x2}D(x1)W(x1)W(FIDO)D(FIDO){FIDO/x1}{FIDO/x1}(1)由反向推理樹得到所有置換：{{x3/x},{MR/x3},{{FIDO/y},{y2/x,x2/y},{x1/x2},{FIDO/x2},

{FIDO/x1},{FIDO/x1}}(2)求出：

U1=(x,x3,y,x,y,x2,x2,x1,x1)U2=(x3,MR,FIDO,y2,x2,x1,FIDO,FIDO,FIDO)(3)求出合一復合：

U=(MR/x,FIDO/y)(4)利用合一復合對目標公式作置換，得到置換例：

C(MR)∧D(FIDO)∧~A(MR,FIDO)該置換例就是推理結果

正向和逆向組合系統是建立在兩個系統相結合的基礎上的。此組合系統的總數據庫由表示目標和表示事實的兩個與或圖結構組成。這些與或圖結構分別用正向系統的F規則和逆向系統的B規則來修正。3.6.3規則雙向演繹系統3.6規則演繹系統3.7產生式系統定義：用來描述若干個不同的以一個基本概念為基礎的系統。這個基本概念就是產生式規則或產生式條件和操作對的概念。實質：在產生式系統中，論域的知識分為兩部分：用事實表示靜態知識，如事物、事件和它們之間的關系；用產生式規則表示推理過程和行為。由于這類系統的知識庫主要用于存儲規則，因此又把此類系統稱為基于規則的系統。3.7.1產生式系統的組成圖3.22產生式系統的主要組成控制策略總數據庫規則庫3.7產生式系統規則庫用于存放與求解問題有關的某個領域知識的規則集。在建立規則庫時，應注意如下問題：

（1）規則庫知識的完整性、一致性、準確性、靈活性。

（2）對知識進行合理的組織與管理：目的是使得推理避免訪問與所求解的問題無關的知識，以提高問題求解效率。總數據庫總數據庫又稱為事實庫、上下文、黑板等。它是一個用于存放問題求解過程中各種當前信息的數據結構，例如：問題的初始狀態、原始證據、推理中得到的中間結論、最終結論等。 當規則庫中某條產生式的前提可與總數據庫中的某些已知事實匹配時，該產生式就被激活，并把其結論放入總數據庫中，作為后面推理的已知事實。顯然，總數據庫的內容是在不斷變化的，是動態的。總數據庫中的已知事實通常用字符串、向量、集合、矩陣、表等數據結構表示。控制策略控制策略又稱推理機構，由一組程序組成，負責整個產生式系統的運行，實現對問題的求解。主要包括推理策略和搜索策略兩部分。

推理策略：主要解決推理方向、沖突消解等問題。搜索策略：主要解決搜索線路、推理效果、推理效率等問題。控制策略的主要工作：（1）按一定的策略從規則庫中選擇與總數據庫中的已知事實相匹配的規則。（2）當發生沖突（即匹配成功的規則不止一條）時，調用相應的沖突解決策略予以消解。（3）在執行某條規則時，若該規則的右部是一個或多個結論，則把這些結論加到總數據庫中；若規則的右部是一個或多個操作，則執行這些操作。（4）對于不確定性知識，在執行每一條規則時，還要按一定的算法計算結論的不確定性。（5）對要執行的規則，如果該規則的后件滿足問題的結束條件，則停止推理。（6）在問題的求解過程中，記住應用過的規則序列，以便最終能夠給出問題的解路徑。選擇規則到執行操作的步驟

1匹配把當前數據庫與規則的條件部分相匹配。

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

3操作操作就是執行規則的操作部分。3.7產生式系統選取規則的原則稱為控制策略（沖突消解）不可撤回方式：屬盲目性搜索,利用問題給出的局部知識選一條可應用規則并作用當前總數據庫,接著再根據新狀態繼續選取規則,搜索過程一直進行下去,不必考慮撤回用過的規則。回溯方式：在問題求解過程中選擇一條規則執行時，建立其回溯點，保留搜索路徑，如以后發現此規則不合適，按原路返回，重新選取另一條規則，繼續搜索過程。圖搜索方式：用圖表示問題求解過程，圖中結點代表問題的狀態，結點間的弧代表應用的規則。用某種方法選擇應用規則，并以圖結構記錄狀態變化過程，直到求出問題的解答。小結：①不可撤回方式相當于沿著單獨的一條路向下延伸搜索下去；②回溯方式不保留完整的搜索樹結構，只顧當前工作的一條路徑，回溯就是對這條路徑進行修正；③圖搜索方式記下完整的搜索樹；3.7.2產生式系統的推理

產生式系統的問題求解過程即為對解空間的搜索過程，也就是推理過程。按照搜索的方向可把產生式系統分為正向推理、逆向推理和雙向推理。3.7產生式系統正向推理：從一組表示事實的謂詞或命題出發，使用一組產生式規則，用以證明該謂詞公式或命題是否成立。

逆向推理：從表示目標的謂詞或命題出發，使用一組產生式規則證明事實謂詞或命題成立，即首先提出一批假設目標，然后逐一驗證這些假設。

雙向推理：雙向推理的推理策略是同時從目標向事實推理和從事實向目標推理，并在推理過程中的某個步驟，實現事實與目標的匹配。3.7產生式系統（1）正向推理從已知事實出發，正向使用推理規則的推理方式，也稱為數據驅動推理或前向鏈推理。基本思想：用戶將初始證據放入總數據庫，推理機根據總數據庫中的初始己知事實，到知識庫中找出當前可適用的規則，形成可用規則集，然后按照沖突消解策略，從知識集中選擇一條規則進行推理，并將推出的新事實加入到總數據庫中作為下一步推理的已知事實,重復進行這一過程，直到求得了所要求的解或者沒有規則可用.例如，有規則集如下：規則1：P1→P2規則2：P2→P3規則3：P3→q3設已知事實P1，正向推理推出q3過程如圖：P1P2P3q3已知規則1(q1)規則2(q2)規則3推出正向推理算法：(1)將用戶提供的初始已知事實送入總數據庫DB；(2)檢查總數據庫DB中是否已經包含了問題的解，若有,則求解結束，并成功退出；否則轉(3)；(3)根據總數據庫DB中的已知事實，掃描知識庫KB，檢查KB中是否有可適用(即可與DB中已知事實匹配)的規則，若有，把KB中所有的適用知識都選出來，構成可適用的知識集KS，否則轉(5)；(4)若KS不空，按某種沖突消解策略從中選出一條知識進行推理，并將推出的新事實加入DB中，然后轉〔2)；若KS空，則轉(5)；(5)詢問用戶是否可進一步補充新的事實，若可補充，則將補充的新事實加入DB中，然后轉(3)；否則表示求不出解，失敗退出;正向推理特點：優點：直觀，允許用戶主動提供有用的事實，適用于診斷、設計、預測、監控等領域。缺點：推理無明確目標，推理效率較低。（2）反向推理以某個假設目標作為出發點的推理方法，也稱為假設驅動推理或后向鏈推理。基本思想：首先選定—個假設目標，然后尋找支持該假設的證據，若所需的證據都能找到，則說明原假設是成立的；若無論如何都找不到所需要的證據，說明原假設不成立，此時需要另作新的假設。P1P2P3目標q3事實規則1假定規則2規則3假定假定結論q3反向推理算法：(1)將要求證的假設(目標)構成一個