遞歸回溯算法

2024/2/8史忠植人工智能：自動推理1內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結自動推理是人工智能的核心內(nèi)容之一，是專家系統(tǒng)、程序推導、程序正確性證明、智能機器人等研究領域的重要基礎。自動推理早期的工作主要集中在機器定理證明。1930年希爾伯特（Herbrand）為定理證明建立了一種重要方法，他的方法奠定了機械定理證明的基礎。機械定理證明的主要突破是1965年由魯賓遜做出的，他建立了所謂歸結原理，使機械定理證明達到了應用階段。在本章，首先討論三段論推理和搜索策略，然后討論歸結演繹推理、產(chǎn)生式系統(tǒng)，最后討論非單調推理。自動推理2024/2/82史忠植人工智能：自動推理2024/2/8史忠植人工智能：自動推理3內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結三段論是一種常用的推理形式，它由三個性質命題組成，其中兩個性質命題是前提，另一個性質命題是結論。例如科學是不斷發(fā)展的；(大前提)

智能科學是科學：(小前提)

所以，智能科學是不斷發(fā)展的。(結論)這就是一個三段論。前兩個性質判斷包含著一個共同項——“科學”，由這兩個具有同項的判斷推出一個新的性質判斷：智能科學是不斷發(fā)展的。三段論2024/2/84史忠植人工智能：自動推理其中，結論中的主項叫做小項，用“S”表示，如上例中的“智能科學"；結論中的謂項叫做大項，用“P”表示，如上例中的“不斷發(fā)展的"；兩個前提中共有的項叫做中項，用“M”表示，如上例中的“科學"。在三段論中，含有大項的前提叫大前提，如上例中的“科學是不斷發(fā)展的”；含有小項的前提叫小前提，如上例中的“智能科學是科學"。三段論2024/2/85史忠植人工智能：自動推理三段論的公理三段論的公理是三段論推理的基本依據(jù)。三段論的公理是客觀事物的最一般、最普遍的關系在人們思維中的反映，是在人類長期反復實踐中被總結出來的，并不斷被實踐所證明的，具有不證自明性。三段論的公理內(nèi)容：對一類事物的全部有所斷定（肯定或否定），則對該類事物的部分也就有所斷定（肯定或否定）。三段論的公理用圖表示如下：2024/2/86史忠植人工智能：自動推理PMSSMP圖1圖2三段論的公理在圖1中，M類全部包含在P類中（所有M是P），S類是M類的一部分（所有S是M），可見，S類的全部必然包含在P類中的。在圖2中，M類全部與P類相排斥（所有M不是P），S類是M類的一部分（所有S是M），可見，S類的全部必然與P類相排斥。2024/2/87史忠植人工智能：自動推理三段論的格三段論的格就是根據(jù)中項在三段論中的不同位置所構成的不同形式的三段論。在三段論的第一格中，中項是大前提的主項、小前提的謂項；在第二格中，中項是大、小前提的謂項；在第三格中，中項是大、小前提的主項；在第四格中，中項是大前提的謂項、小前提的主項。三段論的四個格可以分別表示如下：第一格第二格第三格第四格

M—PP—MM—PP—M

S—M

S—M

M—S

M—SS—PS—PS—PS—P2024/2/88史忠植人工智能：自動推理構成三段論推理的三個性質命題，在質和量上的不同，就形成了三段論的不同形式，這些不同的形式叫做三段論的式。三段論總是由質和量不同的A（全稱肯定命題）、E（全稱否定命題）、I（特稱肯定命題）、O（特稱否定命題）四種命題組合而成，任何一個三段論推理都表現(xiàn)為一定的格和式。A、E、I、O都可以作為大前提、小前提和結論，其排列組合數(shù)目是：4×4×4=64。這樣，每個格都有64式，四個格共有64×4=256式。但大多數(shù)是違反三段論規(guī)則的，是錯誤的式或無效式。三段論的式2024/2/89史忠植人工智能：自動推理根據(jù)三段論推理的規(guī)則，就可以確定出各個格的正確式。四個格總共有256個式，其中只有24式是正確的式。各格正確式如下：第一格：AAA，（AAI），EAE，（EAO），AII，EIO。第二格：AEE，（AEO），EAE，（EAO），AOO，EIO。第三格：AAI，EAO，AII，EIO，IAI，OAO。第四格：AAI，AEE，（AEO），IAI，EAO，EIO。上面的各個式中，凡帶有括號的式叫做“弱式”，共有五個弱式。弱式就是指可推出全稱結論但只推出一個特稱結論的式。如第一格中AII式。我們知道，在第一格中，從AA這兩個前提可以推出全稱結論A，但得出AAI式卻是一個特稱結論，因而這個式就是弱式。例如：所有的植物都是生物；（A）

所有的玫瑰花都是植物；（A）所以，有的玫瑰花是生物。（I）三段論的式2024/2/810史忠植人工智能：自動推理2024/2/8史忠植人工智能：自動推理11內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結問題求解AI中每個研究領域都有其各自的特點和規(guī)律,但就求解問題的過程看,都可抽象為一個問題求解過程。問題求解過程實際上是一個搜索,廣義地說,它包含了全部計算機科學。任何問題求解技術都包括兩個重要的方面:表示和搜索表示是基本的,搜索必須要在表示的基礎上進行。表示關系到搜索的效率。本章討論的表示主要包括:狀態(tài)空間表示問題空間表示2024/2/8史忠植人工智能：自動推理12搜索1974年，Nilsson歸納出的AI研究的基本問題知識的模型化和表示常識性推理、演繹和問題解決啟發(fā)式搜索人工智能系統(tǒng)和語言搜索是人工智能中的一個基本問題,是推理不可分割的一部分,直接關系到智能系統(tǒng)的性能和運行效率AI為什么要研究search?問題沒有直接的解法;需要探索地求解;2024/2/8史忠植人工智能：自動推理13什么是搜索根據(jù)問題的實際情況不斷尋找可利用的知識,構造出一條代價較少的推理路線,使問題得到圓滿解決的過程稱為搜索包括兩個方面：

找到從初始事實到問題最終答案的一條推理路徑

找到的這條路徑在時間和空間上復雜度最小2024/2/8史忠植人工智能：自動推理14搜索策略盲目搜索:也稱為無信息搜索，即只按預定的控制策略進行搜索,在搜索過程中獲得的中間信息不用來改進控制策略啟發(fā)式搜索:在搜索中加入了與問題有關的啟發(fā)性信息,用于指導搜索朝著最有希望的方向進行,加速問題的求解過程并找到最優(yōu)解2024/2/8史忠植人工智能：自動推理15搜索策略一般搜索策略可以通過下面4個準則來評價：（1）完備性：如果存在一個解答，該策略是否保證能夠找到？（2）時間復雜性：需要多長時間可以找到解答？（3）空間復雜性：執(zhí)行搜索需要多大存儲空間？（4）最優(yōu)性：如果存在不同的幾個解答，該策略可以發(fā)現(xiàn)是否最高質量的解答？2024/2/8史忠植人工智能：自動推理16盲目搜索盲目搜索一般是按預定的搜索策略進行搜索。由于這種搜索總是按預定的路線進行，沒有考慮到問題本身的特性，所以這種搜索具有很大的盲目性，效率不高，不便于復雜問題的求解。深度優(yōu)先搜索寬度優(yōu)先搜索迭代加深搜索2024/2/8史忠植人工智能：自動推理1718深度優(yōu)先搜索(Dephth-first)深度優(yōu)先搜索生成節(jié)點并與目標節(jié)點進行比較是沿著樹的最大深度方向進行的，只有當上次訪問的節(jié)點不是目標節(jié)點，而且沒有其他節(jié)點可以生成的時候，才轉到上次訪問節(jié)點的父節(jié)點。轉移到父節(jié)點后，該算法會搜索父節(jié)點的其它的子節(jié)點。防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度——深度界限。2024/2/8史忠植人工智能：自動推理19深度優(yōu)先搜索示意圖SLOMFPQNFFF2024/2/8史忠植人工智能：自動推理20開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？擴展n，把n的后繼節(jié)點放入OPEN表的前端，提供返回節(jié)點n的指針失敗成功是否是否節(jié)點n的深度等于最大深度？否深度優(yōu)先算法框圖2024/2/8史忠植人工智能：自動推理21有界深度(4)優(yōu)先的八數(shù)碼問題深度優(yōu)先搜索樹1238456712384567（目標狀態(tài)）（初始狀態(tài)）深度優(yōu)先搜索樹2024/2/8史忠植人工智能：自動推理22八數(shù)碼有界深度優(yōu)先搜索樹2024/2/8史忠植人工智能：自動推理(1)把初始節(jié)點S0放入OPEN表(2)如果OPEN表為空,則問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)考查節(jié)點n是否為目標節(jié)點.若是,則求得了問題的解,退出(5)若節(jié)點n不可擴展,則轉第(2)步(6)擴展節(jié)點n,將其子節(jié)點放入OPEN表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉第(2)步深度優(yōu)先搜索過程2024/2/8史忠植人工智能：自動推理2324SLOMFPQNFFF寬度優(yōu)先搜索示意圖2024/2/8史忠植人工智能：自動推理25（1）把起始節(jié)點放到OPEN表中(如果該起始節(jié)點為一目標節(jié)點，則求得一個解答)。（2）如果OPEN是個空表，則沒有解，失敗退出；否則繼續(xù)。（3）把第一個節(jié)點(節(jié)點n)從OPEN表移出，并把它放入CLOSED的擴展節(jié)點表中。（4）擴展節(jié)點n。如果沒有后繼節(jié)點，則轉向上述第(2)步。（5）把n的所有后繼節(jié)點放到OPEN表的末端，并提供從這些后繼節(jié)點回到n的指針。（6）如果n的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉向第(2)步。寬度優(yōu)先搜索算法2024/2/8史忠植人工智能：自動推理26開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(n)從OPEN表移至CLOSED表是否有后繼節(jié)點為目標節(jié)點？擴展n，把n的后繼節(jié)點放入OPEN表的末端，提供返回節(jié)點n的指針失敗成功是否是否寬度優(yōu)先算法框圖2024/2/8史忠植人工智能：自動推理27八數(shù)碼難題（8-puzzleproblem）1238456712384567（目標狀態(tài)）（初始狀態(tài)）規(guī)定：將牌移入空格的順序為：從空格左邊開始順時針旋轉。不許斜向移動，也不返回先輩節(jié)點。從圖可見，要擴展26個節(jié)點，共生成46個節(jié)點之后才求得解（目標節(jié)點）。寬度優(yōu)先算法例子2024/2/8史忠植人工智能：自動推理28八數(shù)碼寬度優(yōu)先搜索樹2024/2/8史忠植人工智能：自動推理迭代加深搜索對于有界深度搜索策略，有下面幾點需要說明：1）在有界深度搜索算法中，深度限制dm是一個很重要的參數(shù)。2）深度限制dm不能太大。3）有界深度搜索的主要問題是深度限制值dm的選取。問題：但是對很多問題，我們并不知道該值到底為多少，直到該問題求解完成了，才可以確定出深度限制dm。2024/2/8史忠植人工智能：自動推理29迭代加深搜索改進方法---迭代加深搜索算法先任意給定一個較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結束；如在此限度內(nèi)沒有找到問題的解，則增大深度限制dm，繼續(xù)搜索。迭代加深搜索是一種回避選擇最優(yōu)深度限制問題的策略，它是試圖嘗試所有可能的深度限制：首先深度為0，然后深度為1，然后為2，等等，一直進行下去。問題迭代加深搜索看起來會很浪費，因為很多節(jié)點都要擴展多次。2024/2/8史忠植人工智能：自動推理302024/2/8史忠植人工智能：自動推理31內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結2024/2/8史忠植人工智能：自動推理32回溯算法有些問題需要徹底的搜索才能解決問題，然而，徹底的搜索要以大量的運算時間為代價，對于這種情況可以通過回溯法來去掉一些分枝，從而大大減少搜索的次數(shù)。八皇后問題迷宮問題深度優(yōu)先周游樹或圖四皇后問題中隱含的狀態(tài)樹

四皇后問題2024/2/8史忠植人工智能：自動推理332024/2/8史忠植人工智能：自動推理34四皇后問題樹回溯算法emptyassignment1stvariable2ndvariable3rdvariableAssignment={}2024/2/8史忠植人工智能：自動推理35emptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11)}回溯算法2024/2/8史忠植人工智能：自動推理36emptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v21)}回溯算法2024/2/8史忠植人工智能：自動推理37emptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v21),(var3=v31)}回溯算法2024/2/8史忠植人工智能：自動推理38emptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v21),(var3=v32)}回溯算法2024/2/8史忠植人工智能：自動推理39emptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v22)}回溯算法2024/2/8史忠植人工智能：自動推理40emptyassignment1stvariable2ndvariable3rdvariableAssignment={(var1=v11),(var2=v22),(var3=v31)}回溯算法2024/2/8史忠植人工智能：自動推理412024/2/8史忠植人工智能：自動推理42遞歸回溯算法RecursiveprocedureBACKTRACK(DATA)1.ifTERM(DATA),returnNIL;/*TERM是一個謂詞，'對滿足產(chǎn)生式系統(tǒng)結束條件變量來說取值為真。在成功結束時，返回空表N1L。*/2.ifDEADEND(DATA),retulrnFAIL;/*DEADEND是一個謂詞，對已經(jīng)知道不在一條解路上的自變量來說取值為真。在這種情況下，過程返回符號FAIL。*/3.RULES

APPRULUES(DATA);/*APPRULUES是一個函數(shù)，它計算可應用于其自變量的規(guī)則并排列這些規(guī)則(任意排列或者按照啟發(fā)式準則排列)。*/4.LOOP:ifNULL(RULES),returnFAIL;/*如果不再有可應用的規(guī)則，那么過程失敗。*/5.R

FIRST(RULES);/*選出最好的一條可應用規(guī)則。*/2024/2/8史忠植人工智能：自動推理43遞歸回溯算法6.RULES

TAIL(RULES);/*刪去剛才選用的一條規(guī)則，縮小可應用的規(guī)則表。*/7.RDATA

R(DATA);/*應用規(guī)則R產(chǎn)生一個新的數(shù)據(jù)庫。*/8.PATH

BACKTRACK(RDATA);/*在新數(shù)據(jù)庫上遞歸調用BACKTRACK。*/9.ifPATH=FAIL,goLOOP;/*若遞歸調用失敗，則試另一條規(guī)則。*/10.returnCONS(R,PATH);/*否則，通過把R加到表的前面，向上走一遍成功的規(guī)則表。*/

2024/2/8史忠植人工智能：自動推理44內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結啟發(fā)式搜索前面討論的方法都是盲目的搜索方法,即都沒有利用問題本身的特性信息,在決定要被擴展的節(jié)點時,都沒有考慮該節(jié)點在解的路徑上的可能性有多大,它是否有利于問題求解以及求出的解是否為最優(yōu)啟發(fā)式搜索要用到問題自身的某些特性信息,以指導搜索朝著最有希望的方向前進啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最優(yōu)解弱：一般導致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解2024/2/8史忠植人工智能：自動推理45啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)用于指導搜索過程,且與具體問題有關的控制性信息稱為為啟發(fā)性信息用于評價節(jié)點重要性的函數(shù)稱為估價函數(shù).記為

f(x)=g(x)+h(x)g(x)為從初始節(jié)點S0到節(jié)點x已經(jīng)實際付出的代價h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的估價代價,體現(xiàn)了問題的啟發(fā)性信息,稱為啟發(fā)函數(shù)f(x)表示從初始節(jié)點經(jīng)過節(jié)點x到達目標節(jié)點的最優(yōu)路徑的代價估價值,其作用是用來評估OPEN表中各節(jié)點的重要性,決定其次序2024/2/8史忠植人工智能：自動推理46啟發(fā)式搜索例：八數(shù)碼問題，評價函數(shù)f(n)=d(n)+W(n)d(n):節(jié)點n的深度;W(n):與目標相比,錯位的數(shù)字數(shù)目;1238476528316475初始狀態(tài)目標狀態(tài)2024/2/8史忠植人工智能：自動推理472831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目標123456八數(shù)碼啟發(fā)式搜索2024/2/8史忠植人工智能：自動推理48啟發(fā)式搜索啟發(fā)式就是要猜測：從節(jié)點n開始，找到最優(yōu)解的可能性有多大？從起始節(jié)點開始，經(jīng)過節(jié)點n，到達目標節(jié)點的最佳路徑的費用是多少？gh2024/2/8史忠植人工智能：自動推理49局部擇優(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表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉第(2)步2024/2/8史忠植人工智能：自動推理50局部擇優(yōu)搜索(爬山法)爬山法的三個問題：局部最大。高地：也稱為平頂，在某一局部點周圍f(x)為常量。此時，搜索就無法確定要搜索的最佳方向，會產(chǎn)生隨機走動，這使得搜索效率降低。山脊：山脊可能具有陡峭的斜面，所以搜索可以比較容易地到達山脊的頂部，但是山脊的頂部到山峰之間可能傾斜的很平緩。除非正好有合適的操作符直接沿著山脊的頂部移動，該搜索可能會在山脊的兩面來回震蕩，搜索的前進步伐會很小。2024/2/8史忠植人工智能：自動推理51全局擇優(yōu)搜索(有序搜索/最好優(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é)點的估價值,并為每一個子節(jié)點都配置指向父節(jié)點的指針,把這些子節(jié)點都送入OPEN表,然后對OPEN表中的全部節(jié)點按估價值從小到大的順序進行排列(7)轉第(2)步2024/2/8史忠植人工智能：自動推理52A*算法將狀態(tài)空間一般搜索過程進行如下的限制,就是A*算法把OPEN表中的節(jié)點按估價函數(shù)f(x)=g(x)+h(x)的值從小到大進行排序g(x)是對g*(x)的估價,g(x)>0h(x)是h*(x)的下界,即對所有的x,h(x)<=h*(x)其中:

g*(x)是從初始節(jié)點S0到節(jié)點x的最小代價

h*(x)是從節(jié)點x到目標節(jié)點的最小代價,若有多個目標節(jié)點,則為其中最小的一個2024/2/8史忠植人工智能：自動推理53A*算法f*(S)f*(S)=g*(S)+h*(S)=h*(S)從S無約束地到達目標的最佳路經(jīng)上的耗散值;g(n)一般取實際走過的路徑的費用和.g(n)

g*(n)隨著算法的執(zhí)行，由于指針的變動，g(n)會下降.h

0沒有啟發(fā)式信息;nSg*(n)h*(n)g2024/2/8史忠植人工智能：自動推理54A*算法8數(shù)碼問題h(n)=“不在位”的將牌數(shù)h(n)=將牌“不在位”的距離和2

831

647512345768將牌1：1將牌2：1將牌6：1將牌8：22024/2/8史忠植人工智能：自動推理55A*算法2024/2/8史忠植人工智能：自動推理56A*算法2024/2/8史忠植人工智能：自動推理57A*算法可納性對于可解狀態(tài)圖(即從初始節(jié)點到目標節(jié)點有路徑存在)所說,如果一個搜索算法能在有限步內(nèi)終止,并且能找到最優(yōu)解,則稱該搜索算法是可納的.定理:A*算法是可納的,即在有限步內(nèi)終止,并且找到最優(yōu)解證明思路對于有限圖,A*算法一定會在有限步內(nèi)終止對應無限圖,只要從初始節(jié)點到目標節(jié)點有路徑存在,A*算法也必然終止A*算法一定終止在最優(yōu)路徑上2024/2/8史忠植人工智能：自動推理58A*算法的最優(yōu)性最優(yōu)性A*算法的搜索效率在很大程度上取決于h(x),在滿足h(x)<=h*(x)的前提下,h(x)的值越大越好.H(x)所攜帶的啟發(fā)性信息越多,搜索時所擴展的節(jié)點數(shù)越少,搜索效率就越高2024/2/8史忠植人工智能：自動推理59A*算法的單調性單調性限制單調性限制是指h(x)滿足如下兩個條件h(Sg)=0設xj是節(jié)點xi

的任意子節(jié)點,則有h(xi)-h(xj)<=c(xi,xj)其中:Sg是目標節(jié)點,c(xi,xj)是節(jié)點xi到子節(jié)點xj的邊代價A*算法的h(x)滿足單調性限制時,可有下面的結論若A*算法選擇節(jié)點xn進行擴展,則g(xn)=g*(x)由A*算法所擴展的節(jié)點序列其f值是非遞減的2024/2/8史忠植人工智能：自動推理602024/2/8史忠植人工智能：自動推理61內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結與或圖啟發(fā)式搜索與或（AND-OR）圖的反向推理過程可以看作是一個問題歸約過程，在問題求解過程中，將一個大的問題變換成若干個子問題，子問題又可以分解成更小的子問題，這樣一直分解到可以直接求解為止，全部子問題的解就是原問題的解。原問題稱為初始問題，可直接求解的問題稱為本原問題。問題歸約法不同于狀態(tài)空間法，是另一種問題描述和求解的方法。2024/2/8史忠植人工智能：自動推理62問題歸約一般說來，問題歸約可以用三元組表示：（S0，O，P），其中：S0是初始問題，即要求解的問題；P是本原問題集，其中的每一個問題是不用證明的，自然成立的，如公理、已知事實等，或已證明過的問題；O是操作算子集，它是一組變換規(guī)則，通過一個操作算子把一個問題化成若干個子問題。這樣，問題歸約表示方法就是由初始問題出發(fā)，運用操作算子產(chǎn)生一些子問題，對子問題再運用操作算子產(chǎn)生子問題的子問題，這樣一直進行到產(chǎn)生的問題均為本原問題，則問題得解。2024/2/8史忠植人工智能：自動推理63與或圖與節(jié)點：把單個問題分解為幾個子問題來求解。只有當所有子問題都有解，該父輩節(jié)點才有解。表示一種“與”關系?；蚬?jié)點：同一問題被轉換為幾種不同的后繼問題。只要有一個后繼問題有解，則原問題有解。表示一種“或”關系。與節(jié)點由與運算連接（超?。?或節(jié)點由或運算連接.2024/2/8史忠植人工智能：自動推理64定義：與或圖就是包含與節(jié)點和或節(jié)點的圖，即存在超弧的圖，也稱為超圖.超圖與狀態(tài)空間圖有什么區(qū)別？與或圖是一種更一般的圖.定義：一超弧所相關的邊數(shù)（K）被稱為該超弧的度，實現(xiàn)的連接稱為K-連接.K—連接符：從一個父節(jié)點指向一組含有K個后繼節(jié)點的節(jié)點集.與或圖2024/2/8史忠植人工智能：自動推理65在與或圖中，節(jié)點n0有兩個連接符：1-連接符指向節(jié)點n1；2-連接符指向節(jié)點集合{n4、n5}；對于節(jié)點n0來講，n1可稱為或節(jié)點，n4、n5可稱為與節(jié)點。與或圖

與或圖2024/2/8史忠植人工智能：自動推理6667與或圖知識表示三階梵塔問題。

對于梵塔問題，我們也可以這樣考慮：為把1號桿上的n個盤子搬到3號桿，可先把上面的n-1個盤子搬到2號桿上；再把剩下的一個大盤子搬到3號桿；然后再將2號桿上的n-1個盤子搬到3號桿。這樣，就把原來的一個問題分解為三個子問題。這三個子問題都比原問題簡單，其中第二個子問題已是直接可解的問題。對于第一和第三兩個子問題，可用上面n個盤子的方法，做同樣的處理。

2024/2/8史忠植人工智能：自動推理68123CBA思考：用狀態(tài)空間法有多少個節(jié)點？為什么？梵塔問題2024/2/8史忠植人工智能：自動推理69(1,1,1)=>(3,3,3)(1,1,1)=>(1,1,3)(1,2,3)=>(1,2,2)(3,2,2)=>(3,2,1)(3,3,1)=>(3,3,3)(1,1,3)=>(1,2,3)(3,2,1)=>(3,3,1)(1,1,1)=>(1,2,2)(1,2,2)=>(3,2,2)(3,2,2)=>(3,3,3)梵塔問題的與或樹2024/2/8史忠植人工智能：自動推理70把本原問題的解按照從左至右的順序排列，就得到了原始問題的解：

(1,1,1)=>(1,1,3) (1,1,3)=>(1,2,3)(1,2,3)=>(1,2,2)(1,2,2)=>(3,2,2)(3,2,2)=>(3,2,1)(3,2,1)=>(3,3,1)(3,3,1)=>(3,3,3)

任何一個狀態(tài)圖都可以轉化為與或圖。三階梵塔問題的與或樹2024/2/8史忠植人工智能：自動推理71與或圖搜索有界深度優(yōu)先搜索算法步1把初始節(jié)點S0放入OPEN表。步2把OPEN表中的第一個節(jié)點（記為節(jié)點N）取出放入CLOSED

表，并冠以編號n。步3如果節(jié)點N的深度大于等于深度界限，則轉步5第（1）點。步4如果節(jié)點N可擴展，則作下列工作：

(1)擴展節(jié)點N，將其子節(jié)點放入OPEN表首部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標示過程中使用。

2024/2/8史忠植人工智能：自動推理72與或圖搜索(2)考查這些節(jié)點中是否有終止節(jié)點。若有，標示這些節(jié)點為可解節(jié)點并用可解標示過程對其先輩節(jié)點中的可解節(jié)點進行標示。如果也被標示為可解節(jié)點，就得到解樹，搜索成功，退出。（3）若不能確定為可解節(jié)點，則從OPEN表中刪除具有可解先輩節(jié)點。轉步2步5如果節(jié)點N不可擴展，則作如下工作：（1）表示節(jié)點N為不可解節(jié)點。（2）應用不可解節(jié)點標示過程對節(jié)點N的先輩節(jié)點中不可解的節(jié)點進行標示。如果初始節(jié)點S0也被標示為不可解節(jié)點，則搜索失敗，退出搜索過程；如果不能確定S0為不可解節(jié)點，則從

OPEN表中刪去具有不可解先輩的節(jié)點。（3）轉步2。2024/2/8史忠植人工智能：自動推理

AO*算法算法交替執(zhí)行以下兩個階段的操作：

第一階段：自頂向下地生成局部與或圖-選擇迄今為止最好的局部解圖；對該解圖的一個非終葉節(jié)點進行擴展，計算該節(jié)點各個K-連接符連接的后繼節(jié)點解圖的花費計值；如果可能，標記后繼節(jié)點為能解節(jié)點。

第二階段：自下而上地計算修正與或圖花費估計值-確定最小花費連接符；如果必要，修改父節(jié)點的花費值；或標記父節(jié)點為能解節(jié)點;此過程不斷進行直到到達局部解圖的根節(jié)點為止。2024/2/8史忠植人工智能：自動推理73AO*算法數(shù)據(jù)結構

s：初始節(jié)點；n：當前節(jié)點。

G：以s

為根節(jié)點產(chǎn)生的與或圖；G’：當前選擇的局部與或解圖；h(m)：任意節(jié)點m到N的啟發(fā)式費用估計值；q(n)：目前得到的以節(jié)點n為根的解圖的最小耗費；q0(n)：上一次獲得的以節(jié)點n為根的解圖的最小耗費。2024/2/8史忠植人工智能：自動推理74

AO*搜索算法假設：G；G

；h(n)是從節(jié)點n到一組終葉節(jié)點的一個最優(yōu)解圖的一個代價估計，評價函數(shù)q(n)=h(n)AO*過程:1.建立初始搜索圖，G:=s，計算q(s)=h(s)，IFGOAL(s)THENM(s,SOLVED)；2.Untils已標記為SOLVED,do:3.Begin4.G

:=FIND(G)；根據(jù)連接符標記（指針）找出一個待擴展的侯選局部解圖G

（連接符在11步標記）5.n:=G

中的任一非終節(jié)點;選一個當前節(jié)點6.EXPAND(n),生成子節(jié)點集{ni}，如果ni

G，G:=ADD({ni},G),計算q(ni)=h(ni)，IFGOAL(ni)THENM(ni,SOLVED);2024/2/8史忠植人工智能：自動推理757S:={n};建立含n的節(jié)點集合S.（已擴展待修正）8UntilS為空,do:9Begin(m為S中任一節(jié)點)10REMOVE(m,S),當mc

{S};（m→mc,從底層開始修正）11

修改m的耗散值q(m):對m指向節(jié)點集(n1i，n2i,…nki)的每一個連接符i分別計算qi,qi(m)=Ci+q(n1i)+…+q(nki),并取q(m):=minqi(m);

加(或修正)指針到minqi(m)的連接符上.IFM(nji,SOLVED)THENM(m,SOLVED);（j=1，2，…，k）若該連接符的所有子節(jié)點都是能解的,則m也能解.12IFM(m,SOLVED)

(q(m)

q0(m))THENADD(ma,S);m能解或修正的耗散值與原先估算q0不同,則把m的所有先輩節(jié)點ma添加到S中.（能解或修正向上傳遞）13end(與8匹配)14

end(與2匹配)

AO*搜索算法2024/2/8史忠植人工智能：自動推理76AO*搜索算法流程圖選擇最有希望的局部解圖G’及G’中合適的非葉節(jié)點n：G’:=Find(G),n:=Select(G’)擴展節(jié)點n，計算{mj}的啟發(fā)式信息：

{mi}:=Expand(n),G’:={mi}∪G’,

對所有mj:q(mj):=h(mj)mj到N的估計值;

如果mj屬于N則Mark(mj，Sovled)。建立以n節(jié)點為初始節(jié)點的祖先節(jié)點集合：

A:={n}

A=Φ?

YesNo2024/2/8史忠植人工智能：自動推理77m:=Remove(A)針對m的L個k連接符，求m的最小花費q(m)：

qi(m):=C(mi)+q(ni1)+q(ni2)+……+q(nik))1<i<L;q(m):=minqi(m)（i=1,2,….,L);標記m指向當前花費最小的k連接符。如果m最小花費ki

連接符連接的所有節(jié)點nij可解,標記節(jié)點m可解，即對（j=1,2,….,k)：

ijMark(nij,Sovled)->Mark(m,Sovled),Mark(m,Sovled)∨

q(m)≠q0(m)將m的父節(jié)點ma送集合A:A:=A∪{ma

}YesNoAO*搜索算法流程圖2024/2/8史忠植人工智能：自動推理78與A*算法的區(qū)別評價函數(shù)只考慮h(n):理由:算法有自下而上的修正費用的的操作,實際上局部解圖費用值的估計是在起始節(jié)點S比較,計算g既無必要也不可能.不能優(yōu)先擴展具有最小費用的節(jié)點:理由:K-連接符連接的有關子節(jié)點對父節(jié)點的可解性及費用值的估計都會產(chǎn)生影響.僅適用于無環(huán)圖,否則耗散值遞歸計算不收斂:方法:當新生成的節(jié)點已在圖中時,判斷是否為正被擴展節(jié)點的先輩節(jié)點.控制策略不同:沒有OPEN表和CLOSED表,只用生成的解圖結構G,h(n)是最佳解圖的費用估計.AO*算法與A*算法的區(qū)別2024/2/8史忠植人工智能：自動推理792024/2/8史忠植人工智能：自動推理80內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結博弈一向被認為是富有挑戰(zhàn)性的智力活動，如下棋、打牌、作戰(zhàn)、游戲等等。博弈的研究不斷為人工智能提出新的課題，可以說博弈是人工智能研究的起源和動力之一。博弈的特性是：兩個棋手交替地走棋；比賽的最終結果，是贏、輸和平局中的一種；可用圖搜索技術進行，但效率很低；博弈的過程，是尋找置對手于必敗態(tài)的過程；雙方都無法干預對方的選擇。博弈2024/2/8史忠植人工智能：自動推理8120世紀60年代，研制出的西洋跳棋和國際象棋達到了大師級的水平。1958年麥卡錫提出博弈樹α－β剪枝算法1997年，IBM公司研制的“深藍”國際象棋程序，采用博弈樹搜索算法，該程序戰(zhàn)勝了國際象棋世界冠軍卡斯帕羅夫。博弈2024/2/8史忠植人工智能：自動推理82與深藍下棋的卡斯帕羅夫1997“深藍”贏了卡斯帕羅夫2024/2/8史忠植人工智能：自動推理83對各個局面進行評估評估的目的：對后面的狀態(tài)提前進行考慮，并且以各種狀態(tài)的評估值為基礎作出最好的走棋選擇。評估的方法：用評價函數(shù)對棋局進行評估。贏的評估值設為+∞，輸?shù)脑u估值設為-∞，平局的評估值設為0。評估的標準：由于下棋的雙方是對立的，只能選擇其中一方為評估的標準方。極大極小搜索過程2024/2/8史忠植人工智能：自動推理84命名博弈的雙方，一方為“正方”，對每個狀態(tài)的評估都是對應于該方的輸贏的。例如，贏2個，輸1個等，都是指正方的。正方每走一步，都在選擇使自己贏得更多的節(jié)點，因此這類節(jié)點稱為“MAX”節(jié)點；另一方為“反方”，對每個狀態(tài)的評估都是對應于對手的輸贏的。例如，贏2個，輸一個，其實是指自己輸2個，贏1個的。反方每走一步，都在選擇使對手輸?shù)酶嗟墓?jié)點，因此這類節(jié)點稱為“MIN”節(jié)點。極大極小搜索過程2024/2/8史忠植人工智能：自動推理85極大極小搜索過程2024/2/8史忠植人工智能：自動推理86015-333-3022-30-23541-30689-30-33-3-3-21-36-3031601MAXMINMAXMIN極大極小搜索過程2024/2/8史忠植人工智能：自動推理87-剪枝法的引入在極大極小法中，必須求出所有終端節(jié)點的評估值，當預先考慮的棋步比較多時，計算量會大大增加。為了提高搜索的效率，引入了通過對評估值的上下限進行估計，從而減少需進行評估的節(jié)點范圍的

-剪枝法。

-搜索過程2024/2/8史忠植人工智能：自動推理88MAX節(jié)點的評估下限值

作為正方出現(xiàn)的MAX節(jié)點，假設它的MIN子節(jié)點有N個，那么當它的第一個MIN子節(jié)點的評估值為時，則對于其它的子節(jié)點，如果有高過的，就取那最高的值作為該MAX節(jié)點的評估值；如果沒有，則該MAX節(jié)點的評估值為。MIN節(jié)點的評估上限值

作為反方出現(xiàn)的MIN節(jié)點，假設它的MAX子節(jié)點有N個，那么當它的第一個MAX子節(jié)點的評估值為時，則對于其它子節(jié)點，如果有低于的，就取那個低于的值作為該MIN節(jié)點的評估值；如果沒有，則該MIN節(jié)點的評估值取。

-搜索過程2024/2/8史忠植人工智能：自動推理89MAX節(jié)點

MIN節(jié)點=

剪枝ABCD-搜索過程

剪枝法

設MAX節(jié)點的下限為，則其所有的MIN子節(jié)點中，其評估值的上限小于等于的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了剪枝。2024/2/8史忠植人工智能：自動推理90

剪枝法設MIN節(jié)點的上限為，則其所有的MAX子節(jié)點中，其評估值的下限大于等于的節(jié)點，其以下部分的搜索都可以停止了，即對這部分節(jié)點進行了剪枝。MAX節(jié)點

MIN節(jié)點=

剪枝ABCD-搜索過程2024/2/8史忠植人工智能：自動推理91ABCDEFGHIJKLNOM-搜索過程MAX節(jié)點MAX節(jié)點MIN節(jié)點終端節(jié)點356521642024/2/8史忠植人工智能：自動推理92MAX節(jié)點(5,

)35652164(6,

)(2,

)(-,5)(-,2)(5,

)MIN節(jié)點終端節(jié)點

剪剪枝

剪枝ABCDEFGHIJKLNOMMAX節(jié)點-搜索過程2024/2/8史忠植人工智能：自動推理93一字棋

-剪枝2024/2/8史忠植人工智能：自動推理94

-

剪枝極大節(jié)點的下界為。極小節(jié)點的上界為。剪枝的條件：后輩節(jié)點的值≤祖先節(jié)點的值時，剪枝后輩節(jié)點的值≥祖先節(jié)點的值時，剪枝簡記為：極小≤極大，剪枝極大≥極小，剪枝2024/2/8史忠植人工智能：自動推理95當算法給出所選的走步后，不要馬上停止搜索，而是在原先估計可能的路徑上再往前搜索幾步，再次檢驗會不會出現(xiàn)意外，這是一種增添輔助搜索的方法。對某些博弈的開局階段和殘局階段，往往總結了一些固定的對弈模式，因此可以利用這些知識編好走步表，以便在開局和結局時使用查表法。只是在進入中盤階段后，再調用其他有效的搜索算法，來選擇最優(yōu)的走步。

-搜索過程2024/2/8史忠植人工智能：自動推理962024/2/8史忠植人工智能：自動推理97內(nèi)容提要3.1概述3.2三段論推理

3.3盲目搜索

3.4回溯策略

3.5啟發(fā)式搜索

3.6與或圖啟發(fā)式搜索

3.7博弈搜索

3.8歸結演繹推理

3.9產(chǎn)生式系統(tǒng)

3.10自然演繹推理

3.11非單調推理

3.12小結歸結演繹推理歸結演繹推理本質上就是一種反證法，它是在歸結推理規(guī)則的基礎上實現(xiàn)的。為了證明一個命題P恒真，它證明其反命題

P恒假，即不存在使得

P為真的解釋。由于量詞，以及嵌套的函數(shù)符號，使得謂詞公式往往有無窮的指派，不可能一一測試

P是否為真或假。那么如何來解決這個問題呢？幸運的是存在一個域，即Herbrand域，它是一個可數(shù)無窮的集合，如果一個公式基于Herbrand解釋為假，則就在所有的解釋中取假值?；贖erbrand域，希爾伯特（HerbrandD）給出了重要的定理，為不可滿足的公式判定過程奠定了基礎。Robinson給出了用于從不可滿足的公式推出F的歸結推理規(guī)則，為定理機械證明取得了重要的突破，使其達到了應用的階段。2024/2/8史忠植人工智能：自動推理98歸結演繹推理歸結證明過程是一種反駁程序，即不是證明一個公式是有效的，而是證明公式之非是不一致的。這完全是為了方便，并且不失一般性。歸結推理規(guī)則所應用的對象是命題或謂詞合式公式的一種特殊的形式，稱為子句。因此在使用歸結推理規(guī)則進行歸結之前需要把合式公式化為子句式。在數(shù)理邏輯中，我們知道如何把一個公式化成前束標準型（Q1x1）…（Qnxn）M，由于M中不含量詞總可以把它變換成合取范式。無論是前束標準型還是合取范式都是與原來的合式公式等值的。2024/2/8史忠植人工智能：自動推理99SKOLEM標準型

前束范式

(Q1x1)…(Qnxn)M(x1,…,xn)前束形==(前綴){母式}

量詞串

無量詞公式定理：任何公式G都等價于一個前束范式Skolem函數(shù)：存在量詞不出現(xiàn)在全稱量詞的轄域內(nèi),此時只要用一個新的個體常量(稱為Skolem常量)替換受該存在量詞約束的變元就可消去存在量詞存在量詞位于一個或多個全稱量詞的轄域內(nèi).此時需要Skolem函數(shù),該函數(shù)的變元就是由那些全稱量詞所約束的全稱量詞量化的變量.Skolem函數(shù)所使用的函數(shù)符號必須是新的.2024/2/8史忠植人工智能：自動推理100SKOLEM標準型Skolem標準型：沒有存在量詞的公式。設G是一階邏輯中的公式，將其化為Skolem標準型，母式M給出的子句集S稱為公式G的子句集2024/2/8史忠植人工智能：自動推理101化為子句集謂詞公式化為子句形的步驟

x[P(x)[y[P(y)P(f(x,y))]~y[Q(x,y)P(y)]]](1)消去蘊含符號:PQ~PQ

x[~P(x)[y[~P(y)P(f(x,y))]~y[~Q(x,y)P(y)]]](2)減少否定符號的轄域,把“~”移到緊靠謂詞的位置上~(~P)P~(PQ)~P~Q~(PQ)~P~Q~(x)P(x)~P~(x)P(x)~P

x[~P(x)[y[~P(y)P(f(x,y))]y[Q(x,y)~P(y)]]]2024/2/8史忠植人工智能：自動推理102化為子句集(3)變量標準化:重新命名變元名,使不同量詞約束的變元有不同的名字.

x[~P(x)[y[~P(y)P(f(x,y))]w[Q(x,w)~P(w)]]](4)消去存在量詞:

x[~P(x)[y[~P(y)P(f(x,y))][Q(x,g(x))~P(g(x))]]]2024/2/8史忠植人工智能：自動推理103化為子句集(5)化為前束形:把所有的全稱量詞移到公式的左邊,并使每個量詞的轄域包含這個量詞后面公式的整個部分.即得前束形上例變?yōu)?

x

y[~P(x)[[~P(y)P(f(x,y))][Q(x,g(x))~P(g(x))]]](6)把母式化為合取范式:上例變?yōu)?

x

y[[~P(x)~P(y)P(f(x,y))] [~P(x)Q(x,g(x))] [~P(x)~P(g(x))]]2024/2/8史忠植人工智能：自動推理104化為子句集(7)消去全稱量詞:[[~P(x)~P(y)P(f(x,y))][~P(x)Q(x,g(x))][~P(x)~P(g(x))]](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))2024/2/8史忠植人工智能：自動推理105化為子句集一個子句內(nèi)的文字可含有變量,但這些變量總是被理解為全稱量詞量化的變量G與其子句集S并不等值.但是在不可滿足的意義下兩者是等價的.而且G是S的邏輯推論,SG.反過來不成立2024/2/8史忠植人工智能：自動推理106謂詞邏輯的子句形定理:若G是給定的公式,而相應的子句集為S,則G是不可滿足的當且僅當S是不可滿足的推論：設G=G1…Gn,Si

是Gi的Skolem標準型，令S=Si…Sn，則，G是不可滿足的當且僅當S是不可滿足的。2024/2/8史忠植人工智能：自動推理107子句集例對所有的x,y,z來說,如果y是x父親,z是y的父親,則z是x的祖父.又知道每個人都有父親,試問對某個人來說,誰是他的祖父?引入謂詞:P(x,y):表示x是y的父親Q(x,y):表示x是y的祖父A1:(x)(y)(z)(P(x,y)P(y,z)Q(x,z))SA1:~P(x,y)~P(y,z)Q(x,z)A2:(y)(x)P(x,y)SA2:P(f(y),y)2024/2/8史忠植人工智能：自動推理108子句集例B:(x)(y)Q(x,y)(要證的結論)S~B:~Q(x,y)ANS(x)其中ANS(x)是人為增加的,在推理過程中,ANS(x)變量x同Q(x,y)中的x作同樣的變換,當推理結束的時候,ANS(x)中的變量x便給出了問題的解答。因此:S=SA1SA2

S~B2024/2/8史忠植人工智能：自動推理109置換和合一置換和合一是為了處理謂詞邏輯中子句之間的模式匹配而引進.定義:

置換是形如

{t1/v1,t2/v2,…,tn/vn}

的一個有限集.其中vi是變量,而ti是不同于vi的項(常量,變量,函數(shù)),且vi

vj(i

j)

,

i,j=1,…,n例子：{a/x,w/y,f(s)/z},{g(x)/x}是置換;{x/x},{y/f(x)}不是置換;2024/2/8史忠植人工智能：自動推理110置換定義：不含任何元素的置換稱為空置換，記為

定義:設={t1/v1,t2/v2,…,tn/vn}是一個置換，E是一個表達式。將E中出現(xiàn)的每一個變量符號vi（1

in）,都用項ti置換，這樣得到的表達式記為E，稱E為E的例。2024/2/8史忠植人工智能：自動推理111置換例子：E=P(x,y,z),={a/x,f(b)/y,c/z}E=P(a,f(b),c)E=P(x,g(y),h(x,z)),={a/x,f(b)/y,g(w)/z}E=P(a,g(f(b)),h(a,g(w)))E=P(x,y,z),={y/x,z/y}E=P(y,z,z).EP(z,z,z).(同時)2024/2/8史忠植人工智能：自動推理112置換的復合（乘積）定義：

設={t1/x1,t2/x2,…,tn/xn}和

={u1/y1,u2/y2,…,um/ym}是兩個置換,

也是一個置換,可定義為:先作置換:{t1

/x1,t2

/x2,…,tn

/xn,u1/y1,u2/y2,…,um/ym}若:yi

(x1,x2,…,xn)則刪除ui/yi若:ti

=xi,則刪除ti

=xi所得的置換稱為

和的復合或乘積,記為?

2024/2/8史忠植人工智能：自動推理113置換的復合（乘積）例子:E=P(x,y,z)={a/x,f(z)/y,w/z}E=P(a,f(z),w)={t/z,g(b)/w}E=P(a,f(t),g(b))={a/x,f(t)/y,g(b)/z}2024/2/8史忠植人工智能：自動推理114置換的復合（乘積）定理：設

和

是兩個置換,E是表達式，則E(

)=(E

)

設,,是三個置換,則有:

置換滿足結合率:(?)?=?(

?)

置換的交換率不成立

?=?=2024/2/8史忠植人工智能：自動推理115合一定義:

設有公式集E={E1,...,En}和置換,使得:E1=E2=…=En

則稱E1,...,En是可合一的,并且稱為一合一置換.也稱為{E1,…,En}的合一子(unifier).定義：如果對{E1,…,En}存在這樣的合一子,則稱集合{E1,…,En}是可合一的.2024/2/8史忠植人工智能：自動推理116合一例1:E={P(a,y),P(x,f(b))},={a/x,f(b)/y}.E={P(a,b),P(x,f(b))}合一子不一定唯一E={P(a,y),P(x,f(b))}

1={a/x,f(b)/y}(唯一)E={P(x,y),P(x,f(b))}

1={a/x,f(b)/y}(不唯一)

2={b/x,f(b)/y}2024/2/8史忠植人工智能：自動推理117最一般合一定義:設是公式集E的一個合一,如果對于任一個合一,都存在置換使得:=?,則稱是公式集E的最一般合一置換,記為mgu(mostgeneralunifier)2024/2/8史忠植人工智能：自動推理118最一般合一例子:E={P(x,y),P(x,f(b))}

1={a/x,f(b)/y}

2={b/x,f(b)/y}

={f(b)/y}

1=

{a/x}

2=

{b/x}2024/2/8史忠植人工智能：自動推理119合一算法(1)令k=0,W0=W(W={E1,E2}),

0=

(2)如果Wk已經(jīng)合一,則算法停止,

k=mgu

否則，求出Wk的差異集Dk(3)如果Dk中存在元素xk,

tk,且xk不在tk中出現(xiàn),則轉(4)；否則不可合一，停止(4)令

k+1=

k?{tk/xk}

W

k+1=W

k{tk/xk}=W

k+1(5)k=k+1

然后轉(2)2024/2/8史忠植人工智能：自動推理120合一算法換名:{P(f(x),x),P(x,a)};如果不換名：D={f(x),x}.換名:{P(f(y),y),P(x,a)};mgu:{f(a)/x,a/y}2024/2/8史忠植人工智能：自動推理121合一算法求W={P(a,x,f(g(y))),P(z,f(z),f(u))}的mgu.D0={a,z}.

1=

{a/z}={a/z}.W1=W0

1={P(a,x,f(g(y))),P(a,f(a),f(u))}D1={x,f(a)}.

2=

1{f(a)/x}={a/z,f(a)/x}.W2=W1

2={P(a,f(a),f(g(y))),P(a,f(a),f(u))}D2={g(y),u}.

3=

2{g(y)/u}={a/z,f(a)/x,g(y)/u}W3=W2

3={P(a,f(a),f(g(y)))}

3是mgu.2024/2/8史忠植人工智能：自動推理122合一算法求W={Q(f(a),g(x)),Q(y,y)}的mgu.D0={f(a),y}.

1=

{f(a)/y}={f(a)/y}.W1=W0

1={Q(f(a),g(x)),Q(f(a),f(a))}D1={g(x),f(a)}.不可合一,沒有mgu.2024/2/8史忠植人工智能：自動推理123合一算法求W={P(f(y),y),P(x,a)}的mgu.D0={f(y),x}.

1=

{f(y)/x}={f(y)/x}.W1=W0

1={P(f(y),y),P(f(y),a)}D1={y,a}.

2=

1{a/y}={f(y)/x}{a/y}={f(a)/x,a/y}.W2=W1

2={P(f(a),a)}

2是mgu.2024/2/8史忠植人工智能：自動推理124合一算法性質：若W是關于表達式的有限非空可合一集合，則合一算法將在第（2）步結束，并且最后的

k是W的mgu。若一組表達式E1,…,En是可合一的，則它們的mgu除了相差一個改名外，是唯一確定。2024/2/8史忠植人工智能：自動推理125歸結式定義:設C1和C2是兩個無公共變量的子句,L1和L2分別是C1和C2的文字,如果L1和~L2有mgu:,則:(C1-{L1})(C2-{L2})

稱為C1和C2的一個二元歸結式,而L1L2稱為被歸結的文字若R(C1,C2)是C1,C2的二元歸結式,則:

C1C2

=>R(C1,C2)2024/2/8史忠植人工智能：自動推理126歸結式--例子C1:P(x)Q(x)C2:~P(a)R(x)重命名C2:~P