AI第3章-確定性推理

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

2、術(shù)搜索技術(shù)，包括各種，包括各種規(guī)則規(guī)則、過程過程和和算算法法等等推理技術(shù)推理技術(shù)，力求找到問題的解答。，力求找到問題的解答。 搜索搜索-尋找尋找一條從一條從初始問題初始問題到到問題解問題解的的路徑路徑。 關(guān)鍵關(guān)鍵是如何利用知識，盡可能有效地找到問題的解是如何利用知識，盡可能有效地找到問題的解( (最佳解最佳解) )。 即，通過即，通過推理方法推理方法進(jìn)行進(jìn)行“解解”的搜索。的搜索。一、推理的基本概念一、推理的基本概念 什么是推理什么是推理 推理方法及其分類推理方法及其分類 推理的控制策略及其分類推理的控制策略及其分類1 1、什么是推理、什么是推理 所謂所謂推理推理，就是，就是按照某種策略按照某

3、種策略，由已知判斷，推出另一，由已知判斷，推出另一個判斷的個判斷的思維過程思維過程。 人工智能中，推理是由人工智能中，推理是由程序程序?qū)崿F(xiàn)的，稱之為實(shí)現(xiàn)的，稱之為推理機(jī)推理機(jī)。 智能系統(tǒng)的智能系統(tǒng)的推理過程推理過程實(shí)際上就是一種實(shí)際上就是一種思維過程思維過程。 按照推理過程按照推理過程所用知識的確定與否所用知識的確定與否，推理可分為：，推理可分為： 確定性推理確定性推理（第（第3 3章）章） 不確定性推理不確定性推理（第（第4 4章）章）、推理的方法推理的方法 演繹、歸納、類比、確定、不確定、單調(diào)、非單調(diào)、演繹、歸納、類比、確定、不確定、單調(diào)、非單調(diào)、 啟發(fā)式、非啟發(fā)式。啟發(fā)式、非啟發(fā)式。、推

4、理的控制策略推理的控制策略 如何使用領(lǐng)域知識，使推理過程如何使用領(lǐng)域知識，使推理過程盡快達(dá)到目標(biāo)盡快達(dá)到目標(biāo)的策略。的策略。 推理的控制策略又可分為：推理的控制策略又可分為：搜索策略、推理策略搜索策略、推理策略。2 2、推理的兩個基本問題、推理的兩個基本問題、按推理的、按推理的邏輯基礎(chǔ)邏輯基礎(chǔ)分類分類 演繹推理演繹推理 從已知的從已知的一般性一般性知識出發(fā)，推出蘊(yùn)含在已知知識中，適合于某種知識出發(fā)，推出蘊(yùn)含在已知知識中，適合于某種個別情況個別情況的的結(jié)論。是一種由結(jié)論。是一種由一般一般到到個別個別的推理方法的推理方法, , 其核心是其核心是三段論三段論。 歸納推理歸納推理 一種由一種由個別個別

5、到到一般一般的推理方法。的推理方法。 類比歸納推理類比歸納推理 在兩個或兩類事物有在兩個或兩類事物有許多屬性許多屬性都相同或相似的基礎(chǔ)上，推出它們在都相同或相似的基礎(chǔ)上，推出它們在其他屬性其他屬性上也相同或相似的一種歸納推理。上也相同或相似的一種歸納推理。3 3、推理方法的分類、推理方法的分類假言三段論假言三段論：ABAB，BC BC AC AC 三段論通常由一個三段論通常由一個大前提大前提、一個、一個小前提小前提和一個和一個結(jié)論結(jié)論三三部分組成。部分組成。 大前提大前提是已知的一般性知識，或推理過程得到的判斷。是已知的一般性知識，或推理過程得到的判斷。 小前提小前提是關(guān)于某種具體情況，或某個

6、具體實(shí)例的判斷。是關(guān)于某種具體情況，或某個具體實(shí)例的判斷。 結(jié)論結(jié)論是由大前提推出的，并且適合于小前提的判斷。是由大前提推出的，并且適合于小前提的判斷。 演繹推理演繹推理例，例，有如下三個判斷：有如下三個判斷： a a、計(jì)算機(jī)系的學(xué)生都會編程序；（一般性知識）、計(jì)算機(jī)系的學(xué)生都會編程序；（一般性知識） b b、程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生；（具體情況）、程強(qiáng)是計(jì)算機(jī)系的一位學(xué)生；（具體情況） c c、程強(qiáng)會編程序。（結(jié)論）、程強(qiáng)會編程序。（結(jié)論）三段論推理：三段論推理：其中，其中，a a是大前提；是大前提；b b是小前提；是小前提；c c是經(jīng)是經(jīng)演繹演繹推出的結(jié)論。推出的結(jié)論?？梢姡嚎梢姡航Y(jié)論結(jié)論

7、是是蘊(yùn)含在蘊(yùn)含在大前提中大前提中的。的。-按照按照所選事例的廣泛性：所選事例的廣泛性：（完全、不完全）（完全、不完全） 完全歸納推理完全歸納推理 在進(jìn)行歸納時(shí)，考察相應(yīng)事物的在進(jìn)行歸納時(shí)，考察相應(yīng)事物的全部對象全部對象，根據(jù)，根據(jù)這些對這些對象象是否是否都具有都具有某種屬性，推出某種屬性，推出該類事物該類事物是否具有此屬性。是否具有此屬性。 不完全歸納推理不完全歸納推理 在進(jìn)行歸納時(shí)，在進(jìn)行歸納時(shí)，僅考察僅考察相應(yīng)事物的相應(yīng)事物的部分對象部分對象，即得出關(guān)，即得出關(guān)于該事物的結(jié)論。于該事物的結(jié)論。 歸納推理歸納推理-按照推理按照推理所使用的方法所使用的方法：（枚舉：（枚舉 類比類比 統(tǒng)計(jì)統(tǒng)計(jì)

8、差異歸納）差異歸納） 枚舉歸納推理枚舉歸納推理 在進(jìn)行歸納時(shí)，若已知在進(jìn)行歸納時(shí)，若已知某類事物某類事物的的有限可數(shù)個有限可數(shù)個具體事物具體事物都具有某種都具有某種屬性，則可推出該類事物都具有此種屬性。屬性，則可推出該類事物都具有此種屬性。 例例，設(shè)有如下事例：王強(qiáng)是計(jì)算機(jī)系學(xué)生，會編程序；，設(shè)有如下事例：王強(qiáng)是計(jì)算機(jī)系學(xué)生，會編程序； 高華是計(jì)算機(jī)系學(xué)生，會編程序；高華是計(jì)算機(jī)系學(xué)生，會編程序； 。 當(dāng)這些具體事例足夠多時(shí)，即可當(dāng)這些具體事例足夠多時(shí)，即可歸納歸納出一個出一個一般性的知一般性的知識識：凡是計(jì)算機(jī)系的學(xué)生，就一定會編程序。：凡是計(jì)算機(jī)系的學(xué)生，就一定會編程序。 若兩個若兩個(

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

10、類比歸納推理的基礎(chǔ)基礎(chǔ)是是相似原理相似原理，其可靠程度取決于兩個或兩類，其可靠程度取決于兩個或兩類事物的事物的相似程度相似程度, ,及這兩個或兩類事物的及這兩個或兩類事物的相同屬性相同屬性與與推出的那個屬性推出的那個屬性之間的相關(guān)程度。之間的相關(guān)程度。 類比歸納推理類比歸納推理演繹推理演繹推理 是在已知領(lǐng)域內(nèi)一般性知識的前提下，通過演繹，求解一個具體問題或是在已知領(lǐng)域內(nèi)一般性知識的前提下，通過演繹，求解一個具體問題或者證明一個結(jié)論的正確性。其所得出的結(jié)論實(shí)際上早已者證明一個結(jié)論的正確性。其所得出的結(jié)論實(shí)際上早已蘊(yùn)含蘊(yùn)含在一般性知識的在一般性知識的前提中，演繹推理不過是將已有事實(shí)揭露出來，因而前

11、提中，演繹推理不過是將已有事實(shí)揭露出來，因而不能增值新知識不能增值新知識。歸納推理歸納推理 所推出的結(jié)論所推出的結(jié)論并未包含并未包含在前提內(nèi)容中。這種由個別事物或現(xiàn)象推出一般在前提內(nèi)容中。這種由個別事物或現(xiàn)象推出一般性知識的過程，是性知識的過程，是增值新知識增值新知識的過程。的過程。演繹推理與歸納推理的區(qū)別：演繹推理與歸納推理的區(qū)別：、按推理過程、按推理過程所用知識的確定性所用知識的確定性分類分類 確定性推理確定性推理 不確定性推理不確定性推理、按推理過程推出的、按推理過程推出的結(jié)論是否單調(diào)增加結(jié)論是否單調(diào)增加分類分類 單調(diào)推理單調(diào)推理 非單調(diào)推理非單調(diào)推理、按推理過程是否利用問題的、按推理過

12、程是否利用問題的啟發(fā)性知識啟發(fā)性知識分類分類 啟發(fā)式推理啟發(fā)式推理 非啟發(fā)式推理非啟發(fā)式推理、按推理的邏輯基礎(chǔ)分類、按推理的邏輯基礎(chǔ)分類 推理過程不僅依賴于所用的推理過程不僅依賴于所用的推理方法推理方法，同時(shí)也依賴于，同時(shí)也依賴于推理的推理的控制策略控制策略。 推理的控制策略推理的控制策略是指是指如何使用領(lǐng)域知識，使推理過程如何使用領(lǐng)域知識，使推理過程盡快達(dá)到目標(biāo)的策略盡快達(dá)到目標(biāo)的策略。 推理的控制策略可分為：推理的控制策略可分為：搜索策略搜索策略、推理策略推理策略。4 4、推理的控制策略及其分類、推理的控制策略及其分類 在知識庫中在知識庫中尋找可利用的知識，構(gòu)造一條尋找可利用的知識，構(gòu)造一

13、條代價(jià)較小代價(jià)較小的推的推理路線，主要解決推理線路、推理效果、推理效率等問題。理路線，主要解決推理線路、推理效果、推理效率等問題。 按按是否使用啟發(fā)式信息是否使用啟發(fā)式信息可分為：可分為： 盲目搜索盲目搜索 啟發(fā)式搜索啟發(fā)式搜索 按按問題的表示方式問題的表示方式可分為：可分為： 狀態(tài)空間搜索狀態(tài)空間搜索 與或樹搜索與或樹搜索、搜索策略、搜索策略包括推理方向控制、求解、限制、沖突消解等策略。包括推理方向控制、求解、限制、沖突消解等策略。推理方向控制推理方向控制策略：策略：用于確定推理的控制方向用于確定推理的控制方向, ,可分為可分為正向推理正向推理、 逆向推理逆向推理、混合推理混合推理。求解求解

14、策略：策略：指僅求指僅求一個解一個解，還是求，還是求所有解所有解或或最優(yōu)解最優(yōu)解等。等。限制限制策略：策略：指對推理的指對推理的深度深度、寬度寬度、時(shí)間時(shí)間、空間空間等進(jìn)行的限制。等進(jìn)行的限制。沖突消解沖突消解策略：策略：當(dāng)推理過程有當(dāng)推理過程有多條知識可用多條知識可用時(shí)，如何從多條可用時(shí)，如何從多條可用 知識中知識中選出一條最佳知識用于推理選出一條最佳知識用于推理的策略。的策略。、推理策略、推理策略 正向推理正向推理 從已知事實(shí)出發(fā)，從已知事實(shí)出發(fā)，正向使用正向使用推理規(guī)則。推理規(guī)則。( (數(shù)據(jù)驅(qū)動推理數(shù)據(jù)驅(qū)動推理 前向鏈推理前向鏈推理) ) 從用戶提供的從用戶提供的初始已知事實(shí)初始已知事實(shí)

15、出發(fā)，在出發(fā)，在知識庫中知識庫中找出找出當(dāng)前可適用的知當(dāng)前可適用的知識識，構(gòu)成可適用的，構(gòu)成可適用的知識集知識集KS；然后按某種沖突消解策略，從；然后按某種沖突消解策略，從KS中選出一中選出一條知識進(jìn)行推理，并將推出的新事實(shí)加入到條知識進(jìn)行推理，并將推出的新事實(shí)加入到數(shù)據(jù)庫數(shù)據(jù)庫DB中，作為下一步推中，作為下一步推理的已知事實(shí)（中間事實(shí)）。理的已知事實(shí)（中間事實(shí)）。 在此之后，再從知識庫中選取可適用的知識進(jìn)行推理。重復(fù)進(jìn)行這在此之后，再從知識庫中選取可適用的知識進(jìn)行推理。重復(fù)進(jìn)行這一過程，直到求得所要求的解。一過程，直到求得所要求的解。 推理方向控制策略推理方向控制策略 如何根據(jù)已知事實(shí)，到知

16、識庫中選取可用知識？如何根據(jù)已知事實(shí)，到知識庫中選取可用知識？ 當(dāng)知識庫中有多條知識可用時(shí)，應(yīng)該先使用那一條知識？當(dāng)知識庫中有多條知識可用時(shí)，應(yīng)該先使用那一條知識？ 這些問題涉及到了這些問題涉及到了知識的匹配方法知識的匹配方法和和沖突消解策略沖突消解策略。優(yōu)點(diǎn)優(yōu)點(diǎn)： 比較直觀，允許用戶主動提供有用的事實(shí)信息，適合于診斷、設(shè)計(jì)、比較直觀，允許用戶主動提供有用的事實(shí)信息，適合于診斷、設(shè)計(jì)、預(yù)測、監(jiān)控等領(lǐng)域的問題求解。預(yù)測、監(jiān)控等領(lǐng)域的問題求解。缺點(diǎn)缺點(diǎn)： 推理無明確目標(biāo)，求解問題時(shí)可能會執(zhí)行許多與解無關(guān)的操作，導(dǎo)推理無明確目標(biāo)，求解問題時(shí)可能會執(zhí)行許多與解無關(guān)的操作，導(dǎo)致推理效率較低。致推理效率較

17、低。 逆向推理逆向推理 從從某個假設(shè)目標(biāo)某個假設(shè)目標(biāo)出發(fā)，出發(fā)，逆向逆向使用推理規(guī)則。使用推理規(guī)則。( (目標(biāo)驅(qū)動目標(biāo)驅(qū)動 逆向鏈逆向鏈) ) 首先首先選定一個選定一個假設(shè)目標(biāo)假設(shè)目標(biāo)，然后然后尋找支持該假設(shè)的尋找支持該假設(shè)的證據(jù)證據(jù)。若所需的證。若所需的證據(jù)都能找到，說明原假設(shè)成立；若找不到所需證據(jù)據(jù)都能找到，說明原假設(shè)成立；若找不到所需證據(jù), ,則說明原假設(shè)不成則說明原假設(shè)不成立，需要另作新的假設(shè)。立，需要另作新的假設(shè)。優(yōu)點(diǎn)優(yōu)點(diǎn)： 無需尋找和使用那些與假設(shè)目標(biāo)無關(guān)的信息和知識，推理過程的目無需尋找和使用那些與假設(shè)目標(biāo)無關(guān)的信息和知識，推理過程的目標(biāo)明確，有利于向用戶提供解釋。（在診斷性專家

18、系統(tǒng)中較為有效）標(biāo)明確，有利于向用戶提供解釋。（在診斷性專家系統(tǒng)中較為有效）缺點(diǎn)缺點(diǎn)： 當(dāng)用戶對解的情況認(rèn)識不請時(shí)，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性當(dāng)用戶對解的情況認(rèn)識不請時(shí)，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會影響系統(tǒng)效率。比較大，若選擇不好，可能需要多次提出假設(shè)，會影響系統(tǒng)效率。 混合推理混合推理 將正向推理與逆向推理結(jié)合起來所進(jìn)行的推理，是一種解決較復(fù)雜將正向推理與逆向推理結(jié)合起來所進(jìn)行的推理，是一種解決較復(fù)雜問題的方法。問題的方法。三種類型三種類型：先正向后逆向：先正向后逆向：先進(jìn)行正向推理，從已知事實(shí)出發(fā)推出部分結(jié)果，然后先進(jìn)行正向推理，從已知事實(shí)

19、出發(fā)推出部分結(jié)果，然后 再用逆向推理對這些結(jié)果進(jìn)行證實(shí)或提高其可信度。再用逆向推理對這些結(jié)果進(jìn)行證實(shí)或提高其可信度。先逆向后正向：先逆向后正向：先進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，先進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)， 然后再用正向推理對這些中間假設(shè)進(jìn)行證實(shí)。然后再用正向推理對這些中間假設(shè)進(jìn)行證實(shí)。雙向混合：雙向混合：正向推理和逆向推理同時(shí)進(jìn)行，使推理過程在中間的某一步正向推理和逆向推理同時(shí)進(jìn)行，使推理過程在中間的某一步 結(jié)合起來。結(jié)合起來。內(nèi)容提要內(nèi)容提要1 1、推理的基本概念、推理的基本概念2 2、搜索策略、搜索策略3 3、自然演繹推理、自然演繹推理4 4、歸結(jié)演繹推

20、理、歸結(jié)演繹推理5 5、基于規(guī)則的演繹推理、基于規(guī)則的演繹推理二、搜索策略二、搜索策略 搜索的基本概念搜索的基本概念 狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略 與與/ /或樹的搜索策略或樹的搜索策略 搜索的完備性與效率搜索的完備性與效率、什么是搜索、什么是搜索 搜索是人工智能中的一個搜索是人工智能中的一個基本問題基本問題，與推理密切相關(guān)。與推理密切相關(guān)。搜索策略的搜索策略的優(yōu)劣優(yōu)劣, ,將直接影響智能系統(tǒng)的性能與推理效率。將直接影響智能系統(tǒng)的性能與推理效率。搜索的定義：搜索的定義：根據(jù)經(jīng)驗(yàn)，利用已有知識，按照問題的實(shí)際情況，不斷尋根據(jù)經(jīng)驗(yàn)，利用已有知識，按照問題的實(shí)際情況，不斷尋 找可利用知識，從

21、而構(gòu)造一條找可利用知識，從而構(gòu)造一條代價(jià)最小的推理路線代價(jià)最小的推理路線，使問，使問 題得以解決的過程。題得以解決的過程。搜索的適用情況：搜索的適用情況：不良結(jié)構(gòu)或非結(jié)構(gòu)化問題；不良結(jié)構(gòu)或非結(jié)構(gòu)化問題； 難以獲得求解所需的全部信息；難以獲得求解所需的全部信息； 沒有現(xiàn)成的算法可供求解使用。沒有現(xiàn)成的算法可供求解使用。1 1、搜索的基本概念、搜索的基本概念 按是否使用啟發(fā)式信息按是否使用啟發(fā)式信息 盲目搜索：盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的按預(yù)定的控制策略進(jìn)行搜索，在搜索過程中獲得的中間中間 信息信息并不改變控制策略。并不改變控制策略。 啟發(fā)式搜索：啟發(fā)式搜索：在搜索中加入

22、了與問題有關(guān)的在搜索中加入了與問題有關(guān)的啟發(fā)性信息啟發(fā)性信息，用于，用于指導(dǎo)指導(dǎo) 搜索朝著最有希望的方向前進(jìn)搜索朝著最有希望的方向前進(jìn)，加速問題的求解過程，加速問題的求解過程 并找到最優(yōu)解。并找到最優(yōu)解。 按問題的表示方式按問題的表示方式 狀態(tài)空間搜索：狀態(tài)空間搜索：用狀態(tài)空間法求解問題進(jìn)行的搜索。用狀態(tài)空間法求解問題進(jìn)行的搜索。 與或樹搜索：與或樹搜索：用問題歸約法求解問題進(jìn)行的搜索。用問題歸約法求解問題進(jìn)行的搜索。、搜索的類型、搜索的類型 狀態(tài)空間搜索的狀態(tài)空間搜索的基本思想基本思想 圖搜索的圖搜索的一般過程一般過程 狀態(tài)空間的狀態(tài)空間的盲目搜索盲目搜索 廣度優(yōu)先搜索、廣度優(yōu)先搜索、 深度

23、優(yōu)先搜索、代價(jià)樹搜索。深度優(yōu)先搜索、代價(jià)樹搜索。 狀態(tài)空間的狀態(tài)空間的啟發(fā)式搜索啟發(fā)式搜索 啟發(fā)性信息和估價(jià)函數(shù)、啟發(fā)性信息和估價(jià)函數(shù)、A A算法和算法和A A* *算法。算法。2 2、狀態(tài)空間的搜索策略、狀態(tài)空間的搜索策略先將問題的先將問題的初始狀態(tài)初始狀態(tài)作為作為當(dāng)前擴(kuò)展節(jié)點(diǎn)當(dāng)前擴(kuò)展節(jié)點(diǎn)對其進(jìn)行對其進(jìn)行擴(kuò)展擴(kuò)展，生成，生成一組子節(jié)點(diǎn)一組子節(jié)點(diǎn)。然后檢查問題的然后檢查問題的目標(biāo)狀態(tài)目標(biāo)狀態(tài)是否出現(xiàn)在是否出現(xiàn)在這些子節(jié)點(diǎn)中這些子節(jié)點(diǎn)中。 若出現(xiàn)若出現(xiàn)，則搜索成功，找到了問題的解；，則搜索成功，找到了問題的解； 若未出現(xiàn)若未出現(xiàn)，則，則再從已生成的子節(jié)點(diǎn)中再從已生成的子節(jié)點(diǎn)中選擇一個節(jié)點(diǎn)作為當(dāng)前

24、擴(kuò)展節(jié)點(diǎn)選擇一個節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中，或者沒有可供操作的節(jié)重復(fù)上述過程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中，或者沒有可供操作的節(jié) 點(diǎn)為止。點(diǎn)為止。對一個節(jié)點(diǎn)進(jìn)行對一個節(jié)點(diǎn)進(jìn)行“擴(kuò)展擴(kuò)展”-指對該節(jié)點(diǎn)用某個指對該節(jié)點(diǎn)用某個可用操作可用操作進(jìn)行作用，生成該進(jìn)行作用，生成該 節(jié)點(diǎn)的一組子節(jié)點(diǎn)。節(jié)點(diǎn)的一組子節(jié)點(diǎn)。、狀態(tài)空間搜索的基本思想、狀態(tài)空間搜索的基本思想OPENOPEN表：表：未擴(kuò)展節(jié)點(diǎn)表，用于存放未擴(kuò)展節(jié)點(diǎn)表，用于存放剛剛( (新新) )生成生成節(jié)點(diǎn)。節(jié)點(diǎn)。CLOSEDCLOSED表：表：已擴(kuò)展節(jié)點(diǎn)表，用于存放已擴(kuò)展節(jié)點(diǎn)表，用于存放已經(jīng)擴(kuò)展已經(jīng)擴(kuò)展或或?qū)⒁獢U(kuò)展

25、將要擴(kuò)展節(jié)點(diǎn)。節(jié)點(diǎn)。S S：表示問題的表示問題的初始狀態(tài)初始狀態(tài)。（起始節(jié)點(diǎn)）。（起始節(jié)點(diǎn)）G G：表示搜索過程所得到的表示搜索過程所得到的搜索圖搜索圖。M M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成新生成的、的、且不是自己先輩且不是自己先輩的子節(jié)點(diǎn)集。的子節(jié)點(diǎn)集。狀態(tài)空間搜索算法的狀態(tài)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu)和和符號符號約定約定 3.1 3.1 圖搜索策略圖搜索策略（GraphSearch） 圖搜索控制圖搜索控制可看成是一種可看成是一種在圖中尋找路徑的方法在圖中尋找路徑的方法。 初始節(jié)點(diǎn)初始節(jié)點(diǎn)和和目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)分別代表分別代表初始數(shù)據(jù)庫初始數(shù)據(jù)庫和滿足終和滿足終止條件的止條件的目標(biāo)

26、數(shù)據(jù)庫目標(biāo)數(shù)據(jù)庫。 求得將一個數(shù)據(jù)庫求得將一個數(shù)據(jù)庫變換為變換為另一數(shù)據(jù)庫的另一數(shù)據(jù)庫的規(guī)則序列規(guī)則序列問題問題, ,等價(jià)于等價(jià)于求得圖中的求得圖中的一條路徑一條路徑問題。問題。 將將初始節(jié)點(diǎn)初始節(jié)點(diǎn)S S放入放入未擴(kuò)展節(jié)點(diǎn)表未擴(kuò)展節(jié)點(diǎn)表OPENOPEN表表，并建立當(dāng)前僅包含，并建立當(dāng)前僅包含S S的圖的圖G G； 檢查檢查OPENOPEN表是否為空，若為空，則問題無解，失敗退出；表是否為空，若為空，則問題無解，失敗退出； 將將OPENOPEN表的表的第一個節(jié)點(diǎn)第一個節(jié)點(diǎn)取出放入取出放入已擴(kuò)展節(jié)點(diǎn)表已擴(kuò)展節(jié)點(diǎn)表CLOSEDCLOSED表表，并記該節(jié)點(diǎn)，并記該節(jié)點(diǎn) 為為節(jié)點(diǎn)節(jié)點(diǎn)n； 考察節(jié)點(diǎn)考察

27、節(jié)點(diǎn)n n是否為目標(biāo)節(jié)點(diǎn)是否為目標(biāo)節(jié)點(diǎn)。若是若是，則得到問題的解，成功退出。此時(shí)，則得到問題的解，成功退出。此時(shí) 的的解解為追蹤圖為追蹤圖G G中沿著指針中沿著指針（步驟（步驟6 6中設(shè)置的指針）中設(shè)置的指針）從從n到初始節(jié)點(diǎn)到初始節(jié)點(diǎn)S的的 路徑路徑。(5)(5)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn)，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是節(jié)點(diǎn)n n先輩的那部先輩的那部 分子節(jié)點(diǎn)記入集合分子節(jié)點(diǎn)記入集合M M，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)n n的子節(jié)點(diǎn)加入的子節(jié)點(diǎn)加入G G中。中。1 1、圖搜索的一般過程、圖搜索的一般過程(6) (6) 針對針對M M中子節(jié)

28、點(diǎn)的不同情況，分別作如下處理：中子節(jié)點(diǎn)的不同情況，分別作如下處理： 對那些沒有在對那些沒有在G G中出現(xiàn)過的中出現(xiàn)過的M M成員，設(shè)置一個指向其父節(jié)點(diǎn)成員，設(shè)置一個指向其父節(jié)點(diǎn)( (即即 節(jié)點(diǎn)節(jié)點(diǎn)n)n)的指針，并把它放入的指針，并把它放入OPENOPEN表。（新生成的）表。（新生成的） 對那些原來已在對那些原來已在G G中出現(xiàn)過，但還沒有被擴(kuò)展的中出現(xiàn)過，但還沒有被擴(kuò)展的M M成員，確定是成員，確定是 否需要修改它指向父節(jié)點(diǎn)否需要修改它指向父節(jié)點(diǎn)(n)(n)的指針。的指針。( (已生成但未擴(kuò)展的已生成但未擴(kuò)展的) ) 對那些先前已在對那些先前已在G G中出現(xiàn)過，并已經(jīng)擴(kuò)展了的中出現(xiàn)過，并已經(jīng)

29、擴(kuò)展了的M M成員，確定是否成員，確定是否 需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。( (已生成也擴(kuò)展過的已生成也擴(kuò)展過的) )(7) (7) 按某種策略按某種策略, ,對對OPENOPEN表中的節(jié)點(diǎn)進(jìn)行排序。表中的節(jié)點(diǎn)進(jìn)行排序。(8) (8) 轉(zhuǎn)第轉(zhuǎn)第(2)(2)步。步。 上述過程是上述過程是狀態(tài)空間狀態(tài)空間的的一般圖搜索算法一般圖搜索算法，具有通用性，具有通用性，后面所要討論的各種狀態(tài)空間搜索策略后面所要討論的各種狀態(tài)空間搜索策略都是上述過程的都是上述過程的一個一個特例特例。 各種搜索策略的各種搜索策略的主要區(qū)別主要區(qū)別在于在于“對對OPENOPEN表中節(jié)點(diǎn)

30、的排列表中節(jié)點(diǎn)的排列順序不同順序不同”。 例如，例如，廣度優(yōu)先搜索廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而把先生成的子節(jié)點(diǎn)排在前面，而深深 度優(yōu)先搜索度優(yōu)先搜索則把后生成的子節(jié)點(diǎn)排在前面。則把后生成的子節(jié)點(diǎn)排在前面。2 2、圖搜索一般過程的幾點(diǎn)說明、圖搜索一般過程的幾點(diǎn)說明 在第在第(6)(6)步針對步針對M M中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，若發(fā)生中子節(jié)點(diǎn)的不同情況進(jìn)行處理時(shí)，若發(fā)生第種情況，那么，這個第種情況，那么，這個M M中的節(jié)點(diǎn)究竟應(yīng)該作為哪一個中的節(jié)點(diǎn)究竟應(yīng)該作為哪一個節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？ 一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來決定一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上

31、所付出的代價(jià)來決定, ,哪一條路徑哪一條路徑付出的代價(jià)小付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。 所謂由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的代價(jià)，是指這條路徑所謂由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的代價(jià)，是指這條路徑上的上的所有所有“有向邊有向邊”的代價(jià)之和的代價(jià)之和。 對那些原來已在對那些原來已在G G中出現(xiàn)過，但還沒有被擴(kuò)展的中出現(xiàn)過，但還沒有被擴(kuò)展的M M成員，確定是否成員，確定是否 需要修改它指向父節(jié)點(diǎn)需要修改它指向父節(jié)點(diǎn)(n)(n)的指針。的指針。( (已生成但未擴(kuò)展的已生成但未擴(kuò)展的) ) 若發(fā)生第種情況，除了需要確定該子節(jié)點(diǎn)指向父節(jié)點(diǎn)若發(fā)生第種情況，除了需要確定該子節(jié)點(diǎn)

32、指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。其依據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的代價(jià)。其依據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的代價(jià)。 在搜索圖中，除初始節(jié)點(diǎn)外，任意一個節(jié)點(diǎn)都在搜索圖中，除初始節(jié)點(diǎn)外，任意一個節(jié)點(diǎn)都含有且只含有且只含有含有一個指向其父節(jié)點(diǎn)的指針。因此，由所有節(jié)點(diǎn)及其一個指向其父節(jié)點(diǎn)的指針。因此，由所有節(jié)點(diǎn)及其指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集合是一棵樹，稱為指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集合是一棵樹，稱為搜索樹搜索樹。 對那些先前已在對那些先前已在G G中出現(xiàn)過，并已經(jīng)擴(kuò)展了的中出現(xiàn)過，并已經(jīng)擴(kuò)展了的M M成員，確定是否成員，確定

33、是否 需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。( (已生成也擴(kuò)展過的已生成也擴(kuò)展過的) ) 在搜索過程的第在搜索過程的第(4)(4)步，一旦某個被考察的節(jié)點(diǎn)是目標(biāo)節(jié)步，一旦某個被考察的節(jié)點(diǎn)是目標(biāo)節(jié) 點(diǎn)，則搜索過程成功結(jié)束。此時(shí)，由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)，則搜索過程成功結(jié)束。此時(shí)，由初始節(jié)點(diǎn)到目標(biāo)節(jié) 點(diǎn)路徑上的點(diǎn)路徑上的所有操作所有操作就構(gòu)成了該問題的解，而路徑由過就構(gòu)成了該問題的解，而路徑由過程第程第(6)(6)步所形成的指向父節(jié)點(diǎn)的指針來確定。步所形成的指向父節(jié)點(diǎn)的指針來確定。 如果搜索過程終止在第如果搜索過程終止在第(2)(2)步，即沒有達(dá)到目標(biāo)，且步，即沒有達(dá)

34、到目標(biāo)，且OPENOPEN 表中已無可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。表中已無可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。3.2 3.2 盲目搜索盲目搜索 不需要重新安排不需要重新安排OPENOPEN表表的搜索叫做的搜索叫做“無信息搜索無信息搜索”或或“盲盲目搜索目搜索”。（。（實(shí)際上是對解空間的遍歷）實(shí)際上是對解空間的遍歷） 包括：包括：寬寬( (廣廣) )度優(yōu)先搜索度優(yōu)先搜索 深度優(yōu)先搜索深度優(yōu)先搜索 等代價(jià)搜索等代價(jià)搜索 盲目搜索只適用于求解比較簡單的問題。盲目搜索只適用于求解比較簡單的問題。定義：定義：以以接近起始節(jié)點(diǎn)的程度接近起始節(jié)點(diǎn)的程度逐層逐層擴(kuò)展節(jié)點(diǎn)的搜索方法。擴(kuò)展節(jié)點(diǎn)的搜索方法。特點(diǎn)：特點(diǎn)：一種高

35、代價(jià)搜索，但若有解存在，則必能找到。一種高代價(jià)搜索，但若有解存在，則必能找到。3.2.1 3.2.1 寬度優(yōu)先搜索寬度優(yōu)先搜索（Breadth-first search）搜索是逐層進(jìn)行的，搜索是逐層進(jìn)行的，在對下一層的任一在對下一層的任一節(jié)點(diǎn)進(jìn)行搜索之前，節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的必須搜索完本層的所有節(jié)點(diǎn)。所有節(jié)點(diǎn)。( (解空間的解空間的橫向遍歷橫向遍歷) ) 從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S S開始逐層向下擴(kuò)展，在第開始逐層向下擴(kuò)展，在第n n層節(jié)點(diǎn)還未全層節(jié)點(diǎn)還未全部搜索完之前，不進(jìn)入第部搜索完之前，不進(jìn)入第n+1n+1層節(jié)點(diǎn)的搜索。層節(jié)點(diǎn)的搜索。 未擴(kuò)展節(jié)點(diǎn)表未擴(kuò)展節(jié)點(diǎn)表（OPENOPEN

36、表）中的節(jié)點(diǎn)，總是表）中的節(jié)點(diǎn)，總是按進(jìn)入的先后按進(jìn)入的先后排序排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。1 1、寬度優(yōu)先搜索的、寬度優(yōu)先搜索的基本思想基本思想 將初始節(jié)點(diǎn)將初始節(jié)點(diǎn)S S放入放入OPENOPEN表中；表中； 如果如果OPENOPEN表為空，則問題無解，失敗退出；表為空，則問題無解，失敗退出； 將將OPENOPEN表的第一個節(jié)點(diǎn)取出放入表的第一個節(jié)點(diǎn)取出放入CLOSEDCLOSED表，并記該節(jié)點(diǎn)為表，并記該節(jié)點(diǎn)為n n； 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出；是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的

37、解，成功退出； 若節(jié)點(diǎn)若節(jié)點(diǎn)n n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)(2)步；步； 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPENOPEN表的表的尾部尾部，并為每一個子節(jié)點(diǎn)設(shè)置，并為每一個子節(jié)點(diǎn)設(shè)置 指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)(2)步。步。2 2、寬度優(yōu)先搜索、寬度優(yōu)先搜索算法流程算法流程思考：思考：與原始算法比較異同，寬度優(yōu)先的體現(xiàn)？與原始算法比較異同，寬度優(yōu)先的體現(xiàn)？優(yōu)點(diǎn)：優(yōu)點(diǎn)：能夠保證在搜索樹中，找到一條通向目標(biāo)節(jié)點(diǎn)的最短路徑。能夠保證在搜索樹中，找到一條通向目標(biāo)節(jié)點(diǎn)的最短路徑。寬度優(yōu)先搜索寬度優(yōu)先搜索算法流程算法流程- -動態(tài)：動態(tài)：

38、八數(shù)碼難題：八數(shù)碼難題： 在在33的方格棋盤上，分別放置了標(biāo)有數(shù)字的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)，目標(biāo)狀態(tài)Sg，如下圖所示。，如下圖所示。 要求用寬度優(yōu)先搜索策略，尋找從要求用寬度優(yōu)先搜索策略，尋找從初始狀態(tài)初始狀態(tài)到到目標(biāo)狀態(tài)目標(biāo)狀態(tài)的解路徑的解路徑。56741382S056748321Sg3 3、寬度優(yōu)先搜索的、寬度優(yōu)先搜索的例子例子八數(shù)碼難題的寬度優(yōu)先搜索樹：八數(shù)碼難題的寬度優(yōu)先搜索樹：八數(shù)碼難題的寬度優(yōu)先搜索樹八數(shù)碼難題的寬度優(yōu)先搜索樹- -動態(tài)動態(tài)： 對對任意一個可擴(kuò)展的節(jié)點(diǎn)任意一個可擴(kuò)展的節(jié)點(diǎn)，總是按

39、照固定的操作符順序，總是按照固定的操作符順序 對其進(jìn)行擴(kuò)展（空格左移、上移、右移、下移）。對其進(jìn)行擴(kuò)展（空格左移、上移、右移、下移）。 在對在對任一節(jié)點(diǎn)任一節(jié)點(diǎn)進(jìn)行擴(kuò)展的時(shí)候，如果所得的進(jìn)行擴(kuò)展的時(shí)候，如果所得的某個子節(jié)點(diǎn)某個子節(jié)點(diǎn) （狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復(fù)（狀態(tài)）前面已經(jīng)出現(xiàn)過，則立即將其放棄，不再重復(fù) 畫出（不送入畫出（不送入OPENOPEN表）。表）。因此，寬度優(yōu)先搜索的因此，寬度優(yōu)先搜索的本質(zhì)本質(zhì)是：是： 以初始節(jié)點(diǎn)為根節(jié)點(diǎn)以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照寬度優(yōu)先的，在狀態(tài)空間圖中按照寬度優(yōu)先的原則，生成一棵搜索樹。（橫向搜索）原則，生成一棵搜索樹。（橫向

40、搜索）4 4、上述寬度優(yōu)先算法中上述寬度優(yōu)先算法中需注意的兩個問題需注意的兩個問題：優(yōu)點(diǎn)：優(yōu)點(diǎn)： 只要問題有解，用寬度優(yōu)先搜索總可以得到解，而且只要問題有解，用寬度優(yōu)先搜索總可以得到解，而且得到的是路徑最短的解。得到的是路徑最短的解。缺點(diǎn)：缺點(diǎn)： 盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，將會產(chǎn)盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)，將會產(chǎn)生許多無用節(jié)點(diǎn)，搜索效率低。生許多無用節(jié)點(diǎn)，搜索效率低。5 5、寬度優(yōu)先搜索的寬度優(yōu)先搜索的特點(diǎn)特點(diǎn)3.2.2 3.2.2 深度優(yōu)先搜索深度優(yōu)先搜索（Depth-first search） 首先擴(kuò)展首先擴(kuò)展最新產(chǎn)生的（即最深的）最新產(chǎn)生的（即最深的）節(jié)點(diǎn)，深度

41、相等的節(jié)點(diǎn)，深度相等的節(jié)點(diǎn)可以任意排列。定義節(jié)點(diǎn)的深度如下：節(jié)點(diǎn)可以任意排列。定義節(jié)點(diǎn)的深度如下： 起始節(jié)點(diǎn)（即根節(jié)點(diǎn)）的深度為起始節(jié)點(diǎn)（即根節(jié)點(diǎn)）的深度為0 0。 任何其他節(jié)點(diǎn)的深度，等于其父輩節(jié)點(diǎn)深度加任何其他節(jié)點(diǎn)的深度，等于其父輩節(jié)點(diǎn)深度加1 1。特點(diǎn)：特點(diǎn)：為防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給為防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給 出一個節(jié)點(diǎn)擴(kuò)展的最大深度出一個節(jié)點(diǎn)擴(kuò)展的最大深度-深度界限深度界限。 擴(kuò)展最深擴(kuò)展最深( (新新) )節(jié)點(diǎn)的結(jié)果節(jié)點(diǎn)的結(jié)果, ,使得搜索使得搜索沿著狀態(tài)空間某條單沿著狀態(tài)空間某條單一的路徑一的路徑，從起始節(jié)點(diǎn)向下進(jìn)，從起始節(jié)點(diǎn)向下進(jìn)行。只有當(dāng)搜

42、索到達(dá)一個沒有行。只有當(dāng)搜索到達(dá)一個沒有后裔的狀態(tài)時(shí)，才考慮另一條后裔的狀態(tài)時(shí)，才考慮另一條替代的路徑。替代的路徑。( (解空間解空間縱向遍歷縱向遍歷) ) 從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S S開始，開始，在其子節(jié)點(diǎn)中在其子節(jié)點(diǎn)中選擇一個選擇一個最新生成最新生成的的 節(jié)點(diǎn)進(jìn)行考察；節(jié)點(diǎn)進(jìn)行考察； 若該子節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn)若該子節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)展該子節(jié)點(diǎn), ,然后再然后再在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中在此子節(jié)點(diǎn)的子節(jié)點(diǎn)中選擇一個選擇一個最新生成最新生成的節(jié)點(diǎn)的節(jié)點(diǎn)進(jìn)行考察；進(jìn)行考察； 依此向下搜索，直到某個子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不依此向下搜索，直到某個子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，

43、又不能繼續(xù)擴(kuò)展時(shí)，才選擇其能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)兄弟節(jié)點(diǎn)進(jìn)行考察。進(jìn)行考察。1 1、深度優(yōu)先搜索的深度優(yōu)先搜索的基本思想基本思想 2 2、深度優(yōu)先搜索、深度優(yōu)先搜索算法流程算法流程 將初始節(jié)點(diǎn)將初始節(jié)點(diǎn)S S放入放入OPENOPEN表中；表中； 如果如果OPENOPEN表為空，則問題無解，失敗退出；表為空，則問題無解，失敗退出； 將將OPENOPEN表的第一個節(jié)點(diǎn)取出放入表的第一個節(jié)點(diǎn)取出放入CLOSEDCLOSED表，并記該節(jié)點(diǎn)為表，并記該節(jié)點(diǎn)為n n； 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出；是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問題的解，成功退出； 若節(jié)點(diǎn)若節(jié)

44、點(diǎn)n n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)(2)步；步； 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPENOPEN表的首部，并為每一個子節(jié)點(diǎn)設(shè)置表的首部，并為每一個子節(jié)點(diǎn)設(shè)置 指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第步。指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第步。3 3、深度優(yōu)先搜索的例子、深度優(yōu)先搜索的例子八數(shù)碼問題深度優(yōu)先搜索樹？八數(shù)碼問題深度優(yōu)先搜索樹？12384567目標(biāo)狀態(tài)目標(biāo)狀態(tài) Sg12384567初始狀態(tài)初始狀態(tài) S0 首先擴(kuò)展最新產(chǎn)生的首先擴(kuò)展最新產(chǎn)生的( (最深的最深的) )節(jié)點(diǎn)，若目標(biāo)節(jié)點(diǎn)不在當(dāng)前搜索節(jié)點(diǎn)，若目標(biāo)節(jié)點(diǎn)不在當(dāng)前搜索的分支上？的分支上？ 寬度優(yōu)先搜索寬度優(yōu)先搜索是是將節(jié)

45、點(diǎn)將節(jié)點(diǎn)n n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPENOPEN表的表的尾部尾部，而，而深度優(yōu)深度優(yōu)先搜索先搜索是是把節(jié)點(diǎn)把節(jié)點(diǎn)n n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPENOPEN表的表的首部首部。 在深度優(yōu)先搜索中，搜索在深度優(yōu)先搜索中，搜索一旦一旦進(jìn)入某個分支，進(jìn)入某個分支，就將就將沿著該分支一沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。 但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個無窮分但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個無窮分支，則就不可能得到解。支，則就不可能得到解。所以深度優(yōu)先搜索是不完備的

46、，即使問題有所以深度優(yōu)先搜索是不完備的，即使問題有解，也不一定能求得解解，也不一定能求得解。深度優(yōu)先搜索深度優(yōu)先搜索本質(zhì)本質(zhì)： 以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照深度優(yōu)先深度優(yōu)先的原則，生的原則，生成一棵成一棵搜索樹搜索樹。深度優(yōu)先搜索與寬度優(yōu)先搜索的深度優(yōu)先搜索與寬度優(yōu)先搜索的唯一區(qū)別唯一區(qū)別：4 4、有界深度優(yōu)先搜索、有界深度優(yōu)先搜索動機(jī)：動機(jī)：為了防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給出一個為了防止搜索過程沿著無益的路徑擴(kuò)展下去，往往給出一個節(jié)節(jié) 點(diǎn)擴(kuò)展的最大深度點(diǎn)擴(kuò)展的最大深度，即，即深度界限深度界限。思想：思想：對狀態(tài)空間的深度優(yōu)先搜索對

47、狀態(tài)空間的深度優(yōu)先搜索引入搜索深度界限引入搜索深度界限，設(shè)為，設(shè)為dm，當(dāng)搜，當(dāng)搜 索深度達(dá)到了深度界限而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個分支索深度達(dá)到了深度界限而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個分支 進(jìn)行搜索。進(jìn)行搜索。 即即，沿著一條路徑進(jìn)行下去，直到，沿著一條路徑進(jìn)行下去，直到深度界限深度界限為止，然后再考慮為止，然后再考慮 只有最后一步有差別只有最后一步有差別的的相同深度相同深度或或較淺深度較淺深度可供選擇的路可供選擇的路 徑，接著再考慮最后兩步有差別的那些路徑。徑，接著再考慮最后兩步有差別的那些路徑。八數(shù)碼難題：八數(shù)碼難題：d dm m= =5 55 5、注意問題、注意問題 如果問題有解，且

48、其路徑長度如果問題有解，且其路徑長度dm ，則上述搜索過程，則上述搜索過程一定能求得解。但若解的路徑長度一定能求得解。但若解的路徑長度dm ，則上述搜索過，則上述搜索過程就得不到解。這說明在程就得不到解。這說明在有界深度優(yōu)先搜索有界深度優(yōu)先搜索中，中，深度界限的深度界限的選擇是很重要的選擇是很重要的。 要恰當(dāng)?shù)亟o出要恰當(dāng)?shù)亟o出dm的值是比較困難的。否則即使能求出的值是比較困難的。否則即使能求出解，其也不一定是最優(yōu)解。解，其也不一定是最優(yōu)解。3.2.3 3.2.3 等代價(jià)搜索等代價(jià)搜索 有些問題并不要求有些問題并不要求應(yīng)用算符序列為最少應(yīng)用算符序列為最少的解，而是要求具有的解，而是要求具有某些某

49、些特性特性的解。的解。定義：定義：是是寬度優(yōu)先搜索寬度優(yōu)先搜索的一種的一種推廣推廣，不是沿著，不是沿著等長度路徑斷層等長度路徑斷層進(jìn)行擴(kuò)進(jìn)行擴(kuò) 展，而是沿著展，而是沿著等代價(jià)路徑斷層等代價(jià)路徑斷層進(jìn)行擴(kuò)展。搜索樹中進(jìn)行擴(kuò)展。搜索樹中每條連接弧每條連接弧 線上線上標(biāo)識有代價(jià)標(biāo)識有代價(jià), ,時(shí)間、距離等花費(fèi)。時(shí)間、距離等花費(fèi)。算法應(yīng)用的條件：算法應(yīng)用的條件：該算法是針對該算法是針對代價(jià)樹代價(jià)樹的算法。為了采用該算法對圖的算法。為了采用該算法對圖 進(jìn)行搜索，必須先將圖轉(zhuǎn)換為進(jìn)行搜索，必須先將圖轉(zhuǎn)換為代價(jià)樹代價(jià)樹。代價(jià)樹：代價(jià)樹：邊（連接弧線）上標(biāo)有代價(jià)邊（連接弧線）上標(biāo)有代價(jià)( (或費(fèi)用或費(fèi)用) )

50、的搜索樹。的搜索樹。 在代價(jià)樹中，若用在代價(jià)樹中，若用g(x)表示從初始節(jié)點(diǎn)表示從初始節(jié)點(diǎn)S到節(jié)點(diǎn)到節(jié)點(diǎn)x的的 代價(jià)，用代價(jià)，用c(x1,x2)表示從父節(jié)點(diǎn)表示從父節(jié)點(diǎn)x1到子節(jié)點(diǎn)到子節(jié)點(diǎn)x2的代價(jià)，的代價(jià)， 則有：則有：g(x2)=g(x1)+c(x1,x2)代價(jià)樹搜索：代價(jià)樹搜索：考慮邊的代價(jià)考慮邊的代價(jià)的搜索方法，目的是為了找到一的搜索方法，目的是為了找到一 條條代價(jià)最小代價(jià)最小的解路徑。的解路徑。代價(jià)樹搜索方法包括：代價(jià)樹搜索方法包括：代價(jià)樹的廣度優(yōu)先搜索代價(jià)樹的廣度優(yōu)先搜索 代價(jià)樹的深度優(yōu)先搜索代價(jià)樹的深度優(yōu)先搜索、基本思想、基本思想 每次從每次從OPENOPEN表中選擇節(jié)點(diǎn)往表中選

51、擇節(jié)點(diǎn)往CLOSEDCLOSED表傳送時(shí)，表傳送時(shí)，總是選總是選擇其中代價(jià)最小的節(jié)點(diǎn)擇其中代價(jià)最小的節(jié)點(diǎn)。 也就是說，也就是說，OPENOPEN表中的節(jié)點(diǎn)在任一時(shí)刻都是按其表中的節(jié)點(diǎn)在任一時(shí)刻都是按其代價(jià)代價(jià)從小到大排序從小到大排序的。代價(jià)小的節(jié)點(diǎn)排在前面，代價(jià)大的節(jié)點(diǎn)的。代價(jià)小的節(jié)點(diǎn)排在前面，代價(jià)大的節(jié)點(diǎn)排在后面，而排在后面，而不管節(jié)點(diǎn)在代價(jià)樹中處于什么位置上不管節(jié)點(diǎn)在代價(jià)樹中處于什么位置上。 如果問題有解，代價(jià)樹的寬度優(yōu)先搜索一定可以求得如果問題有解，代價(jià)樹的寬度優(yōu)先搜索一定可以求得解，并且求出的是解，并且求出的是最優(yōu)解最優(yōu)解。1 1、代價(jià)樹的寬度優(yōu)先搜索、代價(jià)樹的寬度優(yōu)先搜索、代價(jià)樹的寬

52、度優(yōu)先搜索算法流程代價(jià)樹的寬度優(yōu)先搜索算法流程 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S S放入放入OPENOPEN表中，置表中，置S S的代價(jià)的代價(jià)g(S)=0g(S)=0； 如果如果OPENOPEN表為空，則問題無解，失敗退出；表為空，則問題無解，失敗退出； 把把OPENOPEN表的第一個節(jié)點(diǎn)取出放入表的第一個節(jié)點(diǎn)取出放入CLOSEDCLOSED表，并記該節(jié)點(diǎn)為表，并記該節(jié)點(diǎn)為n n； 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n n是否為目標(biāo)。若是，則找到了問題的解，成功退出；是否為目標(biāo)。若是，則找到了問題的解，成功退出； 若節(jié)點(diǎn)若節(jié)點(diǎn)n n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)(2)步；否則轉(zhuǎn)第步；否則轉(zhuǎn)第(6)(6)步；步；

53、擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，計(jì)算各，為每一個子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，計(jì)算各 子節(jié)點(diǎn)的代價(jià)，并將各子節(jié)點(diǎn)放入子節(jié)點(diǎn)的代價(jià)，并將各子節(jié)點(diǎn)放入OPENOPEN表中。表中。根據(jù)各子結(jié)點(diǎn)的代根據(jù)各子結(jié)點(diǎn)的代 價(jià)對價(jià)對OPENOPEN表中的表中的全部結(jié)點(diǎn)全部結(jié)點(diǎn)按由小到大的順序排序按由小到大的順序排序。然后轉(zhuǎn)第步。然后轉(zhuǎn)第步。 設(shè)有設(shè)有5 5個城市，它們之間的交通線路如圖所示，圖中的個城市，它們之間的交通線路如圖所示，圖中的數(shù)字表示兩個城市之間的交通費(fèi)用，即代價(jià)。數(shù)字表示兩個城市之間的交通費(fèi)用，即代價(jià)。 用代價(jià)樹的寬度優(yōu)先搜索，求從用代價(jià)樹的寬度優(yōu)先搜索，求從A A

54、市出發(fā)到市出發(fā)到E E市，費(fèi)用市，費(fèi)用最小的交通路線。最小的交通路線。ABCDE43 4 523例子：例子：城市交通問題城市交通問題解：解：首先將交通圖轉(zhuǎn)化為代價(jià)樹。首先將交通圖轉(zhuǎn)化為代價(jià)樹。 具體轉(zhuǎn)化方法如下：具體轉(zhuǎn)化方法如下： 從起始節(jié)點(diǎn)從起始節(jié)點(diǎn)A A開始，把與它直接開始，把與它直接 相鄰的節(jié)點(diǎn)作為它的子節(jié)點(diǎn)。相鄰的節(jié)點(diǎn)作為它的子節(jié)點(diǎn)。 對其他節(jié)點(diǎn)也做相同的處理。對其他節(jié)點(diǎn)也做相同的處理。 若一個節(jié)點(diǎn)已經(jīng)為某節(jié)點(diǎn)的若一個節(jié)點(diǎn)已經(jīng)為某節(jié)點(diǎn)的直系直系 先輩節(jié)點(diǎn)先輩節(jié)點(diǎn)時(shí)，就不能作為這個節(jié)時(shí)，就不能作為這個節(jié) 點(diǎn)的子節(jié)點(diǎn)。點(diǎn)的子節(jié)點(diǎn)。 圖中除了起始節(jié)點(diǎn)圖中除了起始節(jié)點(diǎn)A A之外，其它之外，其它

55、 節(jié)點(diǎn)都可能要在代價(jià)樹中節(jié)點(diǎn)都可能要在代價(jià)樹中出現(xiàn)多出現(xiàn)多 次次，為了區(qū)分它們的多次出現(xiàn)，為了區(qū)分它們的多次出現(xiàn)， 分別用下標(biāo)分別用下標(biāo)1,21,2，標(biāo)出。標(biāo)出。交通圖的代價(jià)樹交通圖的代價(jià)樹2 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 352 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35 對此代價(jià)樹進(jìn)行寬度優(yōu)先搜索，可得到最優(yōu)解，如圖紅線對此代價(jià)樹進(jìn)行寬度優(yōu)先搜索，可得到最優(yōu)解，如圖紅線部分為最優(yōu)解，其代價(jià)為部分為最優(yōu)解，其代價(jià)為8 8。ABCDE43 4 523沿沿代價(jià)最小代價(jià)最小的路徑搜索，即每次展開未展開節(jié)點(diǎn)的路徑搜索，即每次展開未展開節(jié)

56、點(diǎn)中距離中距離A A點(diǎn)最近點(diǎn)最近的那個節(jié)點(diǎn)。的那個節(jié)點(diǎn)。、基本思想、基本思想 與代價(jià)樹的寬度優(yōu)先搜索不同，深度優(yōu)先搜索是與代價(jià)樹的寬度優(yōu)先搜索不同，深度優(yōu)先搜索是從剛擴(kuò)展出的子從剛擴(kuò)展出的子節(jié)點(diǎn)中選擇節(jié)點(diǎn)中選擇一個代價(jià)最小的節(jié)點(diǎn)送入一個代價(jià)最小的節(jié)點(diǎn)送入CLOSEDCLOSED表進(jìn)行考察，表進(jìn)行考察，而不是而不是在整在整個個OPENOPEN表中選擇代價(jià)最小的。表中選擇代價(jià)最小的。2 2、代價(jià)樹的深度優(yōu)先搜索、代價(jià)樹的深度優(yōu)先搜索、代價(jià)樹的深度優(yōu)先搜索算法流程、代價(jià)樹的深度優(yōu)先搜索算法流程 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S S放入放入OPENOPEN表中，置表中，置S S的代價(jià)的代價(jià)g(S)=0g(S)=

57、0； 如果如果OPENOPEN表為空，則問題無解表為空，則問題無解 ，失敗退出；，失敗退出； 把把OPENOPEN表的第一個節(jié)點(diǎn)取出放入表的第一個節(jié)點(diǎn)取出放入CLOSEDCLOSED表，并記該節(jié)點(diǎn)為表，并記該節(jié)點(diǎn)為n n； 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到問題的解，成功退出；是否為目標(biāo)節(jié)點(diǎn)。若是，則找到問題的解，成功退出； 若節(jié)點(diǎn)若節(jié)點(diǎn)n n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)(2)步；步； 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n n，生成其子節(jié)點(diǎn)，生成其子節(jié)點(diǎn)，將這些子節(jié)點(diǎn)按邊代價(jià)由小到大放將這些子節(jié)點(diǎn)按邊代價(jià)由小到大放 入入OpenOpen表的首部表的首部，并為每一個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的

58、指針。然，并為每一個子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。然 后轉(zhuǎn)第步。后轉(zhuǎn)第步。 上述幾種搜索方法的上述幾種搜索方法的本質(zhì)本質(zhì)是：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，是：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，按照按照既定的策略既定的策略對狀態(tài)空間圖進(jìn)行遍歷，并希望能夠盡早對狀態(tài)空間圖進(jìn)行遍歷，并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。 由于由于對狀態(tài)空間圖遍歷的策略對狀態(tài)空間圖遍歷的策略是是既定既定的，因此這些方的，因此這些方法統(tǒng)稱為盲目搜索方法。法統(tǒng)稱為盲目搜索方法。 盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點(diǎn)較多，盲目搜索具有較大的盲目性，產(chǎn)生的無用節(jié)點(diǎn)較多，效率不高。效率不高。狀態(tài)空間的盲目搜索小結(jié)：狀態(tài)空間的盲目搜索小結(jié)： 盲目

59、搜索的效率低，耗費(fèi)過多的計(jì)算時(shí)間和空間，容易盲目搜索的效率低，耗費(fèi)過多的計(jì)算時(shí)間和空間，容易產(chǎn)生組合爆炸。若能找到一種方法用于產(chǎn)生組合爆炸。若能找到一種方法用于排列待擴(kuò)展節(jié)點(diǎn)的順排列待擴(kuò)展節(jié)點(diǎn)的順序序，即選擇，即選擇最有希望的節(jié)點(diǎn)最有希望的節(jié)點(diǎn)加以擴(kuò)展，則搜索效率將會大為加以擴(kuò)展，則搜索效率將會大為提高。提高。( (許多情況下，可通過檢測來確定合理的順序許多情況下，可通過檢測來確定合理的順序) ) 下面介紹的搜索方法就是優(yōu)先考慮這類檢測，稱這類搜下面介紹的搜索方法就是優(yōu)先考慮這類檢測，稱這類搜索為索為啟發(fā)式搜索啟發(fā)式搜索(heuristic search)或或有信息搜索有信息搜索(inform

60、ed search)。3.3 3.3 啟發(fā)式搜索啟發(fā)式搜索 在盲目搜索中找到一個解，所需要擴(kuò)展的節(jié)點(diǎn)數(shù)目可在盲目搜索中找到一個解，所需要擴(kuò)展的節(jié)點(diǎn)數(shù)目可能是很大的，因?yàn)檫@些能是很大的，因?yàn)檫@些節(jié)點(diǎn)的擴(kuò)展次序是隨意的節(jié)點(diǎn)的擴(kuò)展次序是隨意的，而且，而且沒沒有利用已解決問題的任何特性有利用已解決問題的任何特性。 因此，除了那些最簡單的問題之外，一般都需要占用因此，除了那些最簡單的問題之外，一般都需要占用很多時(shí)間或空間（或兩者均有），這種結(jié)果是組合爆炸的很多時(shí)間或空間（或兩者均有），這種結(jié)果是組合爆炸的一種表現(xiàn)形式。一種表現(xiàn)形式。3.3.1 3.3.1 啟發(fā)式搜索策略和估價(jià)函數(shù)啟發(fā)式搜索策略和估價(jià)函數(shù)