人工智能主講:吳順祥

教授模式識別與智能系統研究所Powerpoint中南大學智能系統與智能軟件研究所第三章搜索推理技術3.6產生式系統3.7系統組織技術3.8不確定性推理3.9非單調推理3.10小結3.1圖搜索策略3.2盲目搜索3.3啟發式搜索3.4消解原理3.5規則演繹系統中南大學智能系統與智能軟件研究所第三章搜索推理技術討論的問題：有哪些常用的搜索算法。問題有解時能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。3中南大學智能系統與智能軟件研究所第三章搜索推理技術從問題表示到問題的解決，有一個求解的過程。接下來要研究的是實現求解的過程，采用的基本方法包括搜索和推理。本章先介紹搜索技術，將要討論問題求解的搜索原理，包括一些早期的搜索技術或用于解決比較簡單問題的搜索原理和一些比較新的能夠求解比較復雜問題的搜索原理，包括算法、遺傳算法和模擬退火算法等。4中南大學智能系統與智能軟件研究所3.1

圖搜索策略例子：從某王姓家族的四代中找王A的后代且其壽命為X的人。

王A：壽命47，有兒子王B1、王B3、王B2

王B1：壽命77，有兒子王C1、王C2

王B3：壽命52，有兒子王D1

王B2：壽命65，有兒子王E1、王E2

王F1：壽命32

王G1：壽命96

王C2：壽命87，有兒子王F1

王D1：壽命77，沒有兒子

王E1：壽命57，有兒子王G1

王E2：壽命92，有兒子王H1

王C1：壽命27，沒有兒子

王H1：壽命51若X=57，下面討論一種可通用的圖搜索策略求解此問題。5中南大學智能系統與智能軟件研究所3.1

圖搜索策略如果是一個N代的家族表中找其壽命為X的人，我們最可能用的手工方法是從家族表的開始往下，例中還要求所找的人是某人的后代，就比較復雜了。如果用圖來表示，就很容易了。圖中把姓氏省去，每個成員的后代按例子中給出名字的先后順序。圖示為：6中南大學智能系統與智能軟件研究所3.1

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

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

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

圖搜索(GRAPHSEARCH)的一般過程如下：

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

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

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

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

(5)若n為一目標節點，則有解并成功退出，此解是追蹤圖G中沿著指從n到S這條路徑而得到的(指針將在第7步中設置)。8中南大學智能系統與智能軟件研究所圖搜索過程(6)擴展節點n，同時生成不是n的祖先的那些后繼節點的集合M。把M的這些成員作為n的后繼節點添入圖G中。

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

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

(9)GOLOOP。9中南大學智能系統與智能軟件研究所圖搜索過程圖搜索算法中的幾個重要名詞

1．OPEN表：包括節點和父節點。2．CLOSED表：包括節點編號、節點和父節點。3．搜索圖與搜索樹

此過程生成一個明確的圖G(稱為搜索圖)和一個G的子集T(稱為搜索樹)，樹T上的每個節點也在圖G中。搜索樹是由第7步中設置的指針來確定的。G中的每個節點(除S外)都有一個只指向G中一個父輩節點的指針，該父輩節點就定為樹中那個節點的唯一父輩節點。圖搜索過程圖如下：10中南大學智能系統與智能軟件研究所開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表n為目標節點嗎？把n的后繼節點放入OPEN表的末端，提供返回節點n的指針修改指針方向重排OPEN表失敗成功圖3.1圖搜索過程框圖是是否否3.1圖搜索策略11中南大學智能系統與智能軟件研究所圖搜索方法的幾點分析：

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

盲目搜索

盲目搜索又叫做無信息搜索：一般只適用于求解比較簡單的問題，它只是可以區分出哪個是目標狀態。一般是按預定的搜索策略進行搜索。沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復雜問題的求解。我們將學習的寬度優先搜索和深度優先搜索，屬于盲目搜索方法。特點：不需重排OPEN表種類：寬度優先、深度優先、等代價搜索等。啟發式搜索是在搜索過程中加入了與問題有關的啟發式信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解并找到最優解。13中南大學智能系統與智能軟件研究所3.2.1

寬度優先搜索(breadth-firstsearch)定義:以接近起始節點的程度逐層擴展節點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到它?；仡櫳弦还澋膶ふ覊勖鼮閄的人的例子，如果搜索時，從節點A開始，對他的三個兒子按從左至右搜索，然后對他的所有孫子按從左至右搜索，依此下去。這種搜索方式就是寬度優先搜索。

寬度優先搜索的定義：如果搜索是以接近起始節點的程度依次擴展節點的，那么這種搜索就叫做寬度優先搜索(breadth-firstsearch)，如圖3.3所示。

從圖可見，這種搜索是逐層進行的；在對下一層的任一節點進行搜索之前，必須搜索完本層的所有節點。14中南大學智能系統與智能軟件研究所寬度優先搜索算法如下：

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

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

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

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

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

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

寬度優先搜索(breadth-firstsearch)15中南大學智能系統與智能軟件研究所開始把S放入OPEN表OPEN表為空表？把第一個節點(n)從OPEN表移至CLOSED表是否有后繼節點為目標節點？擴展n，把n的后繼節點放入OPEN表的末端，提供返回節點n的指針失敗成功圖3.2寬度優先算法框圖是否是否3.2盲目搜索16中南大學智能系統與智能軟件研究所寬度優先搜索方法分析：

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

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

例：把寬度優先搜索應用于八數碼難題時所生成的搜索樹，即要把初始棋局變為目標棋局的問題。17中南大學智能系統與智能軟件研究所例子

八數碼難題（8-puzzleproblem）

1238456712384567（目標狀態）（初始狀態）規定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節點。從圖可見，要擴展26個節點，共生成46個節點之后才求得解（目標節點）。3.2盲目搜索18中南大學智能系統與智能軟件研究所1238456712384123845674123856712384123845671238456712384567678910111213123845675675671123845671238456712384567123845672345圖3.4八數碼難題的寬度優先搜索樹134561238456712384567123845671238456712384567232425262712367822123845671238456712384567123845671238456712384567123845671415161718192021123845673.2盲目搜索19中南大學智能系統與智能軟件研究所3.2.2深度優先搜索(depth-firstsearch)

在深度優先搜索中，我們首先擴展最新產生的(即最深的)節點。深度相等的節點可以任意排列。

我們定義節點的深度如下：

(1)起始節點(即根節點)的深度為0。

(2)任何其它節點的深度等于其父輩節點深度加上1。

首先，擴展最深的節點的結果使得搜索沿著狀態空間某條單一的路徑從起始節點向下進行下去；只有當搜索到達一個沒有后裔的狀態時，它才考慮另一條替代的路徑。替代路徑與前面已經試過的路徑不同之處僅僅在于改變最后n步，而且保持n盡可能小。20中南大學智能系統與智能軟件研究所

定義：首先擴展最新產生的(即最深的)節點。

算法：對于許多問題，其狀態空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的已知深度上限還要深。為了避免考慮太長的路徑(防止搜索過程沿著無益的路徑擴展下去)，往往給出一個節點擴展的最大深度——深度界限。任何節點如果達到了深度界限，那么都將把它們作為沒有后繼節點處理。值得說明的是，即使應用了深度界限的規定，所求得的解答路徑并不一定就是最短的路徑。與寬度優先搜索算法最根本的不同在于：將擴展的后繼節點放在OPEN表的前端。其算法如下：3.2.2深度優先搜索(depth-firstsearch)21中南大學智能系統與智能軟件研究所含有深度界限的深度優先搜索算法如下：

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

(2)如果OPEN為一空表，則失敗退出。

(3)把第一個節點(節點n)從OPEN表移到CLOSED表。

(4)如果節點n的深度等于最大深度，則轉向(2)。

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

(6)如果后繼節點中有任一個為目標節點，則求得一個解，成功退出；否則，轉向(2)22中南大學智能系統與智能軟件研究所含有深度界限深度優先搜索圖如下：

例：按深度優先搜索生成的八數碼難題，設置深度界限為5。

下圖8繪出了搜索樹，粗線條的路徑表明含有5條應用規則的一個解?？梢姡疃葍炏人阉鬟^程是沿著一條路徑進行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。23中南大學智能系統與智能軟件研究所24中南大學智能系統與智能軟件研究所3.2.3等代價搜索定義

是寬度優先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧線上的有關代價,表示時間、距離等花費。算法若所有連接弧線具有相等代價，則簡化為寬度優先搜索算法。3.2盲目搜索25中南大學智能系統與智能軟件研究所起始節點記為S；

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

從起始節點S到任一節點i的路徑代價記為g(i)。在搜索樹上，我們假設g(i)也是從起始節點S到節點i的最少代價路徑上的代價，因為它是唯一的路徑；

等代價搜索算法如下：(等代價搜索方法以g(i)的遞增順序擴展其節點)

(1)把起始節點S放到未擴展節點表OPEN中。如果此起始節點為一目標節點，則求得一個解;否則令g(S)=0。

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

(3)從OPEN表中選擇一個節點i，使其g(i)為最小。如果有幾個節點都合格，那么就要選擇一個目標節點作為節點i(要是有目標節點的話)；否則，就從中選一個作為節點i。把節點i從OPEN表移至擴展節點表CLOSED中。

(4)如果節點i為目標節點，則求得一個解。

(5)擴展節點i。如果沒有后繼節點，則轉向第(2)步。

(6)對于節點i的每個后繼節點j，計算g(j)=g(i)+c(i,j)，并把所有后繼節點j放進OPEN表。提供回到節點i的指針。

(7)轉向第(2)步。26中南大學智能系統與智能軟件研究所開始把S放入OPEN表OPEN表為空表？把具有最小g(i)值的節點i從OPEN表移至CLOSED表是否有后繼節點為目標節點？失敗成功圖3.2等代價搜索算法框圖是否是否令g(s)=0S是否目標節點？是成功擴展i，計算其后繼節點j的g(j)，并把后繼節點放入OPEN表否3.2盲目搜索27中南大學智能系統與智能軟件研究所3.3

啟發式搜索特點：重排OPEN表，選擇最有希望的節點加以擴展種類：有序搜索、A*算法等3.3.1啟發式搜索策略和估價函數盲目搜索效率低，耗費過多的計算空間與時間,可能帶來組合爆炸。寬度優先、深度優先搜索，或等代價搜索算法,其主要的差別是OPEN表中待擴展節點的順序問題。人們就試圖找到一種方法用于排列待擴展節點的順序，即選擇最有希望的節點加以擴展，那么，搜索效率將會大為提高。啟發式信息

用來加速搜索過程的有關問題領域的特征信息。28中南大學智能系統與智能軟件研究所3.3

啟發式搜索假設初始狀態、算符和目標狀態的定義都是完全確定的，然后決定一個搜索空間。因此，問題就在于如何有效地搜索這個給定空間。

啟發信息按其用途可分為下列3種：

(1)用于決定要擴展的下一個節點，以免像在寬度優先或深度優先搜索中那樣盲目地擴展。

(2)在擴展一個節點的過程中，用于決定要生成哪一個或哪幾個后繼節點，以免盲目地同時生成所有可能的節點。

(3)用于決定某些應該從搜索樹中拋棄或修剪的節點。29中南大學智能系統與智能軟件研究所估價函數

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

一個節點的"希望"(promise)有幾種不同的定義方法。在狀態空間問題中，一種方法是估算目標節點到此節點的距離；另一種方法認為，解答路徑包括被估價過的節點，并計算全條路徑的長度或難度。每個不同的衡量標準只能考慮該問題中這個節點的某些決定性特性，或者對給定節點與目標節點進行比較，以決定相關特性。

f(n)——表示節點n的估價函數值應用節點“希望”程度（估價函數值）重排OPEN表3.3啟發式搜索30中南大學智能系統與智能軟件研究所3.3

啟發式搜索3.3.2

有序搜索實質：選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點。即利用上述第一種啟發信息的狀態空間搜索算法，即決定哪個是下一步要擴展的節點。這種搜索總是選擇“最有希望”的節點作為下一個被擴展的節點。這種搜索叫做有序搜索(orderedsearch)。31中南大學智能系統與智能軟件研究所用估價函數f來排列GRAPHSEARCH第8步中OPEN表上的節點。根據習慣，OPEN表上的節點按照它們f函數值的遞增順序排列。根據推測，某個具有低的估價值的節點較有可能處在最佳路徑上。應用某個算法(例如等代價算法)選擇OPEN表上具有最小f值的節點作為下一個要擴展的節點。這種搜索方法叫做有序搜索或最佳優先搜索，而其算法就叫做有序搜索算法或最佳優先算法。可見它總是選擇最有希望的節點作為下一個要擴展的節點。有序搜索(orderedsearch)又稱為最好優先搜索(best-firstsearch)。32中南大學智能系統與智能軟件研究所有序狀態空間搜索算法如下：1)把起始節點S放到OPEN表中，計算f(S)并把其值與節點S聯系起來。

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

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

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

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

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

(a)計算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數f把它添入OPEN表。從j加一指向其父輩節點i的指針，以便一旦找到目標節點時記住一個解答路徑。(c)果j已在OPEN表上或CLOSED表上，則比較剛剛對j計算過的f值和前面計算過的該節點在表中的f值。如果新的f值較小，則

(i)以此新值取代舊值。(ii)從j指向i，而不是指向它的父輩節點。(iii)如果節點j在CLOSED表中，則把它移回OPEN表

(7)轉向(2)，即GOTO(2)。33中南大學智能系統與智能軟件研究所開始把S放入OPEN表，計算估價函數f(s)OPEN表為空表？選取OPEN表中f值最小的節點i放入CLOSED表i為目標節點嗎？擴展i，得后繼節點j，計算f(j)，提供返回節點i的指針，利用f(j)對OPEN表重新排序，調整親子關系及指針失敗成功圖3.9有序搜索算法框圖是否是否3.3啟發式搜索算法34中南大學智能系統與智能軟件研究所

寬度優先搜索、等代價搜索和深度優先搜索統統是有序搜索技術的特例。對于寬度優先搜索，我們選擇f(i)作為節點i的深度。對于等代價搜索，f(i)是從起始節點至節點i這段路徑的代價。

有序搜索的有效性直接取決于f的選擇，如果選擇的f不合適，有序搜索就可能失去一個最好的解甚至全部的解。如果沒有適用的準確的希望量度，那么f的選擇將涉及兩個方面的內容：一方面是一個時間和空間之間的折衷方案；另一方面是保證有一個最優的解或任意解。35中南大學智能系統與智能軟件研究所例子八數碼難題（8-puzzleproblem）12384567（目標狀態）12384567（初始狀態）3.3啟發式搜索36中南大學智能系統與智能軟件研究所

下面讓我們再次用八數碼難題的例子來說明過程GRAPHSEARCH是如何應用估價函數排列節點的。舉例說明如下：

我們采用了簡單的估價函數f(n)=d(n)+W(n)其中：d(n)是搜索樹中節點n的深度；W(n)用來計算對應于節點n的數據庫中錯放的棋子個數。因此，起始節點棋局的f值等于0+4=4。

283123164->84

75765八數碼難題的有序搜索樹見下圖：37中南大學智能系統與智能軟件研究所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啟發式搜索38中南大學智能系統與智能軟件研究所估價函數的應用顯著地減少了被擴展的節點數(如果我們只用估價函數f(n)=d(n)，那么我們就得到寬度優先搜索過程)。

正確地選擇估價函數對確定搜索結果具有決定性的作用。使用不能識別某些節點真實希望的估價函數會形成非最小代價路徑；而使用一個過多地估計了全部節點希望的估價函數(就像寬度優先搜索方法得到的估價函數一樣)又會擴展過多的節點。39中南大學智能系統與智能軟件研究所3.3.3A*算法估價函數的定義：

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

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

——g是g*的估計，h是h*的估計令k(ni，nj)表示任意兩個節點ni和nj之間最小代價路徑的實際代價(對于兩節點間沒有通路的節點，函數k沒有定義)。于是，從節點n到某個具體的目標節點ti，某一條最小代價路徑的代價可由k(n,ti)給出。我們令h*(n)表示整個目標節點集合｛ti｝上所有k(n,ti)中最小的一個，因此，h*(n)就是從n到目標節點最小代價路徑的代價，而且從n到目標節點能夠獲得h*(n)的任一路徑就是一條從n到某個目標節點的最佳路徑(對于任何不能到達目標節點的節點n，函數h*沒有定義)。3.3啟發式搜索40中南大學智能系統與智能軟件研究所

通常我們感興趣的是想知道從已知起始節點S到任意節點n的一條最佳路徑的代價k(S,n)。為此，引進一個新函數g*，這將使我們的記號得到某些簡化。對所有從S開始可達到n的路徑來說，函數g*定義為：

g*(n)=k(S,n)

其次，我們定義函數f*，使得在任一節點n上其函數值f*(n)就是從節點S到節點n的一條最佳路徑的實際代價加上從節點n到某目標節點的一條最佳路徑的代價之和，即f*(n)=g*(n)+h*(n)

因而f*(n)值就是從S開始約束通過節點n的一條最佳路徑的代價，而f*(S)=h*(S)是一條從S到某個目標節點中間無約束的一條最佳路徑的代價。41中南大學智能系統與智能軟件研究所

我們希望估價函數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)，它依賴于有關問題的領域的啟發信息。這種信息可能與八數碼難題中的函數W(n)所用的那種信息相似。我們把h叫做啟發函數。42中南大學智能系統與智能軟件研究所3.3.3A*算法A*算法的定義：

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

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

定義3

采用h*(x)的下界h(x)為啟發函數的A算法，稱為A*算法。當h=0時，A*算法就變為有序搜索算法。43中南大學智能系統與智能軟件研究所

A*算法是一種有序搜索算法，其特點在于對估價函數的定義上。對于一般的有序搜索，總是選擇f值最小的節點作為擴展節點。因此，f是根據需要找到一條最小代價路徑的觀點來估算節點的，所以，可考慮每個節點n的估價函數值為兩個分量：從起始節點到節點n的代價以及從節點n到達目標節點的代價。A*算法

(1)把S放入OPEN表，記f=h，令CLOSED為空表。

(2)重復下列過程，直至找到目標節點止。若OPEN為空表，則宣告失敗。

(3)選取OPEN表中未設置過的具有最小f值的節點為最佳節點BESTNODE，并把它放入CLOSED表。

(4)若BESTNODE為一目標節點，則成功求得一解。

(5)若BESTNODE不是目標節點，則擴展之，產生后繼節點SUCCSSOR。44中南大學智能系統與智能軟件研究所

(6)對每個SUCCSSOR進行下列過程：

(a)建立從SUCCSSOR返回BESTNODE的指針。

(b)計算g(SUC)=g(BES)+g(BES,SUC)。

(c)如果SUCCSSOR∈OPEN，則稱此節點為OLD，并把它添至BESTNODE的后繼節點表中。

(d)比較新舊路徑代價。如果g(SUC)＜g(OLD),則重新確定OLD的父輩節點為BESTNODE，記下較小代價g(OLD),并修正f(OLD)值。

(e)若至OLD節點的代價較低或一樣，則停止擴展節點。

(f)若SUCCSSOR不在CLOSE表中，則看其是否在CLOSED表中。

(g)若SUCCSSOR在CLOSE表中，則轉向c。

(h)若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，則把它放入OPEN表中，并添入BESTNODE后裔表，然后轉向(7)

(i)計算f值。

(7)GOLOOP45中南大學智能系統與智能軟件研究所46中南大學智能系統與智能軟件研究所3.4消解原理回顧：

原子公式（atomicformulas）

文字—一個原子公式及其否定。

子句—由文字的析取組成的合適公式。

消解—對謂詞演算公式進行分解和化簡，消去一些符號，以求得導出子句。3.4.1子句集的求取步驟：共9步。47中南大學智能系統與智能軟件研究所第二章中討論過謂詞公式，某些推理規則以及置換合一等概念。在這個基礎上，我們能夠進一步研究消解原理(resolutionprinciple)。有些專家把它叫做歸結原理。消解是一種可用于一定的子句公式的重要推理規則。一子句定義為由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。當消解可使用時，消解過程被應用于母體子句對，以便產生一個導出子句。例如，如果存在某個公理E1∨E2和另一公理～E2∨E3，那么E1∨E3在邏輯上成立。這就是消解，而稱E1∨E3為E1∨E2和～E2∨E3的消解式(resolvent)。48中南大學智能系統與智能軟件研究所3.4.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.4消解原理49中南大學智能系統與智能軟件研究所(2)減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上，并反復應用狄·摩根定律。(3)對變量標準化對啞元（虛構變量）改名，以保證每個量詞有其自己唯一的啞元。3.4消解原理(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)］｝｝50中南大學智能系統與智能軟件研究所(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.4消解原理51中南大學智能系統與智能軟件研究所把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(7)消去全稱量詞所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現的全稱量詞。3.4消解原理(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))］｝52中南大學智能系統與智能軟件研究所(8)消去連詞符號∧用{A,B}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現在一個以上的子句中。3.4消解原理(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)］53中南大學智能系統與智能軟件研究所54中南大學智能系統與智能軟件研究所3.4.2消解推理規則消解式的定義

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

消解式求法取各子句的析取，然后消去互補對。3.4消解原理55中南大學智能系統與智能軟件研究所56中南大學智能系統與智能軟件研究所3.4.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.4消解原理57中南大學智能系統與智能軟件研究所3.4.4

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

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

給出一個公式集S和自標公式L，通過反證或反演來求證目標公式L，其證明步驟如下：(1)否定L，得～L；

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

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

(4)應用消解原理，力圖推導出一個表示矛盾的空子句NIL。消解兩個子句時，可能有一個以上的消解式，因為有多種選擇的方法。不過在任何情況下，它們最多具有有限個消解式。3.4消解原理58中南大學智能系統與智能軟件研究所(2)反演求解的正確性

設公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足～L的，所以不存在能夠滿足并集S∪｛～L｝的解釋。如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。因此，如果L在邏輯上遵循S，那么S∪｛～L｝是不可滿足的?？梢宰C明，如果消解反演反復應用到不可滿足的子句集，那么最終將要產生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集S∪｛～L｝消解得到的子句，最后將產生空子句；反之，可以證明，如果從S∪｛～L｝的子句消解得到空子句，那么L在邏輯上遵循S。例如：二個子句：59中南大學智能系統與智能軟件研究所60中南大學智能系統與智能軟件研究所61中南大學智能系統與智能軟件研究所62中南大學智能系統與智能軟件研究所證明：(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.4消解原理63中南大學智能系統與智能軟件研究所把前提化為子句形：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.4消解原理64中南大學智能系統與智能軟件研究所反演求解過程從反演樹求取答案步驟把由目標公式的否定產生的每個子句添加到目標公式否定之否定的子句中去。按照反演樹，執行和以前相同的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。實質把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。3.4消解原理65中南大學智能系統與智能軟件研究所

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

這個問題說明了兩個事實，然后提出一個問題，而問題的答案大概可從這兩個事實推導出。這兩個事實可以解釋為下列公式集S：(x)[AT(JOHN,x)=>AT(FIDO,x)]和T(JOHN,SCHOOL)首先證明公式(x)AT(FIDO,x)在邏輯上遵循S，然后尋求一個存在x的例，那么就能解決“菲多在哪里”的問題。關鍵想法是把問題化為一個包含某個存在量詞的目標公式，使得此存在量詞量化變量表示對該問題的一個解答。如果問題可以從給出的事實得到答案，那么按這種方法建立的目標函數在邏輯上遵循S。在得到一個證明之后，我們就試圖求取存在量詞量化變量的一個例，作為一個回答。對于上述例題能夠容易地證明(x)AT(FIDO,x)遵循S。我們也可以說明，用一種比較簡單的方法來求取合適的答案。66中南大學智能系統與智能軟件研究所消解反演可用一般方式得到，其辦法是首先對被證明的公式加以否定，再把這個否定式附加到集S中去，化這個擴充集的所有成員為子句形，然后用消解證明這個子句集是不可滿足的。圖4.2表示出上例的反演樹。從S中的公式得到的子句叫做公理。注意目標公式(x)AT(FIDO,x)的否定產生(x)[～AT(FIDO,x)]。其子句形式為:～AT(FIDO,x)對本例應用消解反演求解過程為：(1)目標公式否定的子句形式為:～AT(FIDO,x)把它添加至目標公式的否定之否定的子句中去，得重言式～AT(FIDO,x)∨AT(FIDO,x)(2)用下圖的反演樹進行消解，并在根部得到子句:AT(FIDO，SCHOOL)(3)從根部求得答案AT(FIDO，SCHOOL)，用此子句作為回答語句。因此，子句AT(FIDO，SCHOOL)就是這個問題的合適答案。67中南大學智能系統與智能軟件研究所68中南大學智能系統與智能軟件研究所3.5規則演繹系統對于許多公式來說，子句形是一種低效率的表達式，因為一些重要信息可能在求取子句形過程中丟失。本章將研究采用易于敘述的if-then(如果-那么)規則來求解問題?；谝巹t的問題求解系統運用下述規則:其中，If部分可能由幾個if組成，而Then部分可能由一個或一個以上的then組成。69中南大學智能系統與智能軟件研究所3.5規則演繹系統

定義

在所有基于規則系統中，每個if可能與某斷言(assertion)集中的一個或多個斷言匹配。有時把該斷言集稱為工作內存。在許多基于規則系統中，then部分用于規定放入工作內存的新斷言。這種基于規則的系統叫做規則演繹系統(rulebaseddeductionsystem)。在這種系統中，通常稱每個if部分為前項(antecedent)，稱每個then部分為后項(consequent)。有時，then部分用于規定動作；這時，稱這種基于規則的系統為反應式系統(reactionsystem)或產生式系統(production

system)。產生式系統將在后續篇章中予以介紹，本節討論規則演繹系統。70中南大學智能系統與智能軟件研究所3.5.1規則正向演繹系統基于規則的演繹系統和產生式系統，均有兩種推理方式：正向推理(forwardchanining)和逆向推理(backwardchaining)。定義

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

逆向規則演繹系統（即逆向推理）：從then部分向if部分推理的過程，它是從目標或動作向事實或狀況進行操作的。3.5規則演繹系統71中南大學智能系統與智能軟件研究所3.5.1規則正向演繹系統事實表達式的與或形變換在基于規則的正向演繹系統中，我們把事實表示為非蘊涵形式的與或形，作為系統的總數據庫。我們不想把這些事實化為子句形，而是把它們表示為謂詞演算公式，并把這些公式變換為叫做與或形的非蘊涵形式。要把一個公式化為與或形，可采用下列步驟：

(1)利用(W1→W2)和(～W1∨W2)的等價關系，消去符號→(如果存在該符號的話)。實際上，在事實中間很少有符號→出現，因為可把蘊涵式表示為規則。

(2)用狄·摩根(DeMorgan)定律把否定符號移進括號內，直到每個否定符號的轄域最多只含有一個謂詞為止。

(3)對所得到的表達式進行Skolem化和前束化。

(4)對全稱量詞轄域內的變量進行改名和變量標準化，而存在量詞量化變量用Skolem函數代替。

(5)刪去全稱量詞，而任何余下的變量都被認為具有全稱量化作用。72中南大學智能系統與智能軟件研究所73中南大學智能系統與智能軟件研究所事實表達式的與或圖表示一個事實表達式的與或樹表示3.5規則演繹系統公式的與或圖表示有個有趣的性質，即由變換該公式得到的子句集可作為此與或圖的解圖的集合(終止于葉節點)讀出；也就是說，所得到的每個子句是作為解圖的各個葉節點上文字的析取。這樣，由表達式Q(w,A)∧{[～R(v)∧～P(v)]∨～S(A,v)}得到的子句為Q(w,A),～S(A,v)∨～R(v),～S(A,v)∨～P(v)74中南大學智能系統與智能軟件研究所每個節點表示該事實表達式的一個子表達式。某個事實表達式(E1∨…∨Ek)的析取關系子表達式E1，…，Ek是用后繼節點表示的，并由一個k線連接符把它們連接到父輩節點上。某個事實表達式(E1∧…∧En)的每個合取子表達式E1，…，En是由單一的后繼節點表示的，并由一個單線連接符接到父輩接點。在事實表達式中，我們用k線連接符(一個合取記號)來分解析取式，很可能會令人感到意外。在后面的討論中將會了解到采用這種約定的原因。

75中南大學智能系統與智能軟件研究所與或圖的F規則變換這些規則是建立在某個問題轄域中普通陳述性知識的蘊涵公式基礎上的。我們把允許用作規則的公式類型限制為下列形式：

LW

式中：L是單文字；W為與或形的唯一公式。我們也假設出現在蘊涵式中的任何變量都有全稱量化作用于整個蘊涵式。這些事實和規則中的一些變量被分離標準化，使得沒有一個變量出現在一個以上的規則中，而且使規則變量不同于事實變量。單文字前項的任何蘊涵式，不管其量化情況如何都可以化為某種量化轄域為整個蘊涵式的形式。這個變換過程首先把這些變量的量詞局部地調換到前項，然后再把全部存在量詞Skolem化。3.5規則演繹系統76中南大學智能系統與智能軟件研究所77中南大學智能系統與智能軟件研究所78中南大學智能系統與智能軟件研究所

以下用一個自由變量的命題演算情況來說明如何把這類規則應用于與或圖。

把形式為LW的規則應用到任一個具有葉節點n并由文字L標記的與或圖上，可以得到一個新的與或圖。在新的圖上，節點n由一個單線連接符接到后繼節點(也由L標記)，它是表示為W的一個與或圖結構的根節點。作為例子，考慮把規則S(X∧Y)∨Z應用到圖1所示的與或圖中標有S的葉節點上。所得到的新與或圖結構表示于圖2，圖中標記S的兩個節點由一條叫做匹配弧的弧線連接起來。79中南大學智能系統與智能軟件研究所在應用某條規則之前，一個與或圖(如圖1)表示一個具體的事實表達式。其中，在葉節點結束的一組解圖表示該事實表達式的子句形。我們希望在應用規則之后得到的圖，既能表示原始事實，又能表示從原始事實和該規則推出的事實表達式。

假設我們有一條規則LW，根據此規則及事實表達式F(L)，可以推出表達式F(W)。F(W)是用W代替F中的所有L而得到的。當用規則LW來變換以上述方式描述的F(L)的與或圖表示時，我們就產生一個含有F(W)表示的新圖；也就是說，它是以葉節點終止的解圖集以F(W)子句形式代表該子句集。這個子句集包括在F(L)的子句形和LW的子句形間對L進行所有可能的消解而得到的整集。

80中南大學智能系統與智能軟件研究所再討論圖2的情況。規則S[(X∧Y)∨Z]的子句形是：

～S∨X∨Z,～S∨Y∨Z

[(P∨Q)∧R]∨[S∧(T∨U)]的子句形解圖集為:

P∨Q∨S,R∨S,P∨Q∨T∨U,R∨T∨U

應用兩個規則子句中任一個對上述子句形中的S進行消解：于是我們得到4個子句對S進行消解的消解式的完備集為：X∨Z∨P∨Q,Y∨Z∨P∨Q,R∨X∨Z,R∨Y∨Z

這些消解式全部包含在解圖所表示的子句之中。81中南大學智能系統與智能軟件研究所從上述討論我們可以得出結論：應用一條規則到與或圖的過程，以極其經濟的方式達到了用其它方法要進行多次消解才能達到的目的。

我們要使應用一條規則得到的與或圖繼續表示事實表達式和推得的表達式，這可利用匹配弧兩側有相同標記的節點來實現。對一個節點應用一條規則之后，此節點就不再是該圖的葉節點。不過，它仍然由單一文字標記而且可以繼續具有一些應用于它的規則。我們把圖中標有單文字的任一節點都稱為文字節點，由一個與或圖表示的子句集就是對應于該圖中以文字節點終止的解圖集。82中南大學智能系統與智能軟件研究所作為終止條件的目標公式

應用F規則的目的在于從某個事實公式和某個規則集出發來證明某個目標公式。在正向推理系統中，這種目標表達式只限于可證明的表達式，尤其是可證明的文字析取形的目標公式表達式。我們用文字集表示此目標公式，并設該集各元都為析取關系。(在以后各節所要討論的逆向系統和雙向系統，都不對目標表達式作此限制。)目標文字和規則可用來對與或圖添加后繼節點，當一個目標文字與該圖中文字節點n上的一個文字相匹配時，我們就對該圖添加這個節點n的新后裔，并標記為匹配的目標文字。這個后裔叫做目標節點，目標節點都用匹配弧分別接到它們的副輩節點上。當產生式系統產生一個與或圖，并包含有終止在目標節點上的一個解圖時，系統便成功地結束。此時，該系統實際上已推出一個等價于目標子句的一部分的子句。83中南大學智能系統與智能軟件研究所下圖3給出一個滿足以目標公式(C∨G)為基礎的終止條件的與或圖，可把它解釋為用一個“以事實來推理”的策略對目標表達式(C∨G)的一個證明。最初的事實表達式為(A∨B)。由于不知道A或B哪個為真，因此我們可以試著首先假定A為真，然后再假定B為真，分別地進行證明。如果兩個證明都成功，那么我們就得到根據析取式(A∨B)的一個證明。而A或B到底哪個為真都無關緊要。圖4.7中標有(A∨B)的節點，其兩個后裔由一個2線連接符來連接。因而這兩個后裔都必須出現在最后解圖中，如果對節點n的一個解圖通過k線連接符包含n的任一后裔，那么此解圖必須包含通過這個k線連接符的所有k個后裔。對應動畫圖示：84中南大學智能系統與智能軟件研究所85中南大學智能系統與智能軟件研究所用消解反演來證明目標公式，如下圖推得一個空子句NIL，從而使目標公式(C∨G)得到證明。

我們得到的結論是：當正向演繹系統產生一個含有以目標節點作為終止的解圖時，此系統就成功地終止。86中南大學智能系統與智能軟件研究所對于表達式含有變量的正向產生式系統，我們考慮把一條(LW)形式的規則應用到與或圖的過程，其中L是文字，W是與或形的一個公式，而且所有表達式都可以包含變量。如果這個與或圖含有的某個文字節點L′同L合一，那么這條規則就是可應用的。設其最一般合一者為u，那么這條規則的應用能夠擴展這個圖。為此，建立一個有向的匹配弧，從與或圖中標有L′的節點出發到達一個新的標有L的后繼節點。這個后繼節點是Wu的與或圖表示的根節點，我們用mgu，或者簡寫為u來標記這段匹配弧。87中南大學智能系統與智能軟件研究所3.5.2規則逆向演繹系統定義逆向規則演繹系統是從then向if進行推理的，即從目標或動作向事實或狀況條件進行推理的。

求解過程目標表達式的與或形式逆向演繹系統能夠處理任意形式的目標表達式。首先，采用與變換事實表達式同樣的過程，把目標公式化成與或形，即消去蘊涵符號，把否定符號移進括號內，對全稱量詞Skolem化并刪去存在量詞。留在目標表達式與或形中的變量假定都已存在量詞量化。如：3.5規則演繹系統88中南大學智能系統與智能軟件研究所與或形的目標公式也可以表示為與或圖。不過，與事實表達式的與或圖不同的是，對于目標表達式，與或圖中的k線連接符用來分開合取關系的子表達式。上例所用的目標公式的與或圖如下圖所示。在目標公式的與或圖中，我們把根節點的任一后裔叫做子目標節點，而標在這些后裔節點中的表達式叫做子目標。相應的動態圖89中南大學智能系統與智能軟件研究所90中南大學智能系統與智能軟件研究所2.與或圖的B規則變換

現在讓我們應用B規則即逆向推理規則來變換逆向演繹系統的與或圖結構，這個B規則是建立在確定的蘊涵式基礎上的，正如正向系統的F規則一樣。不過，我們現在把這些B規則限制為:WL形式的表達式。其中，W為任一與或形公式，L為文字，而且蘊涵式中任何變量的量詞轄域為整個蘊涵式。其次，把B規則限制為這種形式的蘊涵式還可以簡化匹配，使之不會引起重大的實際困難。此外，可以把像W

(L1∧L2)這樣的蘊涵式化為兩個規則W

L1和WL2。91中南大學智能系統與智能軟件研究所3.作為終止條件的事實節點的一致解圖

逆向系統中的事實表達式均限制為文字合取形，它可以表示為一個文字集。當一個事實文字和標在該圖文字節點上的文字相匹配時，就可把相應的后裔事實節點添加到該與或圖中去。這個事實節點通過標有mgu的匹配弧與匹配的子目標文字節點連接起來。同一個事實文字可以多次重復使用(每次用不同變量)，以便建立多重事實節點。

逆向系統成功的終止條件是與或圖包含有某個終止在事實節點上的一致解圖。下面我們討論一個簡單的例子,看看基于規則的逆向演繹系統是怎樣工作的。

舉例如下：

這個例子的事實、應用規則和問題分別表示于下：

事實：

F1:DOG(FIDO)；狗的名字叫Fido

F2:～BARKS(FIDO)；Fido是不叫的

F3:WAGSTAIL(FIDO)；Fido搖尾巴

F4:MEOWS(MYRTLE)；貓咪的名字叫Myrtle92中南大學智能系統與智能軟件研究所規則：

R1:[WAGSTAIL(x1)∧DOG(x1)]FRIENDLY(x1)；搖尾巴的狗是溫順的狗。

R2:[FRIENDLY(x2)∧～BARKS(x2)]～AFRAID(y2,x2)；溫順而又不叫的東西是不值得害怕的。

R3:DOG(x3)ANIMAL(x3)；狗為動物。

R4:CAT(x4)ANIMAL(x4)；貓為動物。

R5:MEOWS(x5)CAT(x5)；貓咪是貓。

問題：是否存在這樣的一只貓和一條狗，使得這只貓不怕這條狗?

用目標表達式表示此問題為:93中南大學智能系統與智能軟件研究所94中南大學智能系統與智能軟件研究所上圖表示出這個問題的一致解圖。圖中，用雙線框表示事實節點，用規則編號R1、R2和R5等來標記所應用的規則。此解圖中有八條匹配弧，每條匹配弧上都有一個置換。這些置換為{x/x5}，{MYRTLE/x}，{FIDO/y}，{x/y2,y/x2}，{FIDO/y}({FIDO/y}重復使用四次)。由上圖可見，終止在事實節點前的置換為{MYRTLE/x}和{FIDO/y}。把它應用到目標表達式，我們就得到該問題的回答語句如下：

[CAT(MYRTLE)∧DOG(FIDO)∧～AFRAID(MYRTLE,FIDO)]95中南大學智能系統與智能軟件研究所基于規則的正向演繹系統和逆向演繹系統都具有局限性。正向演繹系統能夠處理任意形式的if表達式，但被限制在then表達式為由文字析取組成的一些表達式。逆向演繹系統能夠處理任意形式的then表達式，但被限制在if表達式為文字合取組成的一些表達式。我們希望能夠構成一個組合的系統，使它具有正向和逆向兩系統的優點，以求克服各自的缺點(局限性)。這個系統就是本節要研究的雙向(正向和逆向)組合演繹系統。3.5.3規則雙向演繹系統3.5規則演繹系統96中南大學智能系統與智能軟件研究所3.5.3規則雙向演繹系統正向和逆向組合系統是建立在兩個系統相結合的基礎上的。此組合系統的總數據庫由表示目標和表示事實的兩個與或圖結構組成。這些與或圖最初用來表示給出的事實和目標的某些表達式集合，現在這些表達式的形式不受約束。這些與或圖結構分別用正向系統的F規則和逆向系統的B規則來修正。設計者必須決定哪些規則用來處理事實圖以及哪些規則用來處理目標圖。盡管新系統在修正由兩部分構成的數據庫時實際上只沿一個方向進行，但是仍然把這些規則分別稱為F規則和B規則。我們繼續限制F規則為單文字前項和B規則為單文字后項。97中南大學智能系統與智能軟件研究所3.5.3規則雙向演繹系統組合演繹系統的主要復雜之處在于其終止條件，終止涉及兩個圖結構之間的適當交接處。這些結構可由標有合一文字的節點上的匹配棱線來連接。我們是用對應的mgu來標記匹配棱線的。對于初始圖，事實圖和目標圖間的匹配棱線必須在葉節點之間。當用F規則和B規則對圖進行擴展之后，匹配就可以出現在任何文字節點上。

在完成兩個圖間的所有可能匹配之后，目標圖中根節點上的表達式是否已經根據事實圖中根節點上的表達式和規則得到證明的問題仍然需要判定。只有當我們求得這樣的一個證明時，證明過程才算成功地終止。當然，當我們能夠斷定在給定方法限度內找不到證明時過程則以失敗告終。98中南大學智能系統與智能軟件研究所3.5.3規則雙向演繹系統一個簡單的終止條件是某個判定與或圖根節點是否為可解過程的直接歸納。這個終止條件是建立在事實節點和目標節點間一種叫做CANCEL的對稱關系的基礎上的。CANCEL的遞歸定義如下：

定義：如果(n,m)中有一個為事實節點，另一個為目標節點，而且如果n和m都由可合一的文字所標記，或者n有個外向k線連接符接至一個后繼節點集{Si}使得對此集的每個元CANCEL(Si,m)都成立，那么就稱這兩節點n和m互相CANCEL(即互相抵消)。

當事實圖的根節點和目標圖的根節點互相CANCEL時，我們得到一個候補解。在事實和目標圖內證明該目標根節點和事實根節點互相CANCEL的圖結構叫做候補CANCEL圖。如果候補CANCEL圖中所有匹配的mgu都是一致的，那么這個候補解就是一個實際解。99中南大學智能系統與智能軟件研究所下面我們舉例說明下圖中的初始事實圖和初始目標圖間的匹配。圖中用粗線條弧線表示出一個一致的候補CANCEL圖。每個事實目標節點匹配的mgu都標示在匹配棱線的旁邊，而且所有這些mgu的合一復合為{f(A)/v,A/y}。由于兩個與或圖的根節點能夠互相CANCEL，所以兩個與或圖得到匹配，使下圖的證明獲得成功。100中南大學智能系統與智能軟件研究所

應用CANCEL圖能夠正確處理與合取有關的目標節點。在證明父輩之前必須證明每個合取式。我們可以用類似的方法來處理與析取有關的事實節點。要在某個證明中使用析取的一個成員，我們就必須能使用每個析取分別證明同一目標。這一過程執行了“據情推理”的策略。

我們應用F規則和B規則來擴展與或搜索圖，因此，置換關系到每條規則的應用。解圖中的所有置換，包括在規則匹配中得到的mgu和匹配事實與目標文字間所得到的mgu，都必須是一致的。101中南大學智能系統與智能軟件研究所3.6產生式系統產生式系統(productionsystem)首先是由Post于1943年提出的產生式規則(productionrule)而得名的。他們用這種規則對符號串進行置換運算。后來，美國的紐厄爾和西蒙利用這個原理建立一個人類的認知模型(1965年)。同時，斯坦福大學利用產生式系統結構設計出第一個專家系統DENDRAL。定義：用來描述若干個不同的以一個基本概念為基礎的系統。這個基本概念就是產生式規則或產生式條件和操作對的概念。實質：在產生式系統中，論域的知識分為兩部分：用事實表示靜態知識，如事物、事件和它們之間的關系；用產生式規則表示推理過程和行為。由于這類系統的知識庫主要用于存儲規則，因此又把此類系統稱為基于規則的系統。102中南大學智能系統與智能軟件研究所3.6.1產生式系統的組成：

其主要由3個部分組成，即總數據庫(或全局數據庫)、產生式規則（知識庫）和控制策略（推理機）。各部分間的關系如下圖。

產生式規則是一個以"如果滿足這個條件，就應當采取某些操作"形式表示的語句。例如，

規則:

如果某種動物是哺乳動物，并且吃肉

那么這種動物被稱為食肉動物

控制策略圖3.22產生式系統的主要組成總數據庫產生式規則3.6產生式系統103中南大學智能系統與智能軟件研究所3.6.1產生式系統的組成

產生式的IF(如果)被稱為條件、前項或產生式的左邊。它說明應用這條規則必須滿足的條件；THEN(那么)部分被稱為操作、結果、后項或產生式的右邊。在產生式系統的執行過程中，如果某條規則的條件滿足了，那么，這條規則就可以被應用；也就是說，系統的控制部分可以執行規則的操作部分。產生式的兩邊可用謂詞邏輯、符號和語言的形式，或用很復雜的過程語句來表示。這取決于所采用數據結構的類型。從形式上看都采用了IF-THEN的形式，但這里所討論的產生式更為通用。在謂詞運算中的IF-THEN實質上是表示了蘊涵關系。也就是說要滿足相應的真值表。這里所討論的條件和操作部分除了可以用謂詞邏輯表示外，還可以有其他多種表示形式，并不受相應的真值表的限制。104中南大學智能系統與智能軟件研究所3.6.1產生式系統的組成總數據庫有時也被稱作上下文，當前數據庫或暫時存儲器?？倲祿焓钱a生式規則的注意中心。產生式規則的左邊表示在啟用這一規則之前總數據庫內必須準備好的條件。例如在上述例子中，在得出該動物是食肉動物的結論之前，必須在總數據庫中存有“該動物是哺乳動物”和“該動物吃肉”這兩個事實。執行產生式規則的操作會引起總數據庫的變化，這就使其他產生式規則的條件可能被滿足?？刂撇呗云渥饔檬钦f明下一步應該選用什么規則，也就是如何應用規則。通常從選擇規則到執行操作分3步：匹配、沖突解決和操作。105中南大學智能系統與智能軟件研究所選擇規則到執行操作的步驟

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

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

3.6產生式系統106中南大學智能系統與智能軟件研究所

這是兩條關于美式足球的規則。R1規則規定進攻一方如果在前三次進攻中前進的距離少于10碼(shortyardage)，那么在第四次進攻(fourthdawn)時，可以踢懸空球(punt)。R2規則規定，如果進攻這一方，在前三次進攻中，前進的距離少于10碼，而進攻的位置又在離對方球門線30碼距離之內，那么就可以射門(fieldgoal)。如果當前數據庫包含事實"fourthdawn"和"shortyardage"以及"within30yards"，則上述兩條規則都被觸發，這就需要用沖突解決來決定首先使用哪一條規則。排序、數據排序、規模排序和就近排序等。107中南大學智能系統與智能軟件研究所

有很多種沖突解決策略，其中一種策略是先使用規則R2，因為R2的條件部分包括了更多的限制，因此規定了一個更為特殊的情況。這是一種按專一性來編排順序的策略，稱為專一性排序。還有不少其他的沖突解決策略，如規則排序、數據排序、規模排序和就近排序等。

(a)專一性排序：如果某一規則條件部分規定的情況，比另一規則條件部分規定的情況更有針對性，則這條規則有較高的優先級。

(b)

規則排序：如果規則編排的順序就表示了啟用的優先級，則稱之為規則排序。

(c)數據排序：把規則條件部分的所有條件按優先級次序編排起來，運行時首先使用在條件部分包含較高優先級數據的規則。108中南大學智能系統與智能軟件研究所

(d)規模排序

按規則的條件部分的規模排列優先級，優先使用被滿足的條件較多的規則。

(e)就近排序

把最近使用的規則放在最優先的位置。這和人類的行為有相似之處。如果某一規則經常被使用，則人們傾向于更多地使用這條規則。

(f)上下文限制

把產生式規則按它們所描述的上下文分組，也就是說按上下文對規則分組。在某種上下文條件下，只能從與其相對應的那組規則中選擇可應用的規則。

不同的系統，使用上述這些策略的不同組合。如何選擇沖突解決策略完全是啟發式的。3操作：

操作就是執行規則的操作部分。109中南大學智能系統與智能軟件研究所2.產生式系統的表示

產生式系統的知識表示方法，包括事實的表示和規則的表示。(1)事實的表示

(a)孤立事實的表示：孤立事實在專家系統中常用〈特性-對象-取值〉(attributeobjectval