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

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

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

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

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

5、性。 不完全歸納推理：不完全歸納推理：在進行歸納時只考察了相應事在進行歸納時只考察了相應事物的物的部分對象部分對象，就得出了關于該事物的結論。，就得出了關于該事物的結論。推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分：按推理的邏輯基礎分：演繹，歸納，類比歸納推理演繹，歸納，類比歸納推理類比歸納推理：類比歸納推理：若在兩個或兩類事物有許多屬性相若在兩個或兩類事物有許多屬性相同或相似，則推出它們在其他屬性上也相同或相似。同或相似，則推出它們在其他屬性上也相同或相似。 類比歸納推理的基礎是類比歸納推理的基礎是相似原理相似原理，其可靠程度取，其可靠程度取決于兩個或兩類事物的

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

23、結構和符號約定OPEN表：表：未擴展節(jié)點表，用于存放剛生成節(jié)點未擴展節(jié)點表，用于存放剛生成節(jié)點CLOSED表：表：已擴展節(jié)點表，用于存放已經擴已擴展節(jié)點表，用于存放已經擴展或將要擴展節(jié)點的展或將要擴展節(jié)點的S：用表示問題的初始狀態(tài)用表示問題的初始狀態(tài)G：表示搜索過程所得到的搜索圖表示搜索過程所得到的搜索圖M：表示當前擴展節(jié)點新生成的且不為自己先輩表示當前擴展節(jié)點新生成的且不為自己先輩的子節(jié)點集的子節(jié)點集狀態(tài)空間的搜索策略v圖搜索的一般過程圖搜索的一般過程(1) 把初始節(jié)點把初始節(jié)點S放入未擴展節(jié)點表放入未擴展節(jié)點表OPEN表，并建立目表，并建立目前僅包含前僅包含S的圖的圖G；(2) 檢查檢查O

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

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

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

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

28、行處理時，如果發(fā)生當第種情況，那么，這個時，如果發(fā)生當第種情況，那么，這個M中的中的節(jié)點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？節(jié)點究竟應該作為哪一個節(jié)點的后繼節(jié)點呢？一般是由原始節(jié)點到該節(jié)點路徑上所付出的代一般是由原始節(jié)點到該節(jié)點路徑上所付出的代價來決定的，哪一條路經付出的代價小，相應價來決定的，哪一條路經付出的代價小，相應的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到的節(jié)點就作為它的父節(jié)點。所謂由原始節(jié)點到該節(jié)點路徑上的代價是指這條路經上的所有有該節(jié)點路徑上的代價是指這條路經上的所有有向邊的代價之和。向邊的代價之和。 狀態(tài)空間的搜索策略v圖搜索的一般過程的幾點說明：圖搜索的一般過程的幾點說明：如果發(fā)

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

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

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

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

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

34、作對于任意一個可擴展的節(jié)點，總是按照固定的操作符的順序對其進行擴展（符的順序對其進行擴展（空格左移、上移、右移、空格左移、上移、右移、下移下移）。）。在對任一節(jié)點進行擴展的時候，在對任一節(jié)點進行擴展的時候，如果所得的某個子如果所得的某個子節(jié)點（狀態(tài)）前面已經出現(xiàn)過，則立即將其放棄，節(jié)點（狀態(tài)）前面已經出現(xiàn)過，則立即將其放棄，不再重復畫出（不送入不再重復畫出（不送入OPEN表）表）。因此，廣度優(yōu)先搜索的本質是，以初始節(jié)點為根節(jié)因此，廣度優(yōu)先搜索的本質是，以初始節(jié)點為根節(jié)點，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一點，在狀態(tài)空間圖中按照廣度優(yōu)先的原則，生成一棵搜索樹。棵搜索樹。廣度優(yōu)先搜索v廣度優(yōu)

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

36、樹搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價函數啟發(fā)性信息和估價函數pA算法和算法和A*算法算法深度優(yōu)先搜索v狀態(tài)空間的深度優(yōu)先搜索狀態(tài)空間的深度優(yōu)先搜索深度優(yōu)先搜索的基本思想：深度優(yōu)先搜索的基本思想：p從初始節(jié)點從初始節(jié)點S開始，在其子節(jié)點中選擇一個最新開始，在其子節(jié)點中選擇一個最新生成的節(jié)點進行考察。生成的節(jié)點進行考察。p如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴如果該子節(jié)點不是目標節(jié)點且可以擴展，則擴展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選展該子節(jié)點，然后再在此子節(jié)點的子節(jié)點中選擇一個最新生成的節(jié)點進行考察。擇一個最新生成的節(jié)點進行考察。p依此向下搜索，直到某個子節(jié)點既

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

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

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

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

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

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

43、或費用) )的樹稱為代價樹的樹稱為代價樹v 在代價樹中，若用在代價樹中，若用g(x)表示從初始節(jié)點表示從初始節(jié)點S到節(jié)點到節(jié)點x的代價，的代價，用用c(x1,x2)表示從父節(jié)點表示從父節(jié)點x1到子節(jié)點到子節(jié)點x2的代價，則有：的代價，則有：g(x2)=g(x1)+c(x1,x2)v代價樹搜索：代價樹搜索：考慮邊的代價的搜索方法，代價樹搜索的考慮邊的代價的搜索方法，代價樹搜索的目的是為了找到一條代價最小的解路徑。代價樹搜索方法目的是為了找到一條代價最小的解路徑。代價樹搜索方法包括：包括：代價樹的廣度優(yōu)先搜索代價樹的廣度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的深度優(yōu)先搜索代價樹的廣度優(yōu)先搜索v代價樹的

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

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

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

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

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

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

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

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

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

53、望的方向前進。v啟發(fā)性信息的概念：啟發(fā)性信息的概念：啟發(fā)性信息是指那種與具體問題啟發(fā)性信息是指那種與具體問題求解過程有關的，并可指導搜索過程朝著最有希望方向前求解過程有關的，并可指導搜索過程朝著最有希望方向前進的控制信息。進的控制信息。啟發(fā)信息的啟發(fā)能力越強，擴展的無用結啟發(fā)信息的啟發(fā)能力越強，擴展的無用結點越少。點越少。v啟發(fā)性信息的種類啟發(fā)性信息的種類有效地幫助確定擴展節(jié)點的信息有效地幫助確定擴展節(jié)點的信息有效的幫助決定哪些后繼節(jié)點應被生成的信息有效的幫助決定哪些后繼節(jié)點應被生成的信息能決定在擴展一個節(jié)點時哪些節(jié)點應從搜索樹上刪除能決定在擴展一個節(jié)點時哪些節(jié)點應從搜索樹上刪除的信息的信息啟

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

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

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

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

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

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

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