AI第3章-確定性推理

ArtificialIntelligence(AI)

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

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

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

什么是推理

推理方法及其分類

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

確定性推理（第3章）

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

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

歸納推理一種由個(gè)別到一般的推理方法。

類比歸納推理在兩個(gè)或兩類事物有許多屬性都相同或相似的基礎(chǔ)上，推出它們?cè)谄渌麑傩陨弦蚕嗤蛳嗨频囊环N歸納推理。3、推理方法的分類假言三段論：A→B，B→C?A→C三段論通常由一個(gè)大前提、一個(gè)小前提和一個(gè)結(jié)論三部分組成。

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

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

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

a、計(jì)算機(jī)系的學(xué)生都會(huì)編程序；（一般性知識(shí)）

b、程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生；（具體情況）

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

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

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

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

例，設(shè)有如下事例：王強(qiáng)是計(jì)算機(jī)系學(xué)生，會(huì)編程序；高華是計(jì)算機(jī)系學(xué)生，會(huì)編程序；

……。當(dāng)這些具體事例足夠多時(shí)，即可歸納出一個(gè)一般性的知識(shí)：凡是計(jì)算機(jī)系的學(xué)生，就一定會(huì)編程序。

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

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

確定性推理

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

單調(diào)推理

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

啟發(fā)式推理

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

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

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

盲目搜索

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

狀態(tài)空間搜索

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

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

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

逆向推理從某個(gè)假設(shè)目標(biāo)出發(fā)，逆向使用推理規(guī)則。(目標(biāo)驅(qū)動(dòng)\逆向鏈)

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

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

搜索的基本概念

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

與/或樹的搜索策略

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

盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間

信息并不改變控制策略。

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

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

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

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

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

圖搜索的一般過程

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

點(diǎn)擴(kuò)展的最大深度，即深度界限。思想：對(duì)狀態(tài)空間的深度優(yōu)先搜索引入搜索深度界限，設(shè)為dm，當(dāng)搜索深度達(dá)到了深度界限而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索。

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

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

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

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

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

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

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

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

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

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

啟發(fā)信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無用結(jié)點(diǎn)就越少。

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

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

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

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

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

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

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

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

實(shí)質(zhì)：選擇OPEN表中具有最小f值的節(jié)點(diǎn)作為下一個(gè)要擴(kuò)展的節(jié)點(diǎn)。

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

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

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

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

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

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

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

S0→S1→S2→S3→Sg局部擇優(yōu)搜索算法流程：(1)把初始節(jié)點(diǎn)S0放入OPEN表，計(jì)算f(S0)。(2)如果OPEN表為空，則問題無解，退出。(3)把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入CLOSED表。(4)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎ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表中的首部，并為每一個(gè)子節(jié)點(diǎn)都配置指向其父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。A*算法是對(duì)A算法的估價(jià)函數(shù)f(n)=g(n)+h(n)加上某些限制后得到的一種啟發(fā)式搜索算法。假設(shè)f*(n)是從初始節(jié)點(diǎn)S出發(fā)經(jīng)過節(jié)點(diǎn)n達(dá)到目標(biāo)節(jié)點(diǎn)的最小代價(jià)，估價(jià)函數(shù)f(n)是對(duì)f*(n)的估計(jì)值。且f*(n)=g*(n)+h*(n)

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

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

h(Sg)=0;

對(duì)任意節(jié)點(diǎn)ni及其任一子節(jié)點(diǎn)nj，都有:0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子節(jié)點(diǎn)nj的邊代價(jià)，則稱h(n)滿足單調(diào)限制。證明：設(shè)A*正要擴(kuò)展節(jié)點(diǎn)n，而節(jié)點(diǎn)序列S0=n0,n1,…,nk=n是由初始節(jié)點(diǎn)S0到節(jié)點(diǎn)n的最佳路徑。其中，ni是這個(gè)序列中最后一個(gè)位于CLOSED表中的節(jié)點(diǎn)，則上述節(jié)點(diǎn)序列中的ni+1節(jié)點(diǎn)必定在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é)點(diǎn)ni+1在最佳路徑上，故有f(ni+1)≤g*(n)+h(n)因?yàn)檫@時(shí)A*擴(kuò)展節(jié)點(diǎn)n而不擴(kuò)展節(jié)點(diǎn)ni+1，則有：

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

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

文字：一個(gè)原子公式和原子公式的否定。如：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é)論）消解過程應(yīng)用于“母體子句對(duì)”，以產(chǎn)生一個(gè)“導(dǎo)出子句”。并稱，“E1∧E3”為“E1∨E2”和“～E2∨E3”的消解式。母體子句對(duì)導(dǎo)出子句3.4.1子句集的求?。?步法）

說明消解過程之前，首先說明任一謂詞演算公式均可以變換為一個(gè)子句集。將謂詞公式變換為為子句集的步驟：①消去蘊(yùn)涵符號(hào)②減少否定符號(hào)的管轄域③對(duì)變量標(biāo)準(zhǔn)化④消去存在量詞⑤化為前束形⑥把母式化為合取范式⑦消去全稱量詞⑧消去連詞符號(hào)∧⑨更換變量名例：將下列謂詞演算公式化為一個(gè)子句集。(x){P(x){(y)[P(y)P(f(x,y))]∧～(y)[Q(x,y)P(y)]}}只應(yīng)用∨和～符號(hào)，以～A∨B替換AB（或AB）。⑴、消去蘊(yùn)涵符號(hào)(x){～P(x)∨{(y)[～P(y)∨P(f(x,y))]∧～(y)[～Q(x,y)∨P(y)]}}⑵、減少否定符號(hào)的管轄域(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)]}}每個(gè)否定符號(hào)“～”最多只用到一個(gè)謂詞符號(hào)上，并反復(fù)應(yīng)用摩根定律。以～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)被另一個(gè)未出現(xiàn)過的變量代替,而不改變公式的真值。合式公式中變量的標(biāo)準(zhǔn)化意味著對(duì)啞元改名,以保證每個(gè)量詞有其惟一的啞元。⑶、對(duì)變量標(biāo)準(zhǔ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ī)則：

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

若該變量受全稱量詞約束，則該變量用一個(gè)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))]}}把所有全稱量詞移到公式的左邊，并使每個(gè)量詞的轄域包括這個(gè)量詞后面公式的整個(gè)部分。前束形={前綴}{母式}

全稱量詞串無量詞公式⑹、把母式化為合取范式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))]}}任何母式都可寫成由一些謂詞公式和(或)謂詞公式的否定的析取的有限集組成的合取。(反復(fù)應(yīng)用分配律)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)的全稱量詞。⑻、消去連詞符號(hào)∧～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)，消去符號(hào)∧。最后得到一個(gè)有限集，其中每個(gè)公式都是文字的析取?！痢立?、更換變量名稱⑧～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)]更換變量符號(hào)的名稱，使一個(gè)變量符號(hào)不出現(xiàn)在一個(gè)以上的子句中。（用x1，x2，x3代替x）3.4.2消解推理規(guī)則消解式的定義：令L1，L2為兩任意原子公式；

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

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

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

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

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

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

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

前提：每個(gè)儲(chǔ)蓄錢的人都獲得利息。

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

S(x,y)表示“x儲(chǔ)蓄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(xiàn)(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(xiàn)(z)④S(a,b)⑤M(b)⑷

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

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

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

方法通用

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

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

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

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

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

不確定性推理

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

system)。

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

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

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

的蘊(yùn)涵式表示；

事實(shí)由謂詞公式（不包括蘊(yùn)涵式）表示；

if部分稱為前項(xiàng)，then部分稱為后項(xiàng)；

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

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

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