1、西安電子科技大學西安電子科技大學Artificial Intelligence (AI)人工智能人工智能主講：戚玉濤Email：qi_第三章：確定性推理西安電子科技大學西安電子科技大學內容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結演繹推理歸結演繹推理5.5.基于規則的演繹推理基于規則的演繹推理西安電子科技大學西安電子科技大學內容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結演繹推理歸結演繹推理5.5.基于規則的演繹推理基于規則的演繹推理西安電子科技大學西安電子科技大學

2、推理的基本概念v推理的基本概念推理的基本概念1.1.什么是推理什么是推理2.2.推理方法及其分類推理方法及其分類3.3.推理的控制策略及其分類推理的控制策略及其分類西安電子科技大學西安電子科技大學推理的基本概念v什么是推理什么是推理所謂推理就是按某種策略由已知判斷推出另一個判所謂推理就是按某種策略由已知判斷推出另一個判斷的思維過程。斷的思維過程。在人工智能中，推理是由程序實現的，稱為推理機。在人工智能中，推理是由程序實現的，稱為推理機。智能系統的推理過程實際上就是一種思維過程。按智能系統的推理過程實際上就是一種思維過程。按照推理過程所用知識的確定性，推理可分為：照推理過程所用知識的確定性，推理

3、可分為：p 確定性推理（第三章）確定性推理（第三章）p 不確定性推理（第四章）不確定性推理（第四章）西安電子科技大學西安電子科技大學推理的基本概念v推理的兩個基本問題推理的兩個基本問題推理的方法：推理的方法：p演繹？歸納？類比？確定？不確定？單調？非單調？演繹？歸納？類比？確定？不確定？單調？非單調？啟發式？非啟發式？啟發式？非啟發式？推理的控制策略：推理的控制策略：p推理的控制策略是指如何使用領域知識使推理過程推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策略。盡快達到目標的策略。p推理的控制策略又可分為推理的控制策略又可分為搜索策略搜索策略和和推理策略推理策略。西安電子科技大學

4、西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類p演繹推理演繹推理: :從已知的一般性知識出發，推出蘊含在從已知的一般性知識出發，推出蘊含在已知知識中的適合于某種個別情況的結論。是一種已知知識中的適合于某種個別情況的結論。是一種由一般到個別的推理方法，其由一般到個別的推理方法，其核心是三段論核心是三段論。p歸納推理歸納推理: :是一種由個別到一般的推理方法。是一種由個別到一般的推理方法。p類比歸納推理類比歸納推理: :是指在兩個或兩類事物有許多屬性是指在兩個或兩類事物有許多屬性都相同或相似的基礎上，推出它們在其他屬性上也都相同或相

5、似的基礎上，推出它們在其他屬性上也相同或相似的一種歸納推理相同或相似的一種歸納推理。西安電子科技大學西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類演繹推理：演繹推理： 假言三段論：假言三段論：AB，BC AC 常用的三段論是由一個常用的三段論是由一個大前提大前提、一個小前提一個小前提和和一個結一個結論論這三部分組成的。這三部分組成的。 大前提是已知的一般性知識或推理過程得到的判斷；大前提是已知的一般性知識或推理過程得到的判斷； 小前提是關于某種具體情況或某個具體實例的判斷；小前提是關于某種具體情況或某個具體實例的判斷； 結論是由

6、大前提推出的，并且適合于小前提的判斷。結論是由大前提推出的，并且適合于小前提的判斷。西安電子科技大學西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類演繹推理：演繹推理： 例如，有如下三個判斷：例如，有如下三個判斷： 計算機系的學生都會編程序；計算機系的學生都會編程序； （一般性知識）（一般性知識） 程強是計算機系的一位學生；程強是計算機系的一位學生； （具體情況）（具體情況） 程強會編程序。（結論）程強會編程序。（結論） 這是一個三段論推理。其中，是大前提，是小前這是一個三段論推理。其中，是大前提，是小前提；是經演繹推出來的結論。

7、提；是經演繹推出來的結論。 可見，可見，其結論是蘊含在大前提中的其結論是蘊含在大前提中的西安電子科技大學西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類歸納推理：歸納推理：按照所選事例的按照所選事例的廣泛性廣泛性可分為可分為完全歸納完全歸納推理推理和和不完全歸納推理不完全歸納推理。 完全歸納推理：完全歸納推理：是指在進行歸納時需要考察相應是指在進行歸納時需要考察相應事物的事物的全部對象全部對象，并根據這些對象是否都具有某，并根據這些對象是否都具有某種屬性，推出該類事物是否具有此屬性。種屬性，推出該類事物是否具有此屬性。 不完全歸納

8、推理：不完全歸納推理：是指在進行歸納時只考察了相是指在進行歸納時只考察了相應事物的應事物的部分對象部分對象，就得出了關于該事物的結論。，就得出了關于該事物的結論。西安電子科技大學西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類歸納推理：歸納推理：按照推理所使用的按照推理所使用的方法方法可分為可分為枚舉枚舉、類類比比、統計統計和和差異歸納推理差異歸納推理等。等。 枚舉歸納推理：枚舉歸納推理：是指在進行歸納時，如果已知某類事是指在進行歸納時，如果已知某類事物的物的有限可數個具體事物有限可數個具體事物都具有某種屬性，則可推出都具有某種屬

9、性，則可推出該類事物都具有此種屬性。該類事物都具有此種屬性。 例如，設有如下事例：例如，設有如下事例：王強是計算機系學生，他會編王強是計算機系學生，他會編程序；高華是計算機系學生，她會編程序；程序；高華是計算機系學生，她會編程序；當這當這些具體事例足夠多時，就可歸納出一個一般性的知識：些具體事例足夠多時，就可歸納出一個一般性的知識：凡是計算機系的學生，就一定會編程序。凡是計算機系的學生，就一定會編程序。西安電子科技大學西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類類比歸納推理：類比歸納推理：若在兩個或兩類事物有許多屬性相若在兩個

10、或兩類事物有許多屬性相同或相似，則推出它們在其他屬性上也相同或相似。同或相似，則推出它們在其他屬性上也相同或相似。 例如：例如：設設A、B分別是兩類事物的集合：分別是兩類事物的集合： A=a1,a2,，B=b1,b2, 并設并設ai與與bi總是成對出現，且當總是成對出現，且當ai有屬性有屬性P時，時，bi就有屬性就有屬性Q與此對應，即與此對應，即P(ai)Q(bi) （i=1,2,.）。）。 當當A與與B中有一新的元素對出現時，若已知中有一新的元素對出現時，若已知a有屬性有屬性P，b有有屬性屬性Q 則類比歸納出結論：則類比歸納出結論：P(a)Q(b)西安電子科技大學西安電子科技大學推理的基本概

11、念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類類比歸納推理：類比歸納推理： 類比歸納推理的基礎是類比歸納推理的基礎是相似原理相似原理，其可靠程度取，其可靠程度取決于兩個或兩類事物的相似程度以及這兩個或兩決于兩個或兩類事物的相似程度以及這兩個或兩類事物的相同屬性與推出的那個屬性之間的相關類事物的相同屬性與推出的那個屬性之間的相關程度。程度。西安電子科技大學西安電子科技大學推理的基本概念v推理方法及其分類推理方法及其分類1.1.按推理的邏輯基礎分類按推理的邏輯基礎分類演繹推理與歸納推理的區別：演繹推理與歸納推理的區別： 演繹推理是在已知領域內的一般性知識的前提

12、下，演繹推理是在已知領域內的一般性知識的前提下，通過演繹求解一個具體問題或者證明一個結論的通過演繹求解一個具體問題或者證明一個結論的正確性。正確性。它所得出的結論實際上早已蘊含在一般它所得出的結論實際上早已蘊含在一般性知識的前提中性知識的前提中，演繹推理只不過是將已有事實，演繹推理只不過是將已有事實揭露出來，因此揭露出來，因此它不能增殖新知識它不能增殖新知識。 歸納推理所推出的結論是沒有包含在前提內容中歸納推理所推出的結論是沒有包含在前提內容中的的。這種由個別事物或現象推出一般性知識的過。這種由個別事物或現象推出一般性知識的過程，程，是增殖新知識的過程是增殖新知識的過程。西安電子科技大學西安電

13、子科技大學推理的基本概念v推理方法及其分類推理方法及其分類2.2.按推理過程所用知識的確定性分類按推理過程所用知識的確定性分類p 確定性推理確定性推理p 不確定性推理不確定性推理3.3.按推理過程推出的結論是否單調增加分類按推理過程推出的結論是否單調增加分類p單調推理單調推理p非單調推理非單調推理4.4.按推理過程是否利用問題的啟發性知識分類按推理過程是否利用問題的啟發性知識分類p啟發式推理啟發式推理p非啟發式推理非啟發式推理西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類推理過程不僅依賴于所用的推理方法，同時也推理過程不僅依賴于所用的推理方法，同時

14、也依賴于推理的控制策略。依賴于推理的控制策略。推理的控制策略是指如何使用領域知識使推理推理的控制策略是指如何使用領域知識使推理過程盡快達到目標的策略過程盡快達到目標的策略。推理的控制策略可分為：推理的控制策略可分為：p搜索策略搜索策略p推理策略推理策略西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類搜索策略：搜索策略：在知識庫中尋找可利用的知識，從而構造在知識庫中尋找可利用的知識，從而構造一條代價較小的推理路線。主要解決推理線路、推理一條代價較小的推理路線。主要解決推理線路、推理效果、推理效率等問題。效果、推理效率等問題。按是否使用啟發式信息可分為：

15、按是否使用啟發式信息可分為：p盲目搜索盲目搜索p啟發式搜索啟發式搜索按問題的表示方式可分為：按問題的表示方式可分為：p狀態空間搜索狀態空間搜索p與或樹搜索與或樹搜索西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類推理策略：推理策略：包括推理方向控制策略、求解策略、限制包括推理方向控制策略、求解策略、限制策略、沖突消解策略等策略、沖突消解策略等p推理方向控制策略：推理方向控制策略：用于確定推理的控制方向，可分為用于確定推理的控制方向，可分為正向推理、逆向推理、混合推理及雙向推理。正向推理、逆向推理、混合推理及雙向推理。p求解策略：求解策略：是指僅求一個

16、解，還是求所有解或最優解等。是指僅求一個解，還是求所有解或最優解等。p限制策略：限制策略：是指對推理的深度、寬度、時間、空間等進是指對推理的深度、寬度、時間、空間等進行的限制。行的限制。p沖突消解策略：沖突消解策略：是指當推理過程有多條知識可用時，如是指當推理過程有多條知識可用時，如何從這多條可用知識中選出一條最佳知識用于推理的策何從這多條可用知識中選出一條最佳知識用于推理的策略。略。西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：正向推理：正向推理：從已知事實出發、正向使用推理規則，從已知事實出發、正向使用推理

17、規則，亦稱為數據驅動推理或前向鏈推理。亦稱為數據驅動推理或前向鏈推理。 正向推理從用戶提供的初始已知事實出發，在知識庫正向推理從用戶提供的初始已知事實出發，在知識庫KB中找出當前可適用的知識，構成可適用的知識集中找出當前可適用的知識，構成可適用的知識集KS；然；然后按某種沖突消解策略從后按某種沖突消解策略從KS中選出一條知識進行推理，中選出一條知識進行推理，并將推出的新事實加入到數據庫并將推出的新事實加入到數據庫DB中，作為下一步推理中，作為下一步推理的已知事實。在此之后，再在知識庫中選取可適用的知的已知事實。在此之后，再在知識庫中選取可適用的知識進行推理。如此重復進行這一過程，直到求得所要求

18、識進行推理。如此重復進行這一過程，直到求得所要求的解。的解。西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略： 正向推理中，如何根據已知事實到知識庫中選取可用知正向推理中，如何根據已知事實到知識庫中選取可用知識？當知識庫中有多條知識可用時應該先使用那一條知識？當知識庫中有多條知識可用時應該先使用那一條知識？這些問題涉及到了識？這些問題涉及到了知識的匹配方法知識的匹配方法和和沖突消解策略。沖突消解策略。 正向推理的優點：正向推理的優點：比較直觀，允許用戶主動提供有用的比較直觀，允許用戶主動提供有用的事實信息，適合于診

19、斷、設計、預測、監控等領域的問事實信息，適合于診斷、設計、預測、監控等領域的問題求解。題求解。 正向推理的缺點：正向推理的缺點：推理無明確目標，求解問題是可能會推理無明確目標，求解問題是可能會執行許多與解無關的操作，導致推理效率較低。執行許多與解無關的操作，導致推理效率較低。 西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：逆向推理：逆向推理：從某個假設目標出發，逆向使用規則，從某個假設目標出發，逆向使用規則，亦稱為目標驅動推理或逆向鏈推理。亦稱為目標驅動推理或逆向鏈推理。逆向推理首先選定一個假設目標，然后尋找支

20、持該逆向推理首先選定一個假設目標，然后尋找支持該假設的證據，若所需的證據都能找到，則說明原假假設的證據，若所需的證據都能找到，則說明原假設是成立的；若找不到所需要的證據，則說明原假設是成立的；若找不到所需要的證據，則說明原假設不成立，此時需要另作新的假設。設不成立，此時需要另作新的假設。西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：逆向推理的主要優點：逆向推理的主要優點：不必尋找和使用那些與假設不必尋找和使用那些與假設目標無關的信息和知識，推理過程的目標明確，有目標無關的信息和知識，推理過程的目標明確，有利于向

21、用戶提供解釋，在診斷性專家系統中較為有利于向用戶提供解釋，在診斷性專家系統中較為有效。效。逆向推理的主要缺點：逆向推理的主要缺點：當用戶對解的情況認識不請當用戶對解的情況認識不請時，由系統自主選擇假設目標的盲目性比較大，若時，由系統自主選擇假設目標的盲目性比較大，若選擇不好，可能需要多次提出假設，會影響系統效選擇不好，可能需要多次提出假設，會影響系統效率。率。西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：混合推理：混合推理：把正向推理和逆向推理結合起來所進行把正向推理和逆向推理結合起來所進行的推理稱為混合推理。

22、是一種解決較復雜問題的方的推理稱為混合推理。是一種解決較復雜問題的方法。法。混合推理方法的三種類型：混合推理方法的三種類型：z1. 先正向后逆向：先正向后逆向：這種方法先進行正向推理，從這種方法先進行正向推理，從已知事實出發推出部分結果，然后再用逆向推理已知事實出發推出部分結果，然后再用逆向推理對這些結果進行證實或提高它們的可信度。對這些結果進行證實或提高它們的可信度。 西安電子科技大學西安電子科技大學推理的基本概念v推理的控制策略及其分類推理的控制策略及其分類p推理方向控制策略：推理方向控制策略：混合推理方法的三種類型：混合推理方法的三種類型：z 2. 先逆向后正向：先逆向后正向：這種方法先

23、進行逆向推理，這種方法先進行逆向推理，從假設目標出發推出一些中間假設，然后再用正從假設目標出發推出一些中間假設，然后再用正向推理對這些中間假設進行證實。向推理對這些中間假設進行證實。 z 3. 雙向混合：雙向混合：是指正向推理和逆向推理同時進是指正向推理和逆向推理同時進行，使推理過程在中間的某一步結合起來。行，使推理過程在中間的某一步結合起來。西安電子科技大學西安電子科技大學內容提要1.1.推理的基本概念推理的基本概念2.2.搜索策略搜索策略3.3.自然演繹推理自然演繹推理4.4.歸結演繹推理歸結演繹推理5.5.基于規則的演繹推理基于規則的演繹推理西安電子科技大學西安電子科技大學搜索策略v搜索

24、策略搜索策略搜索的基本概念搜索的基本概念狀態空間的搜索策略狀態空間的搜索策略與與/ /或樹的搜索策略或樹的搜索策略搜索的完備性與效率搜索的完備性與效率西安電子科技大學西安電子科技大學搜索的基本概念v搜索的基本概念搜索的基本概念搜索是人工智能中的一個基本問題，并與推理密切相搜索是人工智能中的一個基本問題，并與推理密切相關，搜索策略的優劣，將直接影響到智能系統的性能關，搜索策略的優劣，將直接影響到智能系統的性能與推理效率。與推理效率。搜索的定義：搜索的定義：依靠經驗，利用已有知識，根據問題的依靠經驗，利用已有知識，根據問題的實際情況，不斷尋找可利用知識，從而構造一條代價實際情況，不斷尋找可利用知識

25、，從而構造一條代價最小的推理路線，使問題得以解決的過程稱為搜索。最小的推理路線，使問題得以解決的過程稱為搜索。搜索的適用情況：搜索的適用情況：不良結構或非結構化問題；難以獲不良結構或非結構化問題；難以獲得求解所需的全部信息；更沒有現成的算法可供求解得求解所需的全部信息；更沒有現成的算法可供求解使用。使用。西安電子科技大學西安電子科技大學搜索的基本概念v搜索的類型搜索的類型按是否使用啟發式信息：按是否使用啟發式信息：p盲目搜索：盲目搜索：按預定的控制策略進行搜索，在搜索過按預定的控制策略進行搜索，在搜索過程中獲得的中間信息并不改變控制策略。程中獲得的中間信息并不改變控制策略。 p啟發式搜索：啟發

26、式搜索：在搜索中加入了與問題有關的啟發性在搜索中加入了與問題有關的啟發性信息，用于指導搜索朝著最有希望的方向前進，加信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解過程并找到最優解。速問題的求解過程并找到最優解。 按問題的表示方式：按問題的表示方式：p狀態空間搜索：狀態空間搜索：用狀態空間法求解問題進行的搜索用狀態空間法求解問題進行的搜索 p與或樹搜索：與或樹搜索：用問題歸約法求解問題進行的搜索用問題歸約法求解問題進行的搜索 西安電子科技大學西安電子科技大學狀態空間的搜索策略v狀態空間的搜索策略狀態空間的搜索策略狀態空間搜索的基本思想狀態空間搜索的基本思想圖搜索的一般過程圖搜索的一般過

27、程狀態空間的盲目搜索狀態空間的盲目搜索p廣度優先搜索廣度優先搜索p深度優先搜索深度優先搜索p代價樹搜索代價樹搜索狀態空間的啟發式搜索狀態空間的啟發式搜索p啟發性信息和估價函數啟發性信息和估價函數pA算法和算法和A*算法算法西安電子科技大學西安電子科技大學狀態空間的搜索策略v狀態空間搜索的基本思想狀態空間搜索的基本思想先把問題的初始狀態作為當前先把問題的初始狀態作為當前擴展節點擴展節點對其進行對其進行擴展擴展，生成一組子節點。生成一組子節點。然后檢查問題的目標狀態是否出現在這些子節點中。若然后檢查問題的目標狀態是否出現在這些子節點中。若出現，則搜索成功，找到了問題的解；若沒出現，則再出現，則搜索

28、成功，找到了問題的解；若沒出現，則再按照某種搜索策略從已生成的子節點中選擇一個節點作按照某種搜索策略從已生成的子節點中選擇一個節點作為當前擴展節點為當前擴展節點。重復上述過程，直到目標狀態出現在子節點中或者沒有重復上述過程，直到目標狀態出現在子節點中或者沒有可供操作的節點為止。可供操作的節點為止。所謂對一個節點進行所謂對一個節點進行“擴展擴展”是指對該節點用某個可用是指對該節點用某個可用操作進行作用，生成該節點的一組子節點。操作進行作用，生成該節點的一組子節點。 西安電子科技大學西安電子科技大學狀態空間的搜索策略v狀態空間搜索算法的數據結構和符號約定狀態空間搜索算法的數據結構和符號約定OPEN

29、表：表：未擴展節點表，用于存放剛生成節點未擴展節點表，用于存放剛生成節點CLOSED表：表：已擴展節點表，用于存放已經擴已擴展節點表，用于存放已經擴展或將要擴展節點的展或將要擴展節點的S：用表示問題的初始狀態用表示問題的初始狀態G：表示搜索過程所得到的搜索圖表示搜索過程所得到的搜索圖M：表示當前擴展節點新生成的且不為自己先輩表示當前擴展節點新生成的且不為自己先輩的子節點集的子節點集西安電子科技大學西安電子科技大學狀態空間的搜索策略v圖搜索的一般過程圖搜索的一般過程(1) 把初始節點把初始節點S放入未擴展節點表放入未擴展節點表OPEN表，并建立目表，并建立目前僅包含前僅包含S的圖的圖G；(2)

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

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

32、展的M成員，確成員，確定是否需要修改它指向父節點的指針。（原生成但未擴展的）定是否需要修改它指向父節點的指針。（原生成但未擴展的）p 對于那些先前已在對于那些先前已在G中出現過，并已經擴展了的中出現過，并已經擴展了的M成員，確成員，確定是否需要修改其后繼節點指向父節點的指針。（原生成也擴定是否需要修改其后繼節點指向父節點的指針。（原生成也擴展過的）展過的）西安電子科技大學西安電子科技大學v圖搜索的一般過程圖搜索的一般過程 (7) 按某種策略對按某種策略對OPEN表中的節點表中的節點進行排序。進行排序。 (8) 轉第轉第(2)步。步。 狀態空間的搜索策略西安電子科技大學西安電子科技大學狀態空間的

33、搜索策略v圖搜索的一般過程的幾點說明：圖搜索的一般過程的幾點說明：上述過程是狀態空間的一般圖搜索算法，它具上述過程是狀態空間的一般圖搜索算法，它具有通用性，后面所要討論的各種狀態空間搜索有通用性，后面所要討論的各種狀態空間搜索策略都是上述過程的一個特例。策略都是上述過程的一個特例。各種搜索策略的主要區別在于對各種搜索策略的主要區別在于對OPEN表中節表中節點的排列順序不同。點的排列順序不同。例如，廣度優先搜索把先例如，廣度優先搜索把先生成的子節點排在前面，而深度優先搜索則把生成的子節點排在前面，而深度優先搜索則把后生成的子節點排在前面。后生成的子節點排在前面。西安電子科技大學西安電子科技大學狀

34、態空間的搜索策略v圖搜索的一般過程的幾點說明：圖搜索的一般過程的幾點說明：在第在第(6)步針對步針對M中子節點的不同情況進行處理時，如果中子節點的不同情況進行處理時，如果發生當第種情況，那么，這個發生當第種情況，那么，這個M中的節點究竟應該作中的節點究竟應該作為哪一個節點的后繼節點呢？一般是由原始節點到該節為哪一個節點的后繼節點呢？一般是由原始節點到該節點路徑上所付出的代價來決定的，哪一條路經付出的代點路徑上所付出的代價來決定的，哪一條路經付出的代價小，相應的節點就作為它的父節點。所謂由原始節點價小，相應的節點就作為它的父節點。所謂由原始節點到該節點路徑上的代價是指這條路經上的所有有向邊的到該

35、節點路徑上的代價是指這條路經上的所有有向邊的代價之和。代價之和。 如果發生第種情況，除了需要確定該子節點指向父節如果發生第種情況，除了需要確定該子節點指向父節點的指針外，還需要確定其后繼節點指向父節點的指針。點的指針外，還需要確定其后繼節點指向父節點的指針。其依據也是由原始節點到該節點的路徑上的代價。其依據也是由原始節點到該節點的路徑上的代價。西安電子科技大學西安電子科技大學狀態空間的搜索策略v圖搜索的一般過程的幾點說明：圖搜索的一般過程的幾點說明：在搜索圖中，除初始節點外，任意一個節點都含有且在搜索圖中，除初始節點外，任意一個節點都含有且只含有一個指向其父節點的指針。因此，由所有節點只含有一

36、個指向其父節點的指針。因此，由所有節點及其指向父節點的指針所構成的集合是一棵樹，稱為及其指向父節點的指針所構成的集合是一棵樹，稱為搜索樹搜索樹。在搜索過程的第在搜索過程的第(4)步，一旦某個被考察的節點是目標步，一旦某個被考察的節點是目標節點，則搜索過程成功結束。此時，由初始節點到目節點，則搜索過程成功結束。此時，由初始節點到目標節點路徑上的所有操作就構成了該問題的解，而路標節點路徑上的所有操作就構成了該問題的解，而路徑由第徑由第(6)步所形成的指向父節點的指針來確定。步所形成的指向父節點的指針來確定。如果搜索過程終止在第如果搜索過程終止在第(2)步，即沒有達到目標，且步，即沒有達到目標，且O

37、PEN表中已無可供擴展的節點，則失敗結束。表中已無可供擴展的節點，則失敗結束。 西安電子科技大學西安電子科技大學狀態空間的搜索策略v狀態空間的搜索策略狀態空間的搜索策略狀態空間搜索的基本思想狀態空間搜索的基本思想圖搜索的一般過程圖搜索的一般過程狀態空間的盲目搜索狀態空間的盲目搜索p廣度優先搜索廣度優先搜索p深度優先搜索深度優先搜索p代價樹搜索代價樹搜索狀態空間的啟發式搜索狀態空間的啟發式搜索p啟發性信息和估價函數啟發性信息和估價函數pA算法和算法和A*算法算法西安電子科技大學西安電子科技大學廣度優先搜索v狀態空間的廣度優先搜索狀態空間的廣度優先搜索廣度優先搜索的基本思想：廣度優先搜索的基本思想：p從初始節點從初始節點S開始逐層向下擴展，在第開始逐層向下擴展，在第n層層節點還沒有全部搜索完之前，不進入第節點還沒有全部搜索完之前，不進入第n+1層節點的搜索。層節點的搜索。p未擴展節點表未擴展節點表OPEN表中的節點總是按進入表中的節點總是按進入的先后排序，先進入的節點排在前面，后進的先后排序，先進入的節點排在前面，后進入的節點排在后面。入的節點排在后面。西安電子