搜索策略與歸結原理

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

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

3、ED表中。稱此節(jié)點為節(jié)點n。⑤ 若n為一目標節(jié)點，則有解并成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的(指針第7步設置)。⑥ 擴展節(jié)點n，同時生成不是n的祖先的那些后繼節(jié)點的集合M。把M的這些成員作為n的后繼節(jié)點添入圖G中。⑦ 對那些未曾在G中出現(xiàn)過的(既未曾在OPEN表上或CLOSED表上出現(xiàn)過的)M成員設置一個通向n的指針。把M的這些成員加進OPEN表。對已經在OPEN或CLOSED表上的每一個M成員，確定是否需

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

5、否,否,,6,(3)圖搜索方法的分析圖搜索過程的第8步對OPEN表上的節(jié)點進行排序，以便能夠從中選出一個“最好”的節(jié)點作為第4步擴展用。這種排序可以是任意的即盲目的(屬于盲目搜索)，也可以用以后要討論的各種啟發(fā)思想或其它準則為依據(jù)(屬于啟發(fā)式搜索)。每當被選作擴展的節(jié)點為目標節(jié)點時，這一過程就宣告成功結束。這時，能夠重現(xiàn)從起始節(jié)點到目標節(jié)點的這條成功路徑，其辦法是從目標節(jié)點按指針向S返回追溯。當搜索樹不再剩有未被擴展的端結點時，過程就

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

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

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

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

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

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

12、點n為目標節(jié)？,節(jié)點n可擴展？,擴展節(jié)點n，將其子節(jié)點放入Open表的尾部，并為每子字節(jié)點配置指向節(jié)點n的指針,,,,,,,,,,,,成功,退出,,,Y,N,N,Y,Y,N,14,例題 重排九宮問題。在3×3的方格棋盤上放置分別標有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)為S0，目標狀態(tài)為Sg ，如圖所示?？墒褂玫牟僮鞣校嚎崭褡笠啤⒖崭裆弦?、空格右移、空格下移。利用廣度優(yōu)先可得到如圖所示的搜索樹。,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) 缺點：盲目性大，當目標節(jié)點距離初始節(jié)點較遠時，將會產生許多無用節(jié)點，搜索效率低；但是其優(yōu)點為，只要有解，總能找到，而且得到的節(jié)一定是最短路徑解。三、深度優(yōu)先搜索1、基本思想 從

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

19、點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴展，則轉向第(2)步。(6)擴展節(jié)點n，將其子節(jié)點放入Open表的首部，并為每一個子節(jié)點都配置指向父節(jié)點指針，然后轉第(2)步。,18,例如：對前例重排九宮圖問題進行深度優(yōu)先搜索，可得到如下所示的搜索樹（部分）。,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,說明：在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可很快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以，深度優(yōu)先搜索不是完備的，即使問題有解，也不一定能得到解；另外，所求得的解也不一定是最短路徑解。3.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

36、句做歸結證明 C1∧C2?R(C1,C2)任一使C1，C2為真的解釋I下必有R(C1,C2)也是真?？兆泳洹醍擟1=P C2=~P兩個子句的歸結式為空，記作□，稱為空子句，體現(xiàn)了矛盾。,,為兩個子句,,,子句C1、C2的歸結式,38,3.5.3歸結推理過程,子句集S,歸結推理規(guī)則,S′＝空子句□,S′=所得歸結式,說明S是不可滿足的,與S對應的定理成立,推理結束,,,,,,,,,,是,否,39,例

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

38、證畢注：一階謂詞邏輯的歸結方法比命題邏輯的歸結法要復雜得多，原因是要對量詞和變量做專門的處理。,40,3.6 子句形,設有由一階謂詞邏輯描述的公式A1，A2，A3和B，證明在A1∧A2∧A3成立的條件下有B成立。仍然采用反演法來證明。 A1∧A2∧A3∧~B (3.2.1) 是不可滿足的。與命題邏輯不同，首先遇到了量詞問題，為此要將(3.2.1)式化成SKOLEM標準形。,,41

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

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

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

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

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

44、，以不同的狀態(tài)表現(xiàn)不同的時間，而狀態(tà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): 表示形式謂詞，只是為求得回答的動作序列而虛設的。引入狀態(tài)轉移函數(shù)Walk(y, z, s): 表示原狀態(tài)s下，在walk作用下，猴子從y走到z處所建立的新狀態(tài)。Carry(y,z,s): 表示

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

46、突破。,,51,3.7.1 置換與合一,置換：是形為{t1/v1,…,tn/vn}的一個有限集。其中，vi是變量，而ti是不同于vi的項（常量、變量、函數(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?表示結果，并稱為E的一個例。② ?作用于項t，是將t中出現(xiàn)的變量vi以ti代入(i=1,…,n)，結果以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,常使用的置換的運算是置換乘法（合成）若 ?=

48、{t1/x1,…,tn/xn} ?={u1/y1,…,um/ym}置換乘積?·?是新的置換，作用于E相當于先?后?對E的作用。定義如下：先作置換：{t1 ·? /x1 ,…, tn ·? /xn , u1 /y1,…,um/ym }若yi?{x1,…, xn}時，先從中刪除ui/yi；ti·? = xi時，再從中刪除ti ·?/ xi；所設的置換稱作?與?的乘積，記

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} 當 E

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

51、…,Ek有合一置換?，且對E1,…,Ek的任一合一置換?都有置換?存在，使得?= ?·?便說?是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，也可以說，是E1、 E2的最簡單合一置換。,57,例3 E1=P(x), E2=P(y)。顯然{y/x}和{x/y}都是E1 、E2的mgu，說明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 轉 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已合一，這時?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 歸結式,在謂詞邏輯下求兩個子句的歸結式，和命題邏輯一樣是消去互補對，但需考慮變量的合一和置換。二元歸結式：設C1, C2是兩個無公共 變量的子句， L1, L2分別是C1, C2的文字，若L1與~ L

58、2有mgu ?，則(C1 ? - {L1 ?}) ? (C2 ? - {L2 ?})稱作子句C1, C2的一個二元歸結式，而L1, L2為被歸結的文字?！咀⒁狻浚和}邏輯下的歸結式不同的是，先需對C1, C2有關變量作mgu，再消去互補對。同樣有： C1 ? C2 ? R(C1, C2),62,補充：歸結式的定義　　設         &#

59、160;           　　為兩個子句。有互補對L和~ L?！　t 新子句                 　　稱作C1、C2的歸結式?！　w

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

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

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

63、 = {f(y)/x}，將置換?使用于C，可使P(x), P(f(y))合一。顯然C?比C簡單得多。子句因子：若一個子句C的幾個文字有mgu ?，那么C的C?稱作子句C的因子。定義：若C1, C2是無公共變量的子句，作（1） C1, C2的二元歸結式（2） C1的因子和C2的二元歸結式（3） C1,和C2的因子的二元歸結式（4） C1的因子和C2的因子的二元歸結式這四種二元歸結式都叫子句C1, C2的歸結式，記作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歸結式為R(C1, C2) = Q(g(g(a))) ? Q(b)【說明】：上述推理過程的正確性能得到保證。,67,3.7.3 歸結推理過程

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