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

人工智能主講:吳順祥

教授模式識(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ù)討論的問題：有哪些常用的搜索算法。問題有解時(shí)能否找到解。找到的解是最佳的嗎？什么情況下可以找到最佳解？求解的效率如何。3中南大學(xué)智能系統(tǒng)與智能軟件研究所第三章搜索推理技術(shù)從問題表示到問題的解決，有一個(gè)求解的過程。接下來要研究的是實(shí)現(xiàn)求解的過程，采用的基本方法包括搜索和推理。本章先介紹搜索技術(shù)，將要討論問題求解的搜索原理，包括一些早期的搜索技術(shù)或用于解決比較簡(jiǎn)單問題的搜索原理和一些比較新的能夠求解比較復(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

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

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

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

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

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

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

(2)建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表（簡(jiǎn)稱CLOSED表），其初始為空表。

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

(4)選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOSED表中。稱此節(jié)點(diǎn)為節(jié)點(diǎn)n，它是CLOSED表中節(jié)點(diǎn)的編號(hào)。

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

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

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

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

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

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

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

盲目搜索

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

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

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

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

(1)把起始節(jié)點(diǎn)放到OPEN表中(如果該起始節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解答)。

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

(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移出，并把它放入CLOSED擴(kuò)展節(jié)點(diǎn)表中。

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

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

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

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

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

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

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

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

1238456712384567（目標(biāo)狀態(tài)）（初始狀態(tài)）規(guī)定：將牌移入空格的順序?yàn)椋簭目崭褡筮呴_始順時(shí)針旋轉(zhuǎn)。不許斜向移動(dòng)，也不返回先輩節(jié)點(diǎn)。從圖可見，要擴(kuò)展26個(gè)節(jié)點(diǎn)，共生成46個(gè)節(jié)點(diǎn)之后才求得解（目標(biāo)節(jié)點(diǎn)）。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)先搜索中，我們首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。

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

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

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

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

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

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

(1)把起始節(jié)點(diǎn)S放到未擴(kuò)展節(jié)點(diǎn)OPEN表中。如果此節(jié)點(diǎn)為一目標(biāo)節(jié)點(diǎn)，則得到一個(gè)解。

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

(3)把第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從OPEN表移到CLOSED表。

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

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

(6)如果后繼節(jié)點(diǎn)中有任一個(gè)為目標(biāo)節(jié)點(diǎn)，則求得一個(gè)解，成功退出；否則，轉(zhuǎn)向(2)22中南大學(xué)智能系統(tǒng)與智能軟件研究所含有深度界限深度優(yōu)先搜索圖如下：

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

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

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

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

從起始節(jié)點(diǎn)S到任一節(jié)點(diǎn)i的路徑代價(jià)記為g(i)。在搜索樹上，我們假設(shè)g(i)也是從起始節(jié)點(diǎn)S到節(jié)點(diǎn)i的最少代價(jià)路徑上的代價(jià)，因?yàn)樗俏ㄒ坏穆窂剑?/p>

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

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

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

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

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

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

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

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

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

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

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

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

(1)用于決定要擴(kuò)展的下一個(gè)節(jié)點(diǎn)，以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地?cái)U(kuò)展。

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

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

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

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

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

啟發(fā)式搜索3.3.2

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

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

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

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

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

(6)擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j：

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

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

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

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

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

下面讓我們?cè)俅斡冒藬?shù)碼難題的例子來說明過程GRAPHSEARCH是如何應(yīng)用估價(jià)函數(shù)排列節(jié)點(diǎn)的。舉例說明如下：

我們采用了簡(jiǎn)單的估價(jià)函數(shù)f(n)=d(n)+W(n)其中：d(n)是搜索樹中節(jié)點(diǎn)n的深度；W(n)用來計(jì)算對(duì)應(yīng)于節(jié)點(diǎn)n的數(shù)據(jù)庫中錯(cuò)放的棋子個(gè)數(shù)。因此，起始節(jié)點(diǎn)棋局的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)與智能軟件研究所估價(jià)函數(shù)的應(yīng)用顯著地減少了被擴(kuò)展的節(jié)點(diǎn)數(shù)(如果我們只用估價(jià)函數(shù)f(n)=d(n)，那么我們就得到寬度優(yōu)先搜索過程)。

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

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

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

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

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

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

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

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

我們希望估價(jià)函數(shù)f是f*的一個(gè)估計(jì)，此估計(jì)可由下式給出：f(n)=g(n)+h(n)

其中：g是g*的估計(jì)；h是h*的估計(jì)。對(duì)于g(n)來說，一個(gè)明顯的選擇就是搜索樹中從S到n這段路徑的代價(jià)，這一代價(jià)可以由從n到S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代價(jià)路徑)。這個(gè)定義包含了g(n)≥g*(n)。對(duì)于h*(n)的估計(jì)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)進(jìn)行的，則稱該過程為A算法。

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

定義3

采用h*(x)的下界h(x)為啟發(fā)函數(shù)的A算法，稱為A*算法。當(dāng)h=0時(shí)，A*算法就變?yōu)橛行蛩阉魉惴ā?3中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

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

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

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

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

(6)對(duì)每個(gè)SUCCSSOR進(jìn)行下列過程：

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

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

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

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

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

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

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

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

(i)計(jì)算f值。

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

原子公式（atomicformulas）

文字—一個(gè)原子公式及其否定。

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

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

步驟：共9步。

例子:將下列謂詞演算公式化為一個(gè)子句集(x)｛P(x)｛(y)［P(y)P(f(x,y))］∧～(y)［Q(x,y)P(y)］｝｝開始：消去蘊(yùn)涵符號(hào)只應(yīng)用∨和～符號(hào)，以～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)減少否定符號(hào)的轄域每個(gè)否定符號(hào)～最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用狄·摩根定律。(3)對(duì)變量標(biāo)準(zhǔn)化對(duì)啞元（虛構(gòu)變量）改名，以保證每個(gè)量詞有其自己唯一的啞元。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)的約束變量，然后消去存在量詞化為前束形把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。前束形={前綴}{母式}

全稱量詞串無量詞公式(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)消去連詞符號(hào)∧用{A,B}代替(A∧B)，消去符號(hào)∧。最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。(9)更換變量名稱可以更換變量符號(hào)的名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。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具有相同的謂詞符號(hào)，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β,如果L1和L2具有最一般合一σ，那么通過消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句(α∨β)σ。這個(gè)新子句叫做消解式。

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

含有變量的消解式

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

含有變量的子句之消解式例子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基本思想

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

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

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

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

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

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

S(x,y)表示“x儲(chǔ)蓄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)

化為子句形例子儲(chǔ)蓄問題：每個(gè)儲(chǔ)蓄錢的人都獲得利息。如果沒有利息，那么就沒有人去儲(chǔ)蓄錢。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(xiàn)(z)4)S(a,b)5)M(b)(4)

消解反演求NIL圖3.12儲(chǔ)蓄問題反演樹子句（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)生的每個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。用根部的子句作為一個(gè)回答語句。實(shí)質(zhì)把一棵根部有NIL的反演樹變換為根部帶有回答語句的一棵證明樹。3.4消解原理65中南大學(xué)智能系統(tǒng)與智能軟件研究所

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

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

定義

在所有基于規(guī)則系統(tǒng)中，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rulebaseddeductionsystem)。在這種系統(tǒng)中，通常稱每個(gè)if部分為前項(xiàng)(antecedent)，稱每個(gè)then部分為后項(xiàng)(consequent)。有時(shí)，then部分用于規(guī)定動(dòng)作；這時(shí)，稱這種基于規(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)（即正向推理）是從事實(shí)到目標(biāo)進(jìn)行操作的，即從狀況條件到動(dòng)作進(jìn)行推理的，也就是從if到then的方向進(jìn)行推理的。

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

(1)利用(W1→W2)和(～W1∨W2)的等價(jià)關(guān)系，消去符號(hào)→(如果存在該符號(hào)的話)。實(shí)際上，在事實(shí)中間很少有符號(hào)→出現(xiàn)，因?yàn)榭砂烟N(yùn)涵式表示為規(guī)則。

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

(3)對(duì)所得到的表達(dá)式進(jìn)行Skolem化和前束化。

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

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

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

LW

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

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

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

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

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)用兩個(gè)規(guī)則子句中任一個(gè)對(duì)上述子句形中的S進(jìn)行消解：于是我們得到4個(gè)子句對(duì)S進(jìn)行消解的消解式的完備集為：X∨Z∨P∨Q,Y∨Z∨P∨Q,R∨X∨Z,R∨Y∨Z

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

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

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

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

求解過程目標(biāo)表達(dá)式的與或形式逆向演繹系統(tǒng)能夠處理任意形式的目標(biāo)表達(dá)式。首先，采用與變換事實(shí)表達(dá)式同樣的過程，把目標(biāo)公式化成與或形，即消去蘊(yùn)涵符號(hào)，把否定符號(hào)移進(jìn)括號(hào)內(nèi)，對(duì)全稱量詞Skolem化并刪去存在量詞。留在目標(biāo)表達(dá)式與或形中的變量假定都已存在量詞量化。如：3.5規(guī)則演繹系統(tǒng)88中南大學(xué)智能系統(tǒng)與智能軟件研究所與或形的目標(biāo)公式也可以表示為與或圖。不過，與事實(shí)表達(dá)式的與或圖不同的是，對(duì)于目標(biāo)表達(dá)式，與或圖中的k線連接符用來分開合取關(guān)系的子表達(dá)式。上例所用的目標(biāo)公式的與或圖如下圖所示。在目標(biāo)公式的與或圖中，我們把根節(jié)點(diǎn)的任一后裔叫做子目標(biāo)節(jié)點(diǎn)，而標(biāo)在這些后裔節(jié)點(diǎn)中的表達(dá)式叫做子目標(biāo)。相應(yīng)的動(dò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)，這個(gè)B規(guī)則是建立在確定的蘊(yùn)涵式基礎(chǔ)上的，正如正向系統(tǒng)的F規(guī)則一樣。不過，我們現(xiàn)在把這些B規(guī)則限制為:WL形式的表達(dá)式。其中，W為任一與或形公式，L為文字，而且蘊(yùn)涵式中任何變量的量詞轄域?yàn)檎麄€(gè)蘊(yùn)涵式。其次，把B規(guī)則限制為這種形式的蘊(yùn)涵式還可以簡(jiǎn)化匹配，使之不會(huì)引起重大的實(shí)際困難。此外，可以把像W

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

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

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

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

舉例如下：

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

事實(shí)：

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)；狗為動(dòng)物。

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

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

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

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

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

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

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

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

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

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

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

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

規(guī)則:

如果某種動(dòng)物是哺乳動(dòng)物，并且吃肉

那么這種動(dòng)物被稱為食肉動(dòng)物

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

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

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

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

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

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

(b)

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

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

(d)規(guī)模排序

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

(e)就近排序

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

(f)上下文限制

把產(chǎn)生式規(guī)則按它們所描述的上下文分組，也就是說按上下文對(duì)規(guī)則分組。在某種上下文條件下，只能從與其相對(duì)應(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)的知識(shí)表示方法，包括事實(shí)的表示和規(guī)則的表示。(1)事實(shí)的表示

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