搜索策略課件

1、2022-3-181第第3 3章章 搜索策略搜索策略o 問題求解系統(tǒng)劃分為兩大類問題求解系統(tǒng)劃分為兩大類n 知識貧乏系統(tǒng)知識貧乏系統(tǒng) o 依靠依靠搜索技術(shù)搜索技術(shù)解決問題解決問題 o 知識貧乏、缺乏針對性知識貧乏、缺乏針對性o 效率低效率低 n 知識豐富系統(tǒng)知識豐富系統(tǒng) o 依靠依靠推理技術(shù)推理技術(shù)解決問題解決問題o 基于豐富知識的推理技術(shù)，直截了當(dāng)基于豐富知識的推理技術(shù)，直截了當(dāng) o 效率高效率高 2022-3-182第第3 3章章 搜索策略搜索策略o 兩大類兩大類搜索技術(shù)搜索技術(shù):n 1、一般圖搜索、啟發(fā)式搜索、一般圖搜索、啟發(fā)式搜索n 2、基于問題歸約的與或圖搜索、基于問題歸約的與或圖搜

2、索 o 兩種典型的兩種典型的推理技術(shù)推理技術(shù):n 1、基于歸結(jié)的演繹推理、基于歸結(jié)的演繹推理o 歸結(jié)反演歸結(jié)反演n 2、基于規(guī)則的演繹推理、基于規(guī)則的演繹推理o 正向演繹推理正向演繹推理o 逆向演繹推理逆向演繹推理 2022-3-183 o對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達(dá)到所希望目標(biāo)的動作序列，并使其所付出的代價最小、性能最好。o基于給定的問題，問題求解的第一步是目標(biāo)的表示。o搜索就是找到智能系統(tǒng)的動作序列的過程。 2022-3-184o 搜索算法的輸入是給定的問題，輸出是表示為動作序列的方案。o 一旦有了方案，就可以執(zhí)行該方案所給出的動作了。（執(zhí)行階段）o 因此，求解問題包括：

3、n目標(biāo)表示目標(biāo)表示n搜索搜索n執(zhí)行執(zhí)行2022-3-185（1）初始狀態(tài)集合：定義了初始的環(huán)境。（2）操作符集合：把一個問題從一個狀態(tài)變換為另一個狀態(tài)的動作集合。（3）目標(biāo)檢測函數(shù)：用來確定一個狀態(tài)是不是目標(biāo)。（4）路徑費(fèi)用函數(shù)：對每條路徑賦予一定費(fèi)用的函數(shù)。其中，初其中，初始狀態(tài)集始狀態(tài)集合和操作合和操作符集合定符集合定義了問題義了問題的搜索空的搜索空間。間。一般給定問題就是確定該問題的一一般給定問題就是確定該問題的一些基本信息，一個問題由些基本信息，一個問題由4 4部分組成部分組成: :2022-3-186o 和通常的搜索空間不同，人工智能中大多數(shù)問題的狀態(tài)空間在問題求解之前不是全部知道的

4、。 在人工智能中，搜索問題一般包括兩個重在人工智能中，搜索問題一般包括兩個重要的問題：要的問題：v搜索什么搜索什么搜索什么通常指的就是目標(biāo)。搜索什么通常指的就是目標(biāo)。v在哪里搜索在哪里搜索在哪里搜索就是在哪里搜索就是“搜索空間搜索空間”。搜索空間通常。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為是指一系列狀態(tài)的匯集，因此稱為狀態(tài)空間狀態(tài)空間。2022-3-187o所以，人工智能中的搜索可以分成兩個階段：n 狀態(tài)空間的生成階段n 在該狀態(tài)空間中對所求問題狀態(tài)的搜索搜索可以根據(jù)是否使用啟發(fā)式信息分搜索可以根據(jù)是否使用啟發(fā)式信息分為為v盲目搜索盲目搜索v啟發(fā)式搜索啟發(fā)式搜索 2022-3-188o 盲

5、目搜索盲目搜索 只是可以區(qū)分出哪個是目標(biāo)狀態(tài)。 一般是按預(yù)定的搜索策略進(jìn)行搜索。 沒有考慮到問題本身的特性，這種搜索具有很大的盲目性，效率不高，不便于復(fù)雜問題的求解。 o啟發(fā)式搜索啟發(fā)式搜索是在搜索過程中加入了與問題有關(guān)的啟發(fā)式信息，用于指導(dǎo)搜索朝著最有希望的方向前進(jìn)，加速問題的求解并找到最優(yōu)解。 2022-3-189o 根據(jù)問題的表示方式分為n 狀態(tài)空間搜索n 與或圖搜索狀態(tài)空間狀態(tài)空間搜索是用搜索是用狀態(tài)空間狀態(tài)空間法來求解法來求解問題所進(jìn)問題所進(jìn)行的搜索行的搜索與與/ /或圖搜或圖搜索是指用問索是指用問題規(guī)約方法題規(guī)約方法來求解問題來求解問題時所進(jìn)行的時所進(jìn)行的搜索。搜索。2022-3-

6、1810o 考慮一個問題的狀態(tài)空間為一棵樹的形式。o 寬度優(yōu)先搜索o 深度優(yōu)先搜索如果根節(jié)點(diǎn)首先如果根節(jié)點(diǎn)首先擴(kuò)展，然后是擴(kuò)擴(kuò)展，然后是擴(kuò)展根節(jié)點(diǎn)生成的展根節(jié)點(diǎn)生成的所有節(jié)點(diǎn)，然后所有節(jié)點(diǎn)，然后是這些節(jié)點(diǎn)的后是這些節(jié)點(diǎn)的后繼，如此反復(fù)下繼，如此反復(fù)下去。去。在樹的最深一層的節(jié)在樹的最深一層的節(jié)點(diǎn)中擴(kuò)展一個節(jié)點(diǎn)。點(diǎn)中擴(kuò)展一個節(jié)點(diǎn)。只有當(dāng)搜索遇到一個只有當(dāng)搜索遇到一個死亡節(jié)點(diǎn)（非目標(biāo)節(jié)死亡節(jié)點(diǎn)（非目標(biāo)節(jié)點(diǎn)并且是無法擴(kuò)展的點(diǎn)并且是無法擴(kuò)展的節(jié)點(diǎn)）的時候，才返節(jié)點(diǎn)）的時候，才返回上一層選擇其他的回上一層選擇其他的節(jié)點(diǎn)搜索。節(jié)點(diǎn)搜索。2022-3-1811o 無論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點(diǎn)

7、的順序一般都是固定的，即一旦搜索空間給定，節(jié)點(diǎn)遍歷的順序就固定了。這種類型的遍歷稱為“確定性”的，也就是盲目搜索。o 對于啟發(fā)式搜索，在計(jì)算每個節(jié)點(diǎn)的參數(shù)之前無法確定先選擇哪個節(jié)點(diǎn)擴(kuò)展，這種搜索一般也稱為非確定的。 2022-3-1812o 完備性：n 如果存在一個解答，該策略是否保證能夠找到？o 時間復(fù)雜性：n 需要多長時間可以找到解答？o 空間復(fù)雜性：n 執(zhí)行搜索需要多少存儲空間？o 最優(yōu)性：n 如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索策略評價標(biāo)準(zhǔn)搜索策略評價標(biāo)準(zhǔn): :2022-3-1813有許多智力問題有許多智力問題( (如梵塔問題、旅行商問題、八皇如梵塔問題、旅行

8、商問題、八皇后問題、農(nóng)夫過河問題等后問題、農(nóng)夫過河問題等) )和實(shí)際問題（如路徑規(guī)和實(shí)際問題（如路徑規(guī)劃、機(jī)器人行動規(guī)劃等）都可以歸結(jié)為劃、機(jī)器人行動規(guī)劃等）都可以歸結(jié)為狀態(tài)空間搜狀態(tài)空間搜索索。用用狀態(tài)空間搜索狀態(tài)空間搜索來求解問題的系統(tǒng)均定義一個來求解問題的系統(tǒng)均定義一個狀態(tài)狀態(tài)空間空間，并通過適當(dāng)?shù)?，并通過適當(dāng)?shù)乃阉魉惴ㄋ阉魉惴ㄔ谠跔顟B(tài)空間狀態(tài)空間中搜索中搜索解解答路徑答路徑。2022-3-1814nS問題求解（即搜索）過程中所有問題求解（即搜索）過程中所有可能到達(dá)可能到達(dá)的的合法狀態(tài)合法狀態(tài)構(gòu)成的集合；構(gòu)成的集合；nO操作算子操作算子的集合，的集合，操作算子的執(zhí)行會導(dǎo)致問題狀態(tài)的操作算

9、子的執(zhí)行會導(dǎo)致問題狀態(tài)的變遷變遷 ；n狀態(tài)狀態(tài)用于記載問題求解（即搜索）過程中用于記載問題求解（即搜索）過程中某一時刻問某一時刻問題現(xiàn)狀的快照題現(xiàn)狀的快照；o 抽象為矢量形式抽象為矢量形式 Q=q0,q1,qnTo 每個元素每個元素qi稱為稱為狀態(tài)分量狀態(tài)分量 o 給定每個給定每個狀態(tài)分量狀態(tài)分量qi的值就得到一個具體的狀態(tài)的值就得到一個具體的狀態(tài) Qk=q0k,q1k,qnkT2022-3-1815狀態(tài)狀態(tài)表示狀態(tài)的變遷表示狀態(tài)的變遷操作算子操作算子問題的狀態(tài)空間問題的狀態(tài)空間是一個表示該問題的全部可能狀態(tài)是一個表示該問題的全部可能狀態(tài)及其變遷的及其變遷的有向圖有向圖。 o 節(jié)點(diǎn)節(jié)點(diǎn)n 狀態(tài)

10、狀態(tài)o 有向弧有向弧n 狀態(tài)的變遷狀態(tài)的變遷 o 弧上的標(biāo)簽弧上的標(biāo)簽n 導(dǎo)致狀態(tài)變遷的導(dǎo)致狀態(tài)變遷的操作算子操作算子 用用狀態(tài)空間搜索狀態(tài)空間搜索來求解問題的系統(tǒng)均定義一個來求解問題的系統(tǒng)均定義一個狀態(tài)狀態(tài)空間空間，并通過適當(dāng)?shù)模⑼ㄟ^適當(dāng)?shù)乃阉魉惴ㄋ阉魉惴ㄔ谠跔顟B(tài)空間狀態(tài)空間中搜索中搜索解解答路徑答路徑。2022-3-1816S1S2S3S4S5S6S7S8S9S0Sg2022-3-18172022-3-1818 例例2:在一個在一個33的方格棋盤上放置著的方格棋盤上放置著1,2,3,4,5,6,7,8八個數(shù)碼，每個數(shù)碼占一格，且有一個空格。這些八個數(shù)碼，每個數(shù)碼占一格，且有一個空格。這些

11、數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。的數(shù)碼方可移入空格?，F(xiàn)在的現(xiàn)在的問題問題是：對于指定的是：對于指定的初始棋局初始棋局和和目標(biāo)棋局目標(biāo)棋局，給出給出數(shù)碼的移動序列數(shù)碼的移動序列。該問題稱為。該問題稱為八數(shù)碼問題八數(shù)碼問題。 56741382初始棋局初始棋局56748321目標(biāo)棋局目標(biāo)棋局移動數(shù)碼移動數(shù)碼2022-3-18192 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31

12、6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 61 2 3 8 47 6 52022-3-18202022-3-1821：o 1)船上人數(shù)不得超過載重限量，設(shè)為船上人數(shù)不得超過載重限量，設(shè)為K個人；個人； o 2)任何時刻（包括兩岸、船上）野人數(shù)目不得任何時刻（包括兩岸、船上）野人數(shù)目

13、不得超過傳教士；超過傳教士； o 3)允許在河的某一岸或者在船上只有野人而沒允許在河的某一岸或者在船上只有野人而沒有傳教士；有傳教士；2022-3-18222022-3-1823可能到達(dá)可能到達(dá)的的合法狀態(tài)合法狀態(tài)：442=32 o (0,0,1),(0,3,0),(3,0,1),(3,3,0)2022-3-1824(2)狀態(tài)空間表示的經(jīng)典例子狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題傳教士和野人問題”o 定義定義2類類操作算子操作算子：n L(x,y)指示從指示從左岸左岸到到右岸右岸的劃船操作的劃船操作 n R(x,y)指示從指示從右岸右岸到到左岸左岸的劃船操作的劃船操作o x + y K=2

14、(船的載重限制船的載重限制)；o x和和y取值的可能組合只有取值的可能組合只有5個個o 10，20，11，01，02 o ( 允許在船上只有野人而沒有傳教士允許在船上只有野人而沒有傳教士 )n 共有共有10個操作算子個操作算子2022-3-18252022-3-1826 2022-3-1827 2022-3-1828課堂練習(xí)課堂練習(xí)o 有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從左岸到右岸）。假設(shè)船太小，農(nóng)夫每次只能帶一樣左岸到右岸）。假設(shè)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；考慮到安全，無農(nóng)夫看管時，狐貍和小東西過河；考慮到安全，無農(nóng)夫看管時，狐貍和

15、小羊不能在一起，小羊和那籃菜也不能在一起。請為羊不能在一起，小羊和那籃菜也不能在一起。請為該問題的解決設(shè)計(jì)狀態(tài)空間，并畫出狀態(tài)空間圖。該問題的解決設(shè)計(jì)狀態(tài)空間，并畫出狀態(tài)空間圖。2022-3-1829解析解析o 以變量以變量m m、f f、s s、v v分別指示農(nóng)夫、狐貍、小羊、菜分別指示農(nóng)夫、狐貍、小羊、菜, ,且每個且每個變量只可取值變量只可取值1(1(表示在左岸表示在左岸) )或或0(0(表示在右岸表示在右岸) )。問題狀態(tài)可。問題狀態(tài)可以四元組以四元組(m(m、f f、s s、v)v)描述描述, ,設(shè)初始狀態(tài)下均在左岸設(shè)初始狀態(tài)下均在左岸, ,目標(biāo)狀目標(biāo)狀態(tài)下都到達(dá)右岸。從而態(tài)下都到達(dá)

16、右岸。從而, ,問題求解任務(wù)可描述為問題求解任務(wù)可描述為 (1, 1, 1, 1) -(0, 0, 0, 0)(1, 1, 1, 1) -(0, 0, 0, 0)o 由于問題簡單由于問題簡單, ,狀態(tài)空間中可能的狀態(tài)總數(shù)為狀態(tài)空間中可能的狀態(tài)總數(shù)為2 22 22 22 = 2 = 16,16,由于要遵從安全限制由于要遵從安全限制, ,合法的狀態(tài)只有合法的狀態(tài)只有( (除初、目狀態(tài)外除初、目狀態(tài)外):): 1110 1110，11011101，10111011，10101010，01010101，00010001，00100010，01000100；不合法狀態(tài)有不合法狀態(tài)有: 0111,1000

17、,1100,0011,0110,1001: 0111,1000,1100,0011,0110,1001o 設(shè)計(jì)二類操作算子設(shè)計(jì)二類操作算子:Lx:Lx、Rx,xRx,x為為m m、f f、s s、v v時分別指示農(nóng)夫時分別指示農(nóng)夫獨(dú)自獨(dú)自, ,帶狐貍帶狐貍, ,帶小羊帶小羊, ,帶菜過河；狀態(tài)空間圖如下所示帶菜過河；狀態(tài)空間圖如下所示. .由于由于LxLx和和RxRx是互逆操作是互逆操作, ,故而解答路徑可有無數(shù)條故而解答路徑可有無數(shù)條, ,但最近的只有但最近的只有二條二條; ;都是都是7 7個操作步個操作步. . o 思考：為什么不把船的狀態(tài)放到狀態(tài)空間中去？思考：為什么不把船的狀態(tài)放到狀態(tài)

18、空間中去？2022-3-1830解析解析: :四元組四元組(m(m、f f、s s、v)v)2022-3-1831(3)狀態(tài)空間的搜索狀態(tài)空間的搜索o 狀態(tài)空間的搜索記為狀態(tài)空間的搜索記為SE，可表示為五元組：，可表示為五元組：n SE=(S,O,E,I,G)；n E搜索引擎；搜索引擎；n I問題的初始狀態(tài)，問題的初始狀態(tài)，I S；n G問題的目標(biāo)狀態(tài)集合，問題的目標(biāo)狀態(tài)集合，G S。o 搜索引擎搜索引擎E可以設(shè)計(jì)為可以設(shè)計(jì)為實(shí)現(xiàn)任何搜索算法實(shí)現(xiàn)任何搜索算法的控制系統(tǒng)。的控制系統(tǒng)。o 基本思想基本思想通過搜索引擎通過搜索引擎E尋找一個尋找一個操作算子的調(diào)用序操作算子的調(diào)用序列列，使問題從初始狀

19、態(tài)，使問題從初始狀態(tài)I變遷到目標(biāo)狀態(tài)變遷到目標(biāo)狀態(tài)G之一。之一。o 解答路徑解答路徑初初-目變遷過程中目變遷過程中的的狀態(tài)序列狀態(tài)序列或相應(yīng)的或相應(yīng)的操作操作算子調(diào)用序列算子調(diào)用序列。2022-3-1832o 或圖（一般圖）或圖（一般圖）n 一個狀態(tài)一個狀態(tài)可以可以有多個可供選擇有多個可供選擇的操作算子；的操作算子；n 操作算子間的選擇是一種操作算子間的選擇是一種“或或”的關(guān)系的關(guān)系; ;n 這樣的有向圖稱為這樣的有向圖稱為或圖。或圖。2022-3-1833(3)(3)狀態(tài)空間的搜索狀態(tài)空間的搜索o 或圖（一般圖）或圖（一般圖）n 一個狀態(tài)可以有多個可供選擇的操作算子；一個狀態(tài)可以有多個可供選

20、擇的操作算子；n 操作算子間的選擇是一種操作算子間的選擇是一種“或或”的關(guān)系，的關(guān)系，這樣的有這樣的有向圖稱為向圖稱為或圖。或圖。o 狀態(tài)空間狀態(tài)空間一般都表示為一般都表示為或圖（一般圖）或圖（一般圖）o 搜索圖搜索圖在在搜索解答路徑搜索解答路徑的過程中畫出搜索時涉及到的過程中畫出搜索時涉及到的節(jié)點(diǎn)和弧線，構(gòu)成所謂的的節(jié)點(diǎn)和弧線，構(gòu)成所謂的搜索圖搜索圖。狀態(tài)空間搜索狀態(tài)空間搜索一般圖搜索一般圖搜索2022-3-1834(3)狀態(tài)空間的搜索狀態(tài)空間的搜索o 狀態(tài)空間狀態(tài)空間、搜索圖搜索圖和和解答路徑解答路徑之間的關(guān)系之間的關(guān)系S0Sg2022-3-1835 初始布局初始布局目標(biāo)布局目標(biāo)布局移動數(shù)

21、碼移動數(shù)碼2022-3-1836 2022-3-1837初始布局初始布局目標(biāo)布局目標(biāo)布局移動數(shù)碼移動數(shù)碼586427301567408321 2022-3-1838(4)一般圖搜索例子一般圖搜索例子八數(shù)碼游戲八數(shù)碼游戲 o 第二步：制定操作算子集第二步：制定操作算子集n直觀方法直觀方法為每個棋牌制定一套可能的走步：左、上、右、為每個棋牌制定一套可能的走步：左、上、右、下四種移動。下四種移動。o 需要需要32個操作算子個操作算子n簡易方法簡易方法僅為空格制定這僅為空格制定這4種走步。種走步。o 僅需僅需4個操作算子個操作算子o 第三步：設(shè)計(jì)搜索引擎第三步：設(shè)計(jì)搜索引擎 n問題狀態(tài)空間的大小問題狀

22、態(tài)空間的大小與與問題涉及的元素問題涉及的元素個數(shù)是程個數(shù)是程指數(shù)級指數(shù)級爆炸式增長爆炸式增長（即，（即，組合爆炸問題組合爆炸問題）o 如，棋盤布局（問題狀態(tài)）總共有如，棋盤布局（問題狀態(tài)）總共有9!=362880個個 n研究焦點(diǎn)研究焦點(diǎn)是是解決組合爆炸問題解決組合爆炸問題，通過壓縮搜索空間通過壓縮搜索空間，提提高搜索效率高搜索效率。 2022-3-1839狀態(tài)空間狀態(tài)空間、搜索圖搜索圖和和解答路徑解答路徑之間的關(guān)系之間的關(guān)系S0Sg2022-3-1840 （1）搜索術(shù)語）搜索術(shù)語o 1、節(jié)點(diǎn)深度、節(jié)點(diǎn)深度n 根節(jié)點(diǎn)根節(jié)點(diǎn)指示指示初始狀態(tài)初始狀態(tài)，令其深度為，令其深度為0；n 搜索圖中的其他節(jié)點(diǎn)

23、的搜索圖中的其他節(jié)點(diǎn)的深度深度dn就可以遞歸地定義為就可以遞歸地定義為其其父節(jié)點(diǎn)深度父節(jié)點(diǎn)深度dn-1加加1：dn= dn-1+1。 根節(jié)點(diǎn)深度根節(jié)點(diǎn)深度=0=0搜索圖搜索圖2022-3-1841 （1）搜索術(shù)語）搜索術(shù)語o 2、節(jié)點(diǎn)擴(kuò)展、節(jié)點(diǎn)擴(kuò)展n應(yīng)用應(yīng)用操作算子操作算子將將上一狀態(tài)上一狀態(tài)（節(jié)點(diǎn)（節(jié)點(diǎn)ni）變遷到）變遷到下一狀態(tài)下一狀態(tài)（節(jié)點(diǎn)（節(jié)點(diǎn)nj）n節(jié)點(diǎn)節(jié)點(diǎn)ni稱為稱為被擴(kuò)展節(jié)點(diǎn)被擴(kuò)展節(jié)點(diǎn)（父節(jié)點(diǎn)）（父節(jié)點(diǎn)）n節(jié)點(diǎn)節(jié)點(diǎn)nj稱為稱為ni的的子節(jié)點(diǎn)子節(jié)點(diǎn)2022-3-1842o4、路徑代價、路徑代價相鄰節(jié)點(diǎn)相鄰節(jié)點(diǎn)ni和和ni+1間的間的路徑代價路徑代價記為記為C(ni, ni+1) n

24、通常令通常令任意相鄰節(jié)點(diǎn)間任意相鄰節(jié)點(diǎn)間的路徑代價相同的路徑代價相同，并以，并以路徑長度路徑長度1 1指示。指示。n即即C(ni, ni+1)=1 。節(jié)點(diǎn)節(jié)點(diǎn)n ni i節(jié)點(diǎn)節(jié)點(diǎn)ni+1節(jié)點(diǎn)節(jié)點(diǎn)nj2022-3-1843 C(nk,ng) C(ni,nk) C(ni,ng) 2022-3-1844o 符號說明：符號說明：ns-初始狀態(tài)節(jié)點(diǎn)初始狀態(tài)節(jié)點(diǎn)nG-搜索圖搜索圖nOPEN-存放存放待擴(kuò)展節(jié)點(diǎn)待擴(kuò)展節(jié)點(diǎn)的表的表nCLOSE-存放存放已被擴(kuò)展的節(jié)點(diǎn)已被擴(kuò)展的節(jié)點(diǎn)的表的表nMOVE-FIRST(OPEN)-取取OPEN表首的節(jié)點(diǎn)表首的節(jié)點(diǎn)作為作為當(dāng)前要被擴(kuò)展當(dāng)前要被擴(kuò)展的節(jié)點(diǎn)的節(jié)點(diǎn)n，同時，同

25、時將節(jié)點(diǎn)將節(jié)點(diǎn)n移至移至CLOSE表表o 一般圖搜索算法劃分為二個階段：一般圖搜索算法劃分為二個階段：n1、初始化、初始化 n2、搜索循環(huán)、搜索循環(huán) 2022-3-1845o算法劃分為二個階段：算法劃分為二個階段：n1、初始化、初始化 o 建立建立只包含初始狀態(tài)節(jié)點(diǎn)只包含初始狀態(tài)節(jié)點(diǎn)s的搜索圖的搜索圖G:=so OPEN:=so CLOSE:= n2、搜索循環(huán)、搜索循環(huán)o MOVE-FIRST(OPEN)-取出取出OPEN表首的節(jié)點(diǎn)表首的節(jié)點(diǎn)n作為擴(kuò)展的節(jié)作為擴(kuò)展的節(jié)點(diǎn)，同時將其移到點(diǎn)，同時將其移到close表表 o 擴(kuò)展出擴(kuò)展出n的子節(jié)點(diǎn)的子節(jié)點(diǎn),插入插入搜索圖搜索圖G和和OPEN表表 o

26、適當(dāng)?shù)臉?biāo)記和修改指針適當(dāng)?shù)臉?biāo)記和修改指針o 排序排序OPEN表表n通過循環(huán)地執(zhí)行該算法，通過循環(huán)地執(zhí)行該算法，搜索圖搜索圖G會因不斷有新節(jié)點(diǎn)加入而逐會因不斷有新節(jié)點(diǎn)加入而逐步長大，直到搜索到目標(biāo)節(jié)點(diǎn)。步長大，直到搜索到目標(biāo)節(jié)點(diǎn)。 2022-3-1846初始布局初始布局目標(biāo)布局目標(biāo)布局移動數(shù)碼移動數(shù)碼2022-3-18475864273012022-3-18485864273012022-3-18495864273015864270315864073215864273102022-3-18505864273015864270315864073215864273102022-3-185158642

27、73015864270315864073215864273102022-3-18525864273015864270315864073215864273105064873215864703215860473212022-3-18535864273015864270315864073215864273105064873215864703215860473212022-3-18545864273015864270315864073215864273105064873215864703215860473215864273102022-3-1855586427301586427031586407321

28、5864273105064873215864703215860473215604873210564873212022-3-18565864273015864270315864073215864273105064873215864703215860473215604873210564873212022-3-18575864273015864270315864073215864273105064873215864703215860473215604873210564873212022-3-1858586427301586427031586407321586427310506487321586470

29、3215860473215604873210564873215674803212022-3-18595864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-3-18605864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-3-1861586427301586427031586407321586427310506487321586

30、4703215860473215604873210564873215674803215674813205674083212022-3-18625864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-3-186358642730158642703158640732158642731050648732158647032158604732156048732105648732156748032156748132056740832120

31、22-3-18645864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-3-18655864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-3-1866搜索過程中的指針修改搜索過程中的指針修改o 節(jié)點(diǎn)節(jié)點(diǎn)n擴(kuò)展后擴(kuò)展后的子節(jié)點(diǎn)分為的子節(jié)點(diǎn)分為3類類：n(i)

32、全新節(jié)點(diǎn)全新節(jié)點(diǎn)n(ii)已出現(xiàn)在已出現(xiàn)在OPEN表表中的節(jié)點(diǎn)中的節(jié)點(diǎn)n(iii)已出現(xiàn)的已出現(xiàn)的CLOSE表表中的節(jié)點(diǎn)中的節(jié)點(diǎn)o 指針標(biāo)記和修改的方法：指針標(biāo)記和修改的方法：n(i)類節(jié)點(diǎn)：加入類節(jié)點(diǎn)：加入OPEN表，建立從子節(jié)點(diǎn)到父節(jié)點(diǎn)表，建立從子節(jié)點(diǎn)到父節(jié)點(diǎn)n的指針的指針n(ii)類節(jié)點(diǎn)、類節(jié)點(diǎn)、 (iii)類節(jié)點(diǎn)類節(jié)點(diǎn)o 比較比較經(jīng)由經(jīng)由老父節(jié)點(diǎn)老父節(jié)點(diǎn)、新父節(jié)點(diǎn)新父節(jié)點(diǎn)n到達(dá)到達(dá)初始狀態(tài)節(jié)點(diǎn)初始狀態(tài)節(jié)點(diǎn)的的路徑路徑代價代價 o 經(jīng)由新父節(jié)點(diǎn)經(jīng)由新父節(jié)點(diǎn)n的代價比較小，則將原子節(jié)點(diǎn)指向老父節(jié)的代價比較小，則將原子節(jié)點(diǎn)指向老父節(jié)點(diǎn)的指針，修改為指向新父節(jié)點(diǎn)點(diǎn)的指針，修改為指向新父節(jié)點(diǎn)no

33、 (iii)類節(jié)點(diǎn)還得從類節(jié)點(diǎn)還得從CLOSE表中移出，重新加入表中移出，重新加入OPEN表。表。2022-3-1867Sn4ninjn1n2n3n31n32o 節(jié)點(diǎn)節(jié)點(diǎn)ni是當(dāng)前擴(kuò)展的節(jié)點(diǎn)；是當(dāng)前擴(kuò)展的節(jié)點(diǎn)；o 擴(kuò)展出擴(kuò)展出4個后續(xù)節(jié)點(diǎn)；個后續(xù)節(jié)點(diǎn)；o n1、n2是新節(jié)點(diǎn)是新節(jié)點(diǎn)，只需建只需建立指向父節(jié)點(diǎn)的指針，并加立指向父節(jié)點(diǎn)的指針，并加入入OPEN表表；2022-3-1868Sn4ninjn1n2n3n31n32o n4已經(jīng)存在于已經(jīng)存在于OPEN表，并表，并且已有父節(jié)點(diǎn)且已有父節(jié)點(diǎn)njnn4經(jīng)經(jīng)nj的路徑代價大的路徑代價大n取消取消n4指向指向nj的指針的指針n改為建立改為建立n4指向

34、新父節(jié)點(diǎn)指向新父節(jié)點(diǎn)ni的指針的指針o n3已經(jīng)存在于已經(jīng)存在于CLOSE表，表，并且已有父節(jié)點(diǎn)并且已有父節(jié)點(diǎn)njn需要做和需要做和n4同樣的比較和指同樣的比較和指針修改工作。并且要重新加入針修改工作。并且要重新加入open表。表。2022-3-1869（2）一般圖搜索算法）一般圖搜索算法o OPEN表中節(jié)點(diǎn)簡單的排序方式表中節(jié)點(diǎn)簡單的排序方式：n深度優(yōu)先深度優(yōu)先擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于置于OPEN表的前端表的前端，即，即OPEN表表作為作為棧棧，后進(jìn)先出后進(jìn)先出，使，使搜搜索優(yōu)先向縱深方向發(fā)展索優(yōu)先向縱深方向發(fā)展。2022-3-1870深度優(yōu)先深度優(yōu)先

35、實(shí)例實(shí)例2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 6123468911131416

36、18191 2 3 8 47 6 5目標(biāo)目標(biāo)571012151720212022-3-1871深度優(yōu)先搜索深度優(yōu)先搜索o 在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的( (最最深的深的) )節(jié)點(diǎn)，深度節(jié)點(diǎn)，深度 相等的節(jié)點(diǎn)可以任意排列。相等的節(jié)點(diǎn)可以任意排列。o “最晚產(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展最晚產(chǎn)生的節(jié)點(diǎn)最先擴(kuò)展” 起始節(jié)點(diǎn)深度為0 任何其他節(jié)點(diǎn)的深度等于其父輩節(jié)點(diǎn)深度加上1 :dn=dn-1+12022-3-1872深度優(yōu)先搜索深度優(yōu)先搜索很明顯這樣做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴(kuò)展下去，這當(dāng)然是

37、不允許的。為保證找到解，應(yīng)選擇適當(dāng)?shù)纳疃冉缦?，或者采取不斷加大深度界限的辦法，反復(fù)搜索，直到找到解。這種改進(jìn)的方法叫做迭代加深搜索。2022-3-1873Procedure Depth First SearchBegin把初始節(jié)點(diǎn)壓入棧，并設(shè)置棧頂指針；把初始節(jié)點(diǎn)壓入棧，并設(shè)置棧頂指針；While 棧不空棧不空 do Begin彈出棧頂元素；彈出棧頂元素； If 棧頂元素棧頂元素=goal=goal，成功返回并結(jié)束；，成功返回并結(jié)束； Else 以任意次序把棧頂元素的子女壓入棧中；以任意次序把棧頂元素的子女壓入棧中；End WhileEnd基于棧實(shí)現(xiàn)的深度優(yōu)先搜索算法： 2022-3-1874

38、o 初始節(jié)點(diǎn)放到棧中，棧指針指向棧的最上邊的元素。初始節(jié)點(diǎn)放到棧中，棧指針指向棧的最上邊的元素。o為了對該節(jié)點(diǎn)進(jìn)行檢測，需要從棧中彈出該節(jié)點(diǎn)，如果是目標(biāo)，該為了對該節(jié)點(diǎn)進(jìn)行檢測，需要從棧中彈出該節(jié)點(diǎn)，如果是目標(biāo)，該算法結(jié)束，否則把其子節(jié)點(diǎn)以任何順序壓入棧中。該過程直到棧變算法結(jié)束，否則把其子節(jié)點(diǎn)以任何順序壓入棧中。該過程直到棧變成為空。成為空。一棵樹的過程（下圖）。一棵樹的過程（下圖）。 2022-3-1875o 一般不能保證找到最優(yōu)解一般不能保證找到最優(yōu)解o 當(dāng)深度限制不合理時，當(dāng)深度限制不合理時，可能找不到解可能找不到解，可以，可以將算法改為將算法改為可變深度限制可變深度限制o 最壞情況時

39、，搜索空間等同于窮舉最壞情況時，搜索空間等同于窮舉o 是一個通用的與問題無關(guān)的方法是一個通用的與問題無關(guān)的方法2022-3-1876o 深度優(yōu)先搜索深度優(yōu)先搜索的的優(yōu)點(diǎn)優(yōu)點(diǎn)是比寬度優(yōu)先搜索算是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜法需要較少的空間，該算法只需要保存搜索樹的一部分，它由當(dāng)前正在搜索的路徑索樹的一部分，它由當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點(diǎn)標(biāo)志所和該路徑上還沒有完全展開的節(jié)點(diǎn)標(biāo)志所組成。組成。o 深度優(yōu)先搜索的存儲器要求是深度約束的深度優(yōu)先搜索的存儲器要求是深度約束的線性函數(shù)。線性函數(shù)。 2022-3-1877 既不是完備的，也不是最優(yōu)的。既不是完備的，

40、也不是最優(yōu)的。 主要問題是可能搜索到了錯誤的路徑上。很多主要問題是可能搜索到了錯誤的路徑上。很多問題可能具有很深甚至是無限的搜索樹，如果不幸問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜索下去，而不會回到正確的路徑上。這樣一來對于索下去，而不會回到正確的路徑上。這樣一來對于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。很長而且不是最優(yōu)的答案。2022-3-1

41、878（2）一般圖搜索算法）一般圖搜索算法o OPEN表中節(jié)點(diǎn)簡單的排序方式表中節(jié)點(diǎn)簡單的排序方式：n深度優(yōu)先深度優(yōu)先擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于置于OPEN表的前端表的前端，即，即OPEN表表作為作為棧棧，后進(jìn)先出后進(jìn)先出，使，使搜搜索優(yōu)先向縱深方向發(fā)展索優(yōu)先向縱深方向發(fā)展。n寬度優(yōu)先寬度優(yōu)先擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是擴(kuò)展當(dāng)前節(jié)點(diǎn)后生成的子節(jié)點(diǎn)總是置于置于OPEN表的后端表的后端，即，即OPEN表表作為作為隊(duì)列隊(duì)列，先進(jìn)先出先進(jìn)先出，使，使搜索優(yōu)先向橫向方向發(fā)展搜索優(yōu)先向橫向方向發(fā)展。2022-3-1879寬度優(yōu)先寬度優(yōu)先實(shí)例實(shí)例2 31 8 47 6

42、 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標(biāo)目標(biāo)82 3 41 8 7 6 54910111213141516172022-3-1880寬度優(yōu)先搜索寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點(diǎn)的程度依次擴(kuò)展節(jié)點(diǎn)的，那么這種搜

43、索就叫做寬度優(yōu)先搜索。這種搜索是逐層進(jìn)行的，在對下一層的任意節(jié)點(diǎn)進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點(diǎn)?！跋犬a(chǎn)生的節(jié)點(diǎn)先擴(kuò)展”2022-3-1881Procedure Breadth-first-searchProcedure Breadth-first-searchBeginBegin把初始節(jié)點(diǎn)放入隊(duì)列；把初始節(jié)點(diǎn)放入隊(duì)列； RepeatRepeat取得隊(duì)列最前面的元素為取得隊(duì)列最前面的元素為current;current; If current=goal If current=goal 成功返回并結(jié)束；成功返回并結(jié)束； Else doElse do Begin Begin 如果如果curr

44、entcurrent有子女，則有子女，則currentcurrent的子女的子女 以任意次序添加到隊(duì)列的尾部；以任意次序添加到隊(duì)列的尾部； EndEnd Until Until 隊(duì)列為空隊(duì)列為空 EndEnd采用隊(duì)列結(jié)構(gòu)，寬度優(yōu)先算法可以表示如下：2022-3-1882o 寬度優(yōu)先搜索算法原理：寬度優(yōu)先搜索算法原理：o 如果當(dāng)前的節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，則把當(dāng)點(diǎn)如果當(dāng)前的節(jié)點(diǎn)不是目標(biāo)節(jié)點(diǎn)，則把當(dāng)點(diǎn)節(jié)點(diǎn)的子孫以任意順序增加到隊(duì)列的后面，節(jié)點(diǎn)的子孫以任意順序增加到隊(duì)列的后面，并把隊(duì)列的前端元素定義為并把隊(duì)列的前端元素定義為currentcurrent。o 如果目標(biāo)發(fā)現(xiàn)，則算法終止。如果目標(biāo)發(fā)現(xiàn)，則算法終

45、止。 2022-3-1883寬度優(yōu)先搜索的性質(zhì)寬度優(yōu)先搜索的性質(zhì)o 當(dāng)問題有解時，當(dāng)問題有解時，一定一定能找到解能找到解o 當(dāng)問題為單位代價時，且問題有解時，當(dāng)問題為單位代價時，且問題有解時，一定一定能找到最優(yōu)解能找到最優(yōu)解o 方法與問題無關(guān)，具有通用性方法與問題無關(guān)，具有通用性o 效率較低效率較低o 屬于圖搜索方法屬于圖搜索方法2022-3-1884o 寬度優(yōu)先搜索寬度優(yōu)先搜索是一種盲目搜索，是一種盲目搜索，時間和空間復(fù)雜度都比較高，當(dāng)時間和空間復(fù)雜度都比較高，當(dāng)目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時會目標(biāo)節(jié)點(diǎn)距離初始節(jié)點(diǎn)較遠(yuǎn)時會產(chǎn)生許多無用的節(jié)點(diǎn)，搜索效率產(chǎn)生許多無用的節(jié)點(diǎn)，搜索效率低。低。o 寬度優(yōu)

46、先搜索中，時間需求是一寬度優(yōu)先搜索中，時間需求是一個很大的問題，特別是當(dāng)搜索的個很大的問題，特別是當(dāng)搜索的深度比較大時，尤為嚴(yán)重，但是深度比較大時，尤為嚴(yán)重，但是空間需求是比執(zhí)行時間更嚴(yán)重的空間需求是比執(zhí)行時間更嚴(yán)重的問題。問題。 寬度優(yōu)先搜索優(yōu)點(diǎn)：目標(biāo)節(jié)點(diǎn)如果存在，用寬度優(yōu)先搜索算法總可以找到該目標(biāo)節(jié)點(diǎn)，而且是最?。醋疃搪窂剑┑墓?jié)點(diǎn)。寬度優(yōu)先搜索的優(yōu)點(diǎn)和缺點(diǎn)寬度優(yōu)先搜索的優(yōu)點(diǎn)和缺點(diǎn)2022-3-1885總結(jié)總結(jié) o 適用場合適用場合 深度優(yōu)先深度優(yōu)先當(dāng)一個問題有多個解答或多條解答路徑，當(dāng)一個問題有多個解答或多條解答路徑，且只須找到其中一個時；往往應(yīng)對搜索深度加以限制。且只須找到其中一個時；

47、往往應(yīng)對搜索深度加以限制。 寬度優(yōu)先寬度優(yōu)先確保搜索到最短的解答路徑。確保搜索到最短的解答路徑。o 共同優(yōu)缺點(diǎn)：共同優(yōu)缺點(diǎn)： 可直接應(yīng)用一般圖搜索算法實(shí)現(xiàn)，不需要設(shè)計(jì)特別的可直接應(yīng)用一般圖搜索算法實(shí)現(xiàn)，不需要設(shè)計(jì)特別的節(jié)點(diǎn)排序方法，從而簡單易行，適合于許多復(fù)雜度不高的問節(jié)點(diǎn)排序方法，從而簡單易行，適合于許多復(fù)雜度不高的問題求解任務(wù)。題求解任務(wù)。 節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導(dǎo)節(jié)點(diǎn)排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導(dǎo)排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解答，所以也稱為答，所以也稱為盲目搜索盲目搜索。 2022

48、-3-1886有界深度搜索和迭代加深搜索有界深度搜索和迭代加深搜索 有界深度優(yōu)先搜索有界深度優(yōu)先搜索過程總體上按深度優(yōu)先算過程總體上按深度優(yōu)先算法方法進(jìn)行，但對搜索深度需要給出一個深法方法進(jìn)行，但對搜索深度需要給出一個深度限制度限制dmdm，當(dāng)深度達(dá)到了，當(dāng)深度達(dá)到了dmdm的時候，如果還的時候，如果還沒有找到解答，就停止對該分支的搜索，換沒有找到解答，就停止對該分支的搜索，換到另外一個分支進(jìn)行搜索。到另外一個分支進(jìn)行搜索。2022-3-1887策略說明策略說明: : o （1 1）深度限制深度限制dmdm很重要很重要。當(dāng)問題有解，且當(dāng)問題有解，且解的路徑長度小于或等于解的路徑長度小于或等于d

49、mdm時，則搜索過時，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。一樣這并不能保證最先找到的是最優(yōu)解。o 但是當(dāng)?shù)钱?dāng)dmdm取得太小，解的路徑長度大于取得太小，解的路徑長度大于dmdm時，則搜索過程中就找不到解，即這時搜時，則搜索過程中就找不到解，即這時搜索過程甚至是不完備的。索過程甚至是不完備的。2022-3-1888（2 2）深度限制深度限制dmdm不能太大不能太大。當(dāng)。當(dāng)dmdm太大時，搜太大時，搜索過程會產(chǎn)生過多的無用節(jié)點(diǎn)，既浪費(fèi)了計(jì)索過程會產(chǎn)生過多的無用節(jié)點(diǎn)，既浪費(fèi)了計(jì)算機(jī)資源，又降低了搜索效率。算機(jī)資源，又降

50、低了搜索效率。（3 3）有界深度搜索的主要問題是）有界深度搜索的主要問題是深度限制值深度限制值dmdm的選取的選取。 2022-3-1889改進(jìn)方法改進(jìn)方法： （迭代加深搜索）（迭代加深搜索） 先任意給定一個較小的數(shù)作為先任意給定一個較小的數(shù)作為dmdm，然后，然后按有界深度算法搜索，若在此深度限制按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限制內(nèi)找到了解，則算法結(jié)束；如在此限制內(nèi)沒有找到問題的解，則增大深度限制內(nèi)沒有找到問題的解，則增大深度限制dmdm，繼續(xù)搜索。，繼續(xù)搜索。2022-3-1890o 迭代加深搜索迭代加深搜索，試圖嘗試所有可能的深度限制：，試圖嘗試所有可能

51、的深度限制：n首先深度為首先深度為0 0，n然后深度為然后深度為1 1，n然后為然后為2 2，等等。，等等。o 如果初始深度為如果初始深度為0 0，則該算法只生成根節(jié)點(diǎn)，并，則該算法只生成根節(jié)點(diǎn)，并檢測它。檢測它。o 如果根節(jié)點(diǎn)不是目標(biāo)，則深度加如果根節(jié)點(diǎn)不是目標(biāo)，則深度加1 1，通過典型的，通過典型的深度優(yōu)先算法，生成深度為深度優(yōu)先算法，生成深度為1 1的樹。的樹。o 當(dāng)深度限制為當(dāng)深度限制為m m時，樹的深度為時，樹的深度為m m。 2022-3-1891o 迭代加深搜索看起來會很浪費(fèi)，因?yàn)楹芏喙?jié)點(diǎn)迭代加深搜索看起來會很浪費(fèi)，因?yàn)楹芏喙?jié)點(diǎn)都可能擴(kuò)展多次。都可能擴(kuò)展多次。o 然而對于很多問題

52、，這種多次的擴(kuò)展負(fù)擔(dān)實(shí)際然而對于很多問題，這種多次的擴(kuò)展負(fù)擔(dān)實(shí)際上很小，直覺上可以想象，如果一棵樹的分支上很小，直覺上可以想象，如果一棵樹的分支系數(shù)很大，幾乎所有的節(jié)點(diǎn)都在最底層上，則系數(shù)很大，幾乎所有的節(jié)點(diǎn)都在最底層上，則對于上面各層節(jié)點(diǎn)擴(kuò)展多次對整個系統(tǒng)來說影對于上面各層節(jié)點(diǎn)擴(kuò)展多次對整個系統(tǒng)來說影響不是很大。響不是很大。 2022-3-1892搜索最優(yōu)策略的比較搜索最優(yōu)策略的比較 o 表注：表注：b是分支系數(shù)，是分支系數(shù)，d是解答的深度，是解答的深度，m是搜索樹的是搜索樹的最大深度，最大深度，l是深度限制。是深度限制。2022-3-1893o 寬度優(yōu)先搜索、深度優(yōu)先搜索和迭代加深搜寬度優(yōu)

53、先搜索、深度優(yōu)先搜索和迭代加深搜索都可以用于生成和測試算法。索都可以用于生成和測試算法。o 寬度優(yōu)先搜索寬度優(yōu)先搜索需要指數(shù)數(shù)量的空間，深度優(yōu)需要指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復(fù)雜度和最大搜索深度呈線性先搜索的空間復(fù)雜度和最大搜索深度呈線性關(guān)系。關(guān)系。 2022-3-1894o 迭代加深搜索迭代加深搜索對一棵深度受控的樹采用深度對一棵深度受控的樹采用深度優(yōu)先的搜索。它結(jié)合了寬度優(yōu)先和深度優(yōu)先優(yōu)先的搜索。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點(diǎn)。搜索的優(yōu)點(diǎn)。o 和寬度優(yōu)先搜索一樣，它是最優(yōu)的，也是完和寬度優(yōu)先搜索一樣，它是最優(yōu)的，也是完備的。但對空間要求和深度優(yōu)先搜索一樣是備的。但對空間要求和深

54、度優(yōu)先搜索一樣是適中的。適中的。 2022-3-1895一般圖搜索算法一般圖搜索算法o 常用的簡單方式：常用的簡單方式：n 深度優(yōu)先深度優(yōu)先n 寬度優(yōu)先寬度優(yōu)先n 【缺點(diǎn)：節(jié)點(diǎn)排序的盲目性缺點(diǎn)：節(jié)點(diǎn)排序的盲目性】o 在白白在白白搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)搜索了大量無關(guān)的狀態(tài)節(jié)點(diǎn)后才碰到解后才碰到解答，答，效率低效率低o 提高提高一般圖搜索一般圖搜索效率效率的關(guān)鍵的關(guān)鍵n 優(yōu)化優(yōu)化OPEN表中節(jié)點(diǎn)的排序方式表中節(jié)點(diǎn)的排序方式盲目搜索盲目搜索2022-3-1896586427031586407321586427310506487321586470321586047321560487321056487

55、321567480321567481320567408321586427301125634最理想情況：最理想情況：每次排序后每次排序后OPEN表表表首元素表首元素n n總在解答路徑上總在解答路徑上2022-3-1897o 啟發(fā)式知識啟發(fā)式知識指導(dǎo)指導(dǎo)OPEN表排序表排序的的一般圖搜索一般圖搜索：n 全局排序全局排序?qū)PEN表中的表中的所有節(jié)點(diǎn)排序所有節(jié)點(diǎn)排序，使使最有希望最有希望的節(jié)點(diǎn)排在表首。的節(jié)點(diǎn)排在表首。o A算法，算法， A*算法（掌握?。┧惴ǎㄕ莆眨。﹏ 局部排序局部排序僅對僅對新新擴(kuò)展出來的子節(jié)點(diǎn)排序擴(kuò)展出來的子節(jié)點(diǎn)排序，使這些使這些新新節(jié)點(diǎn)中節(jié)點(diǎn)中最有希望最有希望者能優(yōu)先取出

56、考察者能優(yōu)先取出考察和擴(kuò)展；和擴(kuò)展；o 爬山法（了解，爬山法（了解，對對深度優(yōu)先法深度優(yōu)先法的改進(jìn)的改進(jìn)）；）；2022-3-1898o 【基本思想基本思想】n 設(shè)計(jì)體現(xiàn)啟發(fā)式知識的設(shè)計(jì)體現(xiàn)啟發(fā)式知識的評價函數(shù)評價函數(shù)f(n)；n 指導(dǎo)指導(dǎo)一般圖搜索一般圖搜索中中OPEN表待擴(kuò)展節(jié)點(diǎn)的排序表待擴(kuò)展節(jié)點(diǎn)的排序：o 【評價函數(shù)評價函數(shù)f(n)=g(n)+h(n) （掌握）（掌握） 】n n-搜索圖搜索圖G中中的節(jié)點(diǎn)的節(jié)點(diǎn)；n f(n)- G中從初始狀態(tài)節(jié)點(diǎn)中從初始狀態(tài)節(jié)點(diǎn)s，經(jīng)由節(jié)點(diǎn)，經(jīng)由節(jié)點(diǎn)n到達(dá)目到達(dá)目標(biāo)節(jié)點(diǎn)標(biāo)節(jié)點(diǎn)ng，估計(jì)估計(jì)的的最小路徑代價最小路徑代價；n g(n)- G中從中從s到到n，

57、目前實(shí)際目前實(shí)際的路徑代價；的路徑代價；n h(n)-從從n到到ng，估計(jì)估計(jì)的最小路徑代價；的最小路徑代價；2022-3-1899Snng搜索圖搜索圖G Gh(n): n-ng的估計(jì)最小路徑代價的估計(jì)最小路徑代價 g(n):s-n的實(shí)際路徑代價的實(shí)際路徑代價 f(n):s-n-ng的的估計(jì)估計(jì)最小路徑代價最小路徑代價 2022-3-18100o 【評價函數(shù)評價函數(shù)f(n)=g(n)+h(n) （掌握）（掌握） 】n n-搜索圖搜索圖G中中的節(jié)點(diǎn)的節(jié)點(diǎn)；n f(n)- G中從中從s經(jīng)經(jīng)n到到ng，估計(jì)估計(jì)的的最小路徑代價最小路徑代價；n g(n)- G中從中從s到到n，目前實(shí)際目前實(shí)際的路徑代

58、價；的路徑代價；n h(n)-從從n到到ng，估計(jì)估計(jì)的的最小路徑代價最小路徑代價； o h(n)值值-依賴于依賴于啟發(fā)式知識啟發(fā)式知識加以計(jì)算；加以計(jì)算；o h(n)稱為稱為啟發(fā)式函數(shù)啟發(fā)式函數(shù)（掌握意義！掌握意義?。?。o 如何用評價函數(shù)來實(shí)現(xiàn)如何用評價函數(shù)來實(shí)現(xiàn)A算法算法? （ 掌握！掌握?。?2022-3-18101oA算法算法的設(shè)計(jì)與的設(shè)計(jì)與一般圖搜索一般圖搜索相同，劃分為二個階段：相同，劃分為二個階段：n1、初始化、初始化 o 建立只包含初始狀態(tài)節(jié)點(diǎn)建立只包含初始狀態(tài)節(jié)點(diǎn)s的搜索圖的搜索圖G:=so OPEN:=so CLOSE:= n2、搜索循環(huán)、搜索循環(huán)o MOVE-FIRST(

59、OPEN)-取出取出OPEN表首表首的節(jié)點(diǎn)的節(jié)點(diǎn)n o 擴(kuò)展出擴(kuò)展出n的子節(jié)點(diǎn)的子節(jié)點(diǎn),插入搜索圖插入搜索圖G和和OPEN表表 o 適當(dāng)?shù)臉?biāo)記和修改指針（適當(dāng)?shù)臉?biāo)記和修改指針（子節(jié)點(diǎn)子節(jié)點(diǎn)父節(jié)點(diǎn)父節(jié)點(diǎn)）o 排序排序OPEN表（表（評價函數(shù)評價函數(shù)f(n)的值排序）的值排序）n通過循環(huán)地執(zhí)行該算法，搜索圖會因不斷有新節(jié)點(diǎn)加入而逐步通過循環(huán)地執(zhí)行該算法，搜索圖會因不斷有新節(jié)點(diǎn)加入而逐步長大，直到搜索到目標(biāo)節(jié)點(diǎn)。長大，直到搜索到目標(biāo)節(jié)點(diǎn)。2022-3-18102o算法算法A的設(shè)計(jì)與一般圖搜索類似，劃分為二個階段：的設(shè)計(jì)與一般圖搜索類似，劃分為二個階段：n1、初始化、初始化 n2、搜索循環(huán)、搜索循環(huán)o

60、 MOVE-FIRST(OPEN)-取出取出OPEN表首的節(jié)點(diǎn)表首的節(jié)點(diǎn)n o 擴(kuò)展出擴(kuò)展出n的子節(jié)點(diǎn)的子節(jié)點(diǎn),插入搜索圖插入搜索圖G和和OPEN表表 n 對每個子節(jié)點(diǎn)對每個子節(jié)點(diǎn)ni,計(jì)算計(jì)算f(n,ni)=g(n,ni)+h(ni)o 適當(dāng)?shù)臉?biāo)記和修改指針適當(dāng)?shù)臉?biāo)記和修改指針（子節(jié)點(diǎn)子節(jié)點(diǎn)父節(jié)點(diǎn)父節(jié)點(diǎn)）o 排序排序OPEN表表（評價函數(shù)（評價函數(shù)f(n)的值排序）的值排序）2022-3-18103o 擴(kuò)展出擴(kuò)展出n的子節(jié)點(diǎn)的子節(jié)點(diǎn),插入搜索圖插入搜索圖G和和OPEN表表 n 對每個子節(jié)點(diǎn)對每個子節(jié)點(diǎn)ni,計(jì)算計(jì)算f(n,ni)=g(n,ni)+h(ni)o 適當(dāng)?shù)臉?biāo)記和修改指針適當(dāng)?shù)臉?biāo)記和