搜索策略與歸結(jié)原理

1、1,第三講 搜索策略與歸結(jié)原理,2,3.1 圖搜索策略1、基本概念 搜索是人工智能研究領(lǐng)域中基本問(wèn)題之一，在過(guò)去幾十年，人們已對(duì)搜索技術(shù)進(jìn)行了大量研究，取得了一定的成果。 搜索：根據(jù)問(wèn)題的實(shí)際情況不斷尋找可用的知識(shí)，從而構(gòu)造一條代價(jià)較少的推理方法，使問(wèn)題得到圓滿(mǎn)解決的過(guò)程稱(chēng)為搜索。搜索技術(shù)分為盲目搜索和啟發(fā)式搜索。,3,2、圖搜索策略(1) 定義：圖搜索策略可以看作一種在圖中尋找路徑的方法。初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)分

2、別代表初始數(shù)據(jù)庫(kù)和滿(mǎn)足條件的終止數(shù)據(jù)庫(kù)。求將一個(gè)數(shù)據(jù)庫(kù)變換成另一個(gè)數(shù)據(jù)庫(kù)的規(guī)則序列問(wèn)題就等價(jià)于求得圖中的一條路徑問(wèn)題。(2) 圖搜索(Graph Search)的一般過(guò)程　①建立一個(gè)只含有起始節(jié)點(diǎn)S的搜索圖G，把S放到一個(gè)叫做OPEN的未擴(kuò)展節(jié)點(diǎn)表中?！、?建立一個(gè)叫做CLOSED的已擴(kuò)展節(jié)點(diǎn)表，其初始為空表。,4,③ LOOP：若OPEN表是空表，則失敗退出。④ 選擇OPEN表上的第一個(gè)節(jié)點(diǎn)，把它從OPEN表移出并放進(jìn)CLOS

3、ED表中。稱(chēng)此節(jié)點(diǎn)為節(jié)點(diǎn)n。⑤ 若n為一目標(biāo)節(jié)點(diǎn)，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針第7步設(shè)置)。⑥ 擴(kuò)展節(jié)點(diǎn)n，同時(shí)生成不是n的祖先的那些后繼節(jié)點(diǎn)的集合M。把M的這些成員作為n的后繼節(jié)點(diǎn)添入圖G中。⑦ 對(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成員，確定是否需

4、要更改通到n的指針?lè)较?。?duì)已在CLOSED表上的每個(gè)M成員，確定是否需要更改圖G中通向它的每個(gè)后裔節(jié)點(diǎn)的指針?lè)较?。?按某一任意方式或按某個(gè)探試值，重排OPEN表。⑨ GO LOOP。,5,開(kāi)始,把S放入Open表,Open為空表？,失敗,把第一個(gè)節(jié)點(diǎn)(n)從Open表移到Closed表,n為目標(biāo)節(jié)點(diǎn)？,成功,把n的后繼節(jié)點(diǎn)n放入Open表的末端,提供返回節(jié)點(diǎn)n的指針,修改指針?lè)较?重排Open表,,,,,,,,,,,,,是,是,

5、否,否,,6,(3)圖搜索方法的分析圖搜索過(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í)，這一過(guò)程就宣告成功結(jié)束。這時(shí)，能夠重現(xiàn)從起始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的這條成功路徑，其辦法是從目標(biāo)節(jié)點(diǎn)按指針向S返回追溯。當(dāng)搜索樹(shù)不再剩有未被擴(kuò)展的端結(jié)點(diǎn)時(shí)，過(guò)程就

6、以失敗告終(某些節(jié)點(diǎn)最終可能沒(méi)有后繼節(jié)點(diǎn)，所以O(shè)PEN表可能最后變成空表)。在失敗終止的情況下，從起始節(jié)點(diǎn)出發(fā)，一定達(dá)不到目標(biāo)結(jié)點(diǎn)。,7,3.2 盲目搜索策略主要介紹兩種典型的盲目搜索技術(shù)，即廣度優(yōu)先搜索技術(shù)和深度優(yōu)先搜索技術(shù)。一、基于狀態(tài)空間知識(shí)描述的一般搜索過(guò)程1、問(wèn)題 一個(gè)復(fù)雜問(wèn)題的狀態(tài)空間一般都是十分龐大的。例如64階樊塔問(wèn)題（園片的數(shù)目稱(chēng)為梵塔問(wèn)題的階），共有364=0.94×1030個(gè)不同的狀態(tài)，若把它們都

7、存到計(jì)算機(jī)中去，需占據(jù)大量的存儲(chǔ)空間，并且很難實(shí)現(xiàn)。另外把所有的狀態(tài)都存到計(jì)算機(jī)中也是不必要的，因?yàn)榕c問(wèn)題的解相關(guān)的狀態(tài)可能只是其中的一部分。但是，對(duì)于一個(gè)問(wèn)題，如何生成它所需的那部分狀態(tài)從而實(shí)現(xiàn)對(duì)問(wèn),8,題進(jìn)行求解呢？通過(guò)搜索技術(shù)可解決這一問(wèn)題。2、對(duì)Open表和Closed表數(shù)據(jù)結(jié)構(gòu)進(jìn)行說(shuō)明Open表用來(lái)存放剛剛生成的節(jié)點(diǎn)。對(duì)不同的搜索策略，節(jié)點(diǎn)在Open表中的排列順序是不同的。Closed表用來(lái)存放將要擴(kuò)展和已經(jīng)擴(kuò)展的節(jié)點(diǎn)。所

8、謂對(duì)一個(gè)節(jié)點(diǎn)的擴(kuò)展是指：用合適的算符對(duì)該節(jié)點(diǎn)進(jìn)行操作，生稱(chēng)一組子節(jié)點(diǎn)。,Open表,Closed表,9,3、搜索的一般過(guò)程(1)把初始節(jié)點(diǎn)S0放入Open表中，并建立目前只包含S0的圖，記為G。(2)檢查Open表是否為空，若為空則問(wèn)題無(wú)解，退出。(3)把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。(5)擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把其中不是節(jié)點(diǎn)

9、n先輩的那些子節(jié)點(diǎn)記作集合M，并把這些子節(jié)點(diǎn)作為n的子節(jié)點(diǎn)加入G中,10,(6)針對(duì)M中子節(jié)點(diǎn)的不同情況，分別進(jìn)行如下處理：①對(duì)于那些未曾在G中出現(xiàn)過(guò)的M成員，設(shè)置一個(gè)指向父節(jié)點(diǎn)(即節(jié)點(diǎn)n)的指針，并把它們放入Open②對(duì)于那些先前已在G中出現(xiàn)過(guò)的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父親節(jié)點(diǎn)的指針。③對(duì)于那些先前已在G中出現(xiàn)并且已經(jīng)擴(kuò)展了的M成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。(7)按某種搜索策略對(duì)Open表中的

10、節(jié)點(diǎn)進(jìn)行排序。(8)轉(zhuǎn)到第(2)步。,11,二、廣度優(yōu)先搜索廣度優(yōu)先搜索又稱(chēng)寬度優(yōu)先搜索。1、基本思想 從初始節(jié)點(diǎn)S0開(kāi)始，逐層地對(duì)節(jié)點(diǎn)進(jìn)行擴(kuò)展并考察它是否為目標(biāo)節(jié)點(diǎn)，在第n曾的節(jié)點(diǎn)沒(méi)有全部擴(kuò)展并考察前，不對(duì)第n+1層的節(jié)點(diǎn)進(jìn)行擴(kuò)展。Open表中的節(jié)點(diǎn)總是按進(jìn)入的先后順序排列，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的排在后面。具體搜索過(guò)程如下：(1)把初始節(jié)點(diǎn)S0放入Open表中。(2)如果Open表為空，則問(wèn)題無(wú)解，退出。,12

11、,(3)把Open表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入Closed表。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)向第(2)步。(6)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第(2)步。該過(guò)程的流程圖如下：,13,開(kāi)始,把S0送入Open表,Open空？,失敗,退出,把Open表的第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從表中移出,放入Closed表,節(jié)

12、點(diǎn)n為目標(biāo)節(jié)？,節(jié)點(diǎn)n可擴(kuò)展？,擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的尾部，并為每子字節(jié)點(diǎn)配置指向節(jié)點(diǎn)n的指針,,,,,,,,,,,,成功,退出,,,Y,N,N,Y,Y,N,14,例題 重排九宮問(wèn)題。在3×3的方格棋盤(pán)上放置分別標(biāo)有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)為S0，目標(biāo)狀態(tài)為Sg ，如圖所示。可使用的操作符有：空格左移、空格上移、空格右移、空格下移。利用廣度優(yōu)先可得到如圖所示的搜索樹(shù)。,8

13、3 47 6 5,S0,1 2 38 47 6 5,Sg,15,2 8 31 47 6 5,S0,1,2 8 3 1 47 6 5,2,2 31 8 47 6 5,3,2 8 31 4 7 6 5,4,2 8 31 6 47

14、 5,5,8 32 1 47 6 5,6,7,2 8 37 1 4 6 5,2 31 8 47 6 5,8,9,2 3 1 8 47 6 5,2 8 1 4 37 6 5,10,11,2 8 31 4 57 6,2 8 31 6 4

15、 7 5,12,13,2 8 31 6 4 7 5,8 32 1 47 6 5,14,15,2 8 37 1 46 5,1 2 3 8 47 6 5,16,17,2 3 4 1 8 7 6 5,2 8 1 4 37 6 5,18,19,

16、2 8 31 4 57 6,2 8 3 6 41 7 5,20,21,2 8 31 6 7 5 4,8 3 2 1 47 6 5,22,23,8 1 32 47 6 5,2 8 37 46 1 5,24,25,2 8 37

17、 1 46 5,1 2 3 8 4 7 6 5,26,Sg,,,,,,,,,,,,,,,,,,,,,,,,,,16,由上圖可以看出，解的路徑是： (S0) 1→3 →8 →16 →26 (Sg) 缺點(diǎn)：盲目性大，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低；但是其優(yōu)點(diǎn)為，只要有解，總能找到，而且得到的節(jié)一定是最短路徑解。三、深度優(yōu)先搜索1、基本思想 從

18、初始節(jié)點(diǎn)S0開(kāi)始，在其子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，若不是目標(biāo)節(jié)點(diǎn)，則再在該子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)進(jìn)行考察，一直繼續(xù)下去。當(dāng)?shù)竭_(dá)某個(gè)子節(jié)點(diǎn)，且該子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。具體搜索過(guò)程如下：,17,2、搜索過(guò)程(1)把初始節(jié)點(diǎn)S0放入Open表中。(2)如果Open表為空，則問(wèn)題無(wú)解，退出。(3)把Open表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入Closed表。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)

19、點(diǎn)。若是，則求得了問(wèn)題的解，退出。(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)向第(2)步。(6)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入Open表的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)指針，然后轉(zhuǎn)第(2)步。,18,例如：對(duì)前例重排九宮圖問(wèn)題進(jìn)行深度優(yōu)先搜索，可得到如下所示的搜索樹(shù)（部分）。,2 8 31 47 6 5,S0,1,2 8 3 1 47 6 5,2,2 31

20、 8 47 6 5,3,2 8 31 4 7 6 5,4,2 8 31 6 47 5,5,2 8 31 6 4 7 5,2 8 31 6 4 7 5,2 8 31 6 7 5 4,,,,,,,,2 8 31 6 7 5 4,2

21、8 1 6 3 7 5 4,2 81 6 3 7 5 4,6,,,,,19,說(shuō)明：在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可很快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無(wú)窮分支，則就不可能得到解。所以，深度優(yōu)先搜索不是完備的，即使問(wèn)題有解，也不一定能得到解；另外，所求得的解也不一定是最短路徑解。3.

22、3 啟發(fā)式搜索盲目搜索策略具有較大的盲目性，產(chǎn)生的無(wú)用節(jié)點(diǎn)較多，搜索空間較大，效率不高。而啟發(fā)式搜索要用到問(wèn)題本身的某些特性信息，以指導(dǎo)搜索朝著有希望的方向前進(jìn)。,20,一、啟發(fā)性信息和估價(jià)函數(shù)1、啟發(fā)信息搜索過(guò)程的關(guān)鍵是如何確定下一個(gè)要考察的節(jié)點(diǎn)，確定下一個(gè)節(jié)點(diǎn)的方法不同，就產(chǎn)生了不同的搜索策略。在確定下一個(gè)節(jié)點(diǎn)時(shí)，如果能夠充分利用與問(wèn)題求解相關(guān)的特性信息，估計(jì)出下一個(gè)節(jié)點(diǎn)的重要性，就能在選擇下一個(gè)節(jié)點(diǎn)時(shí)，選擇重要性較高的節(jié)點(diǎn)

23、，以利于求得最優(yōu)的解。這些與求解問(wèn)題有關(guān)的特性信息就稱(chēng)為啟發(fā)信息。,21,2、估價(jià)函數(shù)估價(jià)一個(gè)節(jié)點(diǎn)重要性的函數(shù)稱(chēng)為估價(jià)函數(shù)： f(x)=g(x)+h(x)其中g(shù)(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x已經(jīng)實(shí)際付出的代價(jià)；h(x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的估計(jì)代價(jià)，它體現(xiàn)了對(duì)問(wèn)題求解的啟發(fā)性，其函數(shù)形式主要根據(jù)問(wèn)題而定。h(x)稱(chēng)為啟發(fā)函數(shù)，它可以是節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的距離，也可以是節(jié)點(diǎn)x處于最優(yōu)路徑上的概

24、率等。f(x)可以用來(lái)估價(jià)Open表中各節(jié)點(diǎn)的重要程度，決定各節(jié)點(diǎn)在Open表中的次序。,22,g(x)描述了搜索的橫向趨勢(shì)，它有利于提高搜索的完備性，但影響搜索的效率。二、局部擇優(yōu)搜索1、基本思想局部擇優(yōu)搜索是對(duì)深度優(yōu)先搜索方法的一種改進(jìn)的啟發(fā)式搜索方法?；舅枷耄寒?dāng)一個(gè)節(jié)點(diǎn)被擴(kuò)展后，按f(x)對(duì)每個(gè)子節(jié)點(diǎn)計(jì)算估價(jià)值，并選擇最小者作為下一個(gè)要考察的節(jié)點(diǎn)，由于它每次都只是在子節(jié)點(diǎn)的范圍內(nèi)選擇下一個(gè)要考察的節(jié)點(diǎn)，范圍較窄，因此被

25、稱(chēng)為局部擇優(yōu)搜索,,,,23,2、局部擇優(yōu)搜索算法(1)把初始節(jié)點(diǎn)S0放入Open表中，計(jì)算f(S0)(2)如果Open表為空，則問(wèn)題無(wú)解，退出。(3) 把Open表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入Closed表。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得了問(wèn)題的解，退出。(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)地(2)步。(6)擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并按估價(jià)值從小到大的順序依次放到Open表的首部,

26、設(shè)置指向父節(jié)點(diǎn)的指針,24,開(kāi)始,把S0送入Open表，計(jì)算f(S0),Open為空？,失敗，退出,把Open表的第一個(gè)節(jié)點(diǎn)(節(jié)點(diǎn)n)從表中移出，放入Closed表,節(jié)點(diǎn)n可擴(kuò)展？,成功，退出,節(jié)點(diǎn)n為目標(biāo)節(jié)點(diǎn)？,擴(kuò)展節(jié)點(diǎn)n,計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值,并按估價(jià)值從小到大的順序放入Open表的首部,設(shè)置指向父節(jié)點(diǎn)指針,,,,,,,,,,,,,Y,N,N,N,Y,Y,25,三、全局擇優(yōu)搜索擇優(yōu)策略：每次都是從整個(gè)Open表的全體節(jié)點(diǎn)中選

27、擇一個(gè)估價(jià)值最小的節(jié)點(diǎn)。搜索過(guò)程為：(1)把初始節(jié)點(diǎn)S0放入Open表中，計(jì)算f(S0)(2)如果Open表為空，則問(wèn)題無(wú)解，退出。(3) 把Open表的第一個(gè)節(jié)點(diǎn)(記為節(jié)點(diǎn)n)取出放入Closed表。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)，若是，則求得了問(wèn)題的解，退出。,26,(5)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)地(2)步。(6)擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并為每個(gè)子節(jié)點(diǎn)配置指向父節(jié)點(diǎn)的指針，把這些節(jié)點(diǎn)送入Open

28、表中，然后對(duì)Open表的全部節(jié)點(diǎn)按估價(jià)值從小到大的順序進(jìn)行排序。(7)轉(zhuǎn)第(2)步。說(shuō)明：在啟發(fā)式搜索中，估價(jià)函數(shù)的定義是十分重要的，如定義不當(dāng)，則上述搜索算法不一定能找到問(wèn)題的解，即使找到了解，也不一定是最優(yōu)的，因此需要對(duì)估價(jià)函數(shù)進(jìn)行限制，其中A*算法就是其中的一種。,27,3.4 A*算法在3.2節(jié)描述的一般搜索過(guò)程，如果滿(mǎn)足如下條件，它就被稱(chēng)為A*算法 ：(1) 把Open表中的節(jié)點(diǎn)按估價(jià)函數(shù) f(x

29、)=g(x)+h(x) 的值從小到大進(jìn)行排序(一般搜索過(guò)程第7步)(2)g(x)是對(duì)g*(x)的估計(jì),g(x)>0(3)h(x)是h* (x)的下界，即對(duì)于所有的x均有： h(x)<= h* (x)其中g(shù)*(x)是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的最小代價(jià)； h* (x)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，若為多個(gè)目標(biāo)則為其中最小的一個(gè)。,28,說(shuō)明：在該算法中，g(x)是比較容易得到的，

30、它實(shí)際上就是從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)x的路徑代價(jià)，且恒有g(shù)(x)>=g*(x)，而且在算法的執(zhí)行過(guò)程中，隨著更多搜索信息的獲得，g(x)呈下降趨勢(shì)。,S0,X1,X2,X3,,,,,7,3,3,2,29,h(x)的確定依賴(lài)于具體的問(wèn)題，其中h(x)<=h*(x)的限制是十分重要的，它保證A*算法能找到最優(yōu)解。 定義 算法是可納的：對(duì)于一個(gè)可解的狀態(tài)空間圖，如果一個(gè)搜索算法能在有限步內(nèi)終止，并且能找到最優(yōu)解，則該搜索算法是可納的

31、。A *算法的性質(zhì)：1、算法是可納的。證明略2、算法是最優(yōu)的。該算法的搜索效率在很大程度上取決于h(x)，在滿(mǎn)足h(x)<=h*(x)的前提,30,下，h(x)的值愈大愈好。H(x)的值越大，表明他攜帶的啟發(fā)性信息越多，搜索時(shí)擴(kuò)展的節(jié)點(diǎn)數(shù)越少，搜索的效率與高。3、對(duì)h(x) 的單調(diào)性限制在該算法中，每當(dāng)要擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)都要先檢查其子節(jié)點(diǎn)是否已在Open表或Closed表中，有時(shí)還需要調(diào)整指向父節(jié)點(diǎn)的指針，這就增加了搜索的

32、代價(jià)。如果啟發(fā)函數(shù)h(x)被加上單調(diào)性限制，就可以減少檢查和調(diào)整的工作量，從而減少搜索代價(jià)。除此之外，還有關(guān)于針對(duì)與或樹(shù)的搜索策略等。,31,第二部分 歸結(jié)原理,32,前言命題邏輯的歸結(jié)法子句型歸結(jié)原理,33,歸結(jié)（resolution)(也稱(chēng)消解）推理方法：,這是一種機(jī)械化的、可在計(jì)算機(jī)上實(shí)現(xiàn)的推理方法。AI程序設(shè)計(jì)語(yǔ)言Prolog就是基于歸結(jié)原理的一種邏輯程序設(shè)計(jì)語(yǔ)言。,,34,歸結(jié)法（也稱(chēng)消解法）的本質(zhì)是

33、一種反 證法。 為了證明一個(gè)命題A恒真，要證明其反命題~A恒假。所謂恒假就是不存在模型，即在所有的可能解釋中，~A均取假值。但一命題的解釋通常有無(wú)窮多種，不可能一一測(cè)試。為此，Herbrand建議使用一種方法：從眾多的解釋中，選擇一種代表性的解釋?zhuān)?yán)格證明：任何命題，一旦證明為在這種解釋中取假值，即在所有的解釋中取假值，這就是Herbrand解釋。,35,3.5 命題邏輯的歸結(jié)法,

34、要證明： A1∧A2∧A3?B 是定理（重言式） ? A1∧A2∧A3 ∧ ~B 是矛盾(永假)式歸結(jié)推理方法就是從A1∧A2∧A3 ∧ ~B 出發(fā)，使用歸結(jié)推理規(guī)則來(lái)尋找矛盾，最后證明定理成立。歸結(jié)法（消解法）的本質(zhì)是數(shù)學(xué)中的反證法，稱(chēng)為“反演推理方法”。,等價(jià)于,,36,3.5.1 建立子句集,首先，把A1∧A2∧A3 ∧ ~B化成一種稱(chēng)作子句形的標(biāo)準(zhǔn)形式。如： P∧(Q∨R)∧(~P∨

35、~Q)∧(P∨~Q∨R)然后將合取范式寫(xiě)成集合的表示形式，得 S = {P, Q∨R, ~P∨~Q, P∨~Q∨R}, 以“,”代 替“∧”。,,,子句集,,,一個(gè)子句,37,3.5.2 歸結(jié)式,設(shè)C1=P∨C1′ C2=~P∨C2′ 消去互補(bǔ)對(duì)，新子句 R(C1,C2) = C1′∨ C2′沒(méi)有互補(bǔ)對(duì)的兩子句沒(méi)有歸結(jié)式，歸結(jié)推理即對(duì)兩子

36、句做歸結(jié)證明 C1∧C2?R(C1,C2)任一使C1，C2為真的解釋I下必有R(C1,C2)也是真。空子句□當(dāng)C1=P C2=~P兩個(gè)子句的歸結(jié)式為空，記作□，稱(chēng)為空子句，體現(xiàn)了矛盾。,,為兩個(gè)子句,,,子句C1、C2的歸結(jié)式,38,3.5.3歸結(jié)推理過(guò)程,子句集S,歸結(jié)推理規(guī)則,S′＝空子句□,S′=所得歸結(jié)式,說(shuō)明S是不可滿(mǎn)足的,與S對(duì)應(yīng)的定理成立,推理結(jié)束,,,,,,,,,,是,否,39,例

37、：證明(P?Q)∧~Q?~P,先將(P?Q)∧~Q∧~(~P)化成合取范式，得 (~P∨Q)∧~Q∧P建立子句集 S={~P∨Q, ~Q, P)對(duì)S作歸結(jié)~P∨Q~QP~P 1), 2) 歸結(jié)□ 3), 4) 歸結(jié)

38、證畢注：一階謂詞邏輯的歸結(jié)方法比命題邏輯的歸結(jié)法要復(fù)雜得多，原因是要對(duì)量詞和變量做專(zhuān)門(mén)的處理。,40,3.6 子句形,設(shè)有由一階謂詞邏輯描述的公式A1，A2，A3和B，證明在A(yíng)1∧A2∧A3成立的條件下有B成立。仍然采用反演法來(lái)證明。 A1∧A2∧A3∧~B (3.2.1) 是不可滿(mǎn)足的。與命題邏輯不同，首先遇到了量詞問(wèn)題，為此要將(3.2.1)式化成SKOLEM標(biāo)準(zhǔn)形。,,41

39、,3.6.1 SKOLEM標(biāo)準(zhǔn)形（即與或句）,對(duì)給定的一階謂詞邏輯公式G=A1∧A2∧A3∧~B第一步，化成與其等值的前束范式 [方法： “與或句演繹系統(tǒng)”]第二步，化成合取范式第三步，將所有存在量詞（ ? ）消去,,42,補(bǔ)充：與或句演繹系統(tǒng),1、與或句 只有與符號(hào)(?)、或符號(hào)(?)、謂詞(也稱(chēng)原子)和前有非符號(hào)的謂詞(也稱(chēng)負(fù)原子，正負(fù)原子統(tǒng)稱(chēng)句節(jié))以及看不見(jiàn)的全稱(chēng)量詞的合式公式稱(chēng)為與或句。2、與或

40、句的生成步驟 1）化成前束范式，使所有量詞均在合式公式的最前面，且每個(gè)量詞的轄域均是整個(gè)公式。 2）消去存在量詞，只剩下全稱(chēng)量詞。 3、置換規(guī)則 左部只能有一個(gè)句節(jié)，右部可以是任意的與或句。 注：與或句演繹系統(tǒng)可以用于求證某個(gè)目標(biāo)推理，也可以進(jìn)行反向推理。當(dāng)用作反向推理時(shí)，比較實(shí)用。,43,3.6.2子句與子句集,概念原子公式：不含有任何聯(lián)結(jié)詞的謂詞公式文字：原子或原子的否定子句：一些文字的

41、析取如，P(x) ∨~Q(x,y), ~P(x,c) ∨R(x,y,f(x))都是子句由于G的SKOLEM標(biāo)準(zhǔn)形的母式已為合取范式，從而母式的每一個(gè)合取項(xiàng)都是一個(gè)子句，可以說(shuō)，母式是由一些子句的合取組成的。子句集S：將G的已消去存在量詞的SKOLEM標(biāo)準(zhǔn)形，再略去全稱(chēng)量詞，最后以“,”代替合取符號(hào)“∧”，便得子句集S。,44,例：,解：①將G化成SKOLEM標(biāo)準(zhǔn)形G的子句集子句集S中的變量，都認(rèn)為是由全稱(chēng)量詞約束著

42、，子句間是合取關(guān)系。,45,第一類(lèi)：代數(shù)、幾何證明（定理證明）例1.證明梯形的對(duì)角線(xiàn)與上下底構(gòu)成的內(nèi)錯(cuò)角相等,3.6.3 建立子句集舉例,46,證明：①設(shè)梯形的頂點(diǎn)依次為a,b,c,d.引入謂詞：T(x,y,u,v)表示以xy為上底，uv為下底的梯形P(x,y,u,v)表示xy//uvE(x,y,z,u,v,w)表示∠x(chóng)yz = ∠uvw②問(wèn)題的邏輯描述和相應(yīng)的子句集為梯形上下底平行：平形內(nèi)錯(cuò)角相等已

43、知條件要證明的結(jié)論：B: E(a,b,d,c,d,b) 結(jié)論的“非”：S~B:~E(a,b,d,c,d,b)}從而 S = {SA1, SA2, SA3, S~B },47,第二類(lèi) 機(jī)器人動(dòng)作問(wèn)題,例2.猴子香蕉問(wèn)題已知一串香蕉掛在天花板上，猴子直接去拿是夠不到的，但猴子可以走動(dòng)，也可以爬上梯子來(lái)達(dá)到吃香蕉的目的。,分析：?jiǎn)栴}描述，不能忽視動(dòng)作的先后次序，體現(xiàn)時(shí)間概念。常用方法是引入狀態(tài)S來(lái)區(qū)分動(dòng)作的先后

44、，以不同的狀態(tài)表現(xiàn)不同的時(shí)間，而狀態(tài)間的轉(zhuǎn)換由一些算子（函數(shù)）來(lái)實(shí)現(xiàn)。,初始狀態(tài)S0,48,解：引入謂詞P(x,y,z,s): 表示猴子位于x處，香蕉位于y處，梯子位于z處，狀態(tài)為sR(s): 表示s狀態(tài)下猴子吃到香蕉ANS(s): 表示形式謂詞，只是為求得回答的動(dòng)作序列而虛設(shè)的。引入狀態(tài)轉(zhuǎn)移函數(shù)Walk(y, z, s): 表示原狀態(tài)s下，在walk作用下，猴子從y走到z處所建立的新?tīng)顟B(tài)。Carry(y,z,s): 表示

45、原狀態(tài)s下，在Carry作用下，猴子從y搬梯子到z處所建立的新?tīng)顟B(tài)。Climb(s): 表示原狀態(tài)s下，在Climb作用下，猴子爬上梯子所建立的新?tīng)顟B(tài)。,49,初始狀態(tài)為S0，猴子位于a，香蕉位于b,梯子位于c，問(wèn)題描述如下：猴子走到梯子處（從x ? z）猴子搬著梯子到y(tǒng)處猴子爬上梯子吃到香蕉初始條件結(jié)論,walk,50,3.7 歸結(jié)原理,1965年，Robinson提出了歸結(jié)原理，是對(duì)自動(dòng)推理的重大

46、突破。,,51,3.7.1 置換與合一,置換：是形為{t1/v1,…,tn/vn}的一個(gè)有限集。其中，vi是變量，而ti是不同于vi的項(xiàng)（常量、變量、函數(shù)）且vi≠vj，（i≠j),i,j=1,2,…,n例如，{a/x,b/y,f(x)/z},{f(z)/x,y/z}都是置換?？罩脫Q?：不含任何元素的置換。令置換?={t1/v1,t2/v2,…,tn/vn} E是一階謂詞① ?作用于E，就是將E中出現(xiàn)的變量vi均以ti代

47、入（i=1,2,…,n)，以E?表示結(jié)果，并稱(chēng)為E的一個(gè)例。② ?作用于項(xiàng)t，是將t中出現(xiàn)的變量vi以ti代入(i=1,…,n)，結(jié)果以t·?表示。,52,例：?={a/x, f(b)/y, u/z} E=P(x, y, z) t = g(x, y)那么 E? = P(a, f(b), u) t?=g(a, f(b)),53,常使用的置換的運(yùn)算是置換乘法（合成）若 ?=

48、{t1/x1,…,tn/xn} ?={u1/y1,…,um/ym}置換乘積?·?是新的置換，作用于E相當(dāng)于先?后?對(duì)E的作用。定義如下：先作置換：{t1 ·? /x1 ,…, tn ·? /xn , u1 /y1,…,um/ym }若yi?{x1,…, xn}時(shí)，先從中刪除ui/yi；ti·? = xi時(shí)，再?gòu)闹袆h除ti ·?/ xi；所設(shè)的置換稱(chēng)作?與?的乘積，記

49、作?·?,54,例： ?={f(y)/x, z/y} ?={a/x, b/y, y/z} 求?·?解：先做置換 {f(y)·?/x, z·?/y, a/x, b/y, y/z} 即 {f(b)/x, y/y, a/x, b/y, y/z} 先刪除a/x,b/y,再刪y/y，得 ?·? = {f(b)/x,y/z} 當(dāng) E

50、= P(x,y,z)時(shí)， E? = P(f(y), z, z), (E?)? = P(f(b), y, y) E(?·?) = P(f(b), y, y),,(E?)? = E(?·?),55,概念：合一,設(shè)有公式集{E1,…,Ek}和置換?，使E1 ? = E2 ?=…Ek ?稱(chēng)E1,…,Ek是可合一的，且?稱(chēng)為合一置換（union replacement）。若E1,

51、…,Ek有合一置換?，且對(duì)E1,…,Ek的任一合一置換?都有置換?存在，使得?= ?·?便說(shuō)?是E1,…,Ek的最一般置換，記作mgu（most general unification),56,例1 E1=P(a,y),E2=P(x,f(b)),E1,E2可合一， ?={a/x, f(b)/y},且?是E1，E2的mgu.例2 E1=P(x), E2=P(f(y))置換?={f(a)/x, a/y}并不是E1、 E2

52、的mgu，而?= {f(y)/x}才是E1、 E2的mgu，也可以說(shuō)，是E1、 E2的最簡(jiǎn)單合一置換。,57,例3 E1=P(x), E2=P(y)。顯然{y/x}和{x/y}都是E1 、E2的mgu，說(shuō)明mgu不唯一。,58,求mgu的算法（最一般合一置換mgu),令w={E1,E2}。令k=0,w0=w,?0=?(空置換）。如果wk已合一，停止，?k=mgu。否則找不一致集Dk 。若Dk中存在元素vk,tk,其中vk不出現(xiàn)

53、于tk中做 5 ，否則不可合一。令?k+1= ?k·{tk/vk}wk+1=wk{tk/vk} = w?k+1。k+1?k 轉(zhuǎn) 3。,59,例 w={P(a,x,f(g(y))),P(z,f(a),f(u))}其中，E1=P(a,x,f(g(y))),E2=P(z,f(a),f(u))求 E1,E2的mug解：(1) w={P(a,x,f(g(y))),P(z,f(a),f(u))}. (2) ?0

54、=?,w0=w. (3) w0未合一，自左至右找不一致集，有D0={a,z}. (4)取v0=z,t0=a. (5)令?1= ?0·{t0/v0}= ?· {a/z} = {a/z}. w1=w0?1={P(a,x,f(g(y))),P(a,f(a),f(u))}. (3) ′w1未合一，不一致集D1={x,f(a)}.

55、 (4) ′取v1=x,t1=f(a). (5) ′令?2= ?1·{f(a)/x}={a·?/z,f(a)/x}={a.z,f(a)/x} w2=w1?2={P(a),f(a),f(g(y)),p(a,f(a),f(u))}.,60,(3) ′w2未合一，不一致集D2 = {g(y),u}.(4) ′取v2 = u,t2=g(y).(5) ′令?3= ?2&

56、#183;{g(y)/u} = {a/z,f(a)/x}·{g(y)/u} = { a/z,f(a)/x,g(y)/u} . w3 = w2?3={P(a),f(a),f(g(y)),P(a),f(a),f(g(y)))}(3) ′w3已合一，這時(shí)?3={a/z,f(a)/x,g(y)/u} ，即為E1，E2的mgu.注：不可合一的情況

57、 ①不存在vk變量，如w={P(a,b,c),P(d,b,c)} ②不存在tk變量，如w={P(a,b),P(x,y,z)}③出現(xiàn)不一致集為{x,f(x)}形,′,′,′,′,′,61,3.7.2 歸結(jié)式,在謂詞邏輯下求兩個(gè)子句的歸結(jié)式，和命題邏輯一樣是消去互補(bǔ)對(duì)，但需考慮變量的合一和置換。二元?dú)w結(jié)式：設(shè)C1, C2是兩個(gè)無(wú)公共 變量的子句， L1, L2分別是C1, C2的文字，若L1與~ L

58、2有mgu ?，則(C1 ? - {L1 ?}) ? (C2 ? - {L2 ?})稱(chēng)作子句C1, C2的一個(gè)二元?dú)w結(jié)式，而L1, L2為被歸結(jié)的文字?！咀⒁狻浚和}邏輯下的歸結(jié)式不同的是，先需對(duì)C1, C2有關(guān)變量作mgu，再消去互補(bǔ)對(duì)。同樣有： C1 ? C2 ? R(C1, C2),62,補(bǔ)充：歸結(jié)式的定義　　設(shè)         &#

59、160;           　　為兩個(gè)子句。有互補(bǔ)對(duì)L和~ L?！　t 新子句                 　　稱(chēng)作C1、C2的歸結(jié)式?！　w

60、結(jié)過(guò)程就是對(duì)S的子句求歸結(jié)式的過(guò)程。,63,例1 C1 = ~A(x) ? B(x) C2 = A(g(x))【解】：先將C1的變量x改寫(xiě)為y，可得mgu = {g(x)/y}，作歸結(jié)得R(C1, C2) = B(g(x))。例2 C1 = P(x) ? Q(x) C2 = ~P(g(y)) ? ~Q(b) ? R(x)【解】：可知有兩個(gè)合一置換，故有兩個(gè)二元?dú)w結(jié)式。（1）當(dāng)

61、取 ? = {g(y)/x}時(shí)，得R(C1, C2) = Q(g(y)) ? ~Q(b) ? R(x)（2）當(dāng)取 ? = {b/x}時(shí)，得R(C1, C2) = P(b) ? ~P(g(y)) ? R(x),64,例3 C1 = P(x) ? ~Q(b) C2 = ~P(a) ? Q(y) ? R(z)【解】：這時(shí)要注意，求歸結(jié)式不能同時(shí)消去兩個(gè)互補(bǔ)對(duì)。如在 ? = {a/x, b/y}下，得R(z)

62、。這不是C1, C2的二元?dú)w結(jié)式。最簡(jiǎn)單的例子是：C1 = P ? Q， C2 = ~P ? ～Q若消去上述兩個(gè)互補(bǔ)對(duì)便得空子句。但是C1, C2并無(wú)矛盾。這說(shuō)明消去兩個(gè)互補(bǔ)對(duì)的結(jié)果并不是C1, C2的邏輯推論了。因此，消去兩個(gè)互補(bǔ)對(duì)結(jié)果不是二元?dú)w結(jié)式。,65,在對(duì)子句作歸結(jié)前，可先考慮子句內(nèi)部的化簡(jiǎn)，這便提出了子句因子的概念。設(shè) C = P(x) ? P(f(y)) ? ~Q(x)令 ?

63、 = {f(y)/x}，將置換?使用于C，可使P(x), P(f(y))合一。顯然C?比C簡(jiǎn)單得多。子句因子：若一個(gè)子句C的幾個(gè)文字有mgu ?，那么C的C?稱(chēng)作子句C的因子。定義：若C1, C2是無(wú)公共變量的子句，作（1） C1, C2的二元?dú)w結(jié)式（2） C1的因子和C2的二元?dú)w結(jié)式（3） C1,和C2的因子的二元?dú)w結(jié)式（4） C1的因子和C2的因子的二元?dú)w結(jié)式這四種二元?dú)w結(jié)式都叫子句C1, C2的歸結(jié)式，記作R(C1,

64、 C2),66,例4 C1 = P(x) ? P(f(y)) ? Q(g(y)) C2 = ~P(f(g(a))) ? Q(b)【解】：先作C1的因子，取 ? = {f(y)/x}，得C1的因子C1? = P(f(y)) ? Q(g(y)) 于是C1, C2歸結(jié)式為R(C1, C2) = Q(g(g(a))) ? Q(b)【說(shuō)明】：上述推理過(guò)程的正確性能得到保證。,67,3.7.3 歸結(jié)推理過(guò)程

65、,為證明A?B成立，其中A, B是謂詞公式，使用反演過(guò)程，先建立G = A ? ~B 進(jìn)而做出相應(yīng)的子句集S，只需證明S是不可滿(mǎn)足的。 歸結(jié)法是僅有一條推理規(guī)則的推理方法。對(duì)S中的可歸結(jié)的子句作歸結(jié)，求得歸結(jié)式，并將這歸結(jié)式（新子句）仍放入S中，反復(fù)進(jìn)行這個(gè)歸結(jié)過(guò)程直至產(chǎn)生空子句為止。這時(shí)S必是不可滿(mǎn)足的，從而證明A?B是成立的?！咀⒁狻浚簹w結(jié)推理的實(shí)例請(qǐng)?jiān)斠?jiàn)石純一等編著的《人工智能原理》pp48-5