《人工智能》-第三章搜索推理技術(shù)

人工智能主講:吳順祥

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

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

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

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

圖中每個節(jié)點對應(yīng)一個狀態(tài)，每條連線對應(yīng)一個操作符。這些節(jié)點和連線(即狀態(tài)與操作符)又分別由產(chǎn)生式系統(tǒng)的數(shù)據(jù)庫和規(guī)則來標(biāo)記。求得把一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題就等價于求得圖中的一條路徑問題。圖搜索過程圖7中南大學(xué)智能系統(tǒng)與智能軟件研究所圖搜索過程

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

(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為一目標(biāo)節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指從n到S這條路徑而得到的(指針將在第7步中設(shè)置)。8中南大學(xué)智能系統(tǒng)與智能軟件研究所圖搜索過程(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。9中南大學(xué)智能系統(tǒng)與智能軟件研究所圖搜索過程圖搜索算法中的幾個重要名詞

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

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

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

盲目搜索

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

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

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

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

(1)把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標(biāo)節(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é)點是個目標(biāo)節(jié)點，則找到一個解答，成功退出；否則轉(zhuǎn)向第(2)步。3.2.1

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

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

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

例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時所生成的搜索樹，即要把初始棋局變?yōu)槟繕?biāo)棋局的問題。17中南大學(xué)智能系統(tǒng)與智能軟件研究所例子

八數(shù)碼難題（8-puzzleproblem）

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

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

我們定義節(jié)點的深度如下：

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

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

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

定義：首先擴展最新產(chǎn)生的(即最深的)節(jié)點。

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

(1)把起始節(jié)點S放到未擴展節(jié)點OPEN表中。如果此節(jié)點為一目標(biāo)節(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é)點中有任一個為目標(biāo)節(jié)點，則求得一個解，成功退出；否則，轉(zhuǎn)向(2)22中南大學(xué)智能系統(tǒng)與智能軟件研究所含有深度界限深度優(yōu)先搜索圖如下：

例：按深度優(yōu)先搜索生成的八數(shù)碼難題，設(shè)置深度界限為5。

下圖8繪出了搜索樹，粗線條的路徑表明含有5條應(yīng)用規(guī)則的一個解。可見，深度優(yōu)先搜索過程是沿著一條路徑進行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。23中南大學(xué)智能系統(tǒng)與智能軟件研究所24中南大學(xué)智能系統(tǒng)與智能軟件研究所3.2.3等代價搜索定義

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

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

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

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

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

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

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

(4)如果節(jié)點i為目標(biāo)節(jié)點，則求得一個解。

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

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

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

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

用來加速搜索過程的有關(guān)問題領(lǐng)域的特征信息。28中南大學(xué)智能系統(tǒng)與智能軟件研究所3.3

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

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

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

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

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

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

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

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

啟發(fā)式搜索3.3.2

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

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

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

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

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

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

(a)計算f(j)。(b)如果j既不在OPEN表中，又不在CLOSED表中，則用估價函數(shù)f把它添入OPEN表。從j加一指向其父輩節(jié)點i的指針，以便一旦找到目標(biāo)節(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)。33中南大學(xué)智能系統(tǒng)與智能軟件研究所開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？選取OPEN表中f值最小的節(jié)點i放入CLOSED表i為目標(biāo)節(jié)點嗎？擴展i，得后繼節(jié)點j，計算f(j)，提供返回節(jié)點i的指針，利用f(j)對OPEN表重新排序，調(diào)整親子關(guān)系及指針失敗成功圖3.9有序搜索算法框圖是否是否3.3啟發(fā)式搜索算法34中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

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

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

283123164->84

75765八數(shù)碼難題的有序搜索樹見下圖：37中南大學(xué)智能系統(tǒng)與智能軟件研究所5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（5）（7）圖3.10八數(shù)碼難題的有序搜索樹123846（4）73.3啟發(fā)式搜索38中南大學(xué)智能系統(tǒng)與智能軟件研究所估價函數(shù)的應(yīng)用顯著地減少了被擴展的節(jié)點數(shù)(如果我們只用估價函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程)。

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

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

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

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

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

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

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

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

我們希望估價函數(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ù)。42中南大學(xué)智能系統(tǒng)與智能軟件研究所3.3.3A*算法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*算法。當(dāng)h=0時，A*算法就變?yōu)橛行蛩阉魉惴ā?3中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

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

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

(4)若BESTNODE為一目標(biāo)節(jié)點，則成功求得一解。

(5)若BESTNODE不是目標(biāo)節(jié)點，則擴展之，產(chǎn)生后繼節(jié)點SUCCSSOR。44中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

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

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

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

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

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

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

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

(i)計算f值。

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

原子公式（atomicformulas）

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

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

消解—對謂詞演算公式進行分解和化簡，消去一些符號，以求得導(dǎo)出子句。3.4.1子句集的求取步驟：共9步。47中南大學(xué)智能系統(tǒng)與智能軟件研究所第二章中討論過謂詞公式，某些推理規(guī)則以及置換合一等概念。在這個基礎(chǔ)上，我們能夠進一步研究消解原理(resolutionprinciple)。有些專家把它叫做歸結(jié)原理。消解是一種可用于一定的子句公式的重要推理規(guī)則。一子句定義為由文字的析取組成的公式(一個原子公式和原子公式的否定都叫做文字)。當(dāng)消解可使用時，消解過程被應(yīng)用于母體子句對，以便產(chǎn)生一個導(dǎo)出子句。例如，如果存在某個公理E1∨E2和另一公理～E2∨E3，那么E1∨E3在邏輯上成立。這就是消解，而稱E1∨E3為E1∨E2和～E2∨E3的消解式(resolvent)。48中南大學(xué)智能系統(tǒng)與智能軟件研究所3.4.1子句集的求取

步驟：共9步。

例子:將下列謂詞演算公式化為一個子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝開始：消去蘊涵符號只應(yīng)用∨和～符號，以～A∨B替換AB。(1)

(x)｛～P(x)∨{(y)［~P(y)∨P(f(x,y))］∧～(y)［~Q(x,y)∨P(y)］}}3.4消解原理49中南大學(xué)智能系統(tǒng)與智能軟件研究所(2)減少否定符號的轄域每個否定符號～最多只用到一個謂詞符號上，并反復(fù)應(yīng)用狄·摩根定律。(3)對變量標(biāo)準(zhǔn)化對啞元（虛構(gòu)變量）改名，以保證每個量詞有其自己唯一的啞元。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中南大學(xué)智能系統(tǒng)與智能軟件研究所(4)消去存在量詞以Skolem函數(shù)代替存在量詞內(nèi)的約束變量，然后消去存在量詞化為前束形把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形={前綴}{母式}

全稱量詞串無量詞公式(4)

(x)｛～P(x)∨{(y)[~P(y)∨P(f(x,y))］∧［Q(x,g(x)）∧～P(g(x))］｝｝式中，w=g(x)為一Skolem函數(shù)。(5)

(x)(y)｛～P(x)∨｛［～P(y)∨P(f(x,y))］∧［Q(x,g(x))∧～P(g(x))］｝｝3.4消解原理51中南大學(xué)智能系統(tǒng)與智能軟件研究所把母式化為合取范式任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(7)消去全稱量詞所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。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中南大學(xué)智能系統(tǒng)與智能軟件研究所(8)消去連詞符號∧用{A,B}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式是文字的析取。(9)更換變量名稱可以更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。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中南大學(xué)智能系統(tǒng)與智能軟件研究所54中南大學(xué)智能系統(tǒng)與智能軟件研究所3.4.2消解推理規(guī)則消解式的定義

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

消解式求法取各子句的析取，然后消去互補對。3.4消解原理55中南大學(xué)智能系統(tǒng)與智能軟件研究所56中南大學(xué)智能系統(tǒng)與智能軟件研究所3.4.3

含有變量的消解式

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

含有變量的子句之消解式例子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中南大學(xué)智能系統(tǒng)與智能軟件研究所3.4.4

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

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

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

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

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

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

設(shè)公式L在邏輯上遵循公式集S，那么按照定義滿足S的每個解釋也滿足L。決不會有滿足S的解釋能夠滿足～L的，所以不存在能夠滿足并集S∪｛～L｝的解釋。如果一個公式集不能被任一解釋所滿足，那么這個公式是不可滿足的。因此，如果L在邏輯上遵循S，那么S∪｛～L｝是不可滿足的?？梢宰C明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集S∪｛～L｝消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從S∪｛～L｝的子句消解得到空子句，那么L在邏輯上遵循S。例如：二個子句：59中南大學(xué)智能系統(tǒng)與智能軟件研究所60中南大學(xué)智能系統(tǒng)與智能軟件研究所61中南大學(xué)智能系統(tǒng)與智能軟件研究所62中南大學(xué)智能系統(tǒng)與智能軟件研究所證明：(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)

化為子句形例子儲蓄問題：每個儲蓄錢的人都獲得利息。如果沒有利息，那么就沒有人去儲蓄錢。3.4消解原理63中南大學(xué)智能系統(tǒng)與智能軟件研究所把前提化為子句形：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圖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中南大學(xué)智能系統(tǒng)與智能軟件研究所反演求解過程從反演樹求取答案步驟把由目標(biāo)公式的否定產(chǎn)生的每個子句添加到目標(biāo)公式否定之否定的子句中去。按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個子句止。用根部的子句作為一個回答語句。實質(zhì)把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。3.4消解原理65中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

定義

在所有基于規(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)。有時，then部分用于規(guī)定動作；這時，稱這種基于規(guī)則的系統(tǒng)為反應(yīng)式系統(tǒng)(reactionsystem)或產(chǎn)生式系統(tǒng)(production

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

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

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

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

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

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

(4)對全稱量詞轄域內(nèi)的變量進行改名和變量標(biāo)準(zhǔn)化，而存在量詞量化變量用Skolem函數(shù)代替。

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

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

LW

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

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

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

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

80中南大學(xué)智能系統(tǒng)與智能軟件研究所再討論圖2的情況。規(guī)則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

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

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

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

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

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

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

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

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

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

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

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

舉例如下：

這個例子的事實、應(yīng)用規(guī)則和問題分別表示于下：

事實：

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

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

F3:WAGSTAIL(FIDO)；Fido搖尾巴

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

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)；貓咪是貓。

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

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

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

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

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

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

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

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

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

產(chǎn)生式規(guī)則是一個以"如果滿足這個條件，就應(yīng)當(dāng)采取某些操作"形式表示的語句。例如，

規(guī)則:

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

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

控制策略圖3.22產(chǎn)生式系統(tǒng)的主要組成總數(shù)據(jù)庫產(chǎn)生式規(guī)則3.6產(chǎn)生式系統(tǒng)103中南大學(xué)智能系統(tǒng)與智能軟件研究所3.6.1產(chǎn)生式系統(tǒng)的組成

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

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

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

3.6產(chǎn)生式系統(tǒng)106中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

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

(b)

規(guī)則排序：如果規(guī)則編排的順序就表示了啟用的優(yōu)先級，則稱之為規(guī)則排序。

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

(d)規(guī)模排序

按規(guī)則的條件部分的規(guī)模排列優(yōu)先級，優(yōu)先使用被滿足的條件較多的規(guī)則。

(e)就近排序

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

(f)上下文限制

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

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

操作就是執(zhí)行規(guī)則的操作部分。109中南大學(xué)智能系統(tǒng)與智能軟件研究所2.產(chǎn)生式系統(tǒng)的表示

產(chǎn)生式系統(tǒng)的知識表示方法，包括事實的表示和規(guī)則的表示。(1)事實的表示

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