AI第3章-確定性推理

ArtificialIntelligence(AI)

人工智能第3章確定性推理1、推理的基本概念2、搜索策略3、自然演繹推理4、歸結(jié)演繹推理5、基于規(guī)則的演繹推理內(nèi)容提要表示問題是為了進一步解決問題。有了知識的表示方法之后,就需要有解決問題的方法。從問題表示到問題解決，有個求解過程---搜索過程。這一過程中，需要采用適當?shù)乃阉骷夹g(shù)，包括各種規(guī)則、過程和算法等推理技術(shù)，力求找到問題的解答。

搜索---尋找一條從初始問題到問題解的路徑。

關(guān)鍵是如何利用知識，盡可能有效地找到問題的解(最佳解)。即，通過推理方法進行“解”的搜索。一、推理的基本概念

什么是推理

推理方法及其分類

推理的控制策略及其分類1、什么是推理所謂推理，就是按照某種策略，由已知判斷，推出另一個判斷的思維過程。人工智能中，推理是由程序?qū)崿F(xiàn)的，稱之為推理機。智能系統(tǒng)的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定與否，推理可分為：

確定性推理（第3章）

不確定性推理（第4章）⑴、推理的方法演繹、歸納、類比、確定、不確定、單調(diào)、非單調(diào)、啟發(fā)式、非啟發(fā)式。⑵、推理的控制策略如何使用領(lǐng)域知識，使推理過程盡快達到目標的策略。推理的控制策略又可分為：搜索策略、推理策略。2、推理的兩個基本問題⑴、按推理的邏輯基礎分類

演繹推理從已知的一般性知識出發(fā)，推出蘊含在已知知識中，適合于某種個別情況的結(jié)論。是一種由一般到個別的推理方法,其核心是三段論。

歸納推理一種由個別到一般的推理方法。

類比歸納推理在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它們在其他屬性上也相同或相似的一種歸納推理。3、推理方法的分類假言三段論：A→B，B→C?A→C三段論通常由一個大前提、一個小前提和一個結(jié)論三部分組成。

大前提是已知的一般性知識，或推理過程得到的判斷。

小前提是關(guān)于某種具體情況，或某個具體實例的判斷。

結(jié)論是由大前提推出的，并且適合于小前提的判斷。①演繹推理例，有如下三個判斷：

a、計算機系的學生都會編程序；（一般性知識）

b、程強是計算機系的一位學生；（具體情況）

c、程強會編程序。（結(jié)論）三段論推理：其中，a是大前提；b是小前提；c是經(jīng)演繹推出的結(jié)論?？梢姡航Y(jié)論是蘊含在大前提中的。---按照所選事例的廣泛性：（完全、不完全）

完全歸納推理在進行歸納時，考察相應事物的全部對象，根據(jù)這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。

不完全歸納推理在進行歸納時，僅考察相應事物的部分對象，即得出關(guān)于該事物的結(jié)論。②歸納推理---按照推理所使用的方法：（枚舉\類比\統(tǒng)計\差異歸納）

枚舉歸納推理在進行歸納時，若已知某類事物的有限可數(shù)個具體事物都具有某種屬性，則可推出該類事物都具有此種屬性。

例，設有如下事例：王強是計算機系學生，會編程序；高華是計算機系學生，會編程序；

……。當這些具體事例足夠多時，即可歸納出一個一般性的知識：凡是計算機系的學生，就一定會編程序。

若兩個(或兩類)事物有許多屬性相同或相似，推出其在其他屬性上也相同或相似。例如，設A、B分別是兩類事物的集合：A={a1,a2,…}，B={b1,b2,…}設ai與bi總是成對出現(xiàn)，且當ai有屬性P時，bi就有屬性Q與之對應，即：P(ai)→Q(bi)（i=1,2,…..）。當A與B中有一新的元素對出現(xiàn)時，若已知a’有屬性P，b’有屬性Q，則類比歸納出結(jié)論：P(a')→Q(b')

類比歸納推理的基礎是相似原理，其可靠程度取決于兩個或兩類事物的相似程度,及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關(guān)程度。③類比歸納推理演繹推理是在已知領(lǐng)域內(nèi)一般性知識的前提下，通過演繹，求解一個具體問題或者證明一個結(jié)論的正確性。其所得出的結(jié)論實際上早已蘊含在一般性知識的前提中，演繹推理不過是將已有事實揭露出來，因而不能增值新知識。歸納推理所推出的結(jié)論并未包含在前提內(nèi)容中。這種由個別事物或現(xiàn)象推出一般性知識的過程，是增值新知識的過程。演繹推理與歸納推理的區(qū)別：⑵、按推理過程所用知識的確定性分類

確定性推理

不確定性推理⑶、按推理過程推出的結(jié)論是否單調(diào)增加分類

單調(diào)推理

非單調(diào)推理⑷、按推理過程是否利用問題的啟發(fā)性知識分類

啟發(fā)式推理

非啟發(fā)式推理⑴、按推理的邏輯基礎分類推理過程不僅依賴于所用的推理方法，同時也依賴于推理的控制策略。

推理的控制策略是指如何使用領(lǐng)域知識，使推理過程盡快達到目標的策略。推理的控制策略可分為：搜索策略、推理策略。4、推理的控制策略及其分類

在知識庫中尋找可利用的知識，構(gòu)造一條代價較小的推理路線，主要解決推理線路、推理效果、推理效率等問題。①按是否使用啟發(fā)式信息可分為：

盲目搜索

啟發(fā)式搜索②按問題的表示方式可分為：

狀態(tài)空間搜索

與或樹搜索⑴、搜索策略包括推理方向控制、求解、限制、沖突消解等策略。推理方向控制策略：用于確定推理的控制方向,可分為正向推理、

逆向推理、混合推理。求解策略：指僅求一個解，還是求所有解或最優(yōu)解等。限制策略：指對推理的深度、寬度、時間、空間等進行的限制。沖突消解策略：當推理過程有多條知識可用時，如何從多條可用知識中選出一條最佳知識用于推理的策略。⑵、推理策略

正向推理從已知事實出發(fā)，正向使用推理規(guī)則。(數(shù)據(jù)驅(qū)動推理\前向鏈推理)從用戶提供的初始已知事實出發(fā)，在知識庫中找出當前可適用的知識，構(gòu)成可適用的知識集KS；然后按某種沖突消解策略，從KS中選出一條知識進行推理，并將推出的新事實加入到數(shù)據(jù)庫DB中，作為下一步推理的已知事實（中間事實）。在此之后，再從知識庫中選取可適用的知識進行推理。重復進行這一過程，直到求得所要求的解。①推理方向控制策略●如何根據(jù)已知事實，到知識庫中選取可用知識？●當知識庫中有多條知識可用時，應該先使用那一條知識？這些問題涉及到了知識的匹配方法和沖突消解策略。優(yōu)點：比較直觀，允許用戶主動提供有用的事實信息，適合于診斷、設計、預測、監(jiān)控等領(lǐng)域的問題求解。缺點：推理無明確目標，求解問題時可能會執(zhí)行許多與解無關(guān)的操作，導致推理效率較低。

逆向推理從某個假設目標出發(fā)，逆向使用推理規(guī)則。(目標驅(qū)動\逆向鏈)

首先選定一個假設目標，然后尋找支持該假設的證據(jù)。若所需的證據(jù)都能找到，說明原假設成立；若找不到所需證據(jù),則說明原假設不成立，需要另作新的假設。優(yōu)點：無需尋找和使用那些與假設目標無關(guān)的信息和知識，推理過程的目標明確，有利于向用戶提供解釋。（在診斷性專家系統(tǒng)中較為有效）缺點：當用戶對解的情況認識不請時，由系統(tǒng)自主選擇假設目標的盲目性比較大，若選擇不好，可能需要多次提出假設，會影響系統(tǒng)效率。

混合推理將正向推理與逆向推理結(jié)合起來所進行的推理，是一種解決較復雜問題的方法。三種類型：先正向后逆向：先進行正向推理，從已知事實出發(fā)推出部分結(jié)果，然后再用逆向推理對這些結(jié)果進行證實或提高其可信度。先逆向后正向：先進行逆向推理，從假設目標出發(fā)推出一些中間假設，然后再用正向推理對這些中間假設進行證實。雙向混合：正向推理和逆向推理同時進行，使推理過程在中間的某一步結(jié)合起來。內(nèi)容提要1、推理的基本概念2、搜索策略3、自然演繹推理4、歸結(jié)演繹推理5、基于規(guī)則的演繹推理二、搜索策略

搜索的基本概念

狀態(tài)空間的搜索策略

與/或樹的搜索策略

搜索的完備性與效率⑴、什么是搜索搜索是人工智能中的一個基本問題，與推理密切相關(guān)。搜索策略的優(yōu)劣,將直接影響智能系統(tǒng)的性能與推理效率。搜索的定義：根據(jù)經(jīng)驗，利用已有知識，按照問題的實際情況，不斷尋找可利用知識，從而構(gòu)造一條代價最小的推理路線，使問題得以解決的過程。搜索的適用情況：不良結(jié)構(gòu)或非結(jié)構(gòu)化問題；難以獲得求解所需的全部信息；沒有現(xiàn)成的算法可供求解使用。1、搜索的基本概念①按是否使用啟發(fā)式信息

盲目搜索：按預定的控制策略進行搜索，在搜索過程中獲得的中間

信息并不改變控制策略。

啟發(fā)式搜索：在搜索中加入了與問題有關(guān)的啟發(fā)性信息，用于指導

搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優(yōu)解。②按問題的表示方式

狀態(tài)空間搜索：用狀態(tài)空間法求解問題進行的搜索。

與或樹搜索：用問題歸約法求解問題進行的搜索。⑵、搜索的類型

狀態(tài)空間搜索的基本思想

圖搜索的一般過程

狀態(tài)空間的盲目搜索廣度優(yōu)先搜索、

深度優(yōu)先搜索、代價樹搜索。

狀態(tài)空間的啟發(fā)式搜索啟發(fā)性信息和估價函數(shù)、A算法和A*算法。2、狀態(tài)空間的搜索策略①先將問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點。②然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。

若出現(xiàn)，則搜索成功，找到了問題的解；

若未出現(xiàn)，則再從已生成的子節(jié)點中選擇一個節(jié)點作為當前擴展節(jié)點。③重復上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中，或者沒有可供操作的節(jié)點為止。對一個節(jié)點進行“擴展”---指對該節(jié)點用某個可用操作進行作用，生成該節(jié)點的一組子節(jié)點。⑴、狀態(tài)空間搜索的基本思想OPEN表：未擴展節(jié)點表，用于存放剛(新)生成節(jié)點。CLOSED表：已擴展節(jié)點表，用于存放已經(jīng)擴展或?qū)⒁獢U展節(jié)點。S：表示問題的初始狀態(tài)。（起始節(jié)點）G：表示搜索過程所得到的搜索圖。M：表示當前擴展節(jié)點新生成的、且不是自己先輩的子節(jié)點集。狀態(tài)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號約定3.1圖搜索策略（GraphSearch）

圖搜索控制可看成是一種在圖中尋找路徑的方法。

初始節(jié)點和目標節(jié)點分別代表初始數(shù)據(jù)庫和滿足終止條件的目標數(shù)據(jù)庫。求得將一個數(shù)據(jù)庫變換為另一數(shù)據(jù)庫的規(guī)則序列問題,等價于求得圖中的一條路徑問題。⑴將初始節(jié)點S放入未擴展節(jié)點表OPEN表，并建立當前僅包含S的圖G；⑵檢查OPEN表是否為空，若為空，則問題無解，失敗退出；⑶將OPEN表的第一個節(jié)點取出放入已擴展節(jié)點表CLOSED表，并記該節(jié)點為節(jié)點n；⑷考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出。此時的解為追蹤圖G中沿著指針（步驟6中設置的指針）從n到初始節(jié)點S的路徑。(5)擴展節(jié)點n，生成一組子節(jié)點。把這些子節(jié)點中不是節(jié)點n先輩的那部分子節(jié)點記入集合M，并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中。1、圖搜索的一般過程(6)針對M中子節(jié)點的不同情況，分別作如下處理：①對那些沒有在G中出現(xiàn)過的M成員，設置一個指向其父節(jié)點(即節(jié)點n)的指針，并把它放入OPEN表。（新生成的）②對那些原來已在G中出現(xiàn)過，但還沒有被擴展的M成員，確定是否需要修改它指向父節(jié)點(n)的指針。(已生成但未擴展的)③對那些先前已在G中出現(xiàn)過，并已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。(已生成也擴展過的)(7)按某種策略,對OPEN表中的節(jié)點進行排序。(8)轉(zhuǎn)第(2)步。⑴上述過程是狀態(tài)空間的一般圖搜索算法，具有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的一個特例。⑵各種搜索策略的主要區(qū)別在于“對OPEN表中節(jié)點的排列順序不同”。

例如，廣度優(yōu)先搜索把先生成的子節(jié)點排在前面，而深

度優(yōu)先搜索則把后生成的子節(jié)點排在前面。2、圖搜索一般過程的幾點說明⑶在第(6)步針對M中子節(jié)點的不同情況進行處理時，若發(fā)生第②種情況，那么，這個M中的節(jié)點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？一般是由原始節(jié)點到該節(jié)點路徑上所付出的代價來決定,哪一條路徑付出的代價小，相應的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到該節(jié)點路徑上的代價，是指這條路徑上的所有“有向邊”的代價之和。②對那些原來已在G中出現(xiàn)過，但還沒有被擴展的M成員，確定是否需要修改它指向父節(jié)點(n)的指針。(已生成但未擴展的)⑷若發(fā)生第③種情況，除了需要確定該子節(jié)點指向父節(jié)點的指針外，還需要確定其后繼節(jié)點指向父節(jié)點的指針。其依據(jù)也是由原始節(jié)點到該節(jié)點的路徑上的代價。⑸在搜索圖中，除初始節(jié)點外，任意一個節(jié)點都含有且只含有一個指向其父節(jié)點的指針。因此，由所有節(jié)點及其指向父節(jié)點的指針所構(gòu)成的集合是一棵樹，稱為搜索樹。③對那些先前已在G中出現(xiàn)過，并已經(jīng)擴展了的M成員，確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針。(已生成也擴展過的)⑹在搜索過程的第(4)步，一旦某個被考察的節(jié)點是目標節(jié)點，則搜索過程成功結(jié)束。此時，由初始節(jié)點到目標節(jié)點路徑上的所有操作就構(gòu)成了該問題的解，而路徑由過程第(6)步所形成的指向父節(jié)點的指針來確定。⑺如果搜索過程終止在第(2)步，即沒有達到目標，且OPEN表中已無可供擴展的節(jié)點，則失敗結(jié)束。3.2盲目搜索

不需要重新安排OPEN表的搜索叫做“無信息搜索”或“盲目搜索”。（實際上是對解空間的遍歷）包括：寬(廣)度優(yōu)先搜索深度優(yōu)先搜索等代價搜索盲目搜索只適用于求解比較簡單的問題。定義：以接近起始節(jié)點的程度逐層擴展節(jié)點的搜索方法。特點：一種高代價搜索，但若有解存在，則必能找到。3.2.1寬度優(yōu)先搜索（Breadth-firstsearch）搜索是逐層進行的，在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。(解空間的橫向遍歷)從初始節(jié)點S開始逐層向下擴展，在第n層節(jié)點還未全部搜索完之前，不進入第n+1層節(jié)點的搜索。

未擴展節(jié)點表（OPEN表）中的節(jié)點，總是按進入的先后排序，先進入的節(jié)點排在前面，后進入的節(jié)點排在后面。1、寬度優(yōu)先搜索的基本思想⑴將初始節(jié)點S放入OPEN表中；⑵如果OPEN表為空，則問題無解，失敗退出；⑶將OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；⑷考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；⑸若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；⑹擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每一個子節(jié)點設置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。2、寬度優(yōu)先搜索算法流程思考：與原始算法比較異同，寬度優(yōu)先的體現(xiàn)？優(yōu)點：能夠保證在搜索樹中，找到一條通向目標節(jié)點的最短路徑。寬度優(yōu)先搜索算法流程-動態(tài)：八數(shù)碼難題：

在3×3的方格棋盤上，分別放置了標有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0，目標狀態(tài)Sg，如下圖所示。要求用寬度優(yōu)先搜索策略，尋找從初始狀態(tài)到目標狀態(tài)的解路徑。56741382S056748321Sg3、寬度優(yōu)先搜索的例子八數(shù)碼難題的寬度優(yōu)先搜索樹：八數(shù)碼難題的寬度優(yōu)先搜索樹-動態(tài)：⑴對任意一個可擴展的節(jié)點，總是按照固定的操作符順序?qū)ζ溥M行擴展（空格左移、上移、右移、下移）。⑵在對任一節(jié)點進行擴展的時候，如果所得的某個子節(jié)點（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復畫出（不送入OPEN表）。因此，寬度優(yōu)先搜索的本質(zhì)是：

以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照寬度優(yōu)先的原則，生成一棵搜索樹。（橫向搜索）4、上述寬度優(yōu)先算法中需注意的兩個問題：優(yōu)點：只要問題有解，用寬度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。缺點：盲目性較大，當目標節(jié)點距初始節(jié)點較遠時，將會產(chǎn)生許多無用節(jié)點，搜索效率低。5、寬度優(yōu)先搜索的特點3.2.2深度優(yōu)先搜索（Depth-firstsearch）首先擴展最新產(chǎn)生的（即最深的）節(jié)點，深度相等的節(jié)點可以任意排列。定義節(jié)點的深度如下：

起始節(jié)點（即根節(jié)點）的深度為0。

任何其他節(jié)點的深度，等于其父輩節(jié)點深度加1。特點：為防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)點擴展的最大深度---深度界限。擴展最深(新)節(jié)點的結(jié)果,使得搜索沿著狀態(tài)空間某條單一的路徑，從起始節(jié)點向下進行。只有當搜索到達一個沒有后裔的狀態(tài)時，才考慮另一條替代的路徑。(解空間縱向遍歷)

⑴從初始節(jié)點S開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察；⑵若該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點,然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察；⑶依此向下搜索，直到某個子節(jié)點既不是目標節(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟節(jié)點進行考察。1、深度優(yōu)先搜索的基本思想

2、深度優(yōu)先搜索算法流程⑴將初始節(jié)點S放入OPEN表中；⑵如果OPEN表為空，則問題無解，失敗退出；⑶將OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；⑷考察節(jié)點n是否為目標節(jié)點。若是，則得到問題的解，成功退出；⑸若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；⑹擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每一個子節(jié)點設置指向父節(jié)點的指針，然后轉(zhuǎn)第⑵步。3、深度優(yōu)先搜索的例子八數(shù)碼問題深度優(yōu)先搜索樹？12384567目標狀態(tài)

Sg12384567初始狀態(tài)S0首先擴展最新產(chǎn)生的(最深的)節(jié)點，若目標節(jié)點不在當前搜索的分支上？

寬度優(yōu)先搜索是將節(jié)點n的子節(jié)點放入到OPEN表的尾部，而深度優(yōu)先搜索是把節(jié)點n的子節(jié)點放入到OPEN表的首部。在深度優(yōu)先搜索中，搜索一旦進入某個分支，就將沿著該分支一直向下搜索。如果目標節(jié)點恰好在此分支上，則可較快地得到解。但是，如果目標節(jié)點不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解。深度優(yōu)先搜索本質(zhì)：以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹。深度優(yōu)先搜索與寬度優(yōu)先搜索的唯一區(qū)別：4、有界深度優(yōu)先搜索動機：為了防止搜索過程沿著無益的路徑擴展下去，往往給出一個節(jié)

點擴展的最大深度，即深度界限。思想：對狀態(tài)空間的深度優(yōu)先搜索引入搜索深度界限，設為dm，當搜索深度達到了深度界限而仍未出現(xiàn)目標節(jié)點時，就換一個分支進行搜索。

即，沿著一條路徑進行下去，直到深度界限為止，然后再考慮

只有最后一步有差別的相同深度或較淺深度可供選擇的路徑，接著再考慮最后兩步有差別的那些路徑。八數(shù)碼難題：dm=55、注意問題如果問題有解，且其路徑長度≤dm

，則上述搜索過程一定能求得解。但若解的路徑長度>dm，則上述搜索過程就得不到解。這說明在有界深度優(yōu)先搜索中，深度界限的選擇是很重要的。要恰當?shù)亟o出dm的值是比較困難的。否則即使能求出解，其也不一定是最優(yōu)解。3.2.3等代價搜索有些問題并不要求應用算符序列為最少的解，而是要求具有某些特性的解。定義：是寬度優(yōu)先搜索的一種推廣，不是沿著等長度路徑斷層進行擴展，而是沿著等代價路徑斷層進行擴展。搜索樹中每條連接弧

線上標識有代價,時間、距離等花費。算法應用的條件：該算法是針對代價樹的算法。為了采用該算法對圖進行搜索，必須先將圖轉(zhuǎn)換為代價樹。代價樹：邊（連接弧線）上標有代價(或費用)的搜索樹。在代價樹中，若用g(x)表示從初始節(jié)點S到節(jié)點x的代價，用c(x1,x2)表示從父節(jié)點x1到子節(jié)點x2的代價，則有：g(x2)=g(x1)+c(x1,x2)代價樹搜索：考慮邊的代價的搜索方法，目的是為了找到一條代價最小的解路徑。代價樹搜索方法包括：代價樹的廣度優(yōu)先搜索

代價樹的深度優(yōu)先搜索⑴、基本思想每次從OPEN表中選擇節(jié)點往CLOSED表傳送時，總是選擇其中代價最小的節(jié)點。也就是說，OPEN表中的節(jié)點在任一時刻都是按其代價從小到大排序的。代價小的節(jié)點排在前面，代價大的節(jié)點排在后面，而不管節(jié)點在代價樹中處于什么位置上。如果問題有解，代價樹的寬度優(yōu)先搜索一定可以求得解，并且求出的是最優(yōu)解。1、代價樹的寬度優(yōu)先搜索⑵、代價樹的寬度優(yōu)先搜索算法流程①把初始節(jié)點S放入OPEN表中，置S的代價g(S)=0；②如果OPEN表為空，則問題無解，失敗退出；③把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；④考察節(jié)點n是否為目標。若是，則找到了問題的解，成功退出；⑤若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；否則轉(zhuǎn)第(6)步；⑥擴展節(jié)點n，為每一個子節(jié)點都配置指向父節(jié)點的指針，計算各子節(jié)點的代價，并將各子節(jié)點放入OPEN表中。根據(jù)各子結(jié)點的代

價對OPEN表中的全部結(jié)點按由小到大的順序排序。然后轉(zhuǎn)第⑵步。設有5個城市，它們之間的交通線路如圖所示，圖中的數(shù)字表示兩個城市之間的交通費用，即代價。用代價樹的寬度優(yōu)先搜索，求從A市出發(fā)到E市，費用最小的交通路線。ABCDE434523例子：城市交通問題解：首先將交通圖轉(zhuǎn)化為代價樹。具體轉(zhuǎn)化方法如下：①從起始節(jié)點A開始，把與它直接相鄰的節(jié)點作為它的子節(jié)點。②對其他節(jié)點也做相同的處理。③若一個節(jié)點已經(jīng)為某節(jié)點的直系

先輩節(jié)點時，就不能作為這個節(jié)點的子節(jié)點。④圖中除了起始節(jié)點A之外，其它節(jié)點都可能要在代價樹中出現(xiàn)多

次，為了區(qū)分它們的多次出現(xiàn)，分別用下標1,2，……標出。交通圖的代價樹245AC1B1D1D2E1E2B2C2E3E43434235245AC1B1D1D2E1E2B2C2E3E43434235對此代價樹進行寬度優(yōu)先搜索，可得到最優(yōu)解，如圖紅線部分為最優(yōu)解，其代價為8。ABCDE434523沿代價最小的路徑搜索，即每次展開未展開節(jié)點中距離A點最近的那個節(jié)點。⑴、基本思想

與代價樹的寬度優(yōu)先搜索不同，深度優(yōu)先搜索是從剛擴展出的子節(jié)點中選擇一個代價最小的節(jié)點送入CLOSED表進行考察，而不是在整個OPEN表中選擇代價最小的。2、代價樹的深度優(yōu)先搜索⑵、代價樹的深度優(yōu)先搜索算法流程①把初始節(jié)點S放入OPEN表中，置S的代價g(S)=0；②如果OPEN表為空，則問題無解，失敗退出；③把OPEN表的第一個節(jié)點取出放入CLOSED表，并記該節(jié)點為n；④

考察節(jié)點n是否為目標節(jié)點。若是，則找到問題的解，成功退出；⑤若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；⑥擴展節(jié)點n，生成其子節(jié)點，將這些子節(jié)點按邊代價由小到大放入Open表的首部，并為每一個子節(jié)點設置指向父節(jié)點的指針。然后轉(zhuǎn)第②步。上述幾種搜索方法的本質(zhì)是：以初始節(jié)點為根節(jié)點，按照既定的策略對狀態(tài)空間圖進行遍歷，并希望能夠盡早發(fā)現(xiàn)目標節(jié)點。由于對狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點較多，效率不高。狀態(tài)空間的盲目搜索小結(jié)：盲目搜索的效率低，耗費過多的計算時間和空間，容易產(chǎn)生組合爆炸。若能找到一種方法用于排列待擴展節(jié)點的順序，即選擇最有希望的節(jié)點加以擴展，則搜索效率將會大為提高。(許多情況下，可通過檢測來確定合理的順序)下面介紹的搜索方法就是優(yōu)先考慮這類檢測，稱這類搜索為啟發(fā)式搜索(heuristicsearch)或有信息搜索(informedsearch)。3.3啟發(fā)式搜索在盲目搜索中找到一個解，所需要擴展的節(jié)點數(shù)目可能是很大的，因為這些節(jié)點的擴展次序是隨意的，而且沒有利用已解決問題的任何特性。因此，除了那些最簡單的問題之外，一般都需要占用很多時間或空間（或兩者均有），這種結(jié)果是組合爆炸的一種表現(xiàn)形式。3.3.1啟發(fā)式搜索策略和估價函數(shù)具體問題領(lǐng)域的信息常?？梢杂脕砗喕阉?。假設初始狀態(tài)、算符和目標狀態(tài)的定義都是完全確定的，然后決定一個搜索空間。因此，問題就在于如何有效搜索這個給定空間。進行這種搜索的技術(shù)一般需要某些有關(guān)具體問題領(lǐng)域特性的信息，把這類特性信息稱為啟發(fā)信息，并把利用啟發(fā)信息的搜索方法叫做“啟發(fā)式搜索方法”。啟發(fā)式搜索：采用問題自身的特性信息，以指導搜索朝著最有希望的方向前進。啟發(fā)性信息：與具體問題求解過程有關(guān)，可指導搜索過程朝著最有希望方向前進的控制信息。(減少搜索范圍，降低問題復雜度)

啟發(fā)信息的啟發(fā)能力越強，擴展的無用結(jié)點就越少。

強：降低搜索工作量，但可能導致找不到最優(yōu)解。

弱：一般導致工作量加大，極限情況下變?yōu)槊つ克阉鳎赡苷业阶顑?yōu)解。①幫助確定擴展節(jié)點的信息用于決定要擴展的下一個節(jié)點（最有希望的節(jié)點），以免像在寬度優(yōu)先或深度優(yōu)先搜索中那樣盲目地擴展。(擴展誰)②幫助決定哪些后繼節(jié)點應被生成的信息在擴展一個節(jié)點的過程中，用于決定要生成哪些后繼節(jié)點，以免盲目生成所有節(jié)點。(生成誰)③決定在擴展一個節(jié)點時哪些節(jié)點應從搜索樹上刪除的信息利用第一種啟發(fā)信息的狀態(tài)空間搜索算法，即選擇“最有希望”的節(jié)點作為下一個被擴展的節(jié)點。稱為有序搜索(orderedsearch)。

估算節(jié)點希望程度的方法為估價函數(shù)。(重排每步open表節(jié)點順序)啟發(fā)性信息分類（按用途）:估價函數(shù)：用于評估節(jié)點重要性（希望程度）的函數(shù)。一般形式為：

f(x)=g(x)+h(x)其中，g(x)---從初始節(jié)點S0到節(jié)點x的代價；h(x)---啟發(fā)函數(shù)。對從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的代價的估計，體現(xiàn)了問題的啟發(fā)性信息。設問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示。估價函數(shù)為：f(n)=d(n)+W(n)

d(n)：表示節(jié)點n在搜索樹中的深度。

W(n)：表示節(jié)點n中“不在位”的數(shù)碼個數(shù)。計算初始狀態(tài)S0的估價函數(shù)值f(S0)。例子：八數(shù)碼難題56741382S056748321Sg解：取g(n)=d(n)，h(n)=W(n)①說明是用從S0到n的路徑上的單位

代價表示實際代價。②用結(jié)點n中“不在位”的數(shù)碼個數(shù)作為啟發(fā)信息。③一般來說，某節(jié)點中的“不在位”的數(shù)碼個數(shù)越多，說明它離目標節(jié)點越遠（代價的估計）。④對初始節(jié)點S0，d(S0)=0，W(S0)=3。因此，f(S0)=0+3=3

56741382S056748321Sg有序搜索又稱為“最佳優(yōu)先搜索”，它總是選擇最有希望的節(jié)點作為下一個要擴展的節(jié)點。

實質(zhì)：選擇OPEN表中具有最小f值的節(jié)點作為下一個要擴展的節(jié)點。

尼爾遜（Nilsson）曾提出一個有序搜索的基本算法，估價函數(shù)f是這樣確定的：一個節(jié)點的希望程度越大，其f值就越小。3.3.2有序搜索！被選為擴展的節(jié)點，是估價函數(shù)最小的節(jié)點。例子：八數(shù)碼難題估價函數(shù)設置：f(n)=d(n)+W(n)

d(n):節(jié)點n的深度；W(n):錯放的棋子數(shù)。12384567（目標狀態(tài)）12384567（初始狀態(tài)）由圖可見，這里所求得的解答路徑和用其它搜索方法找到的解答路徑相同。不過，估價函數(shù)的應用顯著地減少了被擴展的節(jié)點數(shù)。(若只用估價函數(shù)f(n)=d(n)，即得到寬度優(yōu)先搜索過程)

正確選擇估價函數(shù)，對確定搜索結(jié)果具有決定性作用。使用不能識別某些節(jié)點真實希望的估價函數(shù)，會形成非最小代價路徑；而使用一個過多地估計了全部節(jié)點希望的估價函數(shù)(如寬度優(yōu)先搜索方法得到的估價函數(shù)一樣)又會擴展過多的節(jié)點。算法比較：八數(shù)碼難題的深度優(yōu)先搜索、寬度優(yōu)先搜索和啟發(fā)式搜索三種搜索方法的比較列于表中。136啟發(fā)式搜索3418深度優(yōu)先搜索4626寬度優(yōu)先搜索生成節(jié)點數(shù)擴展節(jié)點數(shù)搜索算法有序搜索小結(jié)：f函數(shù)的重要性：

有序搜索的有效性直接取決于f,是提高搜索效率的關(guān)鍵；如果f不準確，可能失去最佳解，也可能失去全部解。f一般選擇策略：

搜索時間與空間的折衷；保證有解或有最佳解。①最優(yōu)解答狀態(tài)空間中有多條不同代價的解答路徑，求得最優(yōu)解答，如A*算法。②搜索代價與解答質(zhì)量的綜合問題類似于①，但搜索過程可能超出時間與空間的界限。在適當?shù)乃阉髦姓业綕M意解答,并限制滿意解答與最優(yōu)解答的差異程度。如：TSP問題。③最小搜索代價不考慮解答的最優(yōu)化（只有一個解答或多個解答間無差異），盡量使搜索代價最小。如：定理證明。f選擇的三種典型情況⑴、A算法定義在圖搜索算法中，如果能在搜索的每一步都利用估價函數(shù)f(n)=g(n)+h(n)對OPEN表中的節(jié)點排序，則該搜索算法為A算法。由于估價函數(shù)中帶有問題自身的啟發(fā)性信息。因此，A算法也被稱為啟發(fā)式搜索算法。⑵、A算法的類型可根據(jù)搜索過程中選擇擴展節(jié)點的范圍，將啟發(fā)式搜索算法分為：

全局擇優(yōu)搜索算法：從OPEN表的所有節(jié)點中，選擇估價函數(shù)值最小的一個節(jié)點進行擴展。

局部擇優(yōu)搜索算法：僅從剛生成的子節(jié)點中，選擇估價函數(shù)值最小的一個子節(jié)點進行擴展。3.3.3A*算法A算法(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步。(6)擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并為每一個子節(jié)點都配置指向父節(jié)點的指針。把這些子節(jié)點都送入OPEN表中，然后對OPEN表中的全部節(jié)點按估價值從小至大的順序進行排序，然后轉(zhuǎn)第(2)步。全局擇優(yōu)搜索算法流程：設問題的初始狀態(tài)S0和目標狀態(tài)Sg如圖所示。估價函數(shù)為：f(n)=d(n)+w(n)d(n)：表示節(jié)點n在搜索樹中的深度w(n)：表示節(jié)點n中“不在位”的數(shù)碼個數(shù)用全局擇優(yōu)搜索解決該問題。全局擇優(yōu)搜索算法：八數(shù)碼難題56741382S056748321Sg解：該問題的全局擇優(yōu)搜索樹如右圖所示。圖中，每個節(jié)點旁邊的數(shù)字是該節(jié)點的估價函數(shù)值。該問題的解為：

S0→S1→S2→S3→Sg局部擇優(yōu)搜索算法流程：(1)把初始節(jié)點S0放入OPEN表，計算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個節(jié)點（記為節(jié)點n）取出放入CLOSED表。(4)考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，退出。(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步。(6)擴展節(jié)點n，用估價函數(shù)f(x)計算每個子節(jié)點的估價值，并按估價值

從小到大的順序放到OPEN表中的首部，并為每一個子節(jié)點都配置指向其父節(jié)點的指針，然后轉(zhuǎn)第(2)步。A*算法是對A算法的估價函數(shù)f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法。假設f*(n)是從初始節(jié)點S出發(fā)經(jīng)過節(jié)點n達到目標節(jié)點的最小代價，估價函數(shù)f(n)是對f*(n)的估計值。且f*(n)=g*(n)+h*(n)

A*算法對A算法（全局擇優(yōu)的啟發(fā)式搜索算法）中的g(n)和h(n)分別提出如下限制：第一，g(n)是對最小代價g*(n)的估計，且g(n)>0；第二，h(n)是最小代價h*(n)的下界,即對任意節(jié)點n均有h(n)≤h*(n)。即：滿足上述兩條限制的A算法稱為A*算法。A*算法在A*算法中，g(n)比較容易得到，它實際上就是從初始節(jié)點S0到節(jié)點n的路徑代價，恒有：g(n)≥g*(n)在算法執(zhí)行過程中，隨著更多搜索信息的獲得，g(n)呈下降的趨勢。如右圖的例子：對S0擴展后g(n1)=3，g(n2)=7對n1擴展后g(n2)=6，g(n3)=5S0n137n2n332可納性的含義：對任一狀態(tài)空間圖，當從初始節(jié)點到目標節(jié)點有路經(jīng)存在時，如果搜索算法總能在有限步驟內(nèi)找到一條從初始節(jié)點到目標節(jié)點的最佳路徑，并在此路徑上結(jié)束，則稱該搜索算法是可納的。

A*算法是可納的，即它能在有限步內(nèi)終止，并找到問題的最優(yōu)解。A*算法的可納性:第一步：對于有限圖，A*算法一定會在有限步驟內(nèi)終止。第二步：對于無限圖，如果從初始節(jié)點S0到目標節(jié)點Sg有路徑存在，則A*算法也必然會終止。第三步：A*算法一定終止在最優(yōu)路徑上。A*算法的可納性證明：h(n)的確定依賴于具體問題領(lǐng)域的啟發(fā)性信息，其中h(n)≤h*(n)的限制是十分重要的，它可以保證A*算法能找到問題的最優(yōu)解。A*算法的搜索效率很大程度上取決于估價函數(shù)h(n)。一般來說，在滿足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，說明它攜帶的啟發(fā)性信息越多，A*算法搜索時擴展的節(jié)點就越少，搜索效率就越高。A*算法的最優(yōu)性:在A*算法中，每當擴展一個節(jié)點n時，都需要檢查其子節(jié)點是否已在OPEN表或CLOSED表中。對已在OPEN表中的子節(jié)點，需要決定是否調(diào)整指向其父節(jié)點的指針；對已在CLOSED表中的子節(jié)點，除需要決定是否調(diào)整其指向父節(jié)點的指針外，還需要決定是否調(diào)整其子節(jié)點的后繼節(jié)點的父指針。如果能夠保證，每當擴展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，則沒有必要再作上述檢查。h(n)的單調(diào)限制:為能夠保證，每當擴展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑，需要對啟發(fā)函數(shù)h(n)增加單調(diào)性限制。如果啟發(fā)函數(shù)滿足以下兩個條件:

h(Sg)=0;

對任意節(jié)點ni及其任一子節(jié)點nj，都有:0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點nj的邊代價，則稱h(n)滿足單調(diào)限制。證明：設A*正要擴展節(jié)點n，而節(jié)點序列S0=n0,n1,…,nk=n是由初始節(jié)點S0到節(jié)點n的最佳路徑。其中，ni是這個序列中最后一個位于CLOSED表中的節(jié)點，則上述節(jié)點序列中的ni+1節(jié)點必定在OPEN表中，由h(n)的單調(diào)條件可知：g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)所以：g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)依此類推可得：g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)=g*(n)+h(n)由于節(jié)點ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因為這時A*擴展節(jié)點n而不擴展節(jié)點ni+1，則有：

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)即g(n)≤g*(n)，g*(n)是最小代價值。所以有g(shù)(n)=g*(n)如果h(n)滿足單調(diào)條件，則當A*算法擴展節(jié)點n時，該節(jié)點就已經(jīng)找到了通往它的最佳路徑，即g(n)=g*(n)。證明：假設節(jié)點ni+1在節(jié)點ni之后立即擴展，由單調(diào)限制條件可知：

h(ni)-h(ni+1)≤c(ni,ni+1)即：(f(ni)-g(ni))-(f(ni+1)-g(ni+1))≤c(ni,ni+1)亦即：f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以：f(ni)-f(ni+1)≤0即：f(ni)≤f(ni+1)

以上兩個定理都是在h(n)滿足單調(diào)性限制的前提下才成立的。如果h(n)不滿足單調(diào)性限制，則它們不一定成立。如果h(n)滿足單調(diào)限制，則A*算法擴展的節(jié)點序列的f值是非遞減的，即f(ni)≤f(ni+1)。f(n)=g(n)+h(n)g(n)深度h(n)與目標的距離f*=g*+h*A*算法應用：八數(shù)碼難題3.4消解原理第2章中，我們已介紹了謂詞邏輯表示法（謂詞演算、謂詞公式、置換合一）的相關(guān)概念。謂詞演算中，利用前面列出的等價式和永真蘊含式，可以從已知的一些公式推導出新的公式。導出的新公式叫做定理，推導過程中使用的推理規(guī)則序列即是該定理的一個證明。本節(jié)所要介紹的“消解原理(歸結(jié)原理)”正是定理證明的基礎，是應用于“子句”的一種公式類。消解是一種可用于子句公式的重要推理規(guī)則。子句由文字的“析取”組成的公式。（任何文字的“析取式”）

文字：一個原子公式和原子公式的否定。如：P∨Q、～(P∨Q)、～P(x,f(x),y)∨Q(y)等都是子句。什么是消解、子句？文字析取組成的公式原子公式、原子公式的否定P(x1,x2,...,xn)稱為謂詞演算的原子公式子句[P∨Q、～P(x,f(x),y)∨Q(x)∨R(f(x)]如：

E1∨E2

（前提）

～E2∨E3

（前提）

E1∨E3邏輯上成立（結(jié)論）消解過程應用于“母體子句對”，以產(chǎn)生一個“導出子句”。并稱，“E1∧E3”為“E1∨E2”和“～E2∨E3”的消解式。母體子句對導出子句3.4.1子句集的求?。?步法）

說明消解過程之前，首先說明任一謂詞演算公式均可以變換為一個子句集。將謂詞公式變換為為子句集的步驟：①消去蘊涵符號②減少否定符號的管轄域③對變量標準化④消去存在量詞⑤化為前束形⑥把母式化為合取范式⑦消去全稱量詞⑧消去連詞符號∧⑨更換變量名例：將下列謂詞演算公式化為一個子句集。(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}只應用∨和～符號，以～A∨B替換AB（或AB）。⑴、消去蘊涵符號(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧～(y)[～Q(x,y)∨P(y)]}}⑵、減少否定符號的管轄域(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(y){～[～Q(x,y)∨P(y)]}}}①(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧～(y)[～Q(x,y)∨P(y)]}}每個否定符號“～”最多只用到一個謂詞符號上，并反復應用摩根定律。以～A∨～B代替～(A∧B)以～A∧～B代替～(A∨B)以A代替～(～A)以(x){～A}代替～(x)A以(x){～A}代替～(x)A將～移到后面，“全稱”改“存在”。(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(y)[Q(x,y)∧～P(y)]}}任一量詞轄域內(nèi)，受該量詞約束的變量為一啞元(虛構(gòu)變量),它可以在該轄域內(nèi)被另一個未出現(xiàn)過的變量代替,而不改變公式的真值。合式公式中變量的標準化意味著對啞元改名,以保證每個量詞有其惟一的啞元。⑶、對變量標準化②(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(y)[Q(x,y)∧～P(y)]}}(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(w)[Q(x,w)∧～P(w)]}}{w/y}(x){P(x)∧(x)Q(x)}(x){P(x)∧(y)Q(y)}如：⑷、消去存在量詞以Skolem函數(shù)代替存在量詞內(nèi)的約束變量，然后消去存在量詞。規(guī)則：

對于一個受存在量詞約束的變量，若不受全稱量詞約束,則該變量可用一個常量代替。(x)P(x)P(A)公式(y)[(x)P(x,y)]中，因存在量詞處于全稱量詞的轄域內(nèi)，則所存在的x可能依賴于y值。令這種依賴關(guān)系明顯地由函數(shù)g(y)所定義,它把每個y值映射到存在的那個的x，即x=g(y)。---Skolem函數(shù)

若該變量受全稱量詞約束，則該變量用一個S函數(shù)代替,S函數(shù)的變量即全稱量詞的量化變量。(y){(x)P(x,y)}(y){P(g(y),y)}Skolem函數(shù)替代常量或函數(shù)必須是新的，是公式中沒出現(xiàn)過的。③(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧(w)[Q(x,w)∧～P(w)]}}(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}w=g(x)為Skolem函數(shù)⑸、化為前束形(x)(y){～P(x)∨{[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}④(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}把所有全稱量詞移到公式的左邊，并使每個量詞的轄域包括這個量詞后面公式的整個部分。前束形={前綴}{母式}

全稱量詞串無量詞公式⑹、把母式化為合取范式A∨{B∧C}{A∨B}

∧{A∨C}(x)(y){[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨[Q(x,g(x))∧～P(g(x)]]}⑤(x)(y){～P(x)∨{[～P(y)∨P(f(x,y))]∧[Q(x,g(x))∧～P(g(x))]}}任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(反復應用分配律)ABCBCA(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))]}⑥(x)(y){[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}所有余下的量詞均被全稱量詞量化了。消去前綴，即消去明顯出現(xiàn)的全稱量詞。⑻、消去連詞符號∧～P(x)∨～P(y)∨P(f(x,y))～P(x)∨Q(x,g(x))～P(x)∨～P(g(x))⑦{[～P(x)∨～P(y)∨P(f(x,y))]∧[～P(x)∨Q(x,g(x))]∧[～P(x)∨～P(g(x))]}用{A,B}代替(A∧B)，消去符號∧。最后得到一個有限集，其中每個公式都是文字的析取?！痢立?、更換變量名稱⑧～P(x)∨～P(y)∨P(f(x,y))

～P(x)∨Q(x,g(x))

～P(x)∨～P(g(x))⑨

～P(x1)∨～P(y)∨P[f(x1,y)]

～P(x2)∨Q[x2,g(x2)]

～P(x3)∨～P[g(x3)]更換變量符號的名稱，使一個變量符號不出現(xiàn)在一個以上的子句中。（用x1，x2，x3代替x）3.4.2消解推理規(guī)則消解式的定義：令L1，L2為兩任意原子公式；

L1和L2具有相同的謂詞符號，但一般具有不同的變量。已知兩子句L1∨α和～L2∨β，如果L1和L2具有最一般合一者σ,那么通過消解可以從這兩個父輩子句推導出一個新子句(α∨β)σ。這個新子句叫做消解式。消解式求法:取各子句的析取，然后消去互補對。命題邏輯的消解推理舉例：假言推理：P～P∨Q(即P→Q)消解式：Q合并：P∨Q～P∨Q消解式：Q∨Q=Q重言式：P∨Q～P∨～Q消解式：Q∨～Q或P∨～P空子句(矛盾)：P～P消解式：NIL鏈式(三段論)：～P∨Q(即P→Q)～Q∨R(即Q→R)消解式：～P∨R(即P→R)3.4.3含有變量的消解式要把消解推理規(guī)則推廣到含有變量的子句，必須找到一個作用于父輩子句的置換，使父輩子句含有互補文字。例：B(x)～B(x)∨C(x)C(x)P(x)∨Q(x)～Q[f(y)]P[f(y)]置換σ={f(y)/x}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}！消解推理的常用規(guī)則，參見教材中“子句和消解式”對應表。3.4.4消解反演求解過程將要解決的問題作為一個要證明的命題，消解通過反演產(chǎn)生證明。

即,要證明某個命題，其目標公式被否定并化成子句形,然后添加到命題公式集中去,把消解反演系統(tǒng)應用于聯(lián)合集,推出一個空子句(NIL),產(chǎn)生一個矛盾，從而使定理得到證明。消解反演的證明思想，與數(shù)學中反證法的思想十分相似。給出一個公式集{S}和目標公式L，通過反證或反演來求證目標公式L。步驟如下：⑴否定L，得～L；⑵把～L添加到S中去；⑶把新產(chǎn)生的集合｛～L，S｝化成子句集；⑷應用消解原理，推導出一個表示矛盾的空子句。1、消解反演討論：

設公式L在邏輯上遵循公式集S按照定義，滿足S的每個解釋也滿足L，絕不會有滿足S的解釋能夠滿足～L的。所以，不存在能夠滿足并集“S∪{～L}”的解釋。

若一個公式集不能被任一解釋所滿足，則這個公式是不可滿足的。

因此，如果L在邏輯上遵循S，那么S∪{～L}是不可滿足的。

可證：若將消解反演，反復應用到不可滿足的子句集，則最終會產(chǎn)生空子句NIL。因此，如果L在邏輯上遵循S，那么由并集S∪{～L}消解得到的子句,最后將產(chǎn)生空子句。

反之也可證：若從S∪{～L}的子句消解得到空子句，那么L在邏輯上遵循S。例：儲蓄問題

前提：每個儲蓄錢的人都獲得利息。

結(jié)論：如果沒有利息，那么就沒有人去儲蓄錢。⑴規(guī)定原子公式：

S(x,y)表示“x儲蓄y”M(x)表示“x是錢”

I(x)表示“x是利息”

E(x,y)表示“x獲得y”⑵用謂詞公式表示前提和結(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))⑶化為子句形把前提化為子句形：(x){[(y)(S(x,y)∧M(y)][(y)(I(y)∧E(x,y))]}(x)((～[(y)(S(x,y)∧M(y))]∨((y)(I(y)∧E(x,y))))(x)(((y)(～

S(x,y)∨～

M(y))∨((y)(I(y)∧E(x,y))))(x)(((y)(～

S(x,y)∨～

M(y))∨(I(f(x))∧E(x,f(x))))Y=f(x)為Skolem函數(shù)(x)(y)(((～S(x,y))∨～M(y)∨I(f(x)))∧(～S(x,y)∨～M(y)∨E(x,f(x)))))①～S(x,y)∨～M(y)∨I(f(x))②～S(x1,y1)∨～M(y1)∨E(x1,f(x1))結(jié)論：～(x)I(x)(x)(y)(M(y)

～S(x,y))把結(jié)論的否定化為子句形：結(jié)論的否定：

～(～(x)I(x)(x)(y)(M(y)

～S(x,y)))③～I(z)④S(a,b)⑤M(b)～((x)I(x)

∨(x)(y)(～

M(y)∨

～S(x,y)))(～((x)I(x))∧(～(x)(y)(～

M(y)∨～S(x,y)))((x)(～

I(x))∧((x)(y)(M(y)∧S(x,y)))((z)(～

I(z))∧((x)(y)(M(y)∧S(x,y)))(～

I(z))∧((M(b)∧S(a,b)))把前提化為子句形：①

～S(x,y)∨～M(y)∨I(f(x))②

～S(x1,y1)∨～M(y1)∨E(x1,f(x1))把結(jié)論的否定化為子句形：③～I(z)④S(a,b)⑤M(b)⑷

消解反演求NIL圖：儲蓄問題反演樹～M(b)NIL子句（5）子句（7）子句（4）{a/x,b/y}子句（1）子句（3）f(x)/z～S(x,y)∨～M(y)子句（6）消解方法小結(jié)：

求子句集，進行歸結(jié)，方法簡單

通過修改證明樹的方法，提取回答

方法通用

求解效率低，不宜引入啟發(fā)信息

不宜理解推理過程3.5規(guī)則演繹系統(tǒng)以上介紹的經(jīng)典求解方法，對于比較復雜的問題，很難甚至無法解決。因此，需要有更好的求解方法。包括：

規(guī)則演繹系統(tǒng)

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

系統(tǒng)組織技術(shù)

不確定性推理

非單調(diào)推理對于許多公式來說，子句形是一種低效率的表達式，因為一些重要信息可能在求取子句形過程中丟失。采用易于敘述的if-then(如果-那么)規(guī)則來求解問題更為直接。規(guī)則演繹系統(tǒng)概述其中，If部分可能由幾個if組成，而Then部分可能由一個或一個以上的then組成?；谝?guī)則的問題求解系統(tǒng)，運用下述規(guī)則來建立:在所有基于規(guī)則的系統(tǒng)中，每個if可能與某斷言集中的一個或多個斷言匹配（斷言集→工作內(nèi)存），then部分用于規(guī)定放入工作內(nèi)存的新斷言。這種基于規(guī)則的系統(tǒng)叫做規(guī)則演繹系統(tǒng)(rulebaseddeductionsystem)。有時，then部分用于規(guī)定動作。這時，稱這種基于規(guī)則的系統(tǒng)為反應式系統(tǒng)(reactionsystem)或產(chǎn)生式系統(tǒng)(production

system)。

規(guī)則演繹系統(tǒng)屬于高級搜索推理技術(shù)；

其知識表示分為兩類：規(guī)則和事實；

規(guī)則由形如：If…Then

的蘊涵式表示；

事實由謂詞公式（不包括蘊涵式）表示；

if部分稱為前項，then部分稱為后項；

根據(jù)事實和規(guī)則，采用直接法而不是反演系統(tǒng)證明目標公式，強調(diào)

用規(guī)則進行演繹。

類型可分為：正向演繹、逆向演繹、雙向演繹；（與或形變換(子句集)、與或圖表示、葉節(jié)點文字的析?。?.6產(chǎn)生式系統(tǒng)（ProductionSystem）歷史悠久且使用最多的知識表示系統(tǒng)，早在自動機理論、形式文法和程序語言中即得到廣泛應用。主要用來描述若干個不同的，但以一個基本概念為基礎的系統(tǒng)。這個基本概念就是產(chǎn)生式規(guī)則（或產(chǎn)生式條件）和操作對的概念。產(chǎn)生式系統(tǒng)中，論域的知識分為兩部分：①用事實表示的靜態(tài)知識（如事物、事件和它們之間的關(guān)系）②用產(chǎn)生式規(guī)則表示的推理過程和行為系統(tǒng)的知識庫主要用于存儲規(guī)則，因此又將此類系統(tǒng)稱為基于規(guī)則的系統(tǒng)。3.6.1產(chǎn)生式系統(tǒng)的基本結(jié)構(gòu)許多成功的專家系統(tǒng)都采用產(chǎn)生式系統(tǒng)的典型結(jié)構(gòu)，用產(chǎn)生式規(guī)則來表達知識。通常，一個產(chǎn)生式系統(tǒng)包含事實庫、規(guī)則集和規(guī)則解釋（控制器）三部分。⑴、事實庫存放當前已知的知識信息數(shù)據(jù)，包括推理過程中形成的中間結(jié)論知識。即用于存儲有關(guān)問題的狀態(tài)