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

1、第第2 2章章 基于圖的知識(shí)表示與圖搜索技術(shù)基于圖的知識(shí)表示與圖搜索技術(shù)2022-6-1人工智能2第第2 2章章基于圖的知識(shí)表示與圖搜索技術(shù)基于圖的知識(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ù)2022-6-1人工智能32.1 2.1 概述概述2.1.1 2.1.1 知識(shí)與問題求解框架知識(shí)與問題求解框架2.1.2 2.1.2 知識(shí)表示知

2、識(shí)表示2.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)2022-6-1人工智能42.1.1 2.1.1 知識(shí)與問題求解框架知識(shí)與問題求解框架(1)(1) 1.知識(shí)的定義知識(shí)的定義心理學(xué)：個(gè)體通過與環(huán)境相互作用后獲得的信息及其組心理學(xué)：個(gè)體通過與環(huán)境相互作用后獲得的信息及其組織?？棥ＹM(fèi)根鮑姆：知識(shí)是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。費(fèi)根鮑姆：知識(shí)是經(jīng)過消減、塑造、解釋和轉(zhuǎn)換的信息。博恩斯坦博恩斯坦Bernstein：知識(shí)是由特定領(lǐng)域的描述、關(guān)：知識(shí)是由特定領(lǐng)域的描述、關(guān)系和過程組成的。系和過程組成的。 概括地說，知識(shí)是高度組織起來的信息集團(tuán)，概括地說，知識(shí)是高度組織起來的信息集團(tuán)，是人們?cè)陂L(zhǎng)期的生活

3、和社會(huì)實(shí)踐中、科學(xué)研究和科是人們?cè)陂L(zhǎng)期的生活和社會(huì)實(shí)踐中、科學(xué)研究和科學(xué)實(shí)驗(yàn)中積累起來的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)學(xué)實(shí)驗(yàn)中積累起來的經(jīng)驗(yàn)或?qū)陀^世界規(guī)律的認(rèn)識(shí)等。等。2.1.1 2.1.1 知識(shí)與問題求解框架知識(shí)與問題求解框架(2)(2)2.知識(shí)的分類知識(shí)的分類1從應(yīng)用領(lǐng)域來劃分從應(yīng)用領(lǐng)域來劃分常識(shí)性知識(shí)常識(shí)性知識(shí)領(lǐng)域?qū)I(yè)性知識(shí)領(lǐng)域?qū)I(yè)性知識(shí)2從在問題求解中的作用來劃分從在問題求解中的作用來劃分表達(dá)性知識(shí)表達(dá)性知識(shí)過程性知識(shí)過程性知識(shí)控制性知識(shí)控制性知識(shí)3從確定性來劃分從確定性來劃分確定性知識(shí)確定性知識(shí)非確定性知識(shí)非確定性知識(shí)4從知識(shí)的表現(xiàn)形式來劃分，可分為文字、符號(hào)、聲從知識(shí)的表現(xiàn)形式來劃分

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

5、解框架問題的求解框架1表達(dá)性知識(shí)：描述問題的狀態(tài)有關(guān)的各種知識(shí)。表達(dá)性知識(shí)：描述問題的狀態(tài)有關(guān)的各種知識(shí)。2過程性知識(shí)：描述狀態(tài)之間的變換關(guān)系的各種知過程性知識(shí)：描述狀態(tài)之間的變換關(guān)系的各種知識(shí)。識(shí)。3控制性知識(shí)：描述如何在當(dāng)前狀態(tài)下選擇適宜操控制性知識(shí)：描述如何在當(dāng)前狀態(tài)下選擇適宜操作的知識(shí)。作的知識(shí)。2022-6-1人工智能62022-6-1人工智能72.1.2 2.1.2 知識(shí)表示知識(shí)表示(1)(1)知識(shí)表示：就是研究在計(jì)算機(jī)中如何用最適宜知識(shí)表示：就是研究在計(jì)算機(jī)中如何用最適宜的形式表示問題求解過程中所需要的各種知識(shí)，的形式表示問題求解過程中所需要的各種知識(shí)，包括構(gòu)成問題求解框架的全部

6、知識(shí)。包括構(gòu)成問題求解框架的全部知識(shí)。常用的知識(shí)表示形式常用的知識(shí)表示形式狀態(tài)空間圖狀態(tài)空間圖與或圖與或圖謂詞邏輯謂詞邏輯產(chǎn)生式產(chǎn)生式框架框架語義網(wǎng)絡(luò)語義網(wǎng)絡(luò)2.1.2 2.1.2 知識(shí)表示知識(shí)表示(2)(2)2022-6-1人工智能8例例2.12.1麥卡賽問題。麥卡賽問題。 在一個(gè)在一個(gè)2n2n2n2n的方格棋盤中，去掉對(duì)角的兩個(gè)的方格棋盤中，去掉對(duì)角的兩個(gè)方格，如圖方格，如圖a a，問能否將它全部劃成假設(shè)干，問能否將它全部劃成假設(shè)干1 12 2的小長(zhǎng)方塊？的小長(zhǎng)方塊？目標(biāo)狀態(tài)目標(biāo)狀態(tài)初始狀態(tài)初始狀態(tài)可達(dá)狀態(tài)可達(dá)狀態(tài)同構(gòu)問題同構(gòu)問題同態(tài)問題同態(tài)問題2022-6-1人工智能92.1.3 2.1

7、.3 圖搜索技術(shù)圖搜索技術(shù)(1)(1)1.搜索搜索 搜索，簡(jiǎn)單地說就是搜索，簡(jiǎn)單地說就是“尋找，目的是找到問題的解。尋找，目的是找到問題的解。在問題求解過程中，待求解的問題被抽象成一定空間上在問題求解過程中，待求解的問題被抽象成一定空間上的圖，搜索過程就是從圖中初始節(jié)點(diǎn)出發(fā)，沿著與之相的圖，搜索過程就是從圖中初始節(jié)點(diǎn)出發(fā)，沿著與之相連的邊試探著前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)或可解節(jié)點(diǎn)的過程。連的邊試探著前進(jìn)，尋找目標(biāo)節(jié)點(diǎn)或可解節(jié)點(diǎn)的過程。2.搜索樹搜索樹 搜索過程中經(jīng)過考察過的節(jié)點(diǎn)和邊，按原圖的搜索過程中經(jīng)過考察過的節(jié)點(diǎn)和邊，按原圖的連接關(guān)系，便會(huì)構(gòu)成一個(gè)樹型的有向圖，稱為搜索樹。連接關(guān)系，便會(huì)構(gòu)成一個(gè)樹

8、型的有向圖，稱為搜索樹。搜索樹是一個(gè)搜索過程的搜索軌跡，或稱之為搜索空間。搜索樹是一個(gè)搜索過程的搜索軌跡，或稱之為搜索空間。2.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)(2)(2)2022-6-1人工智能10圖 2-2搜索空間示意圖問題的狀態(tài)空間、搜索空間及解的示意圖：2.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)(3)(3)3.搜索策略搜索策略 搜索策略將決定搜索過程按照什么樣的順序考察節(jié)搜索策略將決定搜索過程按照什么樣的順序考察節(jié)點(diǎn)和經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。點(diǎn)和經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。盲目搜索：無向?qū)У乃阉鳎卜Q窮舉搜索。盲目搜索：無向?qū)У乃阉鳎卜Q窮舉搜索。啟發(fā)式搜索：利用啟發(fā)式搜索：

9、利用“啟發(fā)性信息作為導(dǎo)航的搜索過程。啟發(fā)性信息作為導(dǎo)航的搜索過程。 對(duì)于較大或無限狀態(tài)空間問題，盲目搜索效率太低，對(duì)于較大或無限狀態(tài)空間問題，盲目搜索效率太低，所以在實(shí)際當(dāng)中往往是不可行的。啟發(fā)式搜索廣泛地應(yīng)所以在實(shí)際當(dāng)中往往是不可行的。啟發(fā)式搜索廣泛地應(yīng)用于實(shí)際問題求解中，如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、用于實(shí)際問題求解中，如博弈、機(jī)器學(xué)習(xí)、數(shù)據(jù)挖掘、智能檢索等。智能檢索等。2022-6-1人工智能112022-6-1人工智能122.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)空間圖2022-6-1人工智能13

10、2.2.1 2.2.1 狀態(tài)空間圖狀態(tài)空間圖1 11.狀態(tài)狀態(tài) 狀態(tài)對(duì)應(yīng)表達(dá)性知識(shí)，描述一個(gè)問題在開始、狀態(tài)對(duì)應(yīng)表達(dá)性知識(shí)，描述一個(gè)問題在開始、結(jié)束或中間的某一時(shí)刻所處的狀況或狀態(tài)。通常引結(jié)束或中間的某一時(shí)刻所處的狀況或狀態(tài)。通常引進(jìn)一組變量進(jìn)一組變量 ，表示與問題狀態(tài)相關(guān)的各種，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組要素，并用這組變量所構(gòu)成的多元組 來來表示狀態(tài)。表示狀態(tài)。 狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)。12nqqq， ， ，12()nqqq， ，2022-6-1人工智能142.2.1 2.2.1 狀態(tài)空間圖狀態(tài)空間圖2 22.2.操作操作 操作對(duì)應(yīng)過

11、程性知識(shí)，即狀態(tài)轉(zhuǎn)換規(guī)那么，描述操作對(duì)應(yīng)過程性知識(shí)，即狀態(tài)轉(zhuǎn)換規(guī)那么，描述狀態(tài)之間的關(guān)系。狀態(tài)之間的關(guān)系。描述一個(gè)操作要包含兩個(gè)局部描述一個(gè)操作要包含兩個(gè)局部條件條件: :指明被作用的狀態(tài)要滿足的約束條件指明被作用的狀態(tài)要滿足的約束條件動(dòng)作動(dòng)作: :指明一個(gè)操作對(duì)狀態(tài)的分量所做的改變。指明一個(gè)操作對(duì)狀態(tài)的分量所做的改變。操作的表示形式可以是一個(gè)機(jī)械性的步驟、過程、規(guī)那操作的表示形式可以是一個(gè)機(jī)械性的步驟、過程、規(guī)那么或算子。么或算子。操作在狀態(tài)圖中表示為邊。在程序中，狀態(tài)轉(zhuǎn)換規(guī)那么操作在狀態(tài)圖中表示為邊。在程序中，狀態(tài)轉(zhuǎn)換規(guī)那么可用數(shù)據(jù)對(duì)、條件語句、規(guī)那么、函數(shù)、過程等表示?？捎脭?shù)據(jù)對(duì)、條件語

12、句、規(guī)那么、函數(shù)、過程等表示。 如：如果室內(nèi)溫度低于如：如果室內(nèi)溫度低于2626度，那么關(guān)閉空調(diào)。度，那么關(guān)閉空調(diào)。 2022-6-1人工智能152.2.1 2.2.1 狀態(tài)空間圖狀態(tài)空間圖3 33.狀態(tài)空間圖狀態(tài)空間圖n問題的狀態(tài)空間圖是一個(gè)描述該問題全部可能的狀態(tài)及相互關(guān)系的圖，如考慮操作的代價(jià)，狀態(tài)空間圖就是一個(gè)賦值有向圖。n狀態(tài)空間常記為三元組： S：初始狀態(tài)的集合 F：操作的集合 G：目標(biāo)狀態(tài)的集合。 n由問題的狀態(tài)空間表示就可以構(gòu)造出狀態(tài)空間圖。SFG， ，2.2.1 2.2.1 狀態(tài)空間圖狀態(tài)空間圖4 44.求解求解n在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中在狀態(tài)空間表示法中

13、，問題求解過程轉(zhuǎn)化為在圖中尋找尋找從初始狀態(tài)從初始狀態(tài)Q Qs s出發(fā)出發(fā)到達(dá)到達(dá)目標(biāo)狀態(tài)目標(biāo)狀態(tài)Q Qg g的的路徑路徑問題問題，也就是尋找操作序列的問題。，也就是尋找操作序列的問題。n狀態(tài)空間的解為三元組狀態(tài)空間的解為三元組 Q nQ Qs s ：某個(gè)初始狀態(tài)：某個(gè)初始狀態(tài)nQ Qg g ：某個(gè)目標(biāo)狀態(tài)：某個(gè)目標(biāo)狀態(tài)na a：把：把Q Qs s變換成變換成Q Qg g的有限的操作序列的有限的操作序列n狀態(tài)轉(zhuǎn)換圖狀態(tài)轉(zhuǎn)換圖S1S3S2f1f2f3f4QsQgfn2022-6-1人工智能162022-6-1人工智能17例例2.2 翻轉(zhuǎn)錢幣問題翻轉(zhuǎn)錢幣問題1 三枚錢幣處于反、正、反狀態(tài)，每次只許

14、翻動(dòng)一枚錢幣，問連續(xù)翻動(dòng)三次后，能否出現(xiàn)全正或全反狀態(tài)。 初始狀態(tài)Qs目標(biāo)狀態(tài)集合Q0, Q7例例2.2 翻轉(zhuǎn)錢幣問題翻轉(zhuǎn)錢幣問題2引入一個(gè)三元組引入一個(gè)三元組(q(q0 0,q,q1 1,q,q2 2) )來描述總狀態(tài)，錢幣正面為來描述總狀態(tài)，錢幣正面為0 0，反面，反面為為1 1，全部可能的狀態(tài)為：，全部可能的狀態(tài)為： Q Q0 0=(0,0,0)=(0,0,0) ; Q ; Q1 1=(0,0,1); Q=(0,0,1); Q2 2=(0,1,0)=(0,1,0) Q Q3 3=(0,1,1) ; Q=(0,1,1) ; Q4 4=(1,0,0); =(1,0,0); Q Q5 5=(1

15、,0,1)=(1,0,1) Q Q6 6=(1,1,0) ; =(1,1,0) ; Q Q7 7=(1,1,1)=(1,1,1)。翻動(dòng)錢幣的操作抽象為改變上述狀態(tài)的算子，翻動(dòng)錢幣的操作抽象為改變上述狀態(tài)的算子， 即即F Fa, b, ca, b, c a: a:把錢幣把錢幣q q0 0翻轉(zhuǎn)一次翻轉(zhuǎn)一次 b:b:把錢幣把錢幣q q1 1翻轉(zhuǎn)一次翻轉(zhuǎn)一次 c:c:把錢幣把錢幣q q2 2翻轉(zhuǎn)一次翻轉(zhuǎn)一次 問題的狀態(tài)空間為問題的狀態(tài)空間為 2022-6-1人工智能18例例2.2 翻轉(zhuǎn)錢幣問題翻轉(zhuǎn)錢幣問題43.狀態(tài)空間圖狀態(tài)空間圖 問題的狀態(tài)空間為： 2022-6-1人工智能19 構(gòu)造狀態(tài)空間圖： 5

16、07QabcQQ， ， ， ，aabababaabbbbcccbcccb2022-6-1人工智能20例例2.3修道士和野人問題修道士和野人問題1 在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過河去，但受到以下道士們想用這條船將所有的人都運(yùn)過河去，但受到以下條件的限制：條件的限制： 1修道士和野人都會(huì)劃船，但船一次最多只能運(yùn)兩修道士和野人都會(huì)劃船，但船一次最多只能運(yùn)兩個(gè)人；個(gè)人； 2在任何岸邊野人數(shù)目都不得超過修道士，否那么在任何岸邊野人數(shù)目都不得超過修道士，否那么修道士就會(huì)被野人吃掉。修道士就會(huì)被野人吃掉。 假定野人會(huì)服

17、從任何一種過河安排，試規(guī)劃出一種確假定野人會(huì)服從任何一種過河安排，試規(guī)劃出一種確保修道士平安過河方案。保修道士平安過河方案。2022-6-1人工智能21例例2.3修道士和野人問題修道士和野人問題21 1、問題的狀態(tài)、問題的狀態(tài)可以用一個(gè)三元數(shù)組來描述：可以用一個(gè)三元數(shù)組來描述： S S(m, c, b)(m, c, b) m m：左岸的修道士數(shù)：左岸的修道士數(shù) c c：左岸的野人數(shù)：左岸的野人數(shù) b b：左岸的船數(shù)：左岸的船數(shù) 右岸的狀態(tài)不必標(biāo)出，因?yàn)椋河野兜臓顟B(tài)不必標(biāo)出，因?yàn)椋?右岸的修道士數(shù)右岸的修道士數(shù) m m 3 3m m 右岸的野人數(shù)右岸的野人數(shù) c c 3 3c c 右岸的船數(shù)右岸

18、的船數(shù) b b 1 1b b2022-6-1人工智能22例例2.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 1S163 3 0S241 3 0S13 2 1S91 2 1S173 2 0S251 2 0S23 1 1S101 1 1S183 1 0S261 1 0S33 0 1S111 0 1S193 0 0S271 0 0S42 3 1S120 3 1S202 3 0S28 0 3 0S52 2 1S130 2 1S212 2 0S290 2 0S62 1 1S140 1 1S222 1 0S300 1

19、 0S72 0 1S150 0 1S232 0 0S310 0 02022-6-1人工智能23例例2.3修道士和野人問題修道士和野人問題42.2.操作集操作集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)或(

20、m=2,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操作符條 件動(dòng) 作例例2.3修道士和野人問題修道士和野人問題53.狀態(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。2022-6-1人工智能25例例2.3修道士和野人問題修道士和野人問題6S0

21、(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)q01p01S30(0,1,0) p02q02S12(0,3,1)p01q01S29(0,2,0)p20q20S5(2,2,1)q11p114.4.狀態(tài)空間圖：狀態(tài)空間圖：四條S0到S31長(zhǎng)度相等的最短路徑，對(duì)應(yīng)的操作序列就是

22、該問題的四個(gè)最優(yōu)解2022-6-1人工智能262.2.2 2.2.2 隱式狀態(tài)空間圖隱式狀態(tài)空間圖顯式狀態(tài)空間圖：表示了問題所有可能的狀態(tài)及顯式狀態(tài)空間圖：表示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，這種表示方式稱為顯式狀態(tài)空間狀態(tài)之間的關(guān)系，這種表示方式稱為顯式狀態(tài)空間圖，或稱為狀態(tài)空間圖的顯示表示。圖，或稱為狀態(tài)空間圖的顯示表示。隱式狀態(tài)空間圖：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換隱式狀態(tài)空間圖：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換操作的知識(shí)定義的狀態(tài)空間圖。在計(jì)算機(jī)中僅操作的知識(shí)定義的狀態(tài)空間圖。在計(jì)算機(jī)中僅存儲(chǔ)描述問題狀態(tài)及操作的有關(guān)知識(shí)，包括該問題存儲(chǔ)描述問題狀態(tài)及操作的有關(guān)知識(shí)，包括該問題的各狀態(tài)分量的

23、取值情況、分量之間的約束條件、的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動(dòng)作開始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動(dòng)作等。隱式狀態(tài)空間圖也稱為是狀態(tài)空間圖的隱式表等。隱式狀態(tài)空間圖也稱為是狀態(tài)空間圖的隱式表示或隱式圖。示或隱式圖。重排九宮問題的隱式圖描述為： 1有關(guān)狀態(tài)的知識(shí)：狀態(tài)S的定義：S(X0，X1，X2，X3，X4 ，X5， X6 ，X7 ，X8) 其中， Xi0，1，2，3，4，5，6，7，8， ，且 。初始狀態(tài)： S0 0，1，2，3，5，6，4，7，8 目標(biāo)狀態(tài)： Sg 0，1，2，3，4，5，6，7，8 重排九宮問題的狀態(tài)表示80 i

24、ijijXX時(shí)，例例2.42.4重排九宮問題八數(shù)碼問題重排九宮問題八數(shù)碼問題 例例2.42.4重排九宮問題重排九宮問題2 22 2有關(guān)操作的知識(shí)規(guī)那么：有關(guān)操作的知識(shí)規(guī)那么：0 0組規(guī)那么組規(guī)那么 R1(X0=0 ) R1(X0=0 ) (X2=n ) (X2=n ) X0 = n X0 = n X2 X2 =0=0； R2(X0=0 ) R2(X0=0 ) (X4=n ) (X4=n ) X0 = n X0 = n X4 X4 =0=0； R3(X0=0 ) R3(X0=0 ) (X6=n ) (X6=n ) X0 = n X0 = n X6 X6 =0=0； R4(X0=0 ) R4(X0

25、=0 ) (X8=n ) (X8=n ) X0 = n X0 = n X8 X8 =0=0；1 1組規(guī)那么組規(guī)那么 R5(X1=0 ) R5(X1=0 ) (X2=n ) (X2=n ) X1 = n X1 = n X2 X2 =0=0； R6(X1=0 ) R6(X1=0 ) (X8=n ) (X8=n ) X1 = n X1 = n X8 X8 =0=0；8 8組規(guī)那么組規(guī)那么: : R22(X8=0 ) R22(X8=0 ) (X1=n ) (X1=n ) X8 = n X8 = n X1 X1 =0=0； R23(X8=0 ) R23(X8=0 ) (X0=n ) (X0=n ) X8

26、 = n X8 = n X0=0X0=0； R24(X8=0 ) R24(X8=0 ) (X7=n ) (X7=n ) X8 = n X8 = n X7 X7 =0=0；例例2.42.4重排九宮問題重排九宮問題3 3八數(shù)碼的狀態(tài)圖可表示為八數(shù)碼的狀態(tài)圖可表示為 S0, r1 , r2 , , r24 , SgS0, 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ī)那和目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)那么來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為么來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表

27、示。隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表示。例例2.42.4重排九宮問題重排九宮問題4 43 3隱式圖搜索隱式圖搜索 初始狀態(tài)初始狀態(tài)S S 0 0，1 1，2 2，3 3，5 5，6 6，4 4，7 7，8 8 滿滿足條件足條件X0 =0X0 =0，故可以使用第，故可以使用第0 0組的四條規(guī)那么：組的四條規(guī)那么： 如果選擇規(guī)那么如果選擇規(guī)那么R1R1，那么狀態(tài)轉(zhuǎn)換為：，那么狀態(tài)轉(zhuǎn)換為：S1S1 2 2，1 1，0 0，3 3，5 5，6 6，4 4，7 7，8)8)R2R4R1R3 1 2 3 8 5 7 4 6 1 3 8 2 5 7 4 6 1 2 3 8 5 7 4 6 1 2 3 8 4

28、 5 7 6 1 2 3 8 8 5 7 4 62022-6-1人工智能31例例2.5 2.5 旅行商問題旅行商問題(TSP)(1)(TSP)(1) 設(shè)有n個(gè)互相可直達(dá)的城市，某推銷商準(zhǔn)備從其中的A城出發(fā)，周游各城市一遍，最后又回到A城。要求為該推銷商規(guī)劃一條最短的旅行路線。1狀態(tài)描述：該問題的狀態(tài)為以A打頭城市序列： =AA1Ai AjA其中：A、Ai、Aj、A為城市名， 1i、jn-1，AjA，AiA； 1|n+1；當(dāng)i j 時(shí)，Ai Aj； 當(dāng)且僅當(dāng)|=n+1時(shí)，A=A。初始狀態(tài)：=A，|=1終止?fàn)顟B(tài)：=AA1A2A，|=n+1例例2.5 2.5 旅行商問題旅行商問題(TSP)(2)(T

29、SP)(2)2操作描述狀態(tài)轉(zhuǎn)換規(guī)那么：操作描述狀態(tài)轉(zhuǎn)換規(guī)那么：規(guī)那么規(guī)那么1 ：如果：如果=AA1Ai Aj，且，且| n，但，但A，那么置，那么置= A。即沒遍歷完時(shí)，在城市序列中。即沒遍歷完時(shí)，在城市序列中添加一個(gè)沒有到過的城市。添加一個(gè)沒有到過的城市。規(guī)那么規(guī)那么2 ：如果：如果|= n，置，置= A，即從當(dāng)前城市返，即從當(dāng)前城市返回回A城。城。 3隱式圖搜索隱式圖搜索對(duì)于有對(duì)于有A、B、C、D四個(gè)城市所組成的連通城市網(wǎng)，四個(gè)城市所組成的連通城市網(wǎng)，初始狀態(tài)：初始狀態(tài)：=A，|=1，滿足規(guī)那么，滿足規(guī)那么1 ，那么操作的結(jié)果為：那么操作的結(jié)果為：=AB 、或、或=AC、或、或=AD，繼續(xù)

30、使用規(guī)那么繼續(xù)使用規(guī)那么1 ，直到生成包含四個(gè)城市的序列出現(xiàn)，直到生成包含四個(gè)城市的序列出現(xiàn)，再使用規(guī)那么再使用規(guī)那么2。2022-6-1人工智能32補(bǔ)充例補(bǔ)充例 二階梵塔問題二階梵塔問題1 1 有三個(gè)桿，一號(hào)桿有有三個(gè)桿，一號(hào)桿有A A、B B兩個(gè)金盤，兩個(gè)金盤，A A小于小于B B。要求將。要求將A A、B B移至三號(hào)桿，每次只可移動(dòng)一個(gè)盤子，任何時(shí)刻移至三號(hào)桿，每次只可移動(dòng)一個(gè)盤子，任何時(shí)刻B B不不能在能在A A上。上。 1 1有關(guān)狀態(tài)的知識(shí)：有關(guān)狀態(tài)的知識(shí)：用二元組用二元組SASA，SBSB表示狀態(tài)，表示狀態(tài)，SASA表示表示A A所在桿號(hào)，所在桿號(hào)，SBSB表表示示B B所在桿號(hào)。

31、其中所在桿號(hào)。其中: SA ,SB: SA ,SB1,2,3 , 1,2,3 , 那么全部狀態(tài)那么全部狀態(tài)如下：如下： 1 1，1 1，1 1，2 2，1 1，3 3 2 2，1 1，2 2，2 2，2 2，3 3 3 3，1 1，3 3，2 2，3 3，3 3初始狀態(tài)為初始狀態(tài)為1 1，1 1，終止?fàn)顟B(tài)為：，終止?fàn)顟B(tài)為：3 3，3 3 。2022-6-1人工智能33AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2）123S6：（

32、：（3，1）AAAAABABBBBB補(bǔ)充例補(bǔ)充例 二階梵塔問題二階梵塔問題2 22022-6-1人工智能342 2有關(guān)操作的知識(shí)規(guī)那么：有關(guān)操作的知識(shí)規(guī)那么： A Ai i，j j表示金盤表示金盤A A從第從第i i號(hào)桿移到號(hào)桿移到j(luò) j號(hào)桿，號(hào)桿，B Bi i，j j表示金盤表示金盤B B從第從第i i號(hào)桿移到號(hào)桿移到j(luò) j號(hào)桿，其中號(hào)桿，其中：i,j i,j 1,2,31,2,3，但，但i i j j ，全部操作為：，全部操作為： A A1 1，2 2，A A1 1，3 3， A A2 2，1 1 A A2 2，3 3，A A3 3，1 1， A A3 3，2 2 B B1 1，2 2，B

33、 B1 1，3 3， B B2 2，1 1 B B2 2，3 3，B B3 3，1 1， B B3 3，2 2分析每個(gè)操作的條件和動(dòng)作，得到下表：分析每個(gè)操作的條件和動(dòng)作，得到下表：補(bǔ)充例補(bǔ)充例 二階梵塔問題二階梵塔問題3 32022-6-1人工智能35補(bǔ)充例補(bǔ)充例 二階梵塔問題二階梵塔問題4 4操作符操作符條件動(dòng)作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

34、 1,2 或或SA=3SB=2B B（1 1，3 3）SB=1， SA 1,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=22022-6-1人工智能36補(bǔ)充例補(bǔ)充例 二階梵塔問題二階梵塔問題5 53 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,

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

36、節(jié)點(diǎn)之間的關(guān)系，如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)返回指針。系，如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)返回指針。CLOSED表中存放的就是一定搜索策略下的搜索樹。表中存放的就是一定搜索策略下的搜索樹。2022-6-1人工智能38節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)編號(hào)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)OPEN表表CLOSED表表2022-6-1人工智能392.3 狀態(tài)空間圖的盲目搜索狀態(tài)空間圖的盲目搜索2.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索2.3.2 深度優(yōu)先搜索深度優(yōu)先搜索2022-6-1人工智能402.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索1廣度優(yōu)先搜索廣度優(yōu)先搜索A A?eded根本思想：根本思想： 廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置一層一層向廣度優(yōu)

37、先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置一層一層向下的搜索過程。通過將下的搜索過程。通過將OPENOPEN表設(shè)計(jì)為一個(gè)隊(duì)列來實(shí)現(xiàn)，將新生表設(shè)計(jì)為一個(gè)隊(duì)列來實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在成的子節(jié)點(diǎn)放在OPENOPEN表的后面，保證先生成的節(jié)點(diǎn)先考察。表的后面，保證先生成的節(jié)點(diǎn)先考察。廣度優(yōu)先搜索算法：廣度優(yōu)先搜索算法：步步1 1 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0S0放入放入OPENOPEN表中；表中；步步2 2 假設(shè)假設(shè)OPENOPEN表為空，那么搜索失敗，退出；表為空，那么搜索失敗，退出；步步3 3 否那么，取否那么，取OPENOPEN表中第一個(gè)節(jié)點(diǎn)表中第一個(gè)節(jié)點(diǎn)N N放在放在CLOSEDCLOSED表中；并冠

38、表中；并冠以順序編號(hào)以順序編號(hào)n n；步步4 4 假設(shè)節(jié)點(diǎn)假設(shè)節(jié)點(diǎn)N N為目標(biāo)節(jié)點(diǎn)，那么搜索成功。利用為目標(biāo)節(jié)點(diǎn)，那么搜索成功。利用CLOSEDCLOSED表中表中的返回指針找出的返回指針找出S0S0到到N N的路徑即為所求解，退出；的路徑即為所求解，退出；步步5 5 假設(shè)假設(shè)N N不可擴(kuò)展，轉(zhuǎn)步不可擴(kuò)展，轉(zhuǎn)步2 2；步步6 6 否那么，擴(kuò)展否那么，擴(kuò)展N N，將其所有子節(jié)點(diǎn)配上指向，將其所有子節(jié)點(diǎn)配上指向N N的返回指針放的返回指針放入入OPENOPEN表的尾部，轉(zhuǎn)步表的尾部，轉(zhuǎn)步2 2。2.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索22022-6-1人工智能42例例2.6使用廣度優(yōu)先搜索算法求解重排

39、九宮問題使用廣度優(yōu)先搜索算法求解重排九宮問題1 2 38 57 4 611 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 2 38 4 57 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

40、 37 6 5221 2 3 8 57 4 651 2 38 47 6 523八數(shù)碼廣度優(yōu)先搜索八數(shù)碼廣度優(yōu)先搜索1 28 5 37 4 69161 2 38 5 67 42022-6-1人工智能432.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先中廣度優(yōu)先中OPENOPEN表是一個(gè)隊(duì)列，表是一個(gè)隊(duì)列，CLOSEDCLOSED表是一個(gè)順序表，表是一個(gè)順序表，表中各節(jié)點(diǎn)按順序編號(hào)，正被考察的節(jié)點(diǎn)在表中編號(hào)最表中各節(jié)點(diǎn)按順序編號(hào)，正被考察的節(jié)點(diǎn)在表中編號(hào)最大。大。廣度優(yōu)先搜索又稱為寬度優(yōu)先或橫向搜索。廣度優(yōu)先搜索又稱為寬度優(yōu)先或橫向搜索。廣度優(yōu)先策略是完備的，即

41、如果問題的解存在，那么它廣度優(yōu)先策略是完備的，即如果問題的解存在，那么它一定可以找到解，并且找到的解還是最優(yōu)解。一定可以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。缺點(diǎn)搜索效率低。缺點(diǎn)搜索效率低。2022-6-1人工智能442.3.2 深度優(yōu)先搜索深度優(yōu)先搜索(1)深度優(yōu)先搜索的根本思想：深度優(yōu)先搜索的根本思想： 深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子節(jié)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn)，不先在自己的子節(jié)點(diǎn)集合中選擇下一個(gè)被考察的節(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或

42、受到深度限制斷向縱深方向前進(jìn)，直到到達(dá)葉子節(jié)點(diǎn)或受到深度限制時(shí)，才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。時(shí)，才返回到上一級(jí)節(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。深度優(yōu)先搜索算法：深度優(yōu)先搜索算法： 與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是OPENOPEN表被表被設(shè)計(jì)成后進(jìn)先出的棧，新生成的子節(jié)點(diǎn)放在設(shè)計(jì)成后進(jìn)先出的棧，新生成的子節(jié)點(diǎn)放在OPENOPEN表的前表的前面，后生成的節(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索算法只需面，后生成的節(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索算法只需將寬度優(yōu)先搜索算法步將寬度優(yōu)先搜索算法步6 6修改為：修改為：步步6 6 否那么，擴(kuò)展否那么，擴(kuò)展N N，將其所有子節(jié)點(diǎn)配上指

43、向，將其所有子節(jié)點(diǎn)配上指向N N的的指針放入指針放入OPENOPEN表的首部，轉(zhuǎn)步表的首部，轉(zhuǎn)步2 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 552022-6-1人工智能462.3.2 深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索的特點(diǎn)：深度優(yōu)先搜索的特點(diǎn)：OPENOPEN表為一個(gè)堆棧

44、。表為一個(gè)堆棧。深度優(yōu)先又稱縱向搜索。深度優(yōu)先又稱縱向搜索。一般不能保證找到最優(yōu)解。如以下圖所示：一般不能保證找到最優(yōu)解。如以下圖所示：圖2-13 深度優(yōu)先搜索不具有完備性示意圖2022-6-1人工智能471.1.有界深度優(yōu)先搜索有界深度優(yōu)先搜索Acd Acd 為克服深度優(yōu)先搜索的缺乏，可以對(duì)其深度進(jìn)行為克服深度優(yōu)先搜索的缺乏，可以對(duì)其深度進(jìn)行限制限制深度界限的選擇很重要深度界限的選擇很重要 dm 假設(shè)太小，那么達(dá)不到解的深度，得不假設(shè)太小，那么達(dá)不到解的深度，得不到解；假設(shè)太大，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與到解；假設(shè)太大，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間，又降低了搜索效率。由于解的路徑長(zhǎng)度事時(shí)間

45、，又降低了搜索效率。由于解的路徑長(zhǎng)度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出先難以預(yù)料，所以要恰當(dāng)?shù)亟o出dm的值是比較的值是比較困難的。困難的。即使能求出解，它也不一定是最優(yōu)解。即使能求出解，它也不一定是最優(yōu)解。2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(1)(1) 當(dāng)在dm界限之內(nèi)找不到解時(shí)，可以將深度界限dm不斷擴(kuò)大，每次增加一個(gè)深度增量d，直到找到解，或者搜索完整棵樹。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索算法(或迭代加深搜索)。 當(dāng)d =1時(shí)，算法開始蛻變?yōu)閺V度優(yōu)先搜索算法。 2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(2)(2)n迭代加深搜索過程：迭代加深搜索過

46、程：n步步1 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0放入放入OPEN表中，置表中，置S0的深度的深度d S0 0，dm為任意初值。為任意初值。n步步2 假設(shè)假設(shè)OPEN表為空，那么考查表為空，那么考查CLOSED表是否有表是否有待擴(kuò)展節(jié)點(diǎn)：待擴(kuò)展節(jié)點(diǎn)：n 假設(shè)無，那么問題無解，退出。假設(shè)無，那么問題無解，退出。n 假設(shè)有，那么取出假設(shè)有，那么取出CLOSED表中待擴(kuò)展節(jié)表中待擴(kuò)展節(jié)點(diǎn)放入到點(diǎn)放入到OPEN表中，令表中，令 dm=dm+d。n n 2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(3)(3) 步步3 取取OPEN表中第一個(gè)節(jié)點(diǎn)表中第一個(gè)節(jié)點(diǎn)N放在放在CLOSED表中；并冠以編號(hào)表中；并冠以

47、編號(hào)n； 步步4 假設(shè)節(jié)點(diǎn)假設(shè)節(jié)點(diǎn)N為目標(biāo)節(jié)點(diǎn)，成功退出。為目標(biāo)節(jié)點(diǎn)，成功退出。 步步5 假設(shè)假設(shè)N的深度的深度dNdm深度限制值，那么標(biāo)深度限制值，那么標(biāo)N為待擴(kuò)展為待擴(kuò)展節(jié)點(diǎn)，那么轉(zhuǎn)步節(jié)點(diǎn)，那么轉(zhuǎn)步2； 步步6 N無子節(jié)點(diǎn)，那么轉(zhuǎn)步無子節(jié)點(diǎn)，那么轉(zhuǎn)步2； 步步7 擴(kuò)展擴(kuò)展N，將其所有子節(jié)點(diǎn)，將其所有子節(jié)點(diǎn)Ni配上指向配上指向N的指針放入的指針放入OPEN首部首部， 置置 d Ni dN1，轉(zhuǎn)步，轉(zhuǎn)步2。3.3.可采納的有界深度優(yōu)先搜索算法可采納的有界深度優(yōu)先搜索算法(1)(1)問題：?jiǎn)栴}：當(dāng)d d 1 時(shí)， 是否能保證找到最優(yōu)解？2022-6-1人工智能533.3.可采納的有界深度優(yōu)先搜索

48、算法可采納的有界深度優(yōu)先搜索算法(2)(2)步步1 1 把初始節(jié)點(diǎn)把初始節(jié)點(diǎn)S0S0放入放入OPENOPEN表中，置表中，置d(S0)=0d(S0)=0，dm=dm0dm=dm0，G=NULLG=NULL。步步2 2 假設(shè)假設(shè)OPENOPEN表為空，那么考察表為空，那么考察CLOSEDCLOSED表是否有待擴(kuò)展節(jié)點(diǎn)：表是否有待擴(kuò)展節(jié)點(diǎn)： 1 1假設(shè)無待擴(kuò)展節(jié)點(diǎn)，那么判斷假設(shè)無待擴(kuò)展節(jié)點(diǎn)，那么判斷G G表是否為空：表是否為空： 假設(shè)為空，搜索失敗，退出；假設(shè)為空，搜索失敗，退出； 否那么，取出否那么，取出G G表最后面的節(jié)點(diǎn)表最后面的節(jié)點(diǎn)SgSg， Sg Sg即為所求最優(yōu)解，即為所求最優(yōu)解，搜索

49、成功，退出；搜索成功，退出； 2 2假設(shè)有待擴(kuò)展節(jié)點(diǎn)，那么取出假設(shè)有待擴(kuò)展節(jié)點(diǎn)，那么取出CLOSEDCLOSED表中待擴(kuò)展節(jié)點(diǎn)放入表中待擴(kuò)展節(jié)點(diǎn)放入到到OPENOPEN表中，令表中，令dm=dm+dm=dm+d d，轉(zhuǎn)步，轉(zhuǎn)步2 2；3.3.可采納的有界深度優(yōu)先搜索算法可采納的有界深度優(yōu)先搜索算法(3)(3)步步3 3 取取OPENOPEN表中首部的節(jié)點(diǎn)表中首部的節(jié)點(diǎn)N N放在放在CLOSEDCLOSED表中；并冠以順序編號(hào)表中；并冠以順序編號(hào)n n； 步步4 4 假設(shè)假設(shè)d dN Ndmdm，那么標(biāo)，那么標(biāo)N N為待擴(kuò)展節(jié)點(diǎn)，轉(zhuǎn)步為待擴(kuò)展節(jié)點(diǎn)，轉(zhuǎn)步2 2；步步5 5 假設(shè)假設(shè)N N是目標(biāo)節(jié)點(diǎn)

50、是目標(biāo)節(jié)點(diǎn)Sg Sg ，那么令，那么令dmdmd d Sg Sg -1 -1 ，把，把SgSg放到放到G G 表的尾部，轉(zhuǎn)步表的尾部，轉(zhuǎn)步2 2。步步6 6 假設(shè)假設(shè)N N不可擴(kuò)展，那么轉(zhuǎn)步不可擴(kuò)展，那么轉(zhuǎn)步2 2； 步步7 7 否那么，擴(kuò)展否那么，擴(kuò)展N N，將其所有子節(jié)點(diǎn)，將其所有子節(jié)點(diǎn)NiNi配上指向配上指向N N的返回指針放入的返回指針放入OPENOPEN表首部，表首部， 置置d d Ni Ni d dN N1 1 ，轉(zhuǎn)步，轉(zhuǎn)步2 2。 2022-6-1人工智能542.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(1)(1)1.啟發(fā)性知識(shí)與啟發(fā)函數(shù)啟發(fā)性知識(shí)與啟發(fā)函數(shù)n啟發(fā)

51、性知識(shí)啟發(fā)性知識(shí) 就是與被求解問題自身特性相關(guān)的知識(shí)，包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗(yàn)、技巧等，對(duì)應(yīng)于問題求解框架中的控制性知識(shí)。 n啟發(fā)函數(shù)啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識(shí)形式化，即用一定的函數(shù)表示出來，通過函數(shù)計(jì)算來評(píng)價(jià)每種選擇的價(jià)值大小，用以指導(dǎo)搜索過程，這樣的函數(shù)稱為啟發(fā)函數(shù)。 2022-6-1人工智能552022-6-1人工智能562.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(2)(2)2.啟發(fā)函數(shù)的設(shè)計(jì)啟發(fā)函數(shù)的設(shè)計(jì) 在實(shí)際設(shè)計(jì)過程中，啟發(fā)函數(shù)是用來估計(jì)搜索樹節(jié)點(diǎn)在實(shí)際設(shè)計(jì)過程中，啟發(fā)函數(shù)是用來估計(jì)搜索樹節(jié)點(diǎn)x與目標(biāo)節(jié)

52、點(diǎn)接近程度的一種函數(shù)，通常記為與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常記為hx。啟發(fā)函數(shù)可以是：?jiǎn)l(fā)函數(shù)可以是：1一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度；一個(gè)節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的某種距離或差異的量度；2一個(gè)節(jié)點(diǎn)處在最正確路徑上的概率；一個(gè)節(jié)點(diǎn)處在最正確路徑上的概率；3根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。2022-6-1人工智能572.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(3)(3)2.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法2.4.2 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法算法 A*算法在游戲中的應(yīng)用算法在游戲中的應(yīng)用2022-6-1人工智能582.4.1 啟發(fā)

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

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

55、點(diǎn)假設(shè)目標(biāo)節(jié)點(diǎn)Sg N，那么搜索成功，利用，那么搜索成功，利用CLOSED表中的返回指針找出表中的返回指針找出S0到到N的路徑即為所求的路徑即為所求解，退出；解，退出；步步5 假設(shè)假設(shè)N不可擴(kuò)展，那么轉(zhuǎn)步不可擴(kuò)展，那么轉(zhuǎn)步2 ；步步6 否那么，擴(kuò)展否那么，擴(kuò)展N，計(jì)算，計(jì)算N的每個(gè)子節(jié)點(diǎn)的每個(gè)子節(jié)點(diǎn)x的函數(shù)值，并的函數(shù)值，并將將N所有子節(jié)點(diǎn)所有子節(jié)點(diǎn)x配以指向配以指向N的返回指針后放入的返回指針后放入OPEN表中，依據(jù)啟發(fā)函數(shù)對(duì)節(jié)點(diǎn)的計(jì)算，再對(duì)表中，依據(jù)啟發(fā)函數(shù)對(duì)節(jié)點(diǎn)的計(jì)算，再對(duì)OPEN表中表中所有節(jié)點(diǎn)按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步所有節(jié)點(diǎn)按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步2。2022

56、-6-1人工智能602.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法42.局部擇優(yōu)搜索局部擇優(yōu)搜索根本思想：局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)根本思想：局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)先搜索，在先搜索，在OPEN表中保存所有已生成而未考察的節(jié)點(diǎn)，表中保存所有已生成而未考察的節(jié)點(diǎn)，對(duì)其中新生成的每個(gè)子節(jié)點(diǎn)對(duì)其中新生成的每個(gè)子節(jié)點(diǎn)x計(jì)算啟發(fā)函數(shù)，從全部子節(jié)點(diǎn)計(jì)算啟發(fā)函數(shù)，從全部子節(jié)點(diǎn)中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察節(jié)點(diǎn)的范中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察節(jié)點(diǎn)的范圍是剛剛生成的全部子節(jié)點(diǎn)，圍是剛剛生成的全部子節(jié)點(diǎn)，局部擇優(yōu)搜索算法：局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的區(qū)

57、別僅在步與全局擇優(yōu)搜索算法的區(qū)別僅在步6： 步步6 否那么，擴(kuò)展否那么，擴(kuò)展N，計(jì)算，計(jì)算N的每個(gè)子節(jié)點(diǎn)的每個(gè)子節(jié)點(diǎn)x的函數(shù)值，并的函數(shù)值，并將將N的所有子節(jié)點(diǎn)的所有子節(jié)點(diǎn)x配以指向節(jié)點(diǎn)配以指向節(jié)點(diǎn)N的指針后，將全部子節(jié)的指針后，將全部子節(jié)點(diǎn)按啟發(fā)函數(shù)值升序排列后放入點(diǎn)按啟發(fā)函數(shù)值升序排列后放入OPEN表的首部，轉(zhuǎn)步表的首部，轉(zhuǎn)步2。2022-6-1人工智能612.4.2 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法算法1 啟發(fā)函數(shù)是對(duì)當(dāng)前節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)未來可能要付出的代價(jià)的估計(jì)。 在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒有考慮從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)已經(jīng)付出的實(shí)際代價(jià)。 在很多實(shí)際問題中，已經(jīng)付

58、出的實(shí)際代價(jià)是必須考慮的，如TSP問題等。將兩者同時(shí)考慮，用于指導(dǎo)搜索的算法稱為A算法和算法和A*算法算法。2022-6-1人工智能63 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法算法21. A1. A算法算法估價(jià)函數(shù)估價(jià)函數(shù)f fx x : :為了防止在單獨(dú)利用啟發(fā)函數(shù)的時(shí)候?yàn)榱朔乐乖趩为?dú)利用啟發(fā)函數(shù)的時(shí)候誤入歧途，將啟發(fā)函數(shù)誤入歧途，將啟發(fā)函數(shù)h hx x與代價(jià)函數(shù)與代價(jià)函數(shù)g gx x相結(jié)合，相結(jié)合，即初始節(jié)點(diǎn)即初始節(jié)點(diǎn)S0S0到達(dá)節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)x x處已付出的代價(jià)與節(jié)點(diǎn)處已付出的代價(jià)與節(jié)點(diǎn)x x 到達(dá)目到達(dá)目標(biāo)節(jié)點(diǎn)標(biāo)節(jié)點(diǎn)SgSg的接近程度估計(jì)值總和。的接近程度估計(jì)值總和。 f fx

59、x g gx xh hx x g gx x代價(jià)函數(shù)：初始節(jié)點(diǎn)代價(jià)函數(shù)：初始節(jié)點(diǎn)S0S0到達(dá)節(jié)點(diǎn)到達(dá)節(jié)點(diǎn)x x處已付出的代處已付出的代價(jià)，有利于搜索縱向開展，提高搜索效率，但影響完備價(jià)，有利于搜索縱向開展，提高搜索效率，但影響完備性。性。 h hx x啟發(fā)函數(shù)：節(jié)點(diǎn)啟發(fā)函數(shù)：節(jié)點(diǎn)x x 到達(dá)目標(biāo)節(jié)點(diǎn)到達(dá)目標(biāo)節(jié)點(diǎn)SgSg的接近程度估的接近程度估計(jì)值有利于搜索橫向開展，提高搜索的完備性，但影響計(jì)值有利于搜索橫向開展，提高搜索的完備性，但影響搜索效率。搜索效率。 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法算法3代價(jià)代價(jià)gx的計(jì)算的計(jì)算 gx表示從初始節(jié)點(diǎn)表示從初始節(jié)點(diǎn)S0到節(jié)點(diǎn)到節(jié)點(diǎn)x的代價(jià)：的代

60、價(jià)： g S0 0 g xj g xi cxi，xj 其中，其中，cxi，xj表示父節(jié)點(diǎn)表示父節(jié)點(diǎn)xi到子節(jié)點(diǎn)到子節(jié)點(diǎn)xj的代價(jià)的代價(jià)ADCEB464332323462344632C1B1D1D2E1C2E2D3C3B2E4E36B32022-6-1人工智能64 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法算法4對(duì)估價(jià)函數(shù) fx gxhx 令其中的hx=0時(shí)，這時(shí)得到的是代價(jià)樹的非啟發(fā)式搜索算法。按對(duì)節(jié)點(diǎn)的考察范圍不同，可分為兩種搜索策略：分支界限法將全局擇優(yōu)搜索算法中的hx替換為gx ，即可得到分支界限搜索算法。瞎子爬山法將局部擇優(yōu)搜索算法中的hx替換為gx ，即可得到瞎子爬山搜索算法。2