西電人工智能8確定性推理part1

1、西安電子科技大學西安電子科技大學Artificial Intelligence (AI)人工智能人工智能主講：戚玉濤Email：qi_第三章：確定性推理西安電子科技大學西安電子科技大學內(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ī)則的演繹推理西安電子科技大學西安電子科技大學

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

27、程狀態(tài)空間的盲目搜索狀態(tài)空間的盲目搜索p廣度優(yōu)先搜索廣度優(yōu)先搜索p深度優(yōu)先搜索深度優(yōu)先搜索p代價樹搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價函數(shù)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)，則搜索成功，找到了問題的解；若沒出現(xiàn)，則再出現(xiàn)，則搜索

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

29、表：表：未擴展節(jié)點表，用于存放剛生成節(jié)點未擴展節(jié)點表，用于存放剛生成節(jié)點CLOSED表：表：已擴展節(jié)點表，用于存放已經(jīng)擴已擴展節(jié)點表，用于存放已經(jīng)擴展或?qū)⒁獢U展節(jié)點的展或?qū)⒁獢U展節(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)

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

31、節(jié)點擴展節(jié)點n，生成一組子節(jié)點。把這些子節(jié)點中不是，生成一組子節(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成員設(shè)置一個指向其父節(jié)點成員設(shè)置一個指向其父節(jié)點（即節(jié)點（即節(jié)點n）的指針，并把它放入）的指針，并把它放入OPEN表。（新生成的）表。（新生成的）p 對那些原來已在對那些原來已在G中出現(xiàn)過，但還沒有被擴展的中出現(xiàn)過，但還沒有被擴

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

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

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

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

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

37、PEN表中已無可供擴展的節(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代價樹搜索代價樹搜索狀態(tài)空間的啟發(fā)式搜索狀態(tài)空間的啟發(fā)式搜索p啟發(fā)性信息和估價函數(shù)啟發(fā)性信息和估價函數(shù)pA算法和算法和A*算法算法西安電子科技大學西安電子科技大學廣度優(yōu)先搜索v狀態(tài)空間的廣度優(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é)點排在后面。西安電子