人工智能及其應(yīng)用搜索推理技術(shù)修改.pptx

1、第三章 搜索推理技術(shù) 知識(shí)表示方法是問題求解所必需的。表示問題是為了進(jìn)一步解決問題。從問題表示到問題的解決，有一個(gè)求解的過(guò)程 ，也就是搜索過(guò)程。在這一過(guò)程中，采用適當(dāng)?shù)乃阉骷夹g(shù)，包括各種規(guī)則，過(guò)程和算法等推理技術(shù)，力求找到問題的解答。 本章首先介紹圖搜索策略的一般過(guò)程，接著討論一些早期的搜索技術(shù)或用于解決比較簡(jiǎn)單的問題的搜索原理，然后研究一些比較新的能夠求解比較復(fù)雜問題的推理技術(shù)。13.1 圖搜索策略 圖搜索策略可以看成一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分別代表初始數(shù)據(jù)庫(kù)和滿足終止條件的數(shù)據(jù)庫(kù)。求得把一個(gè)數(shù)據(jù)庫(kù)變換為另一個(gè)數(shù)據(jù)庫(kù)的規(guī)則序列問題就等價(jià)于求得圖中的一條路徑問題。23.1

2、圖搜索策略 圖搜索(GRAPHSEARCH)的一般過(guò)程如下： (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è)置) 33.1 圖搜索策略 圖搜索(GRAPHSEARC

3、H)的一般過(guò)程如下：(6) 擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。 (7) 對(duì)那些未曾在G中出現(xiàn)過(guò)的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過(guò)的)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) GO LOOP。 43.1 圖搜索策略 圖搜索過(guò)程框圖3.153.1 圖搜索策略 圖搜索算法中的

4、幾個(gè)重要名詞 1OPEN表 2CLOSED表 3搜索圖與搜索樹 此過(guò)程生成一個(gè)明確的圖G(稱為搜索圖)和一個(gè)G的子集T(稱為搜索樹)，樹T上的每個(gè)節(jié)點(diǎn)也在圖G中。搜索樹是由第7步中設(shè)置的指針來(lái)確定的。G中的每個(gè)節(jié)點(diǎn)(除S外)都有一個(gè)只指向G中一個(gè)父輩節(jié)點(diǎn)的指針，該父輩節(jié)點(diǎn)就指定為樹中那個(gè)節(jié)點(diǎn)的唯一父輩節(jié)點(diǎn)。63.1 圖搜索策略圖搜索方法的幾點(diǎn)分析： 圖搜索過(guò)程的第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í)

5、，這一過(guò)程就宣告成功結(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í)，過(guò)程就以失敗告終(某些節(jié)點(diǎn)最終可能沒有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)節(jié)點(diǎn)。73.2 盲目搜索 盲目搜索又叫做無(wú)信息搜索 ，指無(wú)須重新安排OPEN表的搜索。它包括寬度優(yōu)先搜索，深度優(yōu)先搜索和等代價(jià)搜索等。一般只適用于求解比較簡(jiǎn)單的問題。 83.2 盲目搜索 3.2.1寬度優(yōu)先搜索寬度優(yōu)先搜索(breadth-first search)的定義： 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)

6、的，那么這種搜索就叫做寬度優(yōu)先搜索(breadth-first search)，如圖3.2所示。從圖可見，這種搜索是逐層進(jìn)行的；在對(duì)下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)。 93.2 盲目搜索 3.2.1寬度優(yōu)先搜索3.2寬度優(yōu)先搜索示意圖103.2 盲目搜索 3.2.1寬度優(yōu)先搜索寬度優(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)向上述第

7、(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)步。113.2 盲目搜索 3.2.1寬度優(yōu)先搜索寬度優(yōu)先算法框圖3.3123.2 盲目搜索 3.2.1寬度優(yōu)先搜索例：把寬度優(yōu)先搜索應(yīng)用于八數(shù)碼難題時(shí)所生成的搜索樹，這個(gè)問題就是要把初始棋局變?yōu)槿缦履繕?biāo)棋局的問題： 寬度優(yōu)先搜索方法能夠保證在搜索樹中找到一條通向目標(biāo)節(jié)點(diǎn)的最短途徑；這棵搜索樹提供了所有存在的路徑(如果沒有路徑存在，那么對(duì)有限圖來(lái)說(shuō)，我們就說(shuō)該法失敗退出；對(duì)于無(wú)限圖來(lái)說(shuō)，則永遠(yuǎn)不會(huì)終止)。133.2 盲目

8、搜索 3.2.1寬度優(yōu)先搜索圖 3.4 八數(shù)碼難題的寬度優(yōu)先搜索樹 搜索樹上的所有節(jié)點(diǎn)都標(biāo)記它們所對(duì)應(yīng)的狀態(tài)描述，每個(gè)節(jié)點(diǎn)旁邊的數(shù)字表示節(jié)點(diǎn)擴(kuò)展的順序(按順時(shí)針方向移動(dòng)空格)。圖中最后一個(gè)節(jié)點(diǎn)是目標(biāo)節(jié)點(diǎn)。143.2 盲目搜索 3.2.2深度優(yōu)先搜索另一種盲目(無(wú)信息)搜索叫做深度優(yōu)先搜索(depth-first search)。分析深度優(yōu)先搜索示意圖可看出，在深度優(yōu)先搜索中，我們首先擴(kuò)展最新產(chǎn)生的(即最深的)節(jié)點(diǎn)。深度相等的節(jié)點(diǎn)可以任意排列。 153.2 盲目搜索 3.2.2深度優(yōu)先搜索我們定義節(jié)點(diǎn)的深度如下：(1) 起始節(jié)點(diǎn)(即根節(jié)點(diǎn))的深度為0。(2) 任何其它節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度

9、加上1。首先，擴(kuò)展最深的節(jié)點(diǎn)的結(jié)果使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點(diǎn)向下進(jìn)行下去；只有當(dāng)搜索到達(dá)一個(gè)沒有后裔的狀態(tài)時(shí)，它才考慮另一條替代的路徑。替代路徑與前面已經(jīng)試過(guò)的路徑不同之處僅僅在于改變最后n步，而且保持n盡可能小。 對(duì)于許多問題，其狀態(tài)空間搜索樹的深度可能為無(wú)限深，或者可能至少要比某個(gè)可接受的解答序列的已知深度上限還要深。為了避免考慮太長(zhǎng)的路徑(防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去)，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度深度界限。任何節(jié)點(diǎn)如果達(dá)到了深度界限，那么都將把它們作為沒有后繼節(jié)點(diǎn)處理。值得說(shuō)明的是，即使應(yīng)用了深度界限的規(guī)定，所求得的解答路徑并不一定就是最短的路徑。163.2

10、盲目搜索 3.2.2深度優(yōu)先搜索圖3.5深度優(yōu)先搜索示意圖173.2 盲目搜索 3.2.2深度優(yōu)先搜索含有深度界限的深度優(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)。183.2 盲目搜索 3.2.2深度優(yōu)先

11、搜索深度優(yōu)先搜索算法框圖3.6193.2 盲目搜索 3.2.2深度優(yōu)先搜索例：按深度優(yōu)先搜索生成的八數(shù)碼難題搜索樹，我們?cè)O(shè)置深度界限為5。圖3.8繪出了搜索樹，粗線條的路徑表明含有5條應(yīng)用規(guī)則的一個(gè)解。從圖可見，深度優(yōu)先搜索過(guò)程是沿著一條路徑進(jìn)行下去，直到深度界限為止，然后再考慮只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑，等等。203.2 盲目搜索 3.2.2深度優(yōu)先搜索圖 3.8 八數(shù)碼難題的深度優(yōu)先搜索樹 213.2 盲目搜索 3.2.3等代價(jià)搜索 有些問題并不要求有應(yīng)用算符序列為最少的解，而是要求具有某些特性的解。搜索樹中每條連接弧線上的有關(guān)

12、代價(jià)以及隨之而求得的具有最小代價(jià)的解答路徑，與許多這樣的廣義準(zhǔn)則相符合。 寬度優(yōu)先搜索可被推廣用來(lái)解決這種尋找從起始狀態(tài)至目標(biāo)狀態(tài)的具有最小代價(jià)的路徑問題，這種推廣了的寬度優(yōu)先搜索算法叫做等代價(jià)搜索算法。223.2 盲目搜索 3.2.3等代價(jià)搜索有如下一些記號(hào)：起始節(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)樗俏ㄒ坏穆窂剑?233.2 盲目搜索 3.2.3等代價(jià)搜索等代價(jià)搜索算法：等代價(jià)搜索方法以g(i)的遞增順序擴(kuò)展其節(jié)點(diǎn)，其算法如下：(1

13、) 把起始節(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

14、的指針。(7) 轉(zhuǎn)向第(2)步。243.2 盲目搜索 3.2.3深度優(yōu)先搜索圖 3.9等代價(jià)搜索算法框圖 253.3 啟發(fā)式搜索 盲目搜索的不足：效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。 分析前面介紹的寬度優(yōu)先、深度優(yōu)先搜索，或等代價(jià)搜索算法,其主要的差別是OPEN表中待擴(kuò)展節(jié)點(diǎn)的順序問題。人們就試圖找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順序，即選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展，那么，搜索效率將會(huì)大為提高。啟發(fā)信息：進(jìn)行搜索技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域的特性的信息，把此種信息叫做啟發(fā)信息。把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法。 263.3 啟發(fā)式搜索 3.2.1 啟發(fā)式搜索策略和估價(jià)函數(shù) 1 啟發(fā)式搜

15、索策略假設(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)的過(guò)程中，用于決定要生成哪一個(gè)或哪幾個(gè)后繼節(jié)點(diǎn)，以免盲目地同時(shí)生成所有可能的節(jié)點(diǎn)。(3) 用于決定某些應(yīng)該從搜索樹中拋棄或修剪的節(jié)點(diǎn)。在本節(jié)中，我們只討論利用上述第一種啟發(fā)信息的狀態(tài)空間搜索算法，即決定哪個(gè)是下一步要擴(kuò)展的節(jié)點(diǎn)。這種搜索總是選擇“最有希望”的節(jié)點(diǎn)作為下一個(gè)被擴(kuò)展的節(jié)點(diǎn)。這種搜索叫做有序搜索(ordered search)。

16、 273.3 啟發(fā)式搜索 3.2.1 啟發(fā)式搜索策略和估價(jià)函數(shù) 2 估價(jià)函數(shù) 估價(jià)函數(shù)(evaluation function)：用來(lái)估算節(jié)點(diǎn)希望程度的量度。一個(gè)節(jié)點(diǎn)的“希望”(promise)有幾種不同的定義方法。在狀態(tài)空間問題中，一種方法是估算目標(biāo)節(jié)點(diǎn)到此節(jié)點(diǎn)的距離；另一種方法認(rèn)為，解答路徑包括被估價(jià)過(guò)的節(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)特性。我們用符號(hào)f來(lái)標(biāo)記估價(jià)函數(shù)，用f(n)表示節(jié)點(diǎn)n的估價(jià)函數(shù)值。暫時(shí)令f為任意函數(shù)，以后我們將會(huì)提出f是從起始節(jié)點(diǎn)約束地通過(guò)節(jié)點(diǎn)n而到達(dá)目標(biāo)節(jié)點(diǎn)的最

17、小代價(jià)路徑上的一個(gè)估算代價(jià)。283.3 啟發(fā)式搜索 3.3.2 有序搜索 我們用估價(jià)函數(shù)f來(lái)排列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)先算法。 可見它總是選擇最有希望的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。有序搜索(ordered search)又稱為最好優(yōu)先搜索(best-first search)。 293.3

18、 啟發(fā)式搜索 3.3.2 有序搜索 有序狀態(tài)空間搜索算法如下： (1) 把起始節(jié)點(diǎn)S放到OPEN表中，計(jì)算f(S)并把其值與節(jié)點(diǎn)S聯(lián)系起來(lái)。(2) 如果OPEN是個(gè)空表，則失敗退出，無(wú)解。(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è)解。303.3 啟發(fā)式搜索 3.3.2 有序搜索 有序狀態(tài)空間搜索算法如下： (6) 擴(kuò)展節(jié)點(diǎn)i，生成其全部后繼節(jié)點(diǎn)。對(duì)于i的每一個(gè)后繼節(jié)點(diǎn)j

19、：(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ì)算過(guò)的f值和前面計(jì)算過(guò)的該節(jié)點(diǎn)在表中的f值。如果新的f值較小，則(i)以此新值取代舊值。(ii)從j指向i，而不是指向它的父輩節(jié)點(diǎn)。(iii)如果節(jié)點(diǎn)j在CLOSED中,則把它移回OPEN表.(7) 轉(zhuǎn)向(2)，即GO TO(2)。 313.3 啟發(fā)式搜索 3.3.2 有序搜索 有序搜索算法框圖3.9323.3 啟發(fā)式搜索 3.3.2 有序搜索 寬度

20、優(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)的解或任意解。 333.3 啟發(fā)式搜索 3.3.3 A*算法A*算法的估價(jià)函數(shù)：讓我們描述一個(gè)特別的估價(jià)函數(shù)，這個(gè)估價(jià)函數(shù)f使得在任意節(jié)點(diǎn)上其函數(shù)值f(n)能估算出從節(jié)點(diǎn)S到節(jié)點(diǎn)n的最小代價(jià)路徑的代

21、價(jià)與從節(jié)點(diǎn)n到某一目標(biāo)節(jié)點(diǎn)的最小代價(jià)路徑的代價(jià)之總和，也就是說(shuō)f(n)是約束通過(guò)節(jié)點(diǎn)n的一條最小代價(jià)路徑的代價(jià)的一個(gè)估計(jì)。 因此，OPEN表上具有最小f值的那個(gè)節(jié)點(diǎn)就是所估計(jì)的加有最少嚴(yán)格約束條件的節(jié)點(diǎn)，而且下一步要擴(kuò)展這個(gè)節(jié)點(diǎn)是合適的。343.3 啟發(fā)式搜索 3.2.4 A*算法A*算法的估價(jià)函數(shù)：在正式討論A*算法之前，我們先介紹幾個(gè)有用的記號(hào)。 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上所

22、有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*沒有定義)。 353.3 啟發(fā)式搜索 A*算法的估價(jià)函數(shù)：通常我們感興趣的是想知道從已知起始節(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的路徑來(lái)說(shuō)，函數(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到

23、某目標(biāo)節(jié)點(diǎn)的一條最佳路徑的代價(jià)之和，即: f*(n)=g*(n)+ h*(n)因而f*(n)值就是從S開始約束通過(guò)節(jié)點(diǎn)n的一條最佳路徑的代價(jià)，而f*(S)=h*(S)是一條從S到某個(gè)目標(biāo)節(jié)點(diǎn)中間無(wú)約束的一條最佳路徑的代價(jià)。我們希望估價(jià)函數(shù)f是f*的一個(gè)估計(jì)，此估計(jì)可由下式給出：f(n)=g(n)+h(n)363.3 啟發(fā)式搜索 3.2.4 A*算法A*算法的估價(jià)函數(shù)：其中：g是g*的估計(jì)；h是h*的估計(jì)。對(duì)于g(n)來(lái)說(shuō)，一個(gè)明顯的選擇就是搜索樹中從S到n這段路徑的代價(jià)，這一代價(jià)可以由從n到S尋找指針時(shí)，把所遇到的各段弧線的代價(jià)加起來(lái)給出(這條路徑就是到目前為止用搜索算法找到的從S到n的最小代

24、價(jià)路徑)。 這個(gè)定義包含了g(n)g*(n)。對(duì)于h*(n)的估計(jì)h(n)，它依賴于有關(guān)問題的領(lǐng)域的啟發(fā)信息。我們把h叫做啟發(fā)函數(shù)。 373.3 啟發(fā)式搜索 A*算法的估價(jià)函數(shù)：A算法和A*算法的定義定義1 在GRAPHSEARCH過(guò)程中，如果第8步的重排OPEN表是依據(jù)f(x)=g(x)+h(x)進(jìn)行的，則稱該過(guò)程為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)橛行蛩阉魉惴?。A*算法是一種有序搜索算法，其特點(diǎn)在于對(duì)估價(jià)

25、函數(shù)的定義上。對(duì)于一般的有序搜索，總是選擇f值最小的節(jié)點(diǎn)作為擴(kuò)展節(jié)點(diǎn)。因此，f是根據(jù)需要找到一條最小代價(jià)路徑的觀點(diǎn)來(lái)估算節(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à)。 383.3 啟發(fā)式搜索 3.2.4 A*算法A*算法(1) 把S放入OPEN表，記f=h，令CLOSED為空表。(2) 重復(fù)下列過(guò)程，直至找到目標(biāo)節(jié)點(diǎn)為止。若OPEN為空表，則宣告失敗。(3) 選取OPEN表中未設(shè)置過(guò)的具有最小f值的節(jié)點(diǎn)為最佳節(jié)點(diǎn)BESTNODE，并把它放入CLOSED表。(4) 若BESTNODE為一目標(biāo)節(jié)點(diǎn)，則成功求得一解。(5) 若BESTN

26、ODE不是目標(biāo)節(jié)點(diǎn)，則擴(kuò)展之，產(chǎn)生后繼節(jié)點(diǎn)SUCCSSOR。393.3 啟發(fā)式搜索 3.2.4 A*算法A*算法(6) 對(duì)每個(gè)SUCCSSOR進(jìn)行下列過(guò)程：(a) 建立從SUCCSSOR返回BESTNODE的指針。(b) 計(jì)算g(SUC)=g(BES)+g(BES,SUC)。(c) 如果SUCCSSOROPEN，則稱此節(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) 若SUC

27、CSSOR不在OPEN表中，則看其是否在CLOSED表中。(g) 若SUCCSSOR在CLOSE表中，則轉(zhuǎn)向c。(h) 若SUCCSSOR既不在OPEN表中，又不在CLOSED表中，則把它放入OPEN表中，并添入BESTNODE后裔表，然后轉(zhuǎn)向(7)(7) 計(jì)算f值。(8) GO LOOP 403.3 啟發(fā)式搜索 A* 算 法 參 考 框 圖 3 . 1 1413.4消解原理 前面我們討論了一些簡(jiǎn)單搜索的基本原理，包括某些推理規(guī)則以及置換合一等概念。但對(duì)于許多比較復(fù)雜的系統(tǒng)和問題，如果采用前面討論過(guò)的搜索方法，那么很難甚至無(wú)法使問題獲得解決的。需要應(yīng)用一些更先進(jìn)的推理技術(shù)和系統(tǒng)求解這種比較復(fù)雜

28、的問題，本節(jié)討論消解原理。423.4消解原理 3.4.1化為子句集 第二章中討論過(guò)謂詞公式，某些推理規(guī)則以及置換合一等概念。在這個(gè)基礎(chǔ)上，我們將進(jìn)一步研究消解原理(resolution principle)。有些專家把它叫做歸結(jié)原理。 消解是一種可用于一定的子句公式的重要推理規(guī)則。 一個(gè)子句定義為由文字的析取組成的公式(一個(gè)原子公式和原子公式的否定都叫做文字)。當(dāng)消解可使用時(shí)，消解過(guò)程被應(yīng)用于母體子句對(duì)，以便產(chǎn)生一個(gè)導(dǎo)出子句。例如，如果存在某個(gè)公理E1E2和另一公理E2E3，那么E1E3在邏輯上成立。這就是消解，而稱E1E3為E1E2和E2E3的消解式(resolvent)。 433.4消解原

29、理 3.4.1化為子句集在說(shuō)明消解過(guò)程之前,我們首先說(shuō)明任一謂詞演算公式可以化成一個(gè)子句集。其變換過(guò)程由下列九個(gè)步驟組成：(1)消去蘊(yùn)涵符號(hào) 只應(yīng)用和符號(hào)，以AB替換A=B。(2)減少否定符號(hào)的轄域 每個(gè)否定符號(hào)最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用狄摩根定律。443.4消解原理 3.4.1化為子句集例如： 以AB代替(AB)以AB代替(AB)以(x)A代替(x)A以(x)A代替(x)A以A代替(A)453.4消解原理 3.4.1化為子句集(3)對(duì)變量標(biāo)準(zhǔn)化 在任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元(虛構(gòu)變量)，它可以在該轄域內(nèi)處處統(tǒng)一地被另一個(gè)沒有出現(xiàn)過(guò)的任意變量所代替，而不改變公式的真值

30、。合適公式中變量的標(biāo)準(zhǔn)化，意味著對(duì)啞元改名以保證每個(gè)量詞有其自己唯一的啞元。例如，把 標(biāo)準(zhǔn)化而得到: 463.4消解原理 3.4.1化為子句集(4)消去存在量詞Skolem函數(shù): 在公式(y)(x)P(x,y)中，存在量詞是在全稱量詞的轄域內(nèi)，我們?cè)试S所存在的x可能依賴于y值。令這種依賴關(guān)系明顯地由函數(shù)g(y)所定義，它把每個(gè)y值映射到存在的那個(gè)x。這種函數(shù)叫做Skolem函數(shù)。 如果用Skolem函數(shù)代替存在的x,我們就可以消去全部存在量詞，并寫成：從一個(gè)公式消去一個(gè)存在量詞的一般規(guī)則是以一個(gè)Skolem函數(shù)代替每個(gè)出現(xiàn)的存在量詞的量化變量，而這個(gè)Skolem函數(shù)的變量就是由那些全稱量詞所約

31、束的全稱量詞量化變量，這些全稱量詞的轄域包括要被消去的存在量詞的轄域在內(nèi)。Skolem函數(shù)所使用的函數(shù)符號(hào)必須是新的，即不允許是公式中已經(jīng)出現(xiàn)過(guò)的函數(shù)符號(hào)。 473.4消解原理 3.4.1化為子句集(4)消去存在量詞Skolem函數(shù): 如果要消去的存在量詞不在任何一個(gè)全稱量詞的轄域內(nèi)，那么我們就用不含變量的Skolem函數(shù)即常量。例如，(x)P(x)化為P(A)，其中常量符號(hào)A用來(lái)表示我們知道的存在實(shí)體。A必須是個(gè)新的常量符號(hào)，它未曾在公式中其它地方使用過(guò)。例如：(z)(y)( x)P(x,y,z)483.4消解原理 3.4.1化為子句集例如：(z)(y)(x)P(x,y,z)被(y)P(g(

32、y),y,A)代替，其中g(shù)(y)為一Skolem函數(shù)。 493.4消解原理 3.4.1化為子句集(5)化為前束形到這一步，已不留下任何存在量詞，而且每個(gè)全稱量詞都有自己的變量。把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。所得公式稱為前束形。前束形公式由前綴和母式組成，前綴由全稱量詞串組成，母式由沒有量詞的公式組成，即前束形 = (前綴) (母 式) 全稱量詞串 無(wú)量詞公式 503.4消解原理 3.4.1化為子句集(6)把母式化為合取范式 任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。這種母式叫做合取范式。我們可以反復(fù)應(yīng)用分配律

33、。把任一母式化成合取范式。例如，我們把 ABC化為ABAC 513.4消解原理 3.4.1化為子句集(7)消去全稱量詞到了這一步，所有余下的量詞均被全稱量詞量化了。同時(shí)，全稱量詞的次序也不重要了。因此，我們可以消去前綴，即消去明顯出現(xiàn)的全稱量詞。 (8)消去連詞符號(hào) 用(AB),(AC)代替(AB)(AC)，以消去明顯的符號(hào)。反復(fù)代替的結(jié)果，最后得到一個(gè)有限集，其中每個(gè)公式是文字的析取。任一個(gè)只由文字的析取構(gòu)成的合適公式叫做一個(gè)子句。523.4消解原理 3.4.1化為子句集(9)更換變量名稱可以更換變量符號(hào)的名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。例如，對(duì)于子集P(x)P(y)Pf(x,

34、y),P(x)Qx,g(x),P(x)Pg(x)，在更改變量名后，可以得到子句集： P(x1)P(y)Pf(x1,y), P(x2)Qx2,g(x2), P(x3)Pg(x3) 按照上述9個(gè)步驟。把例子 533.4消解原理3.4.1化為子句集第一步： 第二步： 第三步： 第四步： w=g（x）為一個(gè)Skolem函數(shù) 第五步： 前綴母式543.4消解原理 3.4.1化為子句集 第六步： 第七步： 第八步： 第九步：更改變量名稱：553.4消解原理 3.4.2消解推理規(guī)則 令L1為任一原子公式，L2為另一原子公式； L1和L2具有相同的謂詞符號(hào)，但一般具有不同的變量。已知兩子句L1和L2，如果L1

35、和L2具有最一般合一者，那么通過(guò)消解可以從這兩個(gè)父輩子句推導(dǎo)出一個(gè)新子句()。這個(gè)新子句叫做消解式。它是由取這兩個(gè)子句的析取，然后消去互補(bǔ)對(duì)而得到的。 下面舉出幾個(gè)從父輩子句求消解式的例子: (a) 假言推理 父輩子句消解式563.4消解原理 3.4.2消解推理規(guī)則下面舉出幾個(gè)從父輩子句求消解式的例子: (b) 合并 父輩子句消解式573.4消解原理 3.4.2消解推理規(guī)則 下面舉出幾個(gè)從父輩子句求消解式的例子: (c) 重言式 父輩子句消解式583.4消解原理 3.4.2消解推理規(guī)則 下面舉出幾個(gè)從父輩子句求消解式的例子: (d)空子句(矛盾) 593.4消解原理 3.4.2消解推理規(guī)則 下

36、面舉出幾個(gè)從父輩子句求消解式的例子: (e) 鏈?zhǔn)?三段論) 603.4消解原理 3.4.3含有變量的消解式 為了對(duì)含有變量的子句使用消解規(guī)則，我們必須找到一個(gè)置換，作用于父輩子句使其含有互補(bǔ)文字。 令父輩子句由Li和Mi給出，而且假設(shè)這兩個(gè)子句中的變量已經(jīng)分離標(biāo)準(zhǔn)化。設(shè)li是Li的一個(gè)子集，mi是Mi的一個(gè)子集，使得集li和mi的并集存在一個(gè)最一般的合一者。 消解兩個(gè)子句Li和Mi，得到的新子句: Li-liMi-mi就是這兩個(gè)子句的消解式。 消解兩個(gè)子句時(shí)，可能有一個(gè)以上的消解式，因?yàn)橛卸喾N選擇li和mi的方法。不過(guò)，在任何情況下，它們最多具有有限個(gè)消解式。 613.4消解原理 作為例子，

37、我們考慮兩個(gè)子句: Px,f(A)Px,f(y)Q(y) 和 Pz,f(A)Q(z)如果取 :li=Px,f(A)， mi=Pz,f(A)那么得到消解式: Pz,f(y)Q(z)Q(y)如果取 :li=Q(y)，mi=Q(z)那么得到消解式: Px,f(A)Px,f(y)Py,f(A)進(jìn)一步消解得消解式為: Py,f(y)可見這兩個(gè)子句消解一共可得4個(gè)不同的消解式，其中3個(gè)是消解P得到的，而另一個(gè)是由消解Q得到的。623.4消解原理 3.4.3含有變量的消解式 例1 例2 例3 633.4消解原理 3.4.3含有變量的消解式 下面舉幾個(gè)對(duì)含有變量的子句使用消解的例子。 例1例3例2643.4消

38、解原理 3.4.3含有變量的消解式P72 本節(jié)中所例舉的對(duì)基子句和對(duì)含有變量的子句進(jìn)行消解的例子，其父輩子句和消解式列表示于表4.1。這些例子表示出消解推理的某些常用規(guī)則。 消解推理常用規(guī)則653.4消解原理 3.4.4消解反演求解過(guò)程 1 基本思想 把要解決的問題作為一個(gè)要證明的命題，其目標(biāo)公式被否定并化成子句形，然后添加到命題公式集中去,把消解反演系統(tǒng)應(yīng)用于聯(lián)合集，并推導(dǎo)出一個(gè)空子句（NIL)，產(chǎn)生一個(gè)矛盾，這說(shuō)明目標(biāo)公式的否定式不成立，即有目標(biāo)公式成立，定理得證，問題得到解決。這與數(shù)學(xué)中反證法的思想十分相似。 663.4消解原理 3.4.4消解反演求解過(guò)程 (2) 反演求解的正確性 設(shè)公

39、式L在邏輯上遵循公式集S，那么按照定義滿足S的每個(gè)解釋也滿足L。決不會(huì)有滿足S的解釋能夠滿足L的，所以不存在能夠滿足并集SL的解釋。 如果一個(gè)公式集不能被任一解釋所滿足，那么這個(gè)公式是不可滿足的。因此，如果L在邏輯上遵循S，那么SL是不可滿足的。 可以證明，如果消解反演反復(fù)應(yīng)用到不可滿足的子句集，那么最終將要產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集SL消解得到的子句，最后將產(chǎn)生空子句；反之，可以證明，如果從SL的子句消解得到空子句，那么L在邏輯上遵循S。673.4消解原理 3.4.4消解反演求解過(guò)程 以下按上述的四個(gè)步驟來(lái)對(duì)問題進(jìn)行反演求解： (1)否定L，得L；(2)把L添加

40、到S中去；(3)把新產(chǎn)生的集合L，S化成子句集；(4)應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句NIL。 683.4消解原理 3.4.4消解反演求解過(guò)程 (3) 反演求解的舉例 下面舉個(gè)例子來(lái)說(shuō)明消解反演過(guò)程： 前提：每個(gè)儲(chǔ)蓄錢的人都獲得利息。結(jié)論：如果沒有利息，那么就沒有人去儲(chǔ)蓄錢。證明：令S(x,y)表示x儲(chǔ)蓄y M(x)表示x是錢 I(x)表示x是利息 E(x，y)表示x獲得y于是上述命題寫成下列形式：結(jié)論：693.4消解原理 3.4.4消解反演求解過(guò)程 用化為子句集的九步法，可把前提化為下列的子句集： 其中，y=f（x）為Skolem函數(shù)。而結(jié)論的否定：703.4消解原理 3.4.4

41、消解反演求解過(guò)程（a） 否定L，即有 （b） 把 L添加到 中去，即 （c） 把新產(chǎn)生的集合化成子句集，即（d） 應(yīng)用消解原理，力圖推導(dǎo)出一個(gè)表示矛盾的空子句NIL。 713.4消解原理 3.4.4消解反演求解過(guò)程 儲(chǔ)蓄問題反演樹 723.4消解原理 3.4.4消解反演求解過(guò)程 可把前提和結(jié)論化為下列的子句集：S=S(x,y)M(y)I(f(x),S(x,y)M(y)E(x,f(x)其中，y=f(x)為Skolem函數(shù)。I(z),S(a,b),M(b)733.4消解原理 3.4.4消解反演求解過(guò)程 (2)反演求解過(guò)程 用反演樹求取對(duì)某個(gè)問題的答案，其過(guò)程如下：(1) 把由目標(biāo)公式的否定產(chǎn)生的每

42、個(gè)子句添加到目標(biāo)公式否定之否定的子句中去。(2) 按照反演樹，執(zhí)行和以前相同的消解，直至在根部得到某個(gè)子句止。(3) 用根部的子句作為一個(gè)回答語(yǔ)句。 答案求取涉及到把一棵根部有NIL的反演樹變換為在根部帶有可用作答案的某個(gè)語(yǔ)句的一顆證明樹。由于變換關(guān)系涉及到把由目標(biāo)公式的否定產(chǎn)生的每個(gè)子句變換為一個(gè)重言式，所以被變換的證明樹就是一棵消解的證明樹，其在根部的語(yǔ)句在邏輯上遵循公理加上重言式，因而也單獨(dú)地遵循公理。因此被變換的證明樹本身就證明了求取辦法是正確的。743.4消解原理 ( x)AT(JOHN,X)=AT(FIDO,X)和AT(JOHN,SCHOOL)如果無(wú)論約翰(John)到哪里去，菲多

43、(Fido)也就去那里，那么如果約翰在學(xué)校里，菲多在哪里呢?” 很清楚，這個(gè)問題說(shuō)明了兩個(gè)事實(shí)，然后提出一個(gè)問題，而問題的答案大概可從這兩個(gè)事實(shí)推導(dǎo)出。這兩個(gè)事實(shí)可以解釋為下列公式集S：如果我們首先證明公式( 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(FI

44、DO,X) 遵循S。我們也可以說(shuō)明，用一種比較簡(jiǎn)單的方法來(lái)求取合適的答案。 753.4消解原理 3.4.4消解反演求解過(guò)程 (2)反演求解過(guò)程 消解反演可用一般方式得到，其辦法是首先對(duì)被證明的公式加以否定，再把這個(gè)否定式附加到集S中去，化這個(gè)擴(kuò)充集的所有成員為子句形，然后用消解證明這個(gè)子句集是不可滿足的。圖3.13表示出上例的反演樹。從S中的公式得到的子句叫做公理。注意目標(biāo)公式( x)AT(FIDO,x)的否定產(chǎn)生 ( x)AT(FIDO,x) 其子句形式為:AT(FIDO,x) 763.4消解原理 3.4.4消解反演求解過(guò)程 (2)反演求解過(guò)程 對(duì)本例應(yīng)用消解反演求解過(guò)程，我們有：(1) 目

45、標(biāo)公式否定的子句形式為 :AT(FIDO,x) 把它添加至目標(biāo)公式的否定之否定的子句中去，得重言式 AT(FIDO,x)AT(FIDO,x) (2) 用圖3.14的反演樹進(jìn)行消解，并在根部得到子句:AT (FIDO，SCHOOL) (3) 從根部求得答案AT(FIDO，SCHOOL)，用此子句作為回答語(yǔ)句。因此，子句 AT (FIDO，SCHOOL)就是這個(gè)問題的合適答案，773.4消解原理 3.4.4消解反演求解過(guò)程 (2)反演求解過(guò)程 “菲多在哪里”例題的反演樹 3.13 從消解求取答案例題的反演樹 3.14783.5 規(guī)則演繹系統(tǒng) 對(duì)于許多公式來(lái)說(shuō)，子句形是一種低效率的表達(dá)式，因?yàn)橐恍┲?/p>

46、要信息可能在求取子句形過(guò)程中丟失。本章將研究采用易于敘述的if-then(如果-那么)規(guī)則來(lái)求解問題。 基于規(guī)則的問題求解系統(tǒng)運(yùn)用下述規(guī)則: 其中，If部分可能由幾個(gè)if組成，而Then部分可能由一個(gè)或一個(gè)以上的then組成。 在所有基于規(guī)則系統(tǒng)中，每個(gè)if可能與某斷言(assertion)集中的一個(gè)或多個(gè)斷言匹配。有時(shí)把該斷言集稱為工作內(nèi)存。在許多基于規(guī)則系統(tǒng)中，then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rule based deduction system)。 在這種系統(tǒng)中，通常稱每個(gè)if部分為前項(xiàng)(antecedent)，稱每個(gè)then部分為后項(xiàng)(co

47、nsequent)。793.5 規(guī)則演繹系統(tǒng) 3.5.1 規(guī)則正向演繹系統(tǒng)基于規(guī)則的演繹系統(tǒng)和產(chǎn)生式系統(tǒng)，均有兩種推理方式：正向推理(forward chanining)和逆向推理(backward chaining)。正向推理：從if部分向then部分推理的過(guò)程，它是從事實(shí)或狀況向目標(biāo)或動(dòng)作進(jìn)行操作的。 逆向推理：從then部分向if部分推理的過(guò)程，它是從目標(biāo)或動(dòng)作向事實(shí)或狀況進(jìn)行操作的。803.5 規(guī)則演繹系統(tǒng) 1.事實(shí)表達(dá)式的與或形變換在基于規(guī)則的正向演繹系統(tǒng)中，我們把事實(shí)表示為非蘊(yùn)涵形式的與或形，作為系統(tǒng)的總數(shù)據(jù)庫(kù)。我們不想把這些事實(shí)化為子句形，而是把它們表示為謂詞演算公式，并把這些公

48、式變換為叫做與或形的非蘊(yùn)涵形式。要把一個(gè)公式化為與或形，可采用下列步驟：(1) 利用(W1=W2)和(W1W2)的等價(jià)關(guān)系，消去符號(hào)=(如果存在該符號(hào)的話)。實(shí)際上，在事實(shí)中間很少有符號(hào)=出現(xiàn)，因?yàn)榭砂烟N(yùn)涵式表示為規(guī)則。(2) 用狄摩根(De Morgan)定律把否定符號(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)為具有全稱量化作用。 813.5 規(guī)則演繹系統(tǒng) 例如，我們有事實(shí)表達(dá)式 對(duì)

49、變量更名標(biāo)準(zhǔn)化，使得同一變量不出現(xiàn)在事實(shí)表達(dá)式的不同主要合取式中。更名后得表達(dá)式： Q(w,A)R(v)P(v)S(A,v) 必須注意到Q(v，A)中的變量v可用新變量w代替，而合取式R(v)P(v)中的變量v卻不可更名，因?yàn)楹笳咭渤霈F(xiàn)在析取式S(A,v)中。 與或形表達(dá)式是由符號(hào)和連接的一些文字的子表達(dá)式組成的。呈與或形的表達(dá)式并不是子句形，而是接近于原始表達(dá)式形式，特別是它的子表達(dá)式不是復(fù)合產(chǎn)生的。 把它化為 Q(v,A)R(v)P(v)S(A,v)823.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實(shí)表達(dá)式的與或圖表示 與或形的事實(shí)表達(dá)式可用與或圖來(lái)表示。如圖3.15的與或樹表示出

50、上述例子的與或形事實(shí)表達(dá)。 圖3.15中，每個(gè)節(jié)點(diǎn)表示該事實(shí)表達(dá)式的一個(gè)子表達(dá)式。某個(gè)事實(shí)表達(dá)式(E1Ek)的析取關(guān)系子表達(dá)式E1，Ek是用后繼節(jié)點(diǎn)表示的，并由一個(gè)k線連接符把它們連接到父輩節(jié)點(diǎn)上。 某個(gè)事實(shí)表達(dá)式(E1En)的每個(gè)合取子表達(dá)式E1，En是由單一的后繼節(jié)點(diǎn)表示的，并由一個(gè)單線連接符接到父輩接點(diǎn)。在事實(shí)表達(dá)式中，用k線連接符(一個(gè)合取記號(hào))來(lái)分解析取式，很可能會(huì)令人感到意外。在后面的討論中，我們將會(huì)了解到采用這種約定的原因。 833.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實(shí)表達(dá)式的與或圖表示表示某個(gè)事實(shí)表達(dá)式的與或圖的葉節(jié)點(diǎn)均由表達(dá)式中的文字來(lái)標(biāo)記。圖中標(biāo)記有整個(gè)事實(shí)

51、表達(dá)式的節(jié)點(diǎn)，稱為根節(jié)點(diǎn)，它在圖中沒有祖先。公式的與或圖表示有個(gè)有趣的性質(zhì)，即由變換該公式得到的子句集可作為此與或圖的解圖的集合(終止于葉節(jié)點(diǎn))讀出；也就是說(shuō)，所得到的每個(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)843.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實(shí)表達(dá)式的與或圖表示 圖 3.15 一個(gè)事實(shí)表達(dá)式的與或樹表示 853.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)2.事實(shí)表達(dá)式的與或圖表示 上述每個(gè)子句都是圖3.15解圖之一的葉節(jié)點(diǎn)上文字的析取。所以

52、，我們可把與或圖看做是對(duì)子句集的簡(jiǎn)潔表示。不過(guò)，實(shí)際上表達(dá)式的與或圖表示此子句集表示的通用性稍差，因?yàn)闆]有復(fù)合出共同的子表達(dá)式會(huì)妨礙在子句形中可能做到的某些變量的更名。例如，上面的最后一個(gè)子句，其變量v可全部改為u，但無(wú)法在與或圖中加以表示，因而失去了通用性，并且可能帶來(lái)一些困難。我們一般把事實(shí)表達(dá)式的與或圖表示倒過(guò)來(lái)畫，即把根節(jié)點(diǎn)畫在最下面，而把其后繼節(jié)點(diǎn)往上畫。接下來(lái)我們將要討論目標(biāo)公式的與或圖表示，它是按通常方式畫出的，即目標(biāo)在上面。863.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換這些規(guī)則是建立在某個(gè)問題轄域中普通陳述性知識(shí)的蘊(yùn)涵公式基礎(chǔ)上的。我們把允許用作規(guī)則

53、的公式類型限制為下列形式：L=W 式中：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è)變換過(guò)程首先把這些變量的量詞局部地調(diào)換到前項(xiàng)，然后再把全部存在量詞Skolem化。873.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換舉例說(shuō)明如下： 公式 ( x)( y)( z)P(x,y,z)=( u)Q(x,u可以通過(guò)下列步驟加以變換：

54、 (1) 暫時(shí)消去蘊(yùn)涵符號(hào)( x)( y)( z)P(x,y,z)( u)Q(x,u)(2) 把否定符號(hào)移進(jìn)第一個(gè)析 取式內(nèi)，調(diào)換變量的量詞 ( x)( y)( z) P(x,y,z)( u)Q(x,u)(3) 進(jìn)行Skolem化 ( x)( y)P(x,y,f(x,y)( u)Q(x,u)(4) 把所有全稱量詞移至前面然后消去 P(x,y,f(x,y)Q(x,u)(5) 恢復(fù)蘊(yùn)涵式P(x,y,f(x,y)=Q(x,u) 上述變換的動(dòng)態(tài)演示如下： 883.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換以下用一個(gè)自由變量的命題演算情況來(lái)說(shuō)明如何把這類規(guī)則應(yīng)用于與或圖。 把形式

55、為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 =(XY)Z應(yīng)用到圖3.16所示的與或圖中標(biāo)有S的葉節(jié)點(diǎn)上。所得到的新與或圖結(jié)構(gòu)表示于圖3.17，圖中標(biāo)記S的兩個(gè)節(jié)點(diǎn)由一條叫做匹配弧的弧線連接起來(lái)。 應(yīng)用一條規(guī)則得到的與或圖3.17 不含變量的與或圖 3.16893.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換 在應(yīng)用某條規(guī)則之前，一個(gè)與或圖(如圖3.16)表示一個(gè)具體的事實(shí)表達(dá)式。其中，在葉節(jié)點(diǎn)結(jié)束的一組解圖

56、表示該事實(shí)表達(dá)式的子句形。我們希望在應(yīng)用規(guī)則之后得到的圖，既能表示原始事實(shí)，又能表示從原始事實(shí)和該規(guī)則推出的事實(shí)表達(dá)式。 假設(shè)我們有一條規(guī)則L=W，根據(jù)此規(guī)則及事實(shí)表達(dá)式F(L)，可以推出表達(dá)式F(W)。F(W)是用W代替F中的所有L而得到的。當(dāng)用規(guī)則L= W來(lái)變換以上述方式描述的F(L)的與或圖表示時(shí)，我們就產(chǎn)生一個(gè)含有F(W)表示的新圖；也就是說(shuō)，它是以葉節(jié)點(diǎn)終止的解圖集以F(W)子句形式代表該子句集。這個(gè)子句集包括在F(L)的子句形和L=W的子句形間對(duì)L進(jìn)行所有可能的消解而得到的整集。903.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換再討論圖3.17的情況。規(guī)則S

57、=(XY)Z的子句形是： SXZ, SYZ (PQ)RS(TU)的子句形解圖集為:PQS , RS, PQTU, RTU應(yīng)用兩個(gè)規(guī)則子句中任一個(gè)對(duì)上述子句形中的S進(jìn)行消解： 于是我們得到4個(gè)子 句對(duì)S進(jìn)行消解的消解式的完備集為：XZPQ , YZPQ , RXZ , RYZ這些消解式全部包含在圖3.17的解圖所表示的子句之中。 913.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)3.與或圖的F規(guī)則變換923.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)4.作為終止條件的目標(biāo)公式應(yīng)用F規(guī)則的目的在于從某個(gè)事實(shí)公式和某個(gè)規(guī)則集出發(fā)來(lái)證明某個(gè)目標(biāo)公式。在正向推理系統(tǒng)中，這種目標(biāo)表達(dá)式只限于可證明的表

58、達(dá)式，尤其是可證明的文字析取形的目標(biāo)公式表達(dá)式。 我們用文字集表示此目標(biāo)公式，并設(shè)該集各元都為析取關(guān)系。(在以后各節(jié)所要討論的逆向系統(tǒng)和雙向系統(tǒng)，都不對(duì)目標(biāo)表達(dá)式作此限制。)目標(biāo)文字和規(guī)則可用來(lái)對(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)子句的一部分的子句。 933.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)4.作為

59、終止條件的目標(biāo)公式圖3.18給出一個(gè)滿足以目標(biāo)公式(CG)為基礎(chǔ)的終止條件的與或圖，可把它解釋為用一個(gè)“以事實(shí)來(lái)推理”的策略對(duì)目標(biāo)表達(dá)式(CG)的一個(gè)證明。最初的事實(shí)表達(dá)式為(AB)。由于不知道A或B哪個(gè)為真，因此我們可以試著首先假定A為真，然后再假定B為真，分別地進(jìn)行證明。如果兩個(gè)證明都成功，那么我們就得到根據(jù)析取式(AB)的一個(gè)證明。而A或B到底哪個(gè)為真都無(wú)關(guān)緊要。圖3.18中標(biāo)有(AB)的節(jié)點(diǎn)，其兩個(gè)后裔由一個(gè)2線連接符來(lái)連接。因而這兩個(gè)后裔都必須出現(xiàn)在最后解圖中，如果對(duì)節(jié)點(diǎn)n的一個(gè)解圖通過(guò)k線連接符包含n的任一后裔，那么此解圖必須包含通過(guò)這個(gè)k線連接符的所有k個(gè)后裔。對(duì)應(yīng)動(dòng)畫圖示： 9

60、43.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)4.作為終止條件的目標(biāo)公式滿足中終止條件的與或圖3.18 例子證明過(guò)程如下：把規(guī)則化為子句形，得子句集： AC，AD BE，BG 目標(biāo)的否定為: (CG) 其子句形為: C，G 953.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)用消解反演來(lái)證明目標(biāo)公式，對(duì)應(yīng)動(dòng)畫圖示： 例子證明過(guò)程如下：把規(guī)則化為子句形，得子句集： AC，AD BE，BG 目標(biāo)的否定為: (CG) 其子句形為: C，G 我們推得一個(gè)空子句NIL，從而使目標(biāo)公式(CG)得到證明。用消解反演求證目標(biāo)公式的圖解 963.5 規(guī)則演繹系統(tǒng) 3.5.1規(guī)則正向演繹系統(tǒng)用消解反演來(lái)證明目