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

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

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

3、長(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.2.知識(shí)的分類知識(shí)的分類（1 1）從應(yīng)用領(lǐng)域來劃分）從應(yīng)用領(lǐng)域來劃分n常識(shí)性知識(shí)常識(shí)性知識(shí)n領(lǐng)域（專業(yè)）性知識(shí)領(lǐng)域（專業(yè)）性知識(shí)（2 2）從在問題求解中的作用來劃分）從在問題求解中的作用來劃分n敘述性知識(shí)敘述性知識(shí)n過程性知識(shí)過程性知識(shí)n控制性知識(shí)控制性知識(shí)（3 3）從確定性來劃分）從確定性來劃分n確定性知識(shí)確定性知識(shí)n非確定性知識(shí)非確定性知識(shí)（4 4）從知識(shí)的表現(xiàn)形式來劃分，可分為文字、

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

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

6、程中所需要的各種知識(shí)，包括構(gòu)成問題求解框問題求解過程中所需要的各種知識(shí)，包括構(gòu)成問題求解框架的全部知識(shí)。架的全部知識(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-5-16人工智能9例例2.12.1 麥卡賽問題麥卡賽問題。 在一個(gè)在一個(gè)2n2n 2n2n的方格棋盤中，去掉的方格棋盤中，去掉對(duì)角的兩個(gè)方格，如圖（對(duì)角的兩個(gè)方格，如圖（a a），問能否將它全部劃成若干），問能否將它全部劃成若干1 1 2 2的小長(zhǎng)方塊？的小長(zhǎng)方塊？目標(biāo)狀態(tài)目標(biāo)狀態(tài)初始狀態(tài)初始狀態(tài)可

7、達(dá)狀態(tài)可達(dá)狀態(tài)同構(gòu)問題同構(gòu)問題同態(tài)問題同態(tài)問題2022-5-16人工智能102.1.3 2.1.3 圖搜索技術(shù)圖搜索技術(shù)(1)(1)1.1.搜索搜索 搜索，簡(jiǎn)單地說就是搜索，簡(jiǎn)單地說就是“尋找尋找”，目的是找到問題的解。，目的是找到問題的解。在問題求解過程中，待求解的問題被抽象成一定空間上的圖，在問題求解過程中，待求解的問題被抽象成一定空間上的圖，搜索過程就是搜索過程就是從從圖中圖中初始節(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)過經(jīng)過（考察過）（考察過）

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

9、照什么樣的順序考察節(jié)點(diǎn)和經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。經(jīng)過狀態(tài)空間圖的哪些節(jié)點(diǎn)。盲目搜索：盲目搜索：無向?qū)o向?qū)У牡乃阉魉阉?，也稱窮舉搜索。，也稱窮舉搜索。啟發(fā)式搜索：利用啟發(fā)式搜索：利用“啟發(fā)性信息啟發(fā)性信息”作為作為導(dǎo)航導(dǎo)航的搜索過程。的搜索過程。 對(duì)于較大或無限狀態(tài)空間問題，盲目搜索效率太低，所對(duì)于較大或無限狀態(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ù)挖掘、智能檢索等。2022-5-16人工智能122022-

10、5-16人工智能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)空間圖2022-5-16人工智能142.2.1 2.2.1 狀態(tài)空間圖（狀態(tài)空間圖（1 1）1.1.狀態(tài)狀態(tài) 狀態(tài)對(duì)應(yīng)敘述性知識(shí)狀態(tài)對(duì)應(yīng)敘述性知識(shí)，描述一個(gè)問題在，描述一個(gè)問題在開始、結(jié)束或中間的某一時(shí)刻所處的開始、結(jié)束或中間的某一時(shí)刻所處的狀況狀況或或狀態(tài)狀態(tài)。通常引進(jìn)一組變量。通常引進(jìn)一組變量 ，表，表示與問題狀態(tài)相關(guān)的各種要素，并用這組變示與問題狀態(tài)相關(guān)的各種要素，并用這組變量所構(gòu)成的多元組量所構(gòu)成的多元組 來表示狀來表示狀態(tài)。態(tài)。 狀

11、態(tài)在狀態(tài)圖中表示為狀態(tài)在狀態(tài)圖中表示為節(jié)點(diǎn)節(jié)點(diǎn)。12nqqq， ， ，12()nqqq， ，2022-5-16人工智能152.2.1 2.2.1 狀態(tài)空間圖（狀態(tài)空間圖（2 2）2.2.操作操作 操作對(duì)應(yīng)過程性知識(shí)操作對(duì)應(yīng)過程性知識(shí)，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)，即狀態(tài)轉(zhuǎn)換規(guī)則，描述狀態(tài)之間的關(guān)系。之間的關(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ī)械

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

13、間圖就是一個(gè)個(gè)賦值有向圖賦值有向圖。狀態(tài)空間常記為三元組：狀態(tài)空間常記為三元組： S：初始狀態(tài)的集合初始狀態(tài)的集合 F：操作的集合操作的集合 G：目標(biāo)狀態(tài)的集合。目標(biāo)狀態(tài)的集合。 由問題的狀態(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的的路徑路徑問題問題，也就是尋找操作序列的問題。，也就是尋找操作序列的問題。n狀態(tài)空間的解

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

15、翻轉(zhuǎn)錢幣問題（2 2）1.1.狀態(tài)狀態(tài)引入一個(gè)三元組引入一個(gè)三元組(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)。2022-5-16人工智能192.2.操作操作翻動(dòng)錢幣的操作抽象為改變上述狀態(tài)的算子，翻動(dòng)錢幣的操作抽象為改變上述狀態(tài)的算子， 即即Fa, b, c a: a:把錢幣把錢幣q0翻轉(zhuǎn)一次翻轉(zhuǎn)一次 b:b:把

16、錢幣把錢幣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)空間為：?jiǎn)栴}的狀態(tài)空間為： 2022-5-16人工智能21 構(gòu)造狀態(tài)空間圖：構(gòu)造狀態(tài)空間圖：507QabcQQ， ， ， ，aabababaabbbbcccbcccb例例2.22.2 翻轉(zhuǎn)錢幣問題（翻轉(zhuǎn)錢幣問題（5 5）2022-5-16人工智能22翻轉(zhuǎn)錢幣問題狀態(tài)空間圖的翻轉(zhuǎn)錢幣問題狀態(tài)空間圖的另一種表示另一種表示：引入分量引入分量n表示已經(jīng)

17、翻過的次數(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）2022-5-16人工智能23aabababaabbbbcccbcccb2022-5-16人工智能24例例2.32.3 修道士和野人問題（修道士和野人問題（1 1） 在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士們想用這條船將所有的人都運(yùn)過河去，但受修道士們想用這條船將所有的人都運(yùn)過河去，但受到以下條件的限制：到以下條件的限制： （1 1）修道士和野人都會(huì)劃船，

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

19、 c： 左岸的野人數(shù)左岸的野人數(shù) c c 0,1,2,3 b： 左岸的船數(shù)左岸的船數(shù) b0,1右岸的狀態(tài)不必標(biāo)出，因?yàn)椋河野兜臓顟B(tài)不必標(biāo)出，因?yàn)椋?右岸的修道士人數(shù)右岸的修道士人數(shù) m 3m 右岸的野人數(shù)右岸的野人數(shù) c 3c 右岸的船數(shù)右岸的船數(shù) b 1b2022-5-16人工智能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 0S251 2 0S23 1 1 S101 1 1 S183 1 0S2

20、61 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,q01,q10,q11, q02,q20 2022-5-16人工

21、智能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,c=2)b=0, m=m-2p02b=1, m=0或3, c2b=0

22、, 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.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)為節(jié)點(diǎn)，按照操作要求的條件，在節(jié)點(diǎn)之以全部合法狀態(tài)為節(jié)點(diǎn)，按照操作要

23、求的條件，在節(jié)點(diǎn)之間構(gòu)造有向邊。間構(gòu)造有向邊。2022-5-16人工智能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)q01p01S30(0,1,0) p02q02S12(0,3,1)p01q01S29

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

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

26、隱式圖。重排九宮問題的隱式圖描述為：重排九宮問題的隱式圖描述為： （1 1）有關(guān)狀態(tài)的知識(shí)：）有關(guān)狀態(tài)的知識(shí)：狀態(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 iijijXX時(shí)，例例2.42.4 重排九宮問題重排九宮問題（八數(shù)碼問題）

27、（八數(shù)碼問題） 例例2.42.4 重排九宮問題（重排九宮問題（2 2）（2 2）有關(guān)操作的知識(shí)（規(guī)則）：）有關(guān)操作的知識(shí)（規(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 = n X8 =0；8 8組規(guī)則組規(guī)則: : R22(X8=0 ) (

28、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)圖稱為隱式狀態(tài)隱式狀態(tài)圖圖，或者說，或者說狀態(tài)圖狀態(tài)圖的的隱式表示隱式表示。

29、例例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)2022-5-16人工智能36例例2.52.5 旅行商問題旅行商問題(TSP)(1)(TSP)(1) 設(shè)有設(shè)有n個(gè)互相可直達(dá)的城市，某推銷商準(zhǔn)備從其中的個(gè)互相可直達(dá)的城市，某推銷商準(zhǔn)備從其中的A A城城出發(fā)，周游各城市一遍，最后又回到出發(fā)，周游各城市一遍，最

30、后又回到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 時(shí)，時(shí)，Ai Aj； 當(dāng)且僅當(dāng)當(dāng)且僅當(dāng)| |=n+1時(shí)時(shí)，A=A。初始狀態(tài)初始狀態(tài)： = A，| | = 1終止?fàn)顟B(tài)終止?fàn)顟B(tài)： = AA1A2A，| | = n+1例例2.52.5 旅行商問題旅行商問題(TSP)(2)(TSP)(2)（2 2）操作描述

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

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

33、 ,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） 。2022-5-16人工智能38AB123S0：（：（1，1）123S1：（：（1，2）123S2：（：（1，3）AA123S5：（：（2，3）123S4：（：（2，2）123S3：（：（2，1）123S8：（：（3，3）123S7：（：（3，2）123S6：（：（3，1）AAAAABABBBBB補(bǔ)充例補(bǔ)充例 二階梵塔問題

34、（二階梵塔問題（2 2）2022-5-16人工智能39（2 2）有關(guān)操作的知識(shí)（規(guī)則）：）有關(guān)操作的知識(shí)（規(guī)則）： A（i，j）表示金盤表示金盤A從第從第i號(hào)桿移到號(hào)桿移到j(luò)號(hào)桿，號(hào)桿，B（i，j）表示金盤表示金盤B從第從第i號(hào)桿移到號(hào)桿移到j(luò)號(hào)桿，其中：號(hào)桿，其中：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），）， B（3，2）分析每個(gè)操作的條件和動(dòng)作，得到下表：分析每個(gè)操作的條件和動(dòng)作，

35、得到下表：補(bǔ)充例補(bǔ)充例 二階梵塔問題（二階梵塔問題（3 3）2022-5-16人工智能40補(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 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

36、=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-5-16人工智能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)2022-5-16人工智能422.3 2.3 狀態(tài)空間圖的盲目搜索狀態(tài)空間圖的盲目搜索n盲目搜索盲目搜索

37、: :搜索時(shí)搜索時(shí)不參考不參考與具體待求解問題相關(guān)的任何信息，與具體待求解問題相關(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): :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)系，如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)（返回指針）。如每個(gè)節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號(hào)（返回指針）。CLOSEDCLOSED表中存

38、表中存放的就是一定搜索策略下的搜索樹。放的就是一定搜索策略下的搜索樹。節(jié)點(diǎn)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)父節(jié)點(diǎn)編號(hào)編號(hào)編號(hào)節(jié)點(diǎn)節(jié)點(diǎn)父節(jié)點(diǎn)編號(hào)父節(jié)點(diǎn)編號(hào)OPENOPEN表表CLOSEDCLOSED表表2022-5-16人工智能442.3 狀態(tài)空間圖的盲目搜索狀態(tài)空間圖的盲目搜索2.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索2.3.2 深度優(yōu)先搜索深度優(yōu)先搜索2022-5-16人工智能452.3.1 廣度優(yōu)先搜索（廣度優(yōu)先搜索（1 1） 廣度優(yōu)先搜索（廣度優(yōu)先搜索（A A?eded）基本思想：）基本思想： 廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置置一層一層一層一層向下的搜索過程。通過將

39、向下的搜索過程。通過將OPEN表設(shè)表設(shè)計(jì)為一個(gè)計(jì)為一個(gè)隊(duì)列隊(duì)列來實(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表中第一個(gè)結(jié)點(diǎn)表中第一個(gè)結(jié)點(diǎn)N N 放在放在CLOSED 表中；并冠以順序編號(hào)表中；并冠以順序編號(hào)n；步步4 4 若結(jié)點(diǎn)若結(jié)點(diǎn)N為目標(biāo)結(jié)點(diǎn)，則搜索成功。利用為目標(biāo)結(jié)點(diǎn)，則搜索成功。利用 CL

40、OSED表中的返回指針找出表中的返回指針找出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）2022-5-16人工智能48例例2.6 使用使用廣度優(yōu)先廣度優(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

41、 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 523八數(shù)碼廣度優(yōu)先搜索八數(shù)碼廣度優(yōu)先搜索1 28 5 37 4 69161 2 38 5 6

42、7 42022-5-16人工智能492.3.1 廣度優(yōu)先搜索廣度優(yōu)先搜索廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先中廣度優(yōu)先中OPEN表表是一個(gè)是一個(gè)隊(duì)列隊(duì)列，CLOSED表表是一個(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)先策略是廣度優(yōu)先策略是完備完備的，即如果問題的解存在，則它一定可的，即如果問題的解存在，則它一定可 以找到解，并且找到的解還是最優(yōu)解。以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性

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

44、 與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是OPEN表表被設(shè)計(jì)成被設(shè)計(jì)成后進(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 2。 例例2.7 使用使用深度優(yōu)先深度優(yōu)先搜索算法求解重排九宮問題搜索算法求解重排九宮問題 1 2

45、 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-5-16人工智能532.3.2 深度優(yōu)先搜索深度優(yōu)先搜索深度優(yōu)先搜索的特點(diǎn)：深度優(yōu)先搜索的特點(diǎn)：OPENOPEN表為一個(gè)表為一個(gè)堆棧堆棧。深度優(yōu)先又稱深度優(yōu)先又稱縱向搜索縱向搜索。一般一般不能保證找到最優(yōu)解不能保證找到最優(yōu)解。如下圖所示：。如下圖所示：圖圖2-13 2-13 深度優(yōu)先搜索不具有完備性示意圖深度優(yōu)先搜索

46、不具有完備性示意圖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)先搜索算法2022-5-16人工智能551.1.有界深度優(yōu)先搜索（有界深度優(yōu)先搜索（A Acdcd ）為克服深度優(yōu)先搜索的不足，可以對(duì)其深度進(jìn)行為克服深度優(yōu)先搜索的不足，可以對(duì)其深度進(jìn)行限制限制n深度界限深度界限dm的選擇很重要的選擇很重要 dm 若太小，則達(dá)不到解的深度，得不到解；若太大若太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計(jì)算機(jī)的存儲(chǔ)空間與時(shí)間，又降低了搜索效，既浪費(fèi)了計(jì)算機(jī)的存

47、儲(chǔ)空間與時(shí)間，又降低了搜索效率。由于解的路徑長(zhǎng)度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o率。由于解的路徑長(zhǎng)度事先難以預(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)找不到解時(shí)，可以將深度界限界限之內(nèi)找不到解時(shí)，可以將深度界限dm不斷擴(kuò)大，每次增加一個(gè)深度增量不斷擴(kuò)大，每次增加一個(gè)深度增量 d，直到找到解，直到找到解，或者搜索完整棵樹。這樣算法的完備性得到了保證，或者搜索完整棵樹。這樣算法的完備性得到了保證，稱為稱為可變界深度優(yōu)先搜索算法

48、可變界深度優(yōu)先搜索算法( (或迭代加深搜索或迭代加深搜索) )。 當(dāng)當(dāng)d =1時(shí)，算法開始蛻變?yōu)闀r(shí)，算法開始蛻變?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)： 若無，則問題無解，退出。若無，則問題無解，退出。 若有，則取出若有，則取出CLOSED表中待擴(kuò)展節(jié)點(diǎn)放入到表

49、中待擴(kuò)展節(jié)點(diǎn)放入到OPEN表表 中，令中，令 dm=dm+d。 2.2.可變界深度優(yōu)先搜索算法可變界深度優(yōu)先搜索算法(3)(3) 步步3 3 取取OPEN表中第一個(gè)節(jié)點(diǎn)表中第一個(gè)節(jié)點(diǎn)N放在放在CLOSED表中；并冠以編號(hào)表中；并冠以編號(hào) 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)步2； 步步7 7 擴(kuò)展擴(kuò)展N，將其所有子節(jié)點(diǎn)，將其所有子節(jié)點(diǎn)Ni配上指向配上指向N的指針放入的指針放入OP

50、EN首首 部部，置，置 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 時(shí)，是否能保證找到最優(yōu)解？時(shí)，是否能保證找到最優(yōu)解？2022-5-16人工智能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表為空，則考察表為空，則考察CLOSED表是否有待擴(kuò)展結(jié)點(diǎn)：表是否有待擴(kuò)展結(jié)點(diǎn)： （1 1）若無待擴(kuò)展結(jié)點(diǎn)，則判斷）若無待擴(kuò)展結(jié)點(diǎn)，則判斷

51、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)表中首部的結(jié)點(diǎn)N放在放在CLOSED表中；并冠以順序表中；并冠以順序編號(hào)編號(hào)n； 步步4 4 若若d（N）dm，則

52、標(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。 2022-5-16人工智能622.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(1)(1)1.1.啟發(fā)性知識(shí)與啟

53、發(fā)函數(shù)啟發(fā)性知識(shí)與啟發(fā)函數(shù)啟發(fā)性知識(shí)啟發(fā)性知識(shí) 就是與被求解問題自身特性相關(guān)的知識(shí)，包括被就是與被求解問題自身特性相關(guān)的知識(shí)，包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗(yàn)、技巧等，對(duì)應(yīng)于問題求解框求解此類問題的經(jīng)驗(yàn)、技巧等，對(duì)應(yīng)于問題求解框架中的架中的控制性知識(shí)控制性知識(shí)。 啟發(fā)函數(shù)啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識(shí)形式化，要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識(shí)形式化，即用一定的函數(shù)表示出來，通過函數(shù)計(jì)算來評(píng)價(jià)每即用一定的函數(shù)表示出來，通過函數(shù)計(jì)算來評(píng)價(jià)每種選擇的價(jià)值大小，用以種選擇的價(jià)值大小，用以指導(dǎo)搜索過程指導(dǎo)搜索過

54、程，這樣的函，這樣的函數(shù)稱為數(shù)稱為啟發(fā)函數(shù)啟發(fā)函數(shù)。 2022-5-16人工智能632022-5-16人工智能642.4 2.4 狀態(tài)空間圖的啟發(fā)式搜索狀態(tài)空間圖的啟發(fā)式搜索(2)(2)2.2.啟發(fā)函數(shù)的設(shè)計(jì)啟發(fā)函數(shù)的設(shè)計(jì) 在實(shí)際設(shè)計(jì)過程中，在實(shí)際設(shè)計(jì)過程中，啟發(fā)函數(shù)啟發(fā)函數(shù)是用來估計(jì)搜索樹節(jié)是用來估計(jì)搜索樹節(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）一個(gè)結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的某種距離或差異的）一個(gè)結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的某種距離或差異的量度量度；（2 2）一個(gè)結(jié)點(diǎn)處在最佳路徑上的）一個(gè)結(jié)點(diǎn)處在最佳路徑上的概率概率；

55、（3 3）根據(jù)主觀經(jīng)驗(yàn)的主觀）根據(jù)主觀經(jīng)驗(yàn)的主觀打分打分等。等。2022-5-16人工智能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)用2022-5-16人工智能662.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法（1 1）啟發(fā)式搜索啟發(fā)式搜索用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再搜索算法基礎(chǔ)上再增加啟

56、發(fā)函數(shù)值增加啟發(fā)函數(shù)值的的計(jì)算計(jì)算與與傳播傳播過過程，并且由程，并且由啟發(fā)函數(shù)值啟發(fā)函數(shù)值來來確定確定節(jié)點(diǎn)的節(jié)點(diǎn)的擴(kuò)展順序擴(kuò)展順序。按選擇范圍不同，啟發(fā)式搜索分為按選擇范圍不同，啟發(fā)式搜索分為：全局擇優(yōu)搜索全局擇優(yōu)搜索局部擇優(yōu)搜索局部擇優(yōu)搜索2022-5-16人工智能672.4.1 啟發(fā)式搜索算法啟發(fā)式搜索算法（2 2）1.1.全局擇優(yōu)搜索全局擇優(yōu)搜索基本思想：基本思想： 在在OPEN表中表中保留所有已生成而未考察保留所有已生成而未考察的節(jié)點(diǎn)，的節(jié)點(diǎn)，并用并用啟發(fā)函數(shù)啟發(fā)函數(shù)h(x)對(duì)它們對(duì)它們?nèi)咳窟M(jìn)行估價(jià)，從中選出進(jìn)行估價(jià)，從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而不管這個(gè)節(jié)點(diǎn)出現(xiàn)在搜索樹最優(yōu)節(jié)點(diǎn)進(jìn)行

57、擴(kuò)展，而不管這個(gè)節(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表中，計(jì)算表中，計(jì)算h(S0)；步步2 2 若若OPEN表為空，則搜索失敗，退出；表為空，則搜索失敗，退出；步步3 3 否則，移出否則，移出OPEN表中第一個(gè)結(jié)點(diǎn)表中第一個(gè)結(jié)點(diǎn)N放入放入CLOSED表中，表中，并冠以序號(hào)并冠以序號(hào)n ；步步4 4 若目標(biāo)結(jié)點(diǎn)若目標(biāo)結(jié)點(diǎn)Sg N，則搜索成功，利用，則搜索成功，利用CLOSED表中的表中的返回指針找出返回指針找出S0到到N N 的路徑即為所求解，退出；的路徑

58、即為所求解，退出；步步5 5 若若N N不可擴(kuò)展，則轉(zhuǎn)步不可擴(kuò)展，則轉(zhuǎn)步2 2 ；步步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配以指向配以指向N的返回指針后放入的返回指針后放入OPEN表中，表中，依據(jù)啟發(fā)函數(shù)對(duì)結(jié)點(diǎn)的計(jì)算，再對(duì)依據(jù)啟發(fā)函數(shù)對(duì)結(jié)點(diǎn)的計(jì)算，再對(duì)OPEN表中表中所有結(jié)點(diǎn)所有結(jié)點(diǎn)按按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步2 2。2022-5-16人工智能682.4.1 啟發(fā)式搜索算法（啟發(fā)式搜索算法（4 4）2.2.局部擇優(yōu)搜索局部擇優(yōu)搜索基本思想：局部擇優(yōu)搜索是在啟發(fā)性知識(shí)

59、導(dǎo)航下的深度優(yōu)基本思想：局部擇優(yōu)搜索是在啟發(fā)性知識(shí)導(dǎo)航下的深度優(yōu)先搜索，在先搜索，在OPEN表中保留所有已生成而未考察的結(jié)點(diǎn)，表中保留所有已生成而未考察的結(jié)點(diǎn)，對(duì)其中對(duì)其中新生成的每個(gè)子結(jié)點(diǎn)新生成的每個(gè)子結(jié)點(diǎn)x計(jì)算啟發(fā)函數(shù)計(jì)算啟發(fā)函數(shù)，從，從全部子結(jié)點(diǎn)全部子結(jié)點(diǎn)中選出中選出最優(yōu)結(jié)點(diǎn)最優(yōu)結(jié)點(diǎn)進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察結(jié)點(diǎn)的范進(jìn)行擴(kuò)展，其選擇下一個(gè)要考察結(jié)點(diǎn)的范圍是剛剛生成的全部子結(jié)點(diǎn)，圍是剛剛生成的全部子結(jié)點(diǎn)，局部擇優(yōu)搜索算法：局部擇優(yōu)搜索算法： 與全局擇優(yōu)搜索算法的區(qū)別僅在與全局擇優(yōu)搜索算法的區(qū)別僅在步步6 6： 步步6 6 否則，擴(kuò)展否則，擴(kuò)展N N，計(jì)算，計(jì)算N N的每個(gè)子結(jié)點(diǎn)的每個(gè)子結(jié)

60、點(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。2022-5-16人工智能692.4.2 啟發(fā)式搜索的啟發(fā)式搜索的A算法和算法和A*算法（算法（1） 啟發(fā)函數(shù)是對(duì)當(dāng)前結(jié)點(diǎn)到達(dá)目標(biāo)結(jié)點(diǎn)未來啟發(fā)函數(shù)是對(duì)當(dāng)前結(jié)點(diǎn)到達(dá)目標(biāo)結(jié)點(diǎn)未來可能要付出的代價(jià)的估計(jì)?？赡芤冻龅拇鷥r(jià)的估計(jì)。 在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒有考慮從初始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)已經(jīng)付出的實(shí)際有考慮從初始結(jié)點(diǎn)到當(dāng)前