【教學(xué)課件】第3章-搜索推理策略人工智能

1、Artificial Intelligence (AI)人工智能人工智能主講：何春梅Email：xiaoxiao_第第3章章: 確定性推理確定性推理內(nèi)容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結(jié)演繹推理歸結(jié)演繹推理5.5.基于規(guī)則的演繹推理基于規(guī)則的演繹推理內(nèi)容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結(jié)演繹推理歸結(jié)演繹推理5.5.基于規(guī)則的演繹推理基于規(guī)則的演繹推理推理的基本概念v推理的基本概念推理的基本概念1.1.什么是推理什么是推理2.2.推理方法及其分類推理

2、方法及其分類3.3.推理的控制策略及其分類推理的控制策略及其分類推理的基本概念v什么是推理什么是推理所謂推理就是按某種策略由已知判斷推出另一個(gè)判所謂推理就是按某種策略由已知判斷推出另一個(gè)判斷的思維過(guò)程。斷的思維過(guò)程。在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。在人工智能中，推理是由程序?qū)崿F(xiàn)的，稱為推理機(jī)。v推理的兩個(gè)基本問(wèn)題推理的兩個(gè)基本問(wèn)題推理的方法推理的方法推理的控制策略推理的控制策略推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎(chǔ)分：按推理的邏輯基礎(chǔ)分：演繹，歸納，類比歸納推理演繹，歸納，類比歸納推理p演繹推理演繹推理: :從已知的一般性知識(shí)出發(fā)，推出蘊(yùn)含在已知

3、從已知的一般性知識(shí)出發(fā)，推出蘊(yùn)含在已知知識(shí)中的適合于某種個(gè)別情況的結(jié)論。是一種由一般到知識(shí)中的適合于某種個(gè)別情況的結(jié)論。是一種由一般到個(gè)別的推理方法，其個(gè)別的推理方法，其核心是三段論核心是三段論。 假言三段論：假言三段論：AB，BC AC 常用的三段論是由一個(gè)常用的三段論是由一個(gè)大前提大前提、一個(gè)小前提一個(gè)小前提和和一個(gè)結(jié)論一個(gè)結(jié)論這這三部分組成的。三部分組成的。 大前提是已知的一般性知識(shí)或推理過(guò)程得到的判斷；大前提是已知的一般性知識(shí)或推理過(guò)程得到的判斷； 小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷；小前提是關(guān)于某種具體情況或某個(gè)具體實(shí)例的判斷； 結(jié)論是由大前提推出的，并且適合于小前提的判斷

4、。結(jié)論是由大前提推出的，并且適合于小前提的判斷。其結(jié)其結(jié)論是蘊(yùn)含在前提中的。論是蘊(yùn)含在前提中的。推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎(chǔ)分：按推理的邏輯基礎(chǔ)分：演繹，歸納，類比歸納推理演繹，歸納，類比歸納推理歸納推理：歸納推理：按照所選事例的按照所選事例的廣泛性廣泛性可分為可分為完全歸納完全歸納推理推理和和不完全歸納推理不完全歸納推理。 完全歸納推理：完全歸納推理：在進(jìn)行歸納時(shí)需要考察相應(yīng)事物在進(jìn)行歸納時(shí)需要考察相應(yīng)事物的的全部對(duì)象全部對(duì)象，并根據(jù)這些對(duì)象是否都具有某種屬，并根據(jù)這些對(duì)象是否都具有某種屬性，推出該類事物是否具有此屬性。性，推出該類事物是否具有此屬

5、性。 不完全歸納推理：不完全歸納推理：在進(jìn)行歸納時(shí)只考察了相應(yīng)事在進(jìn)行歸納時(shí)只考察了相應(yīng)事物的物的部分對(duì)象部分對(duì)象，就得出了關(guān)于該事物的結(jié)論。，就得出了關(guān)于該事物的結(jié)論。推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎(chǔ)分：按推理的邏輯基礎(chǔ)分：演繹，歸納，類比歸納推理演繹，歸納，類比歸納推理類比歸納推理：類比歸納推理：若在兩個(gè)或兩類事物有許多屬性相若在兩個(gè)或兩類事物有許多屬性相同或相似，則推出它們?cè)谄渌麑傩陨弦蚕嗤蛳嗨?。同或相似，則推出它們?cè)谄渌麑傩陨弦蚕嗤蛳嗨啤?類比歸納推理的基礎(chǔ)是類比歸納推理的基礎(chǔ)是相似原理相似原理，其可靠程度取，其可靠程度取決于兩個(gè)或兩類事物的

6、相似程度以及這兩個(gè)或兩決于兩個(gè)或兩類事物的相似程度以及這兩個(gè)或兩類事物的相同屬性與推出的那個(gè)屬性之間的相關(guān)類事物的相同屬性與推出的那個(gè)屬性之間的相關(guān)程度。程度。推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎(chǔ)分：按推理的邏輯基礎(chǔ)分：演繹，歸納，類比歸納推理演繹，歸納，類比歸納推理演繹推理與歸納推理的區(qū)別：演繹推理與歸納推理的區(qū)別： 演繹推理是在已知領(lǐng)域內(nèi)的一般性知識(shí)的前提下，通演繹推理是在已知領(lǐng)域內(nèi)的一般性知識(shí)的前提下，通過(guò)演繹求解一個(gè)具體問(wèn)題或者證明一個(gè)結(jié)論的正確性。過(guò)演繹求解一個(gè)具體問(wèn)題或者證明一個(gè)結(jié)論的正確性。它所得出的結(jié)論實(shí)際上早已蘊(yùn)含在一般性知識(shí)的前提它所得出

7、的結(jié)論實(shí)際上早已蘊(yùn)含在一般性知識(shí)的前提中中，演繹推理只不過(guò)是將已有事實(shí)揭露出來(lái)，因此，演繹推理只不過(guò)是將已有事實(shí)揭露出來(lái)，因此它它不能增殖新知識(shí)不能增殖新知識(shí)。 歸納推理所推出的結(jié)論是沒(méi)有包含在前提內(nèi)容中的歸納推理所推出的結(jié)論是沒(méi)有包含在前提內(nèi)容中的。這種由個(gè)別事物或現(xiàn)象推出一般性知識(shí)的過(guò)程，這種由個(gè)別事物或現(xiàn)象推出一般性知識(shí)的過(guò)程，是增是增殖新知識(shí)的過(guò)程殖新知識(shí)的過(guò)程。推理的基本概念v推理方法及其分類推理方法及其分類2.2.按推理過(guò)程所用知識(shí)的確定性分按推理過(guò)程所用知識(shí)的確定性分p 確定性推理確定性推理p 不確定性推理不確定性推理3.3.按推理過(guò)程推出的結(jié)論是否單調(diào)增加分按推理過(guò)程推出的結(jié)論

8、是否單調(diào)增加分p單調(diào)推理單調(diào)推理p非單調(diào)推理非單調(diào)推理4.4.按推理過(guò)程是否利用問(wèn)題的啟發(fā)性知識(shí)分按推理過(guò)程是否利用問(wèn)題的啟發(fā)性知識(shí)分p啟發(fā)式推理啟發(fā)式推理p非啟發(fā)式推理非啟發(fā)式推理推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類推理過(guò)程不僅依賴于所用的推理方法，同時(shí)也推理過(guò)程不僅依賴于所用的推理方法，同時(shí)也依賴于推理的控制策略。依賴于推理的控制策略。推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理推理的控制策略是指如何使用領(lǐng)域知識(shí)使推理過(guò)程盡快達(dá)到目標(biāo)的策略過(guò)程盡快達(dá)到目標(biāo)的策略。推理的控制策略可分為：推理的控制策略可分為：p搜索策略搜索策略p推理策略推理策略推理的基本概念v推理的控制策

9、略及其分類推理的控制策略及其分類搜索策略：搜索策略：在知識(shí)庫(kù)中尋找可利用的知識(shí)，從而構(gòu)造在知識(shí)庫(kù)中尋找可利用的知識(shí)，從而構(gòu)造一條一條代價(jià)較小代價(jià)較小的推理路線。主要解決推理線路、推理的推理路線。主要解決推理線路、推理效果、推理效率等問(wèn)題。效果、推理效率等問(wèn)題。按是否使用啟發(fā)式信息可分為：按是否使用啟發(fā)式信息可分為：p盲目搜索盲目搜索p啟發(fā)式搜索啟發(fā)式搜索按問(wèn)題的表示方式可分為：按問(wèn)題的表示方式可分為：p狀態(tài)空間搜索狀態(tài)空間搜索p與或樹(shù)搜索與或樹(shù)搜索推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類推理策略：推理策略：包括推理方向控制策略、求解策略、限制包括推理方向控制策略、求解策略、

10、限制策略、沖突消解策略等策略、沖突消解策略等p推理方向控制策略：推理方向控制策略：用于確定推理的控制方向，可用于確定推理的控制方向，可分為分為 正向推理正向推理 逆向推理逆向推理 混合推理混合推理 雙向推理雙向推理推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：正向推理：正向推理：從已知事實(shí)出發(fā)、正向使用推理規(guī)則，從已知事實(shí)出發(fā)、正向使用推理規(guī)則，亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈推理。亦稱為數(shù)據(jù)驅(qū)動(dòng)推理或前向鏈推理。 正向推理從用戶提供的正向推理從用戶提供的初始已知事實(shí)初始已知事實(shí)出發(fā)，在出發(fā)，在知識(shí)庫(kù)知識(shí)庫(kù)KB中找出當(dāng)前可適用的知識(shí)，構(gòu)成可適用的中

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

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

13、行許多與解無(wú)關(guān)的操作，導(dǎo)致推理效率較低。 推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：逆向推理：逆向推理：從某個(gè)假設(shè)目標(biāo)出發(fā)，逆向使用規(guī)則，從某個(gè)假設(shè)目標(biāo)出發(fā)，逆向使用規(guī)則，亦稱為亦稱為目標(biāo)驅(qū)動(dòng)推理目標(biāo)驅(qū)動(dòng)推理或或逆向鏈推理逆向鏈推理。逆向推理首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該逆向推理首先選定一個(gè)假設(shè)目標(biāo)，然后尋找支持該假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明原假假設(shè)的證據(jù)，若所需的證據(jù)都能找到，則說(shuō)明原假設(shè)是成立的；若找不到所需要的證據(jù)，則說(shuō)明原假設(shè)是成立的；若找不到所需要的證據(jù)，則說(shuō)明原假設(shè)不成立，此時(shí)需要另作新的假設(shè)。設(shè)不成立，此時(shí)

14、需要另作新的假設(shè)。推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：逆向推理的主要優(yōu)點(diǎn)：逆向推理的主要優(yōu)點(diǎn)：不必尋找和使用那些與假設(shè)不必尋找和使用那些與假設(shè)目標(biāo)無(wú)關(guān)的信息和知識(shí)，推理過(guò)程的目標(biāo)明確，有目標(biāo)無(wú)關(guān)的信息和知識(shí)，推理過(guò)程的目標(biāo)明確，有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有利于向用戶提供解釋，在診斷性專家系統(tǒng)中較為有效。效。逆向推理的主要缺點(diǎn)：逆向推理的主要缺點(diǎn)：當(dāng)用戶對(duì)解的情況認(rèn)識(shí)不請(qǐng)當(dāng)用戶對(duì)解的情況認(rèn)識(shí)不請(qǐng)時(shí)，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若時(shí)，由系統(tǒng)自主選擇假設(shè)目標(biāo)的盲目性比較大，若選擇不好，可能需要多次提出假設(shè)，會(huì)影

15、響系統(tǒng)效選擇不好，可能需要多次提出假設(shè)，會(huì)影響系統(tǒng)效率。率。推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：混合推理：混合推理：把正向推理和逆向推理結(jié)合起來(lái)所進(jìn)行把正向推理和逆向推理結(jié)合起來(lái)所進(jìn)行的推理稱為混合推理。是一種解決較復(fù)雜問(wèn)題的方的推理稱為混合推理。是一種解決較復(fù)雜問(wèn)題的方法。法?；旌贤评矸椒ǖ娜N類型：混合推理方法的三種類型：z1. 先正向后逆向：先正向后逆向：這種方法先進(jìn)行正向推理，從這種方法先進(jìn)行正向推理，從已知事實(shí)出發(fā)推出部分結(jié)果，然后再用逆向推理已知事實(shí)出發(fā)推出部分結(jié)果，然后再用逆向推理對(duì)這些結(jié)果進(jìn)行證實(shí)或提高它們的可信度。

16、對(duì)這些結(jié)果進(jìn)行證實(shí)或提高它們的可信度。 推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：混合推理方法的三種類型：混合推理方法的三種類型：z 2. 先逆向后正向：先逆向后正向：這種方法先進(jìn)行逆向推理，這種方法先進(jìn)行逆向推理，從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正從假設(shè)目標(biāo)出發(fā)推出一些中間假設(shè)，然后再用正向推理對(duì)這些中間假設(shè)進(jìn)行證實(shí)。向推理對(duì)這些中間假設(shè)進(jìn)行證實(shí)。 z 3. 雙向混合：雙向混合：是指正向推理和逆向推理同時(shí)進(jìn)是指正向推理和逆向推理同時(shí)進(jìn)行，使推理過(guò)程在中間的某一步結(jié)合起來(lái)。行，使推理過(guò)程在中間的某一步結(jié)合起來(lái)。推理的基本概念v推理

17、的控制策略及其分類推理的控制策略及其分類推理策略：推理策略：包括推理方向控制策略、求解策略、限制包括推理方向控制策略、求解策略、限制策略、沖突消解策略等策略、沖突消解策略等p求解策略：求解策略：是指僅求一個(gè)解，還是求所有解或最優(yōu)是指僅求一個(gè)解，還是求所有解或最優(yōu)解等。解等。p限制策略：限制策略：是指對(duì)推理的深度、寬度、時(shí)間、空間是指對(duì)推理的深度、寬度、時(shí)間、空間等進(jìn)行的限制。等進(jìn)行的限制。p沖突消解策略：沖突消解策略：是指當(dāng)推理過(guò)程有多條知識(shí)可用時(shí)，是指當(dāng)推理過(guò)程有多條知識(shí)可用時(shí)，如何從這多條可用知識(shí)中選出一條最佳知識(shí)用于推如何從這多條可用知識(shí)中選出一條最佳知識(shí)用于推理的策略。理的策略。內(nèi)容提

18、要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結(jié)演繹推理歸結(jié)演繹推理5.5.基于規(guī)則的演繹推理基于規(guī)則的演繹推理搜索策略v搜索策略搜索策略搜索的基本概念搜索的基本概念狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略與與/ /或樹(shù)的搜索策略或樹(shù)的搜索策略搜索的完備性與效率搜索的完備性與效率搜索的基本概念v搜索的基本概念搜索的基本概念搜索是人工智能中的一個(gè)基本問(wèn)題，并與推理密切相搜索是人工智能中的一個(gè)基本問(wèn)題，并與推理密切相關(guān)，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能關(guān)，搜索策略的優(yōu)劣，將直接影響到智能系統(tǒng)的性能與推理效率。與推理效率。搜索的定義：搜

19、索的定義：依靠經(jīng)驗(yàn)，利用已有知識(shí)，根據(jù)問(wèn)題的依靠經(jīng)驗(yàn)，利用已有知識(shí)，根據(jù)問(wèn)題的實(shí)際情況，不斷尋找可利用知識(shí)，從而構(gòu)造一條代價(jià)實(shí)際情況，不斷尋找可利用知識(shí)，從而構(gòu)造一條代價(jià)最小的推理路線，使問(wèn)題得以解決的過(guò)程稱為搜索。最小的推理路線，使問(wèn)題得以解決的過(guò)程稱為搜索。搜索的適用情況：搜索的適用情況：不良結(jié)構(gòu)或非結(jié)構(gòu)化問(wèn)題；難以獲不良結(jié)構(gòu)或非結(jié)構(gòu)化問(wèn)題；難以獲得求解所需的全部信息；更沒(méi)有現(xiàn)成的算法可供求解得求解所需的全部信息；更沒(méi)有現(xiàn)成的算法可供求解使用。使用。搜索的基本概念v搜索的類型搜索的類型按是否使用啟發(fā)式信息：按是否使用啟發(fā)式信息：p盲目搜索：盲目搜索：按預(yù)定的控制策略進(jìn)行搜索，在搜索過(guò)按預(yù)定

20、的控制策略進(jìn)行搜索，在搜索過(guò)程中獲得的中間信息并不改變控制策略。程中獲得的中間信息并不改變控制策略。 p啟發(fā)式搜索：?jiǎn)l(fā)式搜索：在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性在搜索中加入了與問(wèn)題有關(guān)的啟發(fā)性信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問(wèn)題的求解過(guò)程并找到最優(yōu)解。速問(wèn)題的求解過(guò)程并找到最優(yōu)解。 按問(wèn)題的表示方式：按問(wèn)題的表示方式：p狀態(tài)空間搜索：狀態(tài)空間搜索：用狀態(tài)空間法求解問(wèn)題進(jìn)行的搜索用狀態(tài)空間法求解問(wèn)題進(jìn)行的搜索 p與或樹(shù)搜索：與或樹(shù)搜索：用問(wèn)題歸約法求解問(wèn)題進(jìn)行的搜索用問(wèn)題歸約法求解問(wèn)題進(jìn)行的搜索 狀態(tài)空間的搜索策略v狀態(tài)空間的搜索策略狀態(tài)

21、空間的搜索策略狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索p廣度優(yōu)先搜索廣度優(yōu)先搜索p深度優(yōu)先搜索深度優(yōu)先搜索p代價(jià)樹(shù)搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)pA算法和算法和A*算法算法狀態(tài)空間的搜索策略v狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想先把問(wèn)題的初始狀態(tài)作為當(dāng)前先把問(wèn)題的初始狀態(tài)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)對(duì)其進(jìn)行對(duì)其進(jìn)行擴(kuò)展擴(kuò)展，生成一組子節(jié)點(diǎn)。生成一組子節(jié)點(diǎn)。然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若然后檢查問(wèn)題的目標(biāo)狀態(tài)是否出現(xiàn)在這些子節(jié)點(diǎn)中。若出現(xiàn)

22、，則搜索成功，找到了問(wèn)題的解；若沒(méi)出現(xiàn)，則再出現(xiàn)，則搜索成功，找到了問(wèn)題的解；若沒(méi)出現(xiàn)，則再按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作按照某種搜索策略從已生成的子節(jié)點(diǎn)中選擇一個(gè)節(jié)點(diǎn)作為當(dāng)前擴(kuò)展節(jié)點(diǎn)為當(dāng)前擴(kuò)展節(jié)點(diǎn)。重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有重復(fù)上述過(guò)程，直到目標(biāo)狀態(tài)出現(xiàn)在子節(jié)點(diǎn)中或者沒(méi)有可供操作的節(jié)點(diǎn)為止?？晒┎僮鞯墓?jié)點(diǎn)為止。所謂對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行所謂對(duì)一個(gè)節(jié)點(diǎn)進(jìn)行“擴(kuò)展擴(kuò)展”是指對(duì)該節(jié)點(diǎn)用某個(gè)可用是指對(duì)該節(jié)點(diǎn)用某個(gè)可用操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)操作進(jìn)行作用，生成該節(jié)點(diǎn)的一組子節(jié)點(diǎn)。 狀態(tài)空間的搜索策略v狀態(tài)空間搜索算法的數(shù)據(jù)結(jié)構(gòu)和符號(hào)約定狀態(tài)空間搜索算法的數(shù)據(jù)

23、結(jié)構(gòu)和符號(hào)約定OPEN表：表：未擴(kuò)展節(jié)點(diǎn)表，用于存放剛生成節(jié)點(diǎn)未擴(kuò)展節(jié)點(diǎn)表，用于存放剛生成節(jié)點(diǎn)CLOSED表：表：已擴(kuò)展節(jié)點(diǎn)表，用于存放已經(jīng)擴(kuò)已擴(kuò)展節(jié)點(diǎn)表，用于存放已經(jīng)擴(kuò)展或?qū)⒁獢U(kuò)展節(jié)點(diǎn)的展或?qū)⒁獢U(kuò)展節(jié)點(diǎn)的S：用表示問(wèn)題的初始狀態(tài)用表示問(wèn)題的初始狀態(tài)G：表示搜索過(guò)程所得到的搜索圖表示搜索過(guò)程所得到的搜索圖M：表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩表示當(dāng)前擴(kuò)展節(jié)點(diǎn)新生成的且不為自己先輩的子節(jié)點(diǎn)集的子節(jié)點(diǎn)集狀態(tài)空間的搜索策略v圖搜索的一般過(guò)程圖搜索的一般過(guò)程(1) 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S放入未擴(kuò)展節(jié)點(diǎn)表放入未擴(kuò)展節(jié)點(diǎn)表OPEN表，并建立目表，并建立目前僅包含前僅包含S的圖的圖G；(2) 檢查檢查O

24、PEN表是否為空，若為空，則問(wèn)題無(wú)解，失表是否為空，若為空，則問(wèn)題無(wú)解，失敗退出；敗退出；(3) 把把OPEN表的表的第一個(gè)節(jié)點(diǎn)第一個(gè)節(jié)點(diǎn)取出放入已擴(kuò)展節(jié)點(diǎn)表取出放入已擴(kuò)展節(jié)點(diǎn)表CLOSED表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)表，并記該節(jié)點(diǎn)為節(jié)點(diǎn)n；(4)考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問(wèn)題的解，是否為目標(biāo)節(jié)點(diǎn)。若是則得到了問(wèn)題的解，成功退出。此時(shí)的解為追蹤圖成功退出。此時(shí)的解為追蹤圖G中沿著指針中沿著指針（步驟（步驟6中中設(shè)置的指針）設(shè)置的指針）從從n到初始節(jié)點(diǎn)到初始節(jié)點(diǎn)S的路徑。的路徑。狀態(tài)空間的搜索策略v圖搜索的一般過(guò)程圖搜索的一般過(guò)程(5) 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，生成一組子節(jié)點(diǎn)。把這些子節(jié)

25、點(diǎn)中，生成一組子節(jié)點(diǎn)。把這些子節(jié)點(diǎn)中不是不是節(jié)點(diǎn)節(jié)點(diǎn)n先輩先輩 的那部分子節(jié)點(diǎn)記入集合的那部分子節(jié)點(diǎn)記入集合M，并把這些子節(jié)，并把這些子節(jié)點(diǎn)作為節(jié)點(diǎn)點(diǎn)作為節(jié)點(diǎn)n的子節(jié)點(diǎn)加入的子節(jié)點(diǎn)加入G中中(6) 針對(duì)針對(duì)M中子節(jié)點(diǎn)的不同情況，分別作如下處理：中子節(jié)點(diǎn)的不同情況，分別作如下處理：p 對(duì)那些沒(méi)有在對(duì)那些沒(méi)有在G中出現(xiàn)過(guò)的中出現(xiàn)過(guò)的M成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)成員設(shè)置一個(gè)指向其父節(jié)點(diǎn)（即節(jié)點(diǎn)（即節(jié)點(diǎn)n）的指針，并把它放入）的指針，并把它放入OPEN表。（表。（新生成的新生成的）p 對(duì)那些原來(lái)已在對(duì)那些原來(lái)已在G中出現(xiàn)過(guò)，但還沒(méi)有被擴(kuò)展的中出現(xiàn)過(guò)，但還沒(méi)有被擴(kuò)展的M成員，確成員，確定是否需要修改它指向

26、父節(jié)點(diǎn)的指針。（定是否需要修改它指向父節(jié)點(diǎn)的指針。（原生成但未擴(kuò)展的原生成但未擴(kuò)展的）p 對(duì)于那些先前已在對(duì)于那些先前已在G中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的中出現(xiàn)過(guò)，并已經(jīng)擴(kuò)展了的M成員，確成員，確定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。（定是否需要修改其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。（原生成也擴(kuò)原生成也擴(kuò)展過(guò)的展過(guò)的）v圖搜索的一般過(guò)程圖搜索的一般過(guò)程(7) 按某種策略對(duì)按某種策略對(duì)OPEN表中的節(jié)點(diǎn)表中的節(jié)點(diǎn)進(jìn)行進(jìn)行排序排序。(8) 轉(zhuǎn)第轉(zhuǎn)第(2)步。步。 狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略v圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：上述過(guò)程是狀態(tài)空間的一般圖搜索算法，它具上述過(guò)程是

27、狀態(tài)空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態(tài)空間搜索有通用性，后面所要討論的各種狀態(tài)空間搜索策略都是上述過(guò)程的一個(gè)特例。策略都是上述過(guò)程的一個(gè)特例。各種搜索策略的主要區(qū)別在于對(duì)各種搜索策略的主要區(qū)別在于對(duì)OPEN表中節(jié)表中節(jié)點(diǎn)的排列順序不同點(diǎn)的排列順序不同。例如，廣度優(yōu)先搜索把先。例如，廣度優(yōu)先搜索把先生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把生成的子節(jié)點(diǎn)排在前面，而深度優(yōu)先搜索則把后生成的子節(jié)點(diǎn)排在前面。后生成的子節(jié)點(diǎn)排在前面。狀態(tài)空間的搜索策略v圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：在第在第(6)步針對(duì)步針對(duì)M中子節(jié)點(diǎn)的不同情況進(jìn)行處理中子節(jié)點(diǎn)的不同情況進(jìn)

28、行處理時(shí)，如果發(fā)生當(dāng)?shù)诜N情況，那么，這個(gè)時(shí)，如果發(fā)生當(dāng)?shù)诜N情況，那么，這個(gè)M中的中的節(jié)點(diǎn)究竟應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？節(jié)點(diǎn)究竟應(yīng)該作為哪一個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)呢？一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代一般是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上所付出的代價(jià)來(lái)決定的，哪一條路經(jīng)付出的代價(jià)小，相應(yīng)價(jià)來(lái)決定的，哪一條路經(jīng)付出的代價(jià)小，相應(yīng)的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。所謂由原始節(jié)點(diǎn)到的節(jié)點(diǎn)就作為它的父節(jié)點(diǎn)。所謂由原始節(jié)點(diǎn)到該節(jié)點(diǎn)路徑上的代價(jià)是指這條路經(jīng)上的所有有該節(jié)點(diǎn)路徑上的代價(jià)是指這條路經(jīng)上的所有有向邊的代價(jià)之和。向邊的代價(jià)之和。 狀態(tài)空間的搜索策略v圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：如果發(fā)

29、生第種情況，除了需要確定該子節(jié)點(diǎn)如果發(fā)生第種情況，除了需要確定該子節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針外，還需要確定其后繼節(jié)點(diǎn)指向父節(jié)點(diǎn)的指針。其依據(jù)也是由原始節(jié)點(diǎn)到指向父節(jié)點(diǎn)的指針。其依據(jù)也是由原始節(jié)點(diǎn)到該節(jié)點(diǎn)的路徑上的代價(jià)。該節(jié)點(diǎn)的路徑上的代價(jià)。在搜索圖中，除初始節(jié)點(diǎn)外，任意一個(gè)節(jié)點(diǎn)都在搜索圖中，除初始節(jié)點(diǎn)外，任意一個(gè)節(jié)點(diǎn)都含有且只含有一個(gè)指向其父節(jié)點(diǎn)的指針。因此，含有且只含有一個(gè)指向其父節(jié)點(diǎn)的指針。因此，由所有節(jié)點(diǎn)及其指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集由所有節(jié)點(diǎn)及其指向父節(jié)點(diǎn)的指針?biāo)鶚?gòu)成的集合是一棵樹(shù)，稱為合是一棵樹(shù)，稱為搜索樹(shù)搜索樹(shù)。狀態(tài)空間的搜索策略v圖搜索的一般過(guò)程

30、的幾點(diǎn)說(shuō)明：圖搜索的一般過(guò)程的幾點(diǎn)說(shuō)明：在搜索過(guò)程的第在搜索過(guò)程的第(4)步，一旦某個(gè)被考察的節(jié)點(diǎn)步，一旦某個(gè)被考察的節(jié)點(diǎn)是是目標(biāo)節(jié)點(diǎn)目標(biāo)節(jié)點(diǎn)，則搜索過(guò)程成功結(jié)束。此時(shí)，由，則搜索過(guò)程成功結(jié)束。此時(shí)，由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑上的所有操作就構(gòu)成初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)路徑上的所有操作就構(gòu)成了該問(wèn)題的解，而路徑由第了該問(wèn)題的解，而路徑由第(6)步所形成的指向步所形成的指向父節(jié)點(diǎn)的指針來(lái)確定。父節(jié)點(diǎn)的指針來(lái)確定。如果搜索過(guò)程終止在第如果搜索過(guò)程終止在第(2)步，即沒(méi)有達(dá)到目標(biāo)，步，即沒(méi)有達(dá)到目標(biāo)，且且OPEN表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)表中已無(wú)可供擴(kuò)展的節(jié)點(diǎn)，則失敗結(jié)束。束。 廣度優(yōu)先搜索v狀態(tài)空間的

31、廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索的基本思想：廣度優(yōu)先搜索的基本思想：p從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S開(kāi)始逐層向下擴(kuò)展，在第開(kāi)始逐層向下擴(kuò)展，在第n層層節(jié)點(diǎn)還沒(méi)有全部搜索完之前，不進(jìn)入第節(jié)點(diǎn)還沒(méi)有全部搜索完之前，不進(jìn)入第n+1層節(jié)點(diǎn)的搜索。層節(jié)點(diǎn)的搜索。p未擴(kuò)展節(jié)點(diǎn)表未擴(kuò)展節(jié)點(diǎn)表OPEN表中的節(jié)點(diǎn)總是按進(jìn)入表中的節(jié)點(diǎn)總是按進(jìn)入的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)的先后排序，先進(jìn)入的節(jié)點(diǎn)排在前面，后進(jìn)入的節(jié)點(diǎn)排在后面。入的節(jié)點(diǎn)排在后面。廣度優(yōu)先搜索v狀態(tài)空間的廣度優(yōu)先搜索狀態(tài)空間的廣度優(yōu)先搜索廣度優(yōu)先搜索算法流程：廣度優(yōu)先搜索算法流程： (1)把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S放入放入OPEN表中；表

32、中； (2)如果如果OPEN表為空，則問(wèn)題無(wú)解，失敗退出；表為空，則問(wèn)題無(wú)解，失敗退出； (3)把把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表，并記表，并記該節(jié)點(diǎn)為該節(jié)點(diǎn)為n； (4)考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wèn)題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wèn)題的解，成功退出；成功退出； (5)若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步；步； (6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的表的尾部尾部，并為每，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。步。廣度優(yōu)先搜索v廣度

33、優(yōu)先搜索的例子：廣度優(yōu)先搜索的例子：八數(shù)碼難題八數(shù)碼難題在在33的方格棋盤(pán)上，分別放置了表有數(shù)字的方格棋盤(pán)上，分別放置了表有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)的八張牌，初始狀態(tài)S0，目標(biāo)狀態(tài)，目標(biāo)狀態(tài)Sg，如，如下圖所示。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀下圖所示。要求應(yīng)用廣度優(yōu)先搜索策略尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑態(tài)到目標(biāo)狀態(tài)的解路徑。1238476528314765S0Sg廣度優(yōu)先搜索八八數(shù)數(shù)碼碼難難題題的的寬寬度度優(yōu)優(yōu)先先搜搜索索樹(shù)樹(shù)廣度優(yōu)先搜索v在上述廣度優(yōu)先算法中需要注意兩個(gè)問(wèn)題：在上述廣度優(yōu)先算法中需要注意兩個(gè)問(wèn)題：對(duì)于任意一個(gè)可擴(kuò)展的節(jié)點(diǎn)，總是按照固定的操

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

35、先搜索的特點(diǎn)：廣度優(yōu)先搜索的特點(diǎn)：優(yōu)點(diǎn)：優(yōu)點(diǎn)：p只要問(wèn)題有解，用廣度優(yōu)先搜索總可以得到只要問(wèn)題有解，用廣度優(yōu)先搜索總可以得到解，解，而且得到的是路徑最短的解而且得到的是路徑最短的解。缺點(diǎn)：缺點(diǎn)：p廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初廣度優(yōu)先搜索盲目性較大，當(dāng)目標(biāo)節(jié)點(diǎn)距初始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索始節(jié)點(diǎn)較遠(yuǎn)時(shí)將會(huì)產(chǎn)生許多無(wú)用節(jié)點(diǎn)，搜索效率低。效率低。狀態(tài)空間的搜索策略v狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索p廣度優(yōu)先搜索廣度優(yōu)先搜索p深度優(yōu)先搜索深度優(yōu)先搜索p代價(jià)樹(shù)搜索代價(jià)

36、樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)pA算法和算法和A*算法算法深度優(yōu)先搜索v狀態(tài)空間的深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索的基本思想：深度優(yōu)先搜索的基本思想：p從初始節(jié)點(diǎn)從初始節(jié)點(diǎn)S開(kāi)始，在其子節(jié)點(diǎn)中選擇一個(gè)最新開(kāi)始，在其子節(jié)點(diǎn)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察。生成的節(jié)點(diǎn)進(jìn)行考察。p如果該子節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)如果該子節(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)中選擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察。擇一個(gè)最新生成的節(jié)點(diǎn)進(jìn)行考察。p依此向下搜索，直到某個(gè)子節(jié)點(diǎn)既

37、不是目標(biāo)節(jié)依此向下搜索，直到某個(gè)子節(jié)點(diǎn)既不是目標(biāo)節(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟節(jié)點(diǎn)進(jìn)行考察。行考察。深度優(yōu)先搜索v狀態(tài)空間的深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索算法流程：深度優(yōu)先搜索算法流程： (1) 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S放入放入OPEN表中；表中； (2) 如果如果OPEN表為空，則問(wèn)題無(wú)解表為空，則問(wèn)題無(wú)解 ，失敗退出；，失敗退出； (3) 把把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表，并記表，并記該節(jié)點(diǎn)為該節(jié)點(diǎn)為n； (4) 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則得到問(wèn)題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則

38、得到問(wèn)題的解，成功退出；成功退出； (5) 若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步；步； (6) 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，將其子節(jié)點(diǎn)放入，將其子節(jié)點(diǎn)放入OPEN表的表的首部首部，并為，并為每一個(gè)子節(jié)點(diǎn)設(shè)置每一個(gè)子節(jié)點(diǎn)設(shè)置 指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第指向父節(jié)點(diǎn)的指針，然后轉(zhuǎn)第(2)步。步。深度優(yōu)先搜索v深度優(yōu)先搜索：深度優(yōu)先搜索：八數(shù)碼難題八數(shù)碼難題八數(shù)碼難題的深度優(yōu)八數(shù)碼難題的深度優(yōu)先搜索如右圖先搜索如右圖首先擴(kuò)展最新產(chǎn)生的首先擴(kuò)展最新產(chǎn)生的(最深的最深的)節(jié)點(diǎn)節(jié)點(diǎn)如果目標(biāo)節(jié)點(diǎn)不在當(dāng)如果目標(biāo)節(jié)點(diǎn)不在當(dāng)前搜索的分支上？前搜索的分支上？深度優(yōu)先搜索v深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別

39、是：深度優(yōu)先搜索與廣度優(yōu)先搜索的唯一區(qū)別是：廣度廣度優(yōu)先搜索是將節(jié)點(diǎn)優(yōu)先搜索是將節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPEN表的表的尾部尾部，而深，而深度優(yōu)先搜索是把節(jié)點(diǎn)度優(yōu)先搜索是把節(jié)點(diǎn)n的子節(jié)點(diǎn)放入到的子節(jié)點(diǎn)放入到OPEN表的表的首部首部。v 在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該在深度優(yōu)先搜索中，搜索一旦進(jìn)入某個(gè)分支，就將沿著該分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可分支一直向下搜索。如果目標(biāo)節(jié)點(diǎn)恰好在此分支上，則可較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該較快地得到解。但是，如果目標(biāo)節(jié)點(diǎn)不在此分支上，而該分支又是一個(gè)無(wú)窮分支，則就不可能得到解。分支又是一個(gè)無(wú)

40、窮分支，則就不可能得到解。所以深度優(yōu)所以深度優(yōu)先搜索是不完備的，即使問(wèn)題有解，它也不一定能求得解。先搜索是不完備的，即使問(wèn)題有解，它也不一定能求得解。v深度優(yōu)先搜索本質(zhì)：深度優(yōu)先搜索本質(zhì)：以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，在狀態(tài)空間圖中按照深度優(yōu)先的原則，生成一棵搜索樹(shù)。間圖中按照深度優(yōu)先的原則，生成一棵搜索樹(shù)。有界深度優(yōu)先搜索v有界深度優(yōu)先搜索：有界深度優(yōu)先搜索：動(dòng)機(jī)：動(dòng)機(jī)：為了防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展為了防止搜索過(guò)程沿著無(wú)益的路徑擴(kuò)展下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度，即下去，往往給出一個(gè)節(jié)點(diǎn)擴(kuò)展的最大深度，即深度界限。深度界限。思想：思想：對(duì)狀態(tài)空間的深度優(yōu)先搜索引

41、入搜索深對(duì)狀態(tài)空間的深度優(yōu)先搜索引入搜索深度界限，設(shè)為度界限，設(shè)為dm，當(dāng)搜索深度達(dá)到了深度界限，當(dāng)搜索深度達(dá)到了深度界限而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜而仍未出現(xiàn)目標(biāo)節(jié)點(diǎn)時(shí)，就換一個(gè)分支進(jìn)行搜索。索。有界深度優(yōu)先搜索八數(shù)碼難題：八數(shù)碼難題：dm=4有界深度優(yōu)先搜索v有界深度優(yōu)先搜索：有界深度優(yōu)先搜索：?jiǎn)栴}：?jiǎn)栴}：如果問(wèn)題有解，且其路徑長(zhǎng)度如果問(wèn)題有解，且其路徑長(zhǎng)度 dm ，則，則上述搜索過(guò)程一定能求得解。但是，若解的路上述搜索過(guò)程一定能求得解。但是，若解的路徑長(zhǎng)度徑長(zhǎng)度 dm,則上述搜索過(guò)程就得不到解。這說(shuō)則上述搜索過(guò)程就得不到解。這說(shuō)明在有界深度優(yōu)先搜索中，深度界限的選擇是明在有界

42、深度優(yōu)先搜索中，深度界限的選擇是很重要的。很重要的。要恰當(dāng)?shù)亟o出要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。出解，它也不一定是最優(yōu)解。狀態(tài)空間的搜索策略v狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索p廣度優(yōu)先搜索廣度優(yōu)先搜索p深度優(yōu)先搜索深度優(yōu)先搜索p代價(jià)樹(shù)搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)pA算法和算法和A*算法算法代價(jià)樹(shù)搜索v代價(jià)樹(shù)：代價(jià)樹(shù)：邊上標(biāo)有代價(jià)邊上標(biāo)有代價(jià)( (或費(fèi)用

43、或費(fèi)用) )的樹(shù)稱為代價(jià)樹(shù)的樹(shù)稱為代價(jià)樹(shù)v 在代價(jià)樹(shù)中，若用在代價(jià)樹(shù)中，若用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)v代價(jià)樹(shù)搜索：代價(jià)樹(shù)搜索：考慮邊的代價(jià)的搜索方法，代價(jià)樹(shù)搜索的考慮邊的代價(jià)的搜索方法，代價(jià)樹(shù)搜索的目的是為了找到一條代價(jià)最小的解路徑。代價(jià)樹(shù)搜索方法目的是為了找到一條代價(jià)最小的解路徑。代價(jià)樹(shù)搜索方法包括：包括：代價(jià)樹(shù)的廣度優(yōu)先搜索代價(jià)樹(shù)的廣度優(yōu)先搜索代價(jià)樹(shù)的深度優(yōu)先搜索代價(jià)樹(shù)的深度優(yōu)先搜索代價(jià)樹(shù)的廣度優(yōu)先搜索v代價(jià)樹(shù)的

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

45、的是最優(yōu)解。該算法應(yīng)用的條件：該算法應(yīng)用的條件：該算法是針對(duì)代價(jià)樹(shù)的算法。該算法是針對(duì)代價(jià)樹(shù)的算法。為了采用該算法對(duì)圖進(jìn)行搜索，為了采用該算法對(duì)圖進(jìn)行搜索，必須先將圖轉(zhuǎn)換為代必須先將圖轉(zhuǎn)換為代價(jià)樹(shù)價(jià)樹(shù)。代價(jià)樹(shù)的廣度優(yōu)先搜索v 代價(jià)樹(shù)的廣度優(yōu)先搜索算法流程：代價(jià)樹(shù)的廣度優(yōu)先搜索算法流程：(1) 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S放入放入OPEN表中，置表中，置S的代價(jià)的代價(jià)g(S)=0； (2) 如果如果OPEN表為空，則問(wèn)題無(wú)解表為空，則問(wèn)題無(wú)解 ，失敗退出；，失敗退出； (3) 把把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表，并記該節(jié)表，并記該節(jié)點(diǎn)為點(diǎn)為n； (4) 考察節(jié)點(diǎn)考察

46、節(jié)點(diǎn)n是否為目標(biāo)。若是，則找到了問(wèn)題的解，成功是否為目標(biāo)。若是，則找到了問(wèn)題的解，成功退出；退出； (5) 若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步；否則轉(zhuǎn)第步；否則轉(zhuǎn)第(6)步；步；(6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針，計(jì)算各子節(jié)點(diǎn)的代價(jià)，并將各子節(jié)點(diǎn)放入計(jì)算各子節(jié)點(diǎn)的代價(jià)，并將各子節(jié)點(diǎn)放入OPEN表中。表中。并根并根據(jù)各子結(jié)點(diǎn)的代價(jià)對(duì)據(jù)各子結(jié)點(diǎn)的代價(jià)對(duì)OPEN表中的表中的全部結(jié)點(diǎn)全部結(jié)點(diǎn)按由小到大的順按由小到大的順序排序序排序。然后轉(zhuǎn)第。然后轉(zhuǎn)第(2)步。步。代價(jià)樹(shù)的廣度優(yōu)先搜索v例子：例子：城市交通問(wèn)題。設(shè)有城

47、市交通問(wèn)題。設(shè)有5個(gè)城市，它們之間的交通線個(gè)城市，它們之間的交通線路如下方左圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通路如下方左圖所示，圖中的數(shù)字表示兩個(gè)城市之間的交通費(fèi)用，即代價(jià)。用代價(jià)樹(shù)的廣度優(yōu)先搜索，求從費(fèi)用，即代價(jià)。用代價(jià)樹(shù)的廣度優(yōu)先搜索，求從A市出發(fā)市出發(fā)到到E市，費(fèi)用最小的交通路線。市，費(fèi)用最小的交通路線。ABCDE43 4 523城市交通圖城市交通圖代價(jià)樹(shù)的廣度優(yōu)先搜索v解：解：首先將交通圖轉(zhuǎn)化為代價(jià)首先將交通圖轉(zhuǎn)化為代價(jià)樹(shù)。具體轉(zhuǎn)化方法如下：樹(shù)。具體轉(zhuǎn)化方法如下： 從起始節(jié)點(diǎn)從起始節(jié)點(diǎn)A開(kāi)始，把與它直接開(kāi)始，把與它直接相鄰的節(jié)點(diǎn)作為它的子節(jié)點(diǎn)相鄰的節(jié)點(diǎn)作為它的子節(jié)點(diǎn) 對(duì)其他節(jié)點(diǎn)也

48、做相同的處理對(duì)其他節(jié)點(diǎn)也做相同的處理 若一個(gè)節(jié)點(diǎn)已經(jīng)為某節(jié)點(diǎn)的直系若一個(gè)節(jié)點(diǎn)已經(jīng)為某節(jié)點(diǎn)的直系先輩節(jié)點(diǎn)時(shí)，就不能作為這個(gè)節(jié)先輩節(jié)點(diǎn)時(shí)，就不能作為這個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)。點(diǎn)的子節(jié)點(diǎn)。 圖中除了起始節(jié)點(diǎn)圖中除了起始節(jié)點(diǎn)A之外，其它之外，其它節(jié)點(diǎn)都可能要在代價(jià)樹(shù)中出現(xiàn)多節(jié)點(diǎn)都可能要在代價(jià)樹(shù)中出現(xiàn)多次，為了區(qū)分它們的多次出現(xiàn)，次，為了區(qū)分它們的多次出現(xiàn)，分別用下標(biāo)分別用下標(biāo)1,2，標(biāo)出標(biāo)出城市交通圖的代價(jià)樹(shù)城市交通圖的代價(jià)樹(shù)2 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35代價(jià)樹(shù)的廣度優(yōu)先搜索v解：解：對(duì)此代價(jià)樹(shù)進(jìn)行廣度優(yōu)先搜索，可得到最優(yōu)對(duì)此代價(jià)樹(shù)進(jìn)行廣度優(yōu)先搜索，可得到最優(yōu)解，如

49、圖紅線部分為最優(yōu)解，其代價(jià)為解，如圖紅線部分為最優(yōu)解，其代價(jià)為8ABCDE43 4 5232 4 5AC1B1D1D2E1E2B2C2E3E43 43 4 2 35代價(jià)樹(shù)的深度優(yōu)先搜索v代價(jià)樹(shù)的深度優(yōu)先搜索代價(jià)樹(shù)的深度優(yōu)先搜索基本思想：基本思想：與代價(jià)樹(shù)的廣度優(yōu)先搜索不同，代與代價(jià)樹(shù)的廣度優(yōu)先搜索不同，代價(jià)樹(shù)的深度優(yōu)先搜索是價(jià)樹(shù)的深度優(yōu)先搜索是從剛擴(kuò)展出的子節(jié)點(diǎn)中從剛擴(kuò)展出的子節(jié)點(diǎn)中選擇選擇一個(gè)代價(jià)最小的節(jié)點(diǎn)送入一個(gè)代價(jià)最小的節(jié)點(diǎn)送入CLOSED表進(jìn)行表進(jìn)行考察，而不是在整個(gè)考察，而不是在整個(gè)OPEN表中選擇代價(jià)最小表中選擇代價(jià)最小的。的。代價(jià)樹(shù)的深度優(yōu)先搜索v 代價(jià)樹(shù)的深度優(yōu)先搜索算法流程：

50、代價(jià)樹(shù)的深度優(yōu)先搜索算法流程：(1) 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S放入放入OPEN表中，置表中，置S的代價(jià)的代價(jià)g(S)=0； (2) 如果如果OPEN表為空，則問(wèn)題無(wú)解表為空，則問(wèn)題無(wú)解 ，失敗退出；，失敗退出； (3) 把把OPEN表的第一個(gè)節(jié)點(diǎn)取出放入表的第一個(gè)節(jié)點(diǎn)取出放入CLOSED表，并表，并記該節(jié)點(diǎn)為記該節(jié)點(diǎn)為n； (4) 考察節(jié)點(diǎn)考察節(jié)點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問(wèn)題是否為目標(biāo)節(jié)點(diǎn)。若是，則找到了問(wèn)題的解，成功退出；的解，成功退出； (5) 若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步；步； (6) 擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，生成其子節(jié)點(diǎn)，生成其子節(jié)點(diǎn)，將這些子節(jié)點(diǎn)按邊代價(jià)將

51、這些子節(jié)點(diǎn)按邊代價(jià)由小到大放入由小到大放入Open表的首部表的首部，并為每一個(gè)子節(jié)點(diǎn)設(shè)置，并為每一個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針。然后轉(zhuǎn)第指向父節(jié)點(diǎn)的指針。然后轉(zhuǎn)第(2)步。步。狀態(tài)空間的盲目搜索v狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索上述幾種搜索方法的本質(zhì)是，以初始節(jié)點(diǎn)為根上述幾種搜索方法的本質(zhì)是，以初始節(jié)點(diǎn)為根節(jié)點(diǎn)，按照既定的策略對(duì)狀態(tài)空間圖進(jìn)行遍歷，節(jié)點(diǎn)，按照既定的策略對(duì)狀態(tài)空間圖進(jìn)行遍歷，并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。并希望能夠盡早發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)。由于對(duì)狀態(tài)空間圖遍歷的策略是既定的，因此由于對(duì)狀態(tài)空間圖遍歷的策略是既定的，因此這些方法統(tǒng)稱為盲目搜索方法。這些方法統(tǒng)稱為盲目搜索方法。盲目搜索具有

52、較大的盲目性，產(chǎn)生的無(wú)用節(jié)點(diǎn)盲目搜索具有較大的盲目性，產(chǎn)生的無(wú)用節(jié)點(diǎn)較多，效率不高。較多，效率不高。狀態(tài)空間的搜索策略v狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索p廣度優(yōu)先搜索廣度優(yōu)先搜索p深度優(yōu)先搜索深度優(yōu)先搜索p代價(jià)樹(shù)搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和估價(jià)函數(shù)pA算法和算法和A*算法算法啟發(fā)性信息和估價(jià)函數(shù)v啟發(fā)式搜索：?jiǎn)l(fā)式搜索：采用問(wèn)題自身的特性信息，以指導(dǎo)搜索朝采用問(wèn)題自身的特性信息，以指導(dǎo)搜索朝著最有希望的方向前進(jìn)。著最有希

53、望的方向前進(jìn)。v啟發(fā)性信息的概念：?jiǎn)l(fā)性信息的概念：?jiǎn)l(fā)性信息是指那種與具體問(wèn)題啟發(fā)性信息是指那種與具體問(wèn)題求解過(guò)程有關(guān)的，并可指導(dǎo)搜索過(guò)程朝著最有希望方向前求解過(guò)程有關(guān)的，并可指導(dǎo)搜索過(guò)程朝著最有希望方向前進(jìn)的控制信息。進(jìn)的控制信息。啟發(fā)信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無(wú)用結(jié)啟發(fā)信息的啟發(fā)能力越強(qiáng)，擴(kuò)展的無(wú)用結(jié)點(diǎn)越少。點(diǎn)越少。v啟發(fā)性信息的種類啟發(fā)性信息的種類有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息有效地幫助確定擴(kuò)展節(jié)點(diǎn)的信息有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息有效的幫助決定哪些后繼節(jié)點(diǎn)應(yīng)被生成的信息能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹(shù)上刪除能決定在擴(kuò)展一個(gè)節(jié)點(diǎn)時(shí)哪些節(jié)點(diǎn)應(yīng)從搜索樹(shù)上刪除的信息的信息啟

54、發(fā)性信息和估價(jià)函數(shù)v估價(jià)函數(shù)：估價(jià)函數(shù)：用于評(píng)估節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)用于評(píng)估節(jié)點(diǎn)重要性的函數(shù)稱為估價(jià)函數(shù)。估價(jià)函數(shù)的一般形式為：函數(shù)。估價(jià)函數(shù)的一般形式為：f(x) = g(x)+h(x)g(x)表示從初始節(jié)點(diǎn)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)x的代價(jià)；的代價(jià)；h(x)是從節(jié)點(diǎn)是從節(jié)點(diǎn)x到目標(biāo)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)Sg的最優(yōu)路徑的代價(jià)的最優(yōu)路徑的代價(jià)的的估計(jì)估計(jì)，它體現(xiàn)了問(wèn)題的啟發(fā)性信息。，它體現(xiàn)了問(wèn)題的啟發(fā)性信息。h(x)稱為稱為啟發(fā)函數(shù)啟發(fā)函數(shù)。啟發(fā)性信息和估價(jià)函數(shù)v例子：例子：八數(shù)碼難題八數(shù)碼難題設(shè)問(wèn)題的初始狀態(tài)設(shè)問(wèn)題的初始狀態(tài)S0和目標(biāo)狀態(tài)和目標(biāo)狀態(tài)Sg如圖所示如圖所示估價(jià)函數(shù)為：估價(jià)函數(shù)為：

55、 f(n)=d(n)+W(n)d(n)：表示節(jié)點(diǎn)：表示節(jié)點(diǎn)n在搜索樹(shù)中的深在搜索樹(shù)中的深度度W(n)：表示節(jié)點(diǎn)：表示節(jié)點(diǎn)n中中“不在位不在位”的數(shù)的數(shù)碼個(gè)數(shù)碼個(gè)數(shù)請(qǐng)計(jì)算初始狀態(tài)請(qǐng)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值的估價(jià)函數(shù)值f(S0)1238476528314765S0Sg啟發(fā)性信息和估價(jià)函數(shù)v計(jì)算初始狀態(tài)計(jì)算初始狀態(tài)S0的估價(jià)函數(shù)值的估價(jià)函數(shù)值f(S0)v解：解：取取g(n)=d(n)，h(n)=W(n) 它說(shuō)明是用從它說(shuō)明是用從S0到到n的路徑上的單位的路徑上的單位代價(jià)表示實(shí)際代價(jià)代價(jià)表示實(shí)際代價(jià) 用結(jié)點(diǎn)用結(jié)點(diǎn)n中中“不在位不在位”的數(shù)碼個(gè)數(shù)作為的數(shù)碼個(gè)數(shù)作為啟發(fā)信息。啟發(fā)信息。 一般來(lái)說(shuō)，某節(jié)

56、點(diǎn)中的一般來(lái)說(shuō)，某節(jié)點(diǎn)中的“不在位不在位”的數(shù)的數(shù)碼個(gè)數(shù)越多，說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)碼個(gè)數(shù)越多，說(shuō)明它離目標(biāo)節(jié)點(diǎn)越遠(yuǎn)（代價(jià)的估計(jì)）。（代價(jià)的估計(jì)）。 對(duì)初始節(jié)點(diǎn)對(duì)初始節(jié)點(diǎn)S0，d(S0)=0，W(S0)=3。因此，因此， f(S0)=0+3=3 1238476528314765S0Sg狀態(tài)空間的搜索策略v狀態(tài)空間的搜索策略狀態(tài)空間的搜索策略狀態(tài)空間搜索的基本思想狀態(tài)空間搜索的基本思想圖搜索的一般過(guò)程圖搜索的一般過(guò)程狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索p廣度優(yōu)先搜索廣度優(yōu)先搜索p深度優(yōu)先搜索深度優(yōu)先搜索p代價(jià)樹(shù)搜索代價(jià)樹(shù)搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價(jià)函數(shù)啟發(fā)性信息和

57、估價(jià)函數(shù)pA算法和算法和A*算法算法A算法vA算法：算法：在圖搜索算法中，如果能在搜索的每一步都在圖搜索算法中，如果能在搜索的每一步都利利用估價(jià)函數(shù)用估價(jià)函數(shù)f(n)=g(n)+h(n)對(duì)對(duì)OPEN表中的節(jié)點(diǎn)進(jìn)行排序表中的節(jié)點(diǎn)進(jìn)行排序，則該搜索算法為則該搜索算法為A算法算法。 由于估價(jià)函數(shù)中帶有問(wèn)題自身的由于估價(jià)函數(shù)中帶有問(wèn)題自身的啟發(fā)性信息，因此，啟發(fā)性信息，因此，A算法也被稱為算法也被稱為啟發(fā)式搜索算法啟發(fā)式搜索算法。vA算法的類型：算法的類型：可根據(jù)搜索過(guò)程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，可根據(jù)搜索過(guò)程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，將啟發(fā)式搜索算法分為：將啟發(fā)式搜索算法分為：全局擇優(yōu)搜索算法全局擇優(yōu)搜索算

58、法： 從從OPEN表的表的所有節(jié)點(diǎn)所有節(jié)點(diǎn)中選擇一中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。局部擇優(yōu)搜索算法：局部擇優(yōu)搜索算法：僅從剛生成的子節(jié)點(diǎn)僅從剛生成的子節(jié)點(diǎn)中選擇一個(gè)中選擇一個(gè)估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。估價(jià)函數(shù)值最小的一個(gè)進(jìn)行擴(kuò)展。A算法v 全局擇優(yōu)搜索算法流程全局擇優(yōu)搜索算法流程(1)把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表，計(jì)算表，計(jì)算f(S0)。(2)如果如果OPEN表為空，則問(wèn)題無(wú)解，退出。表為空，則問(wèn)題無(wú)解，退出。(3)把把OPEN表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)表的第一個(gè)節(jié)點(diǎn)（記為節(jié)點(diǎn)n）取出放入）取出放入CLOSED表。表。(4)考察節(jié)點(diǎn)考察節(jié)

59、點(diǎn)n是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，是否為目標(biāo)節(jié)點(diǎn)。若是，則求得了問(wèn)題的解，退出。退出。(5)若節(jié)點(diǎn)若節(jié)點(diǎn)n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第2步。步。(6)擴(kuò)展節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)n，用估價(jià)函數(shù)，用估價(jià)函數(shù)f(x)計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，計(jì)算每個(gè)子節(jié)點(diǎn)的估價(jià)值，并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。并為每一個(gè)子節(jié)點(diǎn)都配置指向父節(jié)點(diǎn)的指針。把這些子節(jié)把這些子節(jié)點(diǎn)都送入點(diǎn)都送入OPEN表中，然后對(duì)表中，然后對(duì)OPEN表中的全部節(jié)點(diǎn)按估價(jià)表中的全部節(jié)點(diǎn)按估價(jià)值從小至大的順序進(jìn)行排序值從小至大的順序進(jìn)行排序，然后轉(zhuǎn)第，然后轉(zhuǎn)第2步。步。A算法v全局擇優(yōu)搜索算法：全局擇優(yōu)搜索算法：八數(shù)碼難題八數(shù)碼難題

60、設(shè)問(wèn)題的初始狀態(tài)設(shè)問(wèn)題的初始狀態(tài)S0和目標(biāo)狀態(tài)和目標(biāo)狀態(tài)Sg如圖所示如圖所示估價(jià)函數(shù)為：估價(jià)函數(shù)為： f(n)=d(n)+W(n)d(n)：表示節(jié)點(diǎn)：表示節(jié)點(diǎn)n在搜索樹(shù)中的深在搜索樹(shù)中的深度度W(n)：表示節(jié)點(diǎn)：表示節(jié)點(diǎn)n中中“不在位不在位”的數(shù)的數(shù)碼個(gè)數(shù)碼個(gè)數(shù)用全局擇優(yōu)搜索解決該問(wèn)題用全局擇優(yōu)搜索解決該問(wèn)題1238476528314765S0Sg啟發(fā)性信息和估價(jià)函數(shù)v 用全局擇優(yōu)搜索求解八數(shù)用全局擇優(yōu)搜索求解八數(shù)碼難題碼難題v 解：解： 該問(wèn)題的全局擇優(yōu)搜索樹(shù)該問(wèn)題的全局擇優(yōu)搜索樹(shù)如右圖所示如右圖所示 在該圖中，每個(gè)節(jié)點(diǎn)旁邊在該圖中，每個(gè)節(jié)點(diǎn)旁邊的數(shù)字是該節(jié)點(diǎn)的估價(jià)函的數(shù)字是該節(jié)點(diǎn)的估價(jià)函數(shù)