第2章基于狀態(tài)空間圖表示的搜索技術(shù)

1、2021-12-31人工智能2第第2 2章章 基于圖的知識表示與圖搜索技術(shù)基于圖的知識表示與圖搜索技術(shù)2.1 2.1 概述概述2.2 2.2 狀態(tài)空間圖表示狀態(tài)空間圖表示2.3 2.3 狀態(tài)空間圖的盲目搜索狀態(tài)空間圖的盲目搜索2.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索2.5 2.5 與或圖表示及搜索技術(shù)與或圖表示及搜索技術(shù)2.6 2.6 博弈樹及搜索技術(shù)博弈樹及搜索技術(shù)2021-12-31人工智能32.1 2.1 概述概述2.1.1 2.1.1 知識與問題求解框架知識與問題求解框架2.1.2 2.1.2 知識表示知識表示2.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)2021-1

2、2-31人工智能42.1.1 2.1.1 知識與問題求解框架知識與問題求解框架(1)(1) 1. 1.知識的定義知識的定義n心理學(xué)心理學(xué)：個體通過與環(huán)境相互作用后獲得的信息及：個體通過與環(huán)境相互作用后獲得的信息及其組織。其組織。n費(fèi)根鮑姆費(fèi)根鮑姆：知識是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的：知識是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。信息。n博恩斯坦博恩斯坦（BernsteinBernstein）：知識是由特定領(lǐng)域的描）：知識是由特定領(lǐng)域的描述、關(guān)系和過程組成的。述、關(guān)系和過程組成的。 概括地說，知識是高度組織起來的信息集團(tuán)，概括地說，知識是高度組織起來的信息集團(tuán)，是人們在長期的生活和社會實(shí)踐中、科學(xué)研究

3、和科是人們在長期的生活和社會實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗中積累起來的經(jīng)驗或?qū)陀^世界規(guī)律的認(rèn)識學(xué)實(shí)驗中積累起來的經(jīng)驗或?qū)陀^世界規(guī)律的認(rèn)識等。等。2.1.1 2.1.1 知識與問題求解框架知識與問題求解框架(2)(2)2.2.知識的分類知識的分類（1 1）從應(yīng)用領(lǐng)域來劃分）從應(yīng)用領(lǐng)域來劃分n常識性知識常識性知識n領(lǐng)域（專業(yè)）性知識領(lǐng)域（專業(yè)）性知識（2 2）從在問題求解中的作用來劃分）從在問題求解中的作用來劃分n敘述性知識敘述性知識n過程性知識過程性知識n控制性知識控制性知識（3 3）從確定性來劃分）從確定性來劃分n確定性知識確定性知識n非確定性知識非確定性知識（4 4）從知識的表現(xiàn)形式來劃分，

4、可分為文字、符號、聲）從知識的表現(xiàn)形式來劃分，可分為文字、符號、聲音、圖形、圖像等。音、圖形、圖像等。2021-12-31人工智能52.1.1 2.1.1 知識與問題求解框架知識與問題求解框架(3)(3)3.3.問題求解框架問題求解框架n問題：是指事件或事物的已知或問題：是指事件或事物的已知或當(dāng)前狀態(tài)當(dāng)前狀態(tài)與與目目標(biāo)狀態(tài)標(biāo)狀態(tài)之間有之間有差異差異。n問題求解：是指在一定的控制策略下，問題求解：是指在一定的控制策略下，通過通過一一系列的系列的操作操作或或運(yùn)算運(yùn)算來來改變改變問題的問題的狀態(tài)狀態(tài)，使之與目，使之與目標(biāo)狀態(tài)接近或一致。標(biāo)狀態(tài)接近或一致。例如，李明在北京，他要去西安（辦事）。例如，李

5、明在北京，他要去西安（辦事）。又如，博弈問題。又如，博弈問題。2021-12-31人工智能6問題的求解框架問題的求解框架（1 1）敘述性知識：敘述性知識：描述問題的狀態(tài)有關(guān)的各種描述問題的狀態(tài)有關(guān)的各種知識。知識。（2 2）過程性知識：過程性知識：描述狀態(tài)之間的變換關(guān)系的描述狀態(tài)之間的變換關(guān)系的各種知識。各種知識。（3 3）控制性知識：控制性知識：描述如何在當(dāng)前狀態(tài)下選擇描述如何在當(dāng)前狀態(tài)下選擇合適操作的知識。合適操作的知識。2021-12-31人工智能82.1.2 2.1.2 知識表示知識表示(1)(1)知識表示：就是研究知識表示：就是研究在計算機(jī)中在計算機(jī)中如何用最合適的形式如何用最合適的

6、形式表示表示問題求解過程中所需要的各種知識，包括構(gòu)成問題求解框問題求解過程中所需要的各種知識，包括構(gòu)成問題求解框架的全部知識。架的全部知識。常用的知識表示形式常用的知識表示形式狀態(tài)空間圖狀態(tài)空間圖與或圖與或圖謂詞邏輯謂詞邏輯產(chǎn)生式產(chǎn)生式框架框架語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)2.1.2 2.1.2 知識表示知識表示(2)(2)2021-12-31人工智能9例例2.12.1 麥卡賽問題麥卡賽問題。 在一個在一個2n2n 2n2n的方格棋盤中，去掉的方格棋盤中，去掉對角的兩個方格，如圖（對角的兩個方格，如圖（a a），問能否將它全部劃成若干），問能否將它全部劃成若干1 1 2 2的小長方塊？的小長方塊？目標(biāo)狀態(tài)目

7、標(biāo)狀態(tài)初始狀態(tài)初始狀態(tài)可達(dá)狀態(tài)可達(dá)狀態(tài)同構(gòu)問題同構(gòu)問題同態(tài)問題同態(tài)問題2021-12-31人工智能102.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)(1)(1)1.1.搜索搜索 搜索，簡單地說就是搜索，簡單地說就是“尋找尋找”，目的是找到問題的解。，目的是找到問題的解。在問題求解過程中，待求解的問題被抽象成一定空間上的圖，在問題求解過程中，待求解的問題被抽象成一定空間上的圖，搜索過程就是搜索過程就是從從圖中圖中初始節(jié)點(diǎn)初始節(jié)點(diǎn)出發(fā)，沿著與之相連的邊出發(fā)，沿著與之相連的邊試探試探著著前進(jìn)，前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)尋找目標(biāo)節(jié)點(diǎn)或或可解節(jié)點(diǎn)可解節(jié)點(diǎn)的過程。的過程。2.2.搜索樹搜索樹 搜索過程中搜索過程中經(jīng)

8、過經(jīng)過（考察過）（考察過）的節(jié)點(diǎn)和邊的節(jié)點(diǎn)和邊，按原圖的連接，按原圖的連接關(guān)系，便會關(guān)系，便會構(gòu)成構(gòu)成一個一個樹型樹型的有的有向圖向圖，稱為搜索樹。搜索樹是，稱為搜索樹。搜索樹是一個搜索過程的搜索軌跡，或稱之為一個搜索過程的搜索軌跡，或稱之為搜索空間搜索空間。2.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)(2)(2)2021-12-31人工智能11圖圖 2-2 2-2 搜索空間示意圖搜索空間示意圖問題的狀態(tài)空間、搜索空間及解的示意圖：問題的狀態(tài)空間、搜索空間及解的示意圖：2.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)(3)(3)3.3.搜索策略搜索策略 搜索策略將決定搜索過程按照什么樣的順序考察節(jié)

9、點(diǎn)和搜索策略將決定搜索過程按照什么樣的順序考察節(jié)點(diǎn)和經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。n盲目搜索：盲目搜索：無向?qū)o向?qū)У牡乃阉魉阉?，也稱窮舉搜索。，也稱窮舉搜索。n啟發(fā)式搜索：利用啟發(fā)式搜索：利用“啟發(fā)性信息啟發(fā)性信息”作為作為導(dǎo)航導(dǎo)航的搜索過程。的搜索過程。 對于較大或無限狀態(tài)空間問題，盲目搜索效率太低，所對于較大或無限狀態(tài)空間問題，盲目搜索效率太低，所以在實(shí)際當(dāng)中往往是不可行的。以在實(shí)際當(dāng)中往往是不可行的。 啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問題求解中，如博弈、機(jī)啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問題求解中，如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。2021

10、-12-31人工智能122021-12-31人工智能132.2 2.2 狀態(tài)空間圖表示狀態(tài)空間圖表示2.2.1 2.2.1 狀態(tài)空間圖狀態(tài)空間圖2.2.2 2.2.2 隱式狀態(tài)空間圖隱式狀態(tài)空間圖2021-12-31人工智能142.2.1 2.2.1 狀態(tài)空間圖（狀態(tài)空間圖（1 1）1.1.狀態(tài)狀態(tài) 狀態(tài)對應(yīng)敘述性知識狀態(tài)對應(yīng)敘述性知識，描述一個問題在，描述一個問題在開始、結(jié)束或中間的某一時刻所處的開始、結(jié)束或中間的某一時刻所處的狀況狀況或或狀態(tài)狀態(tài)。通常引進(jìn)一組變量。通常引進(jìn)一組變量 ，表，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組量所構(gòu)成

11、的多元組 來表示狀來表示狀態(tài)。態(tài)。 狀態(tài)在狀態(tài)圖中表示為狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)節(jié)點(diǎn)。12nqqq， ， ，12()nqqq， ，2021-12-31人工智能152.2.1 2.2.1 狀態(tài)空間圖（狀態(tài)空間圖（2 2）2.2.操作操作 操作對應(yīng)過程性知識操作對應(yīng)過程性知識，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)之間的關(guān)系。之間的關(guān)系。描述一個操作要包含兩個部分描述一個操作要包含兩個部分條件條件: :指明被作用的狀態(tài)要滿足的約束條件指明被作用的狀態(tài)要滿足的約束條件動作動作: :指明一個操作對狀態(tài)的分量所做的改變。指明一個操作對狀態(tài)的分量所做的改變。操作的表示形式可以是一個機(jī)械性的步驟

12、、過程、規(guī)則操作的表示形式可以是一個機(jī)械性的步驟、過程、規(guī)則或算子?；蛩阕?。操作在狀態(tài)圖中表示為操作在狀態(tài)圖中表示為邊邊。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可。在程序中，狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。 如：如果室內(nèi)溫度低于如：如果室內(nèi)溫度低于2626度，則關(guān)閉空調(diào)。度，則關(guān)閉空調(diào)。 2021-12-31人工智能162.2.1 2.2.1 狀態(tài)空間圖（狀態(tài)空間圖（3 3）3.3.狀態(tài)空間圖狀態(tài)空間圖n問題的問題的狀態(tài)空間圖狀態(tài)空間圖是一個描述該問題全部可能的是一個描述該問題全部可能的狀態(tài)狀態(tài)及及相互相互關(guān)系關(guān)系的的圖圖，如考慮操作的代價

13、，狀態(tài)空間圖就是一，如考慮操作的代價，狀態(tài)空間圖就是一個個賦值有向圖賦值有向圖。n狀態(tài)空間常記為三元組：狀態(tài)空間常記為三元組： S：初始狀態(tài)的集合初始狀態(tài)的集合 F：操作的集合操作的集合 G：目標(biāo)狀態(tài)的集合。目標(biāo)狀態(tài)的集合。 n由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。SFG， ，2.2.1 2.2.1 狀態(tài)空間圖（狀態(tài)空間圖（4 4）4.4.求解求解n在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找尋找從初始狀態(tài)從初始狀態(tài)Qs出發(fā)出發(fā)到達(dá)到達(dá)目標(biāo)狀態(tài)目標(biāo)狀態(tài)Qg的的路徑路徑問題問題，也就是尋找操作序列的

14、問題。，也就是尋找操作序列的問題。n狀態(tài)空間的解為三元組狀態(tài)空間的解為三元組 nQs ：某個初始狀態(tài)：某個初始狀態(tài)nQg ：某個目標(biāo)狀態(tài)：某個目標(biāo)狀態(tài)na：把把Qs變換成變換成Qg的有限的操作序列的有限的操作序列n狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖Q1Q3Q2f1f2f3f4QsQgfn2021-12-31人工智能172021-12-31人工智能18例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（1 1） 三三枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。 初始狀態(tài)初始狀態(tài)目標(biāo)

15、狀態(tài)集合目標(biāo)狀態(tài)集合例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（2 2）1.1.狀態(tài)狀態(tài)引入一個三元組引入一個三元組(q0,q1,q2)來描述總狀態(tài)，錢幣正面來描述總狀態(tài)，錢幣正面為為0 0，反面為，反面為1 1，全部可能的狀態(tài)為：，全部可能的狀態(tài)為： Q0=(0,0,0) ; Q1=(0,0,1); Q2=(0,1,0) Q3=(0,1,1) ; Q4=(1,0,0); Q5=(1,0,1) Q6=(1,1,0) ; Q7=(1,1,1)。2021-12-31人工智能192.2.操作操作翻動錢幣的操作抽象為改變上述狀態(tài)的算子，翻動錢幣的操作抽象為改變上述狀態(tài)的算子， 即即Fa, b, c

16、a: a:把錢幣把錢幣q0翻轉(zhuǎn)一次翻轉(zhuǎn)一次 b:b:把錢幣把錢幣q1翻轉(zhuǎn)一次翻轉(zhuǎn)一次 c:c:把錢幣把錢幣q2翻轉(zhuǎn)一次翻轉(zhuǎn)一次問題的狀態(tài)空間為問題的狀態(tài)空間為 例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（3 3）例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（4 4）3.3.狀態(tài)空間圖狀態(tài)空間圖 問題的狀態(tài)空間為：問題的狀態(tài)空間為： 2021-12-31人工智能21 構(gòu)造狀態(tài)空間圖：構(gòu)造狀態(tài)空間圖：507QabcQQ， ， ， ，aabababaabbbbcccbcccb例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（5 5）2021-12-31人工智能22翻轉(zhuǎn)錢幣問題狀態(tài)空間圖的翻轉(zhuǎn)錢幣問題狀

17、態(tài)空間圖的另一種表示另一種表示：引入分量引入分量n表示已經(jīng)翻過的次數(shù)表示已經(jīng)翻過的次數(shù)即即Q50表示經(jīng)過表示經(jīng)過0次翻轉(zhuǎn)到次翻轉(zhuǎn)到達(dá)達(dá)Q5； Q41表示經(jīng)過表示經(jīng)過1次翻轉(zhuǎn)到達(dá)次翻轉(zhuǎn)到達(dá)Q4； 。例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（6 6）2021-12-31人工智能23aabababaabbbbcccbcccb2021-12-31人工智能24例例2.32.3 修道士和野人問題（修道士和野人問題（1 1） 在河的左岸有三個修道士、三個野人和一條船，在河的左岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運(yùn)過河去，但受修道士們想用這條船將所有的人都運(yùn)過河去，但受到以下條

18、件的限制：到以下條件的限制： （1 1）修道士和野人都會劃船，但船一次）修道士和野人都會劃船，但船一次最多最多只只能能運(yùn)兩個人運(yùn)兩個人； （2 2）在任何岸邊）在任何岸邊野人數(shù)目野人數(shù)目都都不得超過修道士不得超過修道士，否則修道士就會被野人吃掉。否則修道士就會被野人吃掉。 假定野人會服從任何一種過河安排，試規(guī)劃出假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。一種確保修道士安全過河方案。2021-12-31人工智能25例例2.32.3 修道士和野人問題（修道士和野人問題（2 2）1 1、問題的狀態(tài)、問題的狀態(tài)可以用一個三元數(shù)組來描述：可以用一個三元數(shù)組來描述： S(m, c

19、, b) m：左岸的修道士人數(shù)左岸的修道士人數(shù) m0,1,2,3 c： 左岸的野人數(shù)左岸的野人數(shù) c c 0,1,2,3 b： 左岸的船數(shù)左岸的船數(shù) b0,1右岸的狀態(tài)不必標(biāo)出，因為：右岸的狀態(tài)不必標(biāo)出，因為： 右岸的修道士人數(shù)右岸的修道士人數(shù) m 3m 右岸的野人數(shù)右岸的野人數(shù) c 3c 右岸的船數(shù)右岸的船數(shù) b 1b2021-12-31人工智能26例例2.32.3 修道士和野人問題（修道士和野人問題（3 3）狀態(tài)m, c, b狀態(tài)m, c, b狀態(tài)m, c, b狀態(tài)m, c, bS03 3 1S81 3 1 S163 3 0S241 3 0S13 2 1S91 2 1 S173 2 0S2

20、51 2 0S23 1 1 S101 1 1 S183 1 0S261 1 0S33 0 1 S111 0 1 S193 0 0S271 0 0S42 3 1 S120 3 1 S202 3 0S28 0 3 0不可能狀態(tài)不可能狀態(tài)不合法狀態(tài)不合法狀態(tài)合法狀態(tài)合法狀態(tài)1616例例2.32.3 修道士和野人問題（修道士和野人問題（4 4）2 2、操作操作 pij 操作：左岸到右岸操作：左岸到右岸 qij 操作：右岸到左岸操作：右岸到左岸 船上修道士人數(shù)船上修道士人數(shù)i，野人人數(shù)，野人人數(shù)j滿足：滿足： 1 i+j 2可實(shí)施的操作集為：可實(shí)施的操作集為：F p01, p10,p11,p02,p20

21、,q01,q10,q11, q02,q20 2021-12-31人工智能28例例2.32.3 修道士和野人問題（修道士和野人問題（5 5）操作集操作集Fp01, p10,p11,p02,p20,q01,q10,q11, q02,q20q20b=0, (m=0,c=2)或(m=1,c=1)b=1, m=m+2q02b=0, m=0或3, c2b=1, c=c+2q11b=0, m=c, c2b=1, m=m+1, c=c+1q10b=0, (m=0,c=1)或(m=2,c=2)b=1, m=m+1q01b=0, m=0或3, c2b=1, c=c+1p20b=1, (m=3,c=1)或(m=2,

22、c=2)b=0, m=m-2p02b=1, m=0或3, c2b=0, c=c-2p11b=1, m=c, c1b=0, m=m-1, c=c-1p10b=1, (m=3,c=2)或(m=1,c=1)b=0, m=m-1p01b=1, m=0或3, c1b=0, c=c-1操作符條 件動 作例例2.32.3 修道士和野人問題（修道士和野人問題（6 6）3.3.狀態(tài)空間狀態(tài)空間給出狀態(tài)和操作的描述之后，該問題的狀態(tài)空間是：給出狀態(tài)和操作的描述之后，該問題的狀態(tài)空間是：S0， P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20，S31。 以全部合法狀態(tài)

23、為節(jié)點(diǎn)，按照操作要求的條件，在節(jié)點(diǎn)之以全部合法狀態(tài)為節(jié)點(diǎn)，按照操作要求的條件，在節(jié)點(diǎn)之間構(gòu)造有向邊。間構(gòu)造有向邊。2021-12-31人工智能30例例2.32.3 修道士和野人問題（修道士和野人問題（7 7）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q10S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S31(0,0,0)q11p11S14(0,1,1)p01q01p02q02S10(1,1,1)p10q10S13(0,2,1)q01p01S

24、30(0,1,0) p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.4.狀態(tài)空間圖：狀態(tài)空間圖：四條四條S S0 0到到S S3131長度相等的最短路徑，對應(yīng)的操作長度相等的最短路徑，對應(yīng)的操作序列就是該問題的四個最優(yōu)解序列就是該問題的四個最優(yōu)解 P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20 2021-12-31人工智能312.2.2 隱式狀態(tài)空間圖隱式狀態(tài)空間圖顯式狀態(tài)空間顯式狀態(tài)空間圖：圖： 表表示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，這

25、種這種 表表示方式稱為示方式稱為顯式狀態(tài)空間圖顯式狀態(tài)空間圖，或稱為，或稱為狀態(tài)空間狀態(tài)空間圖的圖的 顯式表示顯式表示。隱式狀態(tài)空間隱式狀態(tài)空間圖：圖： 利利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的知識定用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的知識定義的義的 狀狀態(tài)空間圖。在計算機(jī)中僅存儲描述問題狀態(tài)及態(tài)空間圖。在計算機(jī)中僅存儲描述問題狀態(tài)及操作操作 的的有關(guān)知識，包括該問題的各狀態(tài)分量的取值情有關(guān)知識，包括該問題的各狀態(tài)分量的取值情況、況、 分分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以及全及全 部部操作的條件和動作等。隱式狀態(tài)空間圖也稱為操作的條件和動作等。隱式狀

26、態(tài)空間圖也稱為是是狀狀 態(tài)態(tài)空間圖的隱式表示或隱式圖?？臻g圖的隱式表示或隱式圖。重排九宮問題的隱式圖描述為：重排九宮問題的隱式圖描述為： （1 1）有關(guān)狀態(tài)的知識：）有關(guān)狀態(tài)的知識：狀態(tài)狀態(tài)S的定義：的定義：S(X0，X1，X2，X3，X4 ，X5， X6 ，X7 ，X8) 其中，其中， Xi 0，1，2，3，4，5，6，7，8， ，且，且 。初始狀態(tài)：初始狀態(tài)： S S0 0 （0 0，1 1，2 2，3 3，5 5，6 6，4 4，7 7，8 8） 目標(biāo)狀態(tài)：目標(biāo)狀態(tài)： S Sg g （0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8） 重排九宮問題的狀態(tài)表示80 i

27、ijijXX時，例例2.42.4 重排九宮問題重排九宮問題（八數(shù)碼問題）（八數(shù)碼問題） 例例2.42.4 重排九宮問題（重排九宮問題（2 2）（2 2）有關(guān)操作的知識（規(guī)則）：）有關(guān)操作的知識（規(guī)則）：0 0組規(guī)則組規(guī)則 R1(X0=0 ) (X2=n ) X0 = n X2 =0； R2(X0=0 ) (X4=n ) X0 = n X4 =0； R3(X0=0 ) (X6=n ) X0 = n X6 =0； R4(X0=0 ) (X8=n ) X0 = n X8 =0；1 1組規(guī)則組規(guī)則 R5(X1=0 ) (X2=n ) X1 = n X2 =0； R6(X1=0 ) (X8=n ) X1

28、 = n X8 =0；8 8組規(guī)則組規(guī)則: : R22(X8=0 ) (X1=n ) X8 = n X1 =0； R23(X8=0 ) (X0=n ) X8 = n X0=0； R24(X8=0 ) (X7=n ) X8 = n X7 =0；例例2.42.4 重排九宮問題（重排九宮問題（3 3） 八數(shù)碼的狀態(tài)圖可表示為八數(shù)碼的狀態(tài)圖可表示為 （S0, R1 , R2 , , R24 , Sg） 八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點(diǎn)和八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為生。類似于這樣表示的狀態(tài)圖稱

29、為隱式狀態(tài)隱式狀態(tài)圖圖，或者說，或者說狀態(tài)圖狀態(tài)圖的的隱式表示隱式表示。例例2.42.4 重排九宮問題（重排九宮問題（4 4）（3 3）隱式圖搜索）隱式圖搜索 初始狀態(tài)初始狀態(tài)S（ 0，1，2，3，5，6，4，7，8 ）滿足條件滿足條件X0 =0，故可以使用第，故可以使用第0 0組的四條規(guī)則：組的四條規(guī)則： 如果選擇規(guī)則如果選擇規(guī)則R1，則狀態(tài)轉(zhuǎn)換為：，則狀態(tài)轉(zhuǎn)換為：S1（ 2，1，0，3，5，6，4，7，8)2021-12-31人工智能36例例2.52.5 旅行商問題旅行商問題(TSP)(1)(TSP)(1) 設(shè)有設(shè)有n個互相可直達(dá)的城市，某推銷商準(zhǔn)備從其中的個互相可直達(dá)的城市，某推銷商準(zhǔn)備

30、從其中的A A城城出發(fā)，周游各城市一遍，最后又回到出發(fā)，周游各城市一遍，最后又回到A A城。要求為該推銷商規(guī)城。要求為該推銷商規(guī)劃一條最短的旅行路線。劃一條最短的旅行路線。（1 1）狀態(tài)描述：該問題的狀態(tài)為以）狀態(tài)描述：該問題的狀態(tài)為以A A打頭城市序列：打頭城市序列： = AA1Ai AjA 其中：其中：A、Ai、Aj、A為城市名，為城市名， 1 i、j n-1，Aj A，Ai A； 1 | | n+1；當(dāng)當(dāng)i j 時，時，Ai Aj； 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)| |=n+1時時，A=A。初始狀態(tài)初始狀態(tài)： = A，| | = 1終止?fàn)顟B(tài)終止?fàn)顟B(tài)： = AA1A2A，| | = n+1例例2.52.

31、5 旅行商問題旅行商問題(TSP)(2)(TSP)(2)（2 2）操作描述（狀態(tài)轉(zhuǎn)換規(guī)則）：）操作描述（狀態(tài)轉(zhuǎn)換規(guī)則）：規(guī)則規(guī)則1 1 ：如果：如果 =AA1Ai Aj，且且| | n，但但A，則置，則置 = A。即沒遍歷完時，在城市序列中添加一個沒即沒遍歷完時，在城市序列中添加一個沒 有到過的城市。有到過的城市。規(guī)則規(guī)則2 2 ：如果：如果| | |= |= n n，置，置 = = A A，即從當(dāng)前城市返回，即從當(dāng)前城市返回A A城。城。 （3 3）隱式圖搜索）隱式圖搜索對于有對于有A、B、C、D四個四個城市所組成的連通城市網(wǎng)，城市所組成的連通城市網(wǎng)，初始狀態(tài)：初始狀態(tài)： =A，| |=1，

32、滿足規(guī)則滿足規(guī)則1 1 ，則操作的結(jié)果為則操作的結(jié)果為： =AB 、或或 =AC、或或 =AD，繼續(xù)使用規(guī)則繼續(xù)使用規(guī)則1 1 ，直到生成包含四個城市的序列出現(xiàn)，再使用，直到生成包含四個城市的序列出現(xiàn)，再使用規(guī)則規(guī)則2 2。2021-12-31人工智能37補(bǔ)充例補(bǔ)充例 二階梵塔問題（二階梵塔問題（1 1） 一號桿有一號桿有A、B兩個金盤，兩個金盤，A小于小于B。要求將。要求將A、B移至三號桿移至三號桿，每次只可移動一個盤子，任何時刻，每次只可移動一個盤子，任何時刻B不能在不能在A上。上。 （1 1）有關(guān)狀態(tài)的知識：）有關(guān)狀態(tài)的知識：用二元組用二元組（SA，SB）表示狀態(tài)，表示狀態(tài)，SA表示表示

33、A所在桿號，所在桿號，SB表表示示B所在桿號。其中所在桿號。其中: : SA ,SB 1,2,3 , , 則則全部狀態(tài)如下：全部狀態(tài)如下： （1，1），（），（1，2），（），（1，3） （2，1），（），（2，2），（），（2，3） （3，1），（），（3，2），（），（3，3）初始狀態(tài)為初始狀態(tài)為（1，1），），終止?fàn)顟B(tài)為終止?fàn)顟B(tài)為：（3，3） 。2021-12-31人工智能38AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2

34、）123S6：（：（3，1）AAAAABABBBBB補(bǔ)充例補(bǔ)充例 二階梵塔問題（二階梵塔問題（2 2）2021-12-31人工智能39（2 2）有關(guān)操作的知識（規(guī)則）：）有關(guān)操作的知識（規(guī)則）： A（i，j）表示金盤表示金盤A從第從第i號桿移到號桿移到j(luò)號桿，號桿，B（i，j）表示金盤表示金盤B從第從第i號桿移到號桿移到j(luò)號桿，其中：號桿，其中：i,j 1,2,3，但，但i j ，全部操作為：，全部操作為： A（1，2），），A（1，3），）， A（2，1） A（2，3），），A（3，1），）， A（3，2） B（1，2），），B（1，3），）， B（2，1） B（2，3），），B（3，1），

35、）， B（3，2）分析每個操作的條件和動作，得到下表：分析每個操作的條件和動作，得到下表：補(bǔ)充例補(bǔ)充例 二階梵塔問題（二階梵塔問題（3 3）2021-12-31人工智能40補(bǔ)充例補(bǔ)充例 二階梵塔問題（二階梵塔問題（4 4）操作符操作符條件動作A A（1 1，2 2）SA=1SA=2A A（1 1，3 3）SA=1SA=3A A（2 2，1 1）SA=2SA=1A A（2 2，3 3）SA=2 SA=3A A（3 3，1 1）SA=3 SA=1A A（3 3，2 2）SA=3 SA=2B（1 1，2 2）SB=1， SA 1,2 或或SA=3SB=2B B（1 1，3 3）SB=1， SA 1,

36、3 或或SA=2SB=3B B（2 2，1 1）SB=2， SA 1,2 或或SA=3SB=1B B（2 2，3 3）SB=2， SA 2,3 或或SA=1SB=3B B（3 3，1 1）SB=3， SA 1,3 或或SA=2SB=1B B（3 3，2 2）SB=3， SA 2,3 或或SA=1SB=22021-12-31人工智能41補(bǔ)充例補(bǔ)充例 二階梵塔問題（二階梵塔問題（5 5）（3 3）狀態(tài)空間圖）狀態(tài)空間圖1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(3,2)A(3,1)B(1,3)A(2,3)2021-12-31

37、人工智能422.3 2.3 狀態(tài)空間圖的盲目搜索狀態(tài)空間圖的盲目搜索n盲目搜索盲目搜索: :搜索時搜索時不參考不參考與具體待求解問題相關(guān)的任何信息，與具體待求解問題相關(guān)的任何信息，只是按預(yù)先設(shè)定的順序逐個考察節(jié)點(diǎn)只是按預(yù)先設(shè)定的順序逐個考察節(jié)點(diǎn)。盲目搜索與問題無關(guān)，。盲目搜索與問題無關(guān)，具有通用性。具有通用性。n算法中使用的數(shù)據(jù)結(jié)構(gòu)算法中使用的數(shù)據(jù)結(jié)構(gòu): :OPEN表：表：專門登記已經(jīng)生成但還沒有考察的節(jié)點(diǎn)，即待考專門登記已經(jīng)生成但還沒有考察的節(jié)點(diǎn)，即待考察節(jié)點(diǎn)。察節(jié)點(diǎn)。CLOSED表：表：用來記錄考察過的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，用來記錄考察過的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，如每個節(jié)點(diǎn)指向父節(jié)點(diǎn)的編

38、號（返回指針）。如每個節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號（返回指針）。C CLOSEDLOSED表中存表中存放的就是一定搜索策略下的搜索樹。放的就是一定搜索策略下的搜索樹。節(jié)點(diǎn)節(jié)點(diǎn)父節(jié)點(diǎn)編號父節(jié)點(diǎn)編號編號編號節(jié)點(diǎn)節(jié)點(diǎn)父節(jié)點(diǎn)編號父節(jié)點(diǎn)編號OPENOPEN表表CLOSEDCLOSED表表2021-12-31人工智能442.3 狀態(tài)空間圖的盲目搜索狀態(tài)空間圖的盲目搜索2.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索2.3.2 深度優(yōu)先搜索深度優(yōu)先搜索2021-12-31人工智能452.3.1 廣度優(yōu)先搜索（廣度優(yōu)先搜索（1 1） 廣度優(yōu)先搜索（廣度優(yōu)先搜索（A A?eded）基本思想：）基本思想： 廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在

39、樹中的出現(xiàn)位廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置置一層一層一層一層向下的搜索過程。通過將向下的搜索過程。通過將OPEN表設(shè)表設(shè)計為一個計為一個隊列隊列來實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在來實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在OPEN表的表的后面后面，保證先生成的節(jié)點(diǎn)先考察保證先生成的節(jié)點(diǎn)先考察。廣度優(yōu)先搜索算法：廣度優(yōu)先搜索算法：步步1 1 把初始結(jié)點(diǎn)把初始結(jié)點(diǎn)S S0 0放入放入OPEN表中；表中；步步2 2 若若OPEN表為空，則搜索失敗，退出；表為空，則搜索失敗，退出；步步3 3 否則，取否則，取OPEN表中第一個結(jié)點(diǎn)表中第一個結(jié)點(diǎn)N N 放在放在CLOSED 表中；并冠以順序編號表中；并冠以順序編號

40、n；步步4 4 若結(jié)點(diǎn)若結(jié)點(diǎn)N為目標(biāo)結(jié)點(diǎn)，則搜索成功。利用為目標(biāo)結(jié)點(diǎn)，則搜索成功。利用 CLOSED表中的返回指針找出表中的返回指針找出S0到到N的路徑即的路徑即 為所求解，退出；為所求解，退出；步步5 5 若若N不可擴(kuò)展，轉(zhuǎn)步不可擴(kuò)展，轉(zhuǎn)步2 2；步步6 6 否則，擴(kuò)展否則，擴(kuò)展N，將其所有子結(jié)點(diǎn)配上指向，將其所有子結(jié)點(diǎn)配上指向N 的返回指針放入的返回指針放入OPEN表表的的尾部尾部，轉(zhuǎn)步，轉(zhuǎn)步2 2。2.3.1 廣度優(yōu)先搜索（廣度優(yōu)先搜索（2 2）2021-12-31人工智能48例例2.6 使用使用廣度優(yōu)先廣度優(yōu)先搜索算法求解重排九宮問題搜索算法求解重排九宮問題1 2 38 57 4 61

41、1 2 38 5 67 481 38 2 57 4 6101 2 38 4 5 7 671 2 38 4 57 6 6 1 38 2 57 4 6111 2 38 4 57 621 2 38 5 7 4 631 38 2 57 4 641 2 37 8 5 4 612 2 31 8 57 4 6131 2 38 47 6 5141 2 3 4 58 7 6151 28 5 37 4 6171 3 58 27 4 6188 1 3 2 57 4 6191 2 37 8 54 6202 31 8 5 7 4 6211 28 4 37 6 5221 2 3 8 57 4 651 2 38 47 6

42、523八數(shù)碼廣度優(yōu)先搜索八數(shù)碼廣度優(yōu)先搜索1 28 5 37 4 69161 2 38 5 67 42021-12-31人工智能492.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先中廣度優(yōu)先中OPEN表表是一個是一個隊列隊列，CLOSED表表是一個是一個順序表順序表， 表中各節(jié)點(diǎn)按順序編號，正被考察的節(jié)點(diǎn)在表中編號最大。表中各節(jié)點(diǎn)按順序編號，正被考察的節(jié)點(diǎn)在表中編號最大。廣度優(yōu)先搜索又稱為廣度優(yōu)先搜索又稱為寬度優(yōu)先寬度優(yōu)先或或橫向搜索橫向搜索。廣度優(yōu)先策略是廣度優(yōu)先策略是完備完備的，即如果問題的解存在，則它一定可的，即如果問題的解存在，則它一定可 以找到解，

43、并且找到的解還是最優(yōu)解。以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。缺點(diǎn)搜索缺點(diǎn)搜索效率低效率低。2021-12-31人工智能502.3.2 深度優(yōu)先搜索深度優(yōu)先搜索(1)(1)深度優(yōu)先搜索的基本思想：深度優(yōu)先搜索的基本思想： 深度優(yōu)先搜索是一種深度優(yōu)先搜索是一種一直向下一直向下的搜索過程，它的搜索過程，它優(yōu)先在自己的子結(jié)點(diǎn)集合中選擇下一個被考察的結(jié)優(yōu)先在自己的子結(jié)點(diǎn)集合中選擇下一個被考察的結(jié)點(diǎn)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子結(jié)點(diǎn)或受，不斷向縱深方向前進(jìn)，直到到達(dá)葉子結(jié)點(diǎn)或受到深度限制時，才返回到上一級結(jié)點(diǎn)沿另一方向繼到

44、深度限制時，才返回到上一級結(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。續(xù)前進(jìn)。n深度優(yōu)先搜索算法：深度優(yōu)先搜索算法：n 與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是OPEN表表被設(shè)計成被設(shè)計成后進(jìn)先出的棧后進(jìn)先出的棧，新生成的子結(jié)點(diǎn)放在，新生成的子結(jié)點(diǎn)放在OPEN表的前面，表的前面，后生成的結(jié)點(diǎn)優(yōu)先被考察后生成的結(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索。深度優(yōu)先搜索算法只需算法只需將寬度優(yōu)先搜索算法將寬度優(yōu)先搜索算法步步6 6修改為修改為：n步步6 6 否則，擴(kuò)展否則，擴(kuò)展N N，將其所有子結(jié)點(diǎn)配上指向，將其所有子結(jié)點(diǎn)配上指向N N 的的指針放入指針放入OPENOPEN表的表的首部首部，轉(zhuǎn)步，轉(zhuǎn)步2

45、2。 例例2.7 使用使用深度優(yōu)先深度優(yōu)先搜索算法求解重排九宮問題搜索算法求解重排九宮問題 1 2 38 57 4 611 2 38 4 5 7 631 2 38 4 57 6 1 2 38 4 57 61 2 38 5 7 4 61 2 38 4 57 61 2 38 47 6 541 28 4 37 6 51 2 3 8 57 4 621 2 38 47 6 552021-12-31人工智能532.3.2 深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索的特點(diǎn)：深度優(yōu)先搜索的特點(diǎn)：nOPENOPEN表為一個表為一個堆棧堆棧。n深度優(yōu)先又稱深度優(yōu)先又稱縱向搜索縱向搜索。n一般一般不能保證找到最優(yōu)解不能保

46、證找到最優(yōu)解。如下圖所示：。如下圖所示：圖圖2-13 2-13 深度優(yōu)先搜索不具有完備性示意圖深度優(yōu)先搜索不具有完備性示意圖2.3.2 深度優(yōu)先搜索深度優(yōu)先搜索1.1.有界深度優(yōu)先搜索有界深度優(yōu)先搜索2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法3.3.可采納的有界深度優(yōu)先搜索算法可采納的有界深度優(yōu)先搜索算法2021-12-31人工智能551.1.有界深度優(yōu)先搜索（有界深度優(yōu)先搜索（A Acdcd ）為克服深度優(yōu)先搜索的不足，可以對其深度進(jìn)行為克服深度優(yōu)先搜索的不足，可以對其深度進(jìn)行限制限制n深度界限深度界限dm的選擇很重要的選擇很重要 dm 若太小，則達(dá)不到解的深度，得不到解；若太大若

47、太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計算機(jī)的存儲空間與時間，又降低了搜索效，既浪費(fèi)了計算機(jī)的存儲空間與時間，又降低了搜索效率。由于解的路徑長度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o率。由于解的路徑長度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出出dm的值是比較困難的。的值是比較困難的。n即使能求出解，它也不一定是最優(yōu)解。即使能求出解，它也不一定是最優(yōu)解。2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(1)(1) 當(dāng)在當(dāng)在dm界限之內(nèi)找不到解時，可以將深度界限界限之內(nèi)找不到解時，可以將深度界限dm不斷擴(kuò)大，每次增加一個深度增量不斷擴(kuò)大，每次增加一個深度增量 d，直到找到解，直到找到解，或者搜索完整棵

48、樹。這樣算法的完備性得到了保證，或者搜索完整棵樹。這樣算法的完備性得到了保證，稱為稱為可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法( (或迭代加深搜索或迭代加深搜索) )。 當(dāng)當(dāng)d =1時，算法開始蛻變?yōu)闀r，算法開始蛻變?yōu)閺V度優(yōu)先搜索廣度優(yōu)先搜索算法。算法。 2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(2)(2)n迭代加深搜索過程：迭代加深搜索過程：步步1 1 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表中，置表中，置S0的深度的深度d (S0)=0， dm為任意初值。為任意初值。步步2 2 若若OPEN表為空，表為空，則考查則考查CLOSED表是否有待擴(kuò)展節(jié)點(diǎn)：表是否有待擴(kuò)展節(jié)點(diǎn)：

49、若無，則問題無解，退出。若無，則問題無解，退出。 若有，則取出若有，則取出CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到表中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表表 中，令中，令 dm=dm+d。 2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(3)(3) 步步3 3 取取OPEN表中第一個節(jié)點(diǎn)表中第一個節(jié)點(diǎn)N放在放在CLOSED表中；并冠以編號表中；并冠以編號 n； 步步4 4 若節(jié)點(diǎn)若節(jié)點(diǎn)N為目標(biāo)節(jié)點(diǎn)，成功退出。為目標(biāo)節(jié)點(diǎn)，成功退出。 步步5 5 若若N的深度的深度d（N）dm（深度限制值），（深度限制值），則標(biāo)則標(biāo)N為待擴(kuò)展節(jié)為待擴(kuò)展節(jié) 點(diǎn)，點(diǎn)，則轉(zhuǎn)步則轉(zhuǎn)步2； 步步6 6 N無子節(jié)點(diǎn)，則轉(zhuǎn)步無子節(jié)點(diǎn)，則轉(zhuǎn)

50、步2； 步步7 7 擴(kuò)展擴(kuò)展N，將其所有子節(jié)點(diǎn)，將其所有子節(jié)點(diǎn)Ni配上指向配上指向N的指針放入的指針放入OPEN首首 部部，置，置 d(Ni) d(N)1，轉(zhuǎn)步，轉(zhuǎn)步2。3.3.可采納的有界深度優(yōu)先搜索算法可采納的有界深度優(yōu)先搜索算法(1)(1)問題：當(dāng)問題：當(dāng)d d 11 時，是否能保證找到最優(yōu)解？時，是否能保證找到最優(yōu)解？2021-12-31人工智能613.3.可采納的有界深度優(yōu)先搜索算法可采納的有界深度優(yōu)先搜索算法(2)(2)步步1 1 把初始結(jié)點(diǎn)把初始結(jié)點(diǎn)S0放入放入OPEN表中，置表中，置d(S0)=0，dm=dm0，G=NULL。步步2 2 若若OPEN表為空，則考察表為空，則考察

51、CLOSED表是否有待擴(kuò)展結(jié)點(diǎn)：表是否有待擴(kuò)展結(jié)點(diǎn)： （1 1）若無待擴(kuò)展結(jié)點(diǎn)，則判斷）若無待擴(kuò)展結(jié)點(diǎn)，則判斷G表是否為空：表是否為空： 若為空，搜索失敗，退出；若為空，搜索失敗，退出； 否則，取出否則，取出G表最后面的結(jié)點(diǎn)表最后面的結(jié)點(diǎn)Sg， Sg即為所求最優(yōu)解，搜索成功即為所求最優(yōu)解，搜索成功，退出；，退出； （2 2）若有待擴(kuò)展結(jié)點(diǎn)，則取出）若有待擴(kuò)展結(jié)點(diǎn)，則取出CLOSED表中待擴(kuò)展結(jié)點(diǎn)放入到表中待擴(kuò)展結(jié)點(diǎn)放入到OPEN表中，令表中，令dm=dm+d，轉(zhuǎn)步，轉(zhuǎn)步2 2；3.3.可采納的有界深度優(yōu)先搜索算法可采納的有界深度優(yōu)先搜索算法(3)(3)步步3 3 取取OPEN表中首部的結(jié)點(diǎn)表中

52、首部的結(jié)點(diǎn)N放在放在CLOSED表中；并冠以順序表中；并冠以順序編號編號n； 步步4 4 若若d（N）dm，則標(biāo)，則標(biāo)N為待擴(kuò)展結(jié)點(diǎn)，轉(zhuǎn)步為待擴(kuò)展結(jié)點(diǎn)，轉(zhuǎn)步2 2；步步5 5 若若N是目標(biāo)結(jié)點(diǎn)是目標(biāo)結(jié)點(diǎn)S Sg g ，則令，則令dm md（ S Sg g ）-1 ，把，把S Sg g放到放到G 表表的尾部，轉(zhuǎn)步的尾部，轉(zhuǎn)步2 2。步步6 6 若若N不可擴(kuò)展，則轉(zhuǎn)步不可擴(kuò)展，則轉(zhuǎn)步2 2； 步步7 7 否則，擴(kuò)展否則，擴(kuò)展N，將其所有子結(jié)點(diǎn)，將其所有子結(jié)點(diǎn)Ni配上指向配上指向N的返回指針放的返回指針放入入OPEN表首部，表首部， 置置d（ Ni ）d（N）1 ，轉(zhuǎn)步，轉(zhuǎn)步2 2。 2021-12

53、-31人工智能622.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(1)(1)1.1.啟發(fā)性知識與啟發(fā)函數(shù)啟發(fā)性知識與啟發(fā)函數(shù)n啟發(fā)性知識啟發(fā)性知識 就是與被求解問題自身特性相關(guān)的知識，包括被就是與被求解問題自身特性相關(guān)的知識，包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗、技巧等，對應(yīng)于問題求解框求解此類問題的經(jīng)驗、技巧等，對應(yīng)于問題求解框架中的架中的控制性知識控制性知識。 n啟發(fā)函數(shù)啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識形式化，要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識形式化，即用一定的函數(shù)表示出來，通過函數(shù)計算來

54、評價每即用一定的函數(shù)表示出來，通過函數(shù)計算來評價每種選擇的價值大小，用以種選擇的價值大小，用以指導(dǎo)搜索過程指導(dǎo)搜索過程，這樣的函，這樣的函數(shù)稱為數(shù)稱為啟發(fā)函數(shù)啟發(fā)函數(shù)。 2021-12-31人工智能632021-12-31人工智能642.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(2)(2)2.2.啟發(fā)函數(shù)的設(shè)計啟發(fā)函數(shù)的設(shè)計 在實(shí)際設(shè)計過程中，在實(shí)際設(shè)計過程中，啟發(fā)函數(shù)啟發(fā)函數(shù)是用來估計搜索樹節(jié)是用來估計搜索樹節(jié)點(diǎn)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為h(x)。啟啟發(fā)函數(shù)可以是：發(fā)函數(shù)可以是：（1 1）一個結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的某種距離或差異

55、的）一個結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的某種距離或差異的量度量度；（2 2）一個結(jié)點(diǎn)處在最佳路徑上的）一個結(jié)點(diǎn)處在最佳路徑上的概率概率；（3 3）根據(jù)主觀經(jīng)驗的主觀）根據(jù)主觀經(jīng)驗的主觀打分打分等。等。2021-12-31人工智能652.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(3)(3)2.4.1 2.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法2.4.2 2.4.2 啟發(fā)式搜索的啟發(fā)式搜索的A A算法和算法和A A* *算法算法2.4.32.4.3 A A* *算法在游戲中的應(yīng)用算法在游戲中的應(yīng)用2021-12-31人工智能662.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法（1 1）啟發(fā)式搜索啟發(fā)式搜索用

56、啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值增加啟發(fā)函數(shù)值的的計算計算與與傳播傳播過過程，并且由程，并且由啟發(fā)函數(shù)值啟發(fā)函數(shù)值來來確定確定節(jié)點(diǎn)的節(jié)點(diǎn)的擴(kuò)展順序擴(kuò)展順序。按選擇范圍不同，啟發(fā)式搜索分為按選擇范圍不同，啟發(fā)式搜索分為：全局擇優(yōu)搜索全局擇優(yōu)搜索局部擇優(yōu)搜索局部擇優(yōu)搜索2021-12-31人工智能672.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法（2 2）1.1.全局擇優(yōu)搜索全局擇優(yōu)搜索基本思想：基本思想： 在在OPEN表中表中保留所有已生成而未考察保留所有已生成而未考察的節(jié)點(diǎn)，的節(jié)點(diǎn)，并用并用啟發(fā)函數(shù)啟

57、發(fā)函數(shù)h(x)對它們對它們?nèi)咳窟M(jìn)行估價，從中選出進(jìn)行估價，從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而不管這個節(jié)點(diǎn)出現(xiàn)在搜索樹最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而不管這個節(jié)點(diǎn)出現(xiàn)在搜索樹的什么地方。的什么地方。2.4.1 啟發(fā)式搜索算法（啟發(fā)式搜索算法（3 3）全局擇優(yōu)搜索算法全局擇優(yōu)搜索算法：步步1 1 把初始結(jié)點(diǎn)把初始結(jié)點(diǎn)S0放入放入OPEN表中，計算表中，計算h(S0)；步步2 2 若若OPEN表為空，則搜索失敗，退出；表為空，則搜索失敗，退出；步步3 3 否則，移出否則，移出OPEN表中第一個結(jié)點(diǎn)表中第一個結(jié)點(diǎn)N放入放入CLOSED表中，表中，并冠以序號并冠以序號n ；步步4 4 若目標(biāo)結(jié)點(diǎn)若目標(biāo)結(jié)點(diǎn)Sg N，則

58、搜索成功，利用，則搜索成功，利用CLOSED表中的表中的返回指針找出返回指針找出S0到到N N 的路徑即為所求解，退出；的路徑即為所求解，退出；步步5 5 若若N N不可擴(kuò)展，則轉(zhuǎn)步不可擴(kuò)展，則轉(zhuǎn)步2 2 ；步步6 6 否則，擴(kuò)展否則，擴(kuò)展N，計算，計算N的每個子結(jié)點(diǎn)的每個子結(jié)點(diǎn)x的函數(shù)值，并將的函數(shù)值，并將N所有子結(jié)點(diǎn)所有子結(jié)點(diǎn)x配以指向配以指向N的返回指針后放入的返回指針后放入OPEN表中，表中，依據(jù)啟發(fā)函數(shù)對結(jié)點(diǎn)的計算，再對依據(jù)啟發(fā)函數(shù)對結(jié)點(diǎn)的計算，再對OPEN表中表中所有結(jié)點(diǎn)所有結(jié)點(diǎn)按按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步2 2。2021-12-31人工

59、智能682.4.1 啟發(fā)式搜索算法（啟發(fā)式搜索算法（4 4）2.2.局部擇優(yōu)搜索局部擇優(yōu)搜索基本思想：局部擇優(yōu)搜索是在啟發(fā)性知識導(dǎo)航下的深度優(yōu)基本思想：局部擇優(yōu)搜索是在啟發(fā)性知識導(dǎo)航下的深度優(yōu)先搜索，在先搜索，在OPEN表中保留所有已生成而未考察的結(jié)點(diǎn)，表中保留所有已生成而未考察的結(jié)點(diǎn)，對其中對其中新生成的每個子結(jié)點(diǎn)新生成的每個子結(jié)點(diǎn)x計算啟發(fā)函數(shù)計算啟發(fā)函數(shù)，從，從全部子結(jié)點(diǎn)全部子結(jié)點(diǎn)中選出中選出最優(yōu)結(jié)點(diǎn)最優(yōu)結(jié)點(diǎn)進(jìn)行擴(kuò)展，其選擇下一個要考察結(jié)點(diǎn)的范進(jìn)行擴(kuò)展，其選擇下一個要考察結(jié)點(diǎn)的范圍是剛剛生成的全部子結(jié)點(diǎn)，圍是剛剛生成的全部子結(jié)點(diǎn)，局部擇優(yōu)搜索算法：局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的

60、區(qū)別僅在與全局擇優(yōu)搜索算法的區(qū)別僅在步步6 6： 步步6 6 否則，擴(kuò)展否則，擴(kuò)展N N，計算，計算N N的每個子結(jié)點(diǎn)的每個子結(jié)點(diǎn)x x的函數(shù)值，并將的函數(shù)值，并將N N的所有子結(jié)點(diǎn)的所有子結(jié)點(diǎn)x x配以指向結(jié)點(diǎn)配以指向結(jié)點(diǎn)N N的指針后，將的指針后，將全部子結(jié)點(diǎn)全部子結(jié)點(diǎn)按按啟發(fā)函數(shù)值升序排列后放入啟發(fā)函數(shù)值升序排列后放入OPEN表的首部，轉(zhuǎn)步表的首部，轉(zhuǎn)步2 2。2021-12-31人工智能692.4.2 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法（算法（1） 啟發(fā)函數(shù)是對當(dāng)前結(jié)點(diǎn)到達(dá)目標(biāo)結(jié)點(diǎn)未來啟發(fā)函數(shù)是對當(dāng)前結(jié)點(diǎn)到達(dá)目標(biāo)結(jié)點(diǎn)未來可能要付出的代價的估計?？赡芤冻龅拇鷥r的估計。 在全