人工智能第三章_搜索策略-

1、2022-3-151第第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-152第第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-153 o對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達(dá)到所希望目標(biāo)的動作序列，并使其所付出的代價最小、性能最好。o基于給定的問題，問題求解的第一步是目標(biāo)的表示。o搜索就是找到智能系統(tǒng)的動作序列的過程。 2022-3-154o 搜索算法的輸入是給定的問題，輸出時表示為動作序列的方案。o 一旦有了方案，就可以執(zhí)行該方案所給出的動作了。（執(zhí)行階段）o 因此，求解問題包括：

3、n目標(biāo)表示目標(biāo)表示n搜索搜索n執(zhí)行執(zhí)行2022-3-155（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-156o 和通常的搜索空間不同，人工智能中大多數(shù)問題的狀狀態(tài)空間在問題求解之前不是全部知道

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

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

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

7、度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點的順序一般都是固定的，即一旦搜索空間給定，節(jié)點遍歷的順序就固定了。這種類型的遍歷稱為“確定性”的，也就是盲目搜索。o 對于啟發(fā)式搜索，在計算每個節(jié)點的參數(shù)之前無法確定先選擇哪個節(jié)點擴(kuò)展，這種搜索一般也稱為非確定的。 2022-3-1512o 完備性：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-1513有許多智力問題有許多智力問題( (如梵塔問

8、題、旅行商問題、八皇如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等后問題、農(nóng)夫過河問題等) )和實際問題（如路徑規(guī)和實際問題（如路徑規(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-1514nS問題求解（即搜索）過程中所有問題求解（即搜索）過程中所有可能到達(dá)可能到達(dá)的的合法狀態(tài)合法狀態(tài)構(gòu)成的集合；構(gòu)成的集合；nO操作算子操作算子的集合，的集合，

9、操作算子的執(zhí)行會導(dǎo)致問題狀態(tài)的操作算子的執(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-1515狀態(tài)狀態(tài)表示狀態(tài)的變遷表示狀態(tài)的變遷操作算子操作算子問題的狀態(tài)空間問題的狀態(tài)空間是一個表示該問題的全部可能狀態(tài)是一個表示該問題的全部可能狀態(tài)及其變遷的及其變遷的

10、有向圖有向圖。 o 節(jié)點節(jié)點n 狀態(tài)狀態(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-1516S1S2S3S4S5S6S7S8S9S0Sg2022-3-15172022-3-1518 例例2:在一個在一個33的方格棋盤上放置著的方格棋盤上放置著1,2,3,4,5,6,7,8八個數(shù)碼，每個數(shù)碼占一格，且有一個空格。這些八個數(shù)碼

11、，每個數(shù)碼占一格，且有一個空格。這些數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。的數(shù)碼方可移入空格。現(xiàn)在的現(xiàn)在的問題問題是：對于指定的是：對于指定的初始棋局初始棋局和和目標(biāo)棋局目標(biāo)棋局，給出給出數(shù)碼的移動序列數(shù)碼的移動序列。該問題稱為。該問題稱為八數(shù)碼問題八數(shù)碼問題。 56741382初始棋局初始棋局56748321目標(biāo)棋局目標(biāo)棋局移動數(shù)碼移動數(shù)碼2022-3-15192 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

12、 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 61 2 3 8 47 6 52022-3-15202022-3-1521 例例3:錢幣翻轉(zhuǎn)問題。設(shè)有錢幣翻轉(zhuǎn)問題。設(shè)有3個錢幣，其初始狀態(tài)個錢幣，其初始狀態(tài)為為(正、反、正正、反、正),欲得的目標(biāo)狀態(tài)為

13、欲得的目標(biāo)狀態(tài)為(正、正、正正、正、正)或或(反、反、反反、反、反)。問題是允許每次只能且必須翻。問題是允許每次只能且必須翻轉(zhuǎn)一個錢幣，連翻三次。問能否達(dá)到目標(biāo)狀態(tài)。轉(zhuǎn)一個錢幣，連翻三次。問能否達(dá)到目標(biāo)狀態(tài)。 分析：通過引入一個分析：通過引入一個三維變量三維變量將問題表示出來。設(shè)將問題表示出來。設(shè)三維變量為：三維變量為：Q=qQ=q1 1,q,q2 2,q,q3 3 ，式中，式中q qi i (i=1,2,3)=1(i=1,2,3)=1表表示錢幣為正面，示錢幣為正面，q qi i (i=1,2,3)=0 (i=1,2,3)=0表示錢幣為反面。表示錢幣為反面。則三個錢幣可能出現(xiàn)的狀態(tài)有則三個錢幣

14、可能出現(xiàn)的狀態(tài)有8 8種組合：種組合：Q Q0 0=(0,0,0),Q=(0,0,0),Q1 1=(0,0,1),Q=(0,0,1),Q2 2=(0,1,0),Q=(0,1,0),Q3 3=(0,1,1),Q=(0,1,1),Q4 4= =(1,0,0),Q(1,0,0),Q5 5=(1,0,1), Q=(1,0,1), Q6 6=(1,1,0), Q=(1,1,0), Q7 7=(1,1,1)=(1,1,1)。即初始狀態(tài)為即初始狀態(tài)為Q Q5 5，目標(biāo)狀態(tài)為目標(biāo)狀態(tài)為Q Q0 0或或Q Q7 7，要求步數(shù)為要求步數(shù)為3 3。2022-3-1522錢幣問題的狀態(tài)空間圖錢幣問題的狀態(tài)空間圖202

15、2-3-1523：o 1)船上人數(shù)不得超過載重限量，設(shè)為船上人數(shù)不得超過載重限量，設(shè)為K個人；個人； o 2)任何時刻（包括兩岸、船上）野人數(shù)目不得超任何時刻（包括兩岸、船上）野人數(shù)目不得超過傳教士；過傳教士； o 3)允許在河的某一岸或者在船上只有野人而沒有允許在河的某一岸或者在船上只有野人而沒有傳教士；傳教士；2022-3-15242022-3-1525可能到達(dá)可能到達(dá)的的合法狀態(tài)合法狀態(tài)：442=32 o (0,0,1),(0,3,0),(3,0,1),(3,3,0)2022-3-1526(2)狀態(tài)空間表示的經(jīng)典例子狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題傳教士和野人問題”o 定義定義2

16、類類操作算子操作算子：n L(x,y)指示從指示從左岸左岸到到右岸右岸的劃船操作的劃船操作 n R(x,y)指示從指示從右岸右岸到到左岸左岸的劃船操作的劃船操作o x + y K=2(船的載重限制船的載重限制)；o x和和y取值的可能組合只有取值的可能組合只有5個個o 10，20，11，01，02 o ( 允許在船上只有野人而沒有傳教士允許在船上只有野人而沒有傳教士 )n 共有共有10個操作算子個操作算子2022-3-15272022-3-1528 2022-3-1529 2022-3-1530課堂練習(xí)課堂練習(xí)o 有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜過河（從有一農(nóng)夫帶一只狐貍、一只小羊和一籃菜

17、過河（從左岸到右岸）。假設(shè)船太小，農(nóng)夫每次只能帶一樣左岸到右岸）。假設(shè)船太小，農(nóng)夫每次只能帶一樣?xùn)|西過河；考慮到安全，無農(nóng)夫看管時，狐貍和小東西過河；考慮到安全，無農(nóng)夫看管時，狐貍和小羊不能在一起，小羊和那籃菜也不能在一起。請為羊不能在一起，小羊和那籃菜也不能在一起。請為該問題的解決設(shè)計狀態(tài)空間，并畫出狀態(tài)空間圖。該問題的解決設(shè)計狀態(tài)空間，并畫出狀態(tài)空間圖。2022-3-1531解析解析o 以變量以變量m m、f f、s s、v v分別指示農(nóng)夫、狐貍、小羊、菜分別指示農(nóng)夫、狐貍、小羊、菜, ,且每個且每個變量只可取值變量只可取值1(1(表示在左岸表示在左岸) )或或0(0(表示在右岸表示在右岸

18、) )。問題狀態(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á)右岸。從而, ,問題求解任務(wù)可描述為問題求解任務(wù)可描述為 (1, 1, 1, 1) -(0, 0, 0, 0)(1, 1, 1, 1) -(0, 0, 0, 0)o 思考：為什么不把船的狀態(tài)放到狀態(tài)空間中去？思考：為什么不把船的狀態(tài)放到狀態(tài)空間中去？o 由于問題簡單由于問題簡單, ,狀態(tài)空間中可能的狀態(tài)總數(shù)為狀態(tài)空間中可能的狀態(tài)總數(shù)為2 22 22 22 = 2 = 16,16,由于要遵從安全限制由于要遵從安全限制

19、, ,合法的狀態(tài)只有合法的狀態(tài)只有( (除初、目狀態(tài)外除初、目狀態(tài)外):): 1110 1110，11011101，10111011，10101010，01010101，00010001，00100010，01000100；不合法狀態(tài)有不合法狀態(tài)有: 0111,1000,1100,0011,0110,1001: 0111,1000,1100,0011,0110,1001o 設(shè)計二類操作算子設(shè)計二類操作算子:Lx:Lx、Rx,xRx,x為為m m、f f、s s、v v時分別指示農(nóng)夫時分別指示農(nóng)夫獨(dú)自獨(dú)自, ,帶狐貍帶狐貍, ,帶小羊帶小羊, ,帶菜過河；狀態(tài)空間圖如下所示帶菜過河；狀態(tài)空間圖如

20、下所示. .由于由于LxLx和和RxRx是互逆操作是互逆操作, ,故而解答路徑可有無數(shù)條故而解答路徑可有無數(shù)條, ,但最近的只有但最近的只有二條二條; ;都是都是7 7個操作步個操作步. . 2022-3-1532解析解析: :四元組四元組(m(m、f f、s s、v)v)代表（農(nóng)夫、狐貍、小羊、菜）代表（農(nóng)夫、狐貍、小羊、菜）2022-3-1533(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)集合，問

21、題的目標(biāo)狀態(tài)集合，G S。o 搜索引擎搜索引擎E可以設(shè)計為可以設(shè)計為實現(xiàn)任何搜索算法實現(xiàn)任何搜索算法的控制系統(tǒng)。的控制系統(tǒng)。o 基本思想基本思想通過搜索引擎通過搜索引擎E尋找一個尋找一個操作算子的調(diào)用序操作算子的調(diào)用序列列，使問題從初始狀態(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-1534o 或圖（一般圖）或圖（一般圖）n 一個狀態(tài)一個狀態(tài)可以可以有多個可供選擇有多個可供選擇的操作算子；的操作算子；n 操作算子間的選擇是一種操作算子間的選擇是

22、一種“或或”的關(guān)系的關(guān)系; ;n 這樣的有向圖稱為這樣的有向圖稱為或圖。或圖。2022-3-1535(3)(3)狀態(tài)空間的搜索狀態(tài)空間的搜索o 或圖（一般圖）或圖（一般圖）n 一個狀態(tài)可以有多個可供選擇的操作算子；一個狀態(tài)可以有多個可供選擇的操作算子；n 操作算子間的選擇是一種操作算子間的選擇是一種“或或”的關(guān)系，的關(guān)系，這樣的有這樣的有向圖稱為向圖稱為或圖?；驁D。o 狀態(tài)空間狀態(tài)空間一般都表示為一般都表示為或圖（一般圖）或圖（一般圖）o 搜索圖搜索圖在在搜索解答路徑搜索解答路徑的過程中畫出搜索時涉及到的過程中畫出搜索時涉及到的節(jié)點和弧線，構(gòu)成所謂的的節(jié)點和弧線，構(gòu)成所謂的搜索圖搜索圖。狀態(tài)空

23、間搜索狀態(tài)空間搜索一般圖搜索一般圖搜索2022-3-1536(3)狀態(tài)空間的搜索狀態(tài)空間的搜索o 狀態(tài)空間狀態(tài)空間、搜索圖搜索圖和和解答路徑解答路徑之間的關(guān)系之間的關(guān)系S0Sg2022-3-1537 初始布局初始布局目標(biāo)布局目標(biāo)布局移動數(shù)碼移動數(shù)碼2022-3-1538 2022-3-1539初始布局初始布局目標(biāo)布局目標(biāo)布局移動數(shù)碼移動數(shù)碼586427301567408321 2022-3-1540(4)一般圖搜索例子一般圖搜索例子八數(shù)碼游戲八數(shù)碼游戲 o 第二步：制定操作算子集第二步：制定操作算子集n直觀方法直觀方法為每個棋牌制定一套可能的走步：左、上、右、為每個棋牌制定一套可能的走步：左、

24、上、右、下四種移動。下四種移動。o 需要需要32個操作算子個操作算子n簡易方法簡易方法僅為空格制定這僅為空格制定這4種走步。種走步。o 僅需僅需4個操作算子個操作算子o 第三步：設(shè)計搜索引擎第三步：設(shè)計搜索引擎 n問題狀態(tài)空間的大小問題狀態(tài)空間的大小與與問題涉及的元素問題涉及的元素個數(shù)是程個數(shù)是程指數(shù)級指數(shù)級爆炸式增長爆炸式增長（即，（即，組合爆炸問題組合爆炸問題）o 如，棋盤布局（問題狀態(tài)）總共有如，棋盤布局（問題狀態(tài)）總共有9!=362880個個 n研究焦點研究焦點是是解決組合爆炸問題解決組合爆炸問題，通過壓縮搜索空間通過壓縮搜索空間，提提高搜索效率高搜索效率。 2022-3-1541狀態(tài)

25、空間狀態(tài)空間、搜索圖搜索圖和和解答路徑解答路徑之間的關(guān)系之間的關(guān)系S0Sg2022-3-1542 （1）搜索術(shù)語）搜索術(shù)語o 1、節(jié)點深度、節(jié)點深度n 根節(jié)點根節(jié)點指示指示初始狀態(tài)初始狀態(tài)，令其深度為，令其深度為0；n 搜索圖中的其他節(jié)點的搜索圖中的其他節(jié)點的深度深度dn就可以遞歸地定義為就可以遞歸地定義為其其父節(jié)點深度父節(jié)點深度dn-1加加1：dn= dn-1+1。 根節(jié)點深度根節(jié)點深度=0=0搜索圖搜索圖2022-3-1543 （1）搜索術(shù)語）搜索術(shù)語o 2、節(jié)點擴(kuò)展、節(jié)點擴(kuò)展n應(yīng)用應(yīng)用操作算子操作算子將將上一狀態(tài)上一狀態(tài)（節(jié)點（節(jié)點ni）變遷到）變遷到下一狀態(tài)下一狀態(tài)（節(jié)點（節(jié)點nj）n

26、節(jié)點節(jié)點ni稱為稱為被擴(kuò)展節(jié)點被擴(kuò)展節(jié)點（父節(jié)點）（父節(jié)點）n節(jié)點節(jié)點nj稱為稱為ni的的子節(jié)點子節(jié)點2022-3-1544o4、路徑代價、路徑代價相鄰節(jié)點相鄰節(jié)點ni和和ni+1間的間的路徑代價路徑代價記為記為C(ni, ni+1) n通常令通常令任意相鄰節(jié)點任意相鄰節(jié)點間的路徑代價相同間的路徑代價相同，并以路徑長度并以路徑長度1 1指示。指示。n即即C(ni, ni+1)=1 。節(jié)點節(jié)點n ni i節(jié)點節(jié)點ni+1節(jié)點節(jié)點nj2022-3-1545 C(nk,ng) C(ni,nk) C(ni,ng) 2022-3-1546o 符號說明：符號說明：ns-初始狀態(tài)節(jié)點初始狀態(tài)節(jié)點nG-搜索圖

27、搜索圖nOPEN-存放存放待擴(kuò)展節(jié)點待擴(kuò)展節(jié)點的表的表nCLOSE-存放存放已被擴(kuò)展的節(jié)點已被擴(kuò)展的節(jié)點的表的表nMOVE-FIRST(OPEN)-取取OPEN表首的節(jié)點表首的節(jié)點作為作為當(dāng)前要被擴(kuò)展當(dāng)前要被擴(kuò)展的節(jié)點的節(jié)點n，同時，同時將節(jié)點將節(jié)點n移至移至CLOSE表表o 一般圖搜索算法劃分為二個階段：一般圖搜索算法劃分為二個階段：n1、初始化、初始化 n2、搜索循環(huán)、搜索循環(huán) 2022-3-1547o算法劃分為二個階段：算法劃分為二個階段：n1、初始化、初始化 o 建立建立只包含初始狀態(tài)節(jié)點只包含初始狀態(tài)節(jié)點s的搜索圖的搜索圖G:=so OPEN:=so CLOSE:= n2、搜索循環(huán)、

28、搜索循環(huán)o MOVE-FIRST(OPEN)-取出取出OPEN表首的節(jié)點表首的節(jié)點n作為擴(kuò)展的節(jié)作為擴(kuò)展的節(jié)點，同時將其移到點，同時將其移到close表表 o 擴(kuò)展出擴(kuò)展出n的子節(jié)點的子節(jié)點,插入插入搜索圖搜索圖G和和OPEN表表 o 適當(dāng)?shù)臉?biāo)記和修改指針適當(dāng)?shù)臉?biāo)記和修改指針o 排序排序OPEN表表n通過循環(huán)地執(zhí)行該算法，通過循環(huán)地執(zhí)行該算法，搜索圖搜索圖G會因不斷有新節(jié)點加入而逐會因不斷有新節(jié)點加入而逐步長大，直到搜索到目標(biāo)節(jié)點。步長大，直到搜索到目標(biāo)節(jié)點。 2022-3-1548初始布局初始布局目標(biāo)布局目標(biāo)布局移動數(shù)碼移動數(shù)碼2022-3-15495864273012022-3-15505

29、864273012022-3-15515864273015864270315864073215864273102022-3-15525864273015864270315864073215864273102022-3-15535864273015864270315864073215864273102022-3-15545864273015864270315864073215864273105064873215864703215860473212022-3-1555586427301586427031586407321586427310506487321586470321586047321202

30、2-3-15565864273015864270315864073215864273105064873215864703215860473215864273102022-3-15575864273015864270315864073215864273105064873215864703215860473215604873210564873212022-3-15585864273015864270315864073215864273105064873215864703215860473215604873210564873212022-3-15595864273015864270315864073

31、215864273105064873215864703215860473215604873210564873212022-3-15605864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-3-15615864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212022-3-15625864273015864270315864073215864

32、273105064873215864703215860473215604873210564873215674803212022-3-15635864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-3-1564586427301586427031586407321586427310506487321586470321586047321560487321056487321567480321567481320567408321202

33、2-3-15655864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-3-15665864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212022-3-1567586427301586427031586407321586427310506487321586470321

34、5860473215604873210564873215674803215674813205674083212022-3-1568搜索過程中的指針修改搜索過程中的指針修改o 節(jié)點節(jié)點n擴(kuò)展后擴(kuò)展后的子節(jié)點分為的子節(jié)點分為3類類：n(i)全新節(jié)點全新節(jié)點n(ii)已出現(xiàn)在已出現(xiàn)在OPEN表表中的節(jié)點中的節(jié)點n(iii)已出現(xiàn)的已出現(xiàn)的CLOSE表表中的節(jié)點中的節(jié)點o 指針標(biāo)記和修改的方法：指針標(biāo)記和修改的方法：n(i)類節(jié)點：加入類節(jié)點：加入OPEN表，建立從子節(jié)點到父節(jié)點表，建立從子節(jié)點到父節(jié)點n的指針的指針n(ii)類節(jié)點、類節(jié)點、 (iii)類節(jié)點類節(jié)點o 比較比較經(jīng)由經(jīng)由老父節(jié)點老父節(jié)點

35、、新父節(jié)點新父節(jié)點n到達(dá)到達(dá)初始狀態(tài)節(jié)點初始狀態(tài)節(jié)點的的路徑代價路徑代價 o 經(jīng)由節(jié)點經(jīng)由節(jié)點n的代價比較小，則移動子節(jié)點指向老父節(jié)的代價比較小，則移動子節(jié)點指向老父節(jié)點的指針，改為指向新父節(jié)點點的指針，改為指向新父節(jié)點no (iii)類節(jié)點還得從類節(jié)點還得從CLOSE表中移出，重新加入表中移出，重新加入OPEN表表。2022-3-1569Sn4ninjn1n2n3n31n32o 節(jié)點節(jié)點ni是當(dāng)前擴(kuò)展的節(jié)點；是當(dāng)前擴(kuò)展的節(jié)點；o 擴(kuò)展出擴(kuò)展出4個后續(xù)節(jié)點；個后續(xù)節(jié)點；o n1、n2是新節(jié)點是新節(jié)點，只需建只需建立指向父節(jié)點的指針，并加立指向父節(jié)點的指針，并加入入OPEN表表；2022-3-1

36、570Sn4ninjn1n2n3n31n32o n4已經(jīng)存在于已經(jīng)存在于OPEN表，并表，并且已有父節(jié)點且已有父節(jié)點njnn4經(jīng)經(jīng)nj的路徑代價大的路徑代價大n取消取消n4指向指向nj的指針的指針n改為建立改為建立n4指向新父節(jié)點指向新父節(jié)點ni的指針的指針o n3已經(jīng)存在于已經(jīng)存在于CLOSE表，表，并且已有父節(jié)點并且已有父節(jié)點njn需要做和需要做和n4同樣的比較和指同樣的比較和指針修改工作。并且要重新加入針修改工作。并且要重新加入open表。表。2022-3-1571 o 提高搜索效率的關(guān)鍵提高搜索效率的關(guān)鍵優(yōu)化優(yōu)化OPENOPEN表中節(jié)點的排序表中節(jié)點的排序方式方式。o 簡單的排序策略簡

37、單的排序策略按預(yù)先確定的順序或隨機(jī)地排按預(yù)先確定的順序或隨機(jī)地排序新加入到序新加入到OPENOPEN表中的節(jié)點。表中的節(jié)點。 o 常用的簡單方式：常用的簡單方式： 寬度優(yōu)先寬度優(yōu)先擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是置于擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是置于OPENOPEN表的后端，即表的后端，即OPENOPEN表作為表作為隊列隊列使用，使用，先進(jìn)先出先進(jìn)先出，使搜索優(yōu)先向，使搜索優(yōu)先向橫橫廣廣方向發(fā)展。方向發(fā)展。 深度優(yōu)先深度優(yōu)先擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是置于擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是置于OPENOPEN表的前端，即表的前端，即OPENOPEN表作為表作為棧棧使用，使用，后進(jìn)先出后進(jìn)先出，使搜

38、索優(yōu)先向，使搜索優(yōu)先向縱深縱深方向發(fā)展。方向發(fā)展。2022-3-1572o 寬度優(yōu)先寬度優(yōu)先擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是置置于于OPEN表的后端表的后端，即，即OPEN表表作為作為隊列隊列，先進(jìn)先先進(jìn)先出出，使，使搜索優(yōu)先向橫向方向發(fā)展搜索優(yōu)先向橫向方向發(fā)展。o 過程：指從初始節(jié)點過程：指從初始節(jié)點S0開始，向下逐層搜索，在開始，向下逐層搜索，在n層節(jié)層節(jié)點未搜索完之前，不進(jìn)入點未搜索完之前，不進(jìn)入n+1層搜索。層搜索。同層節(jié)點的搜索同層節(jié)點的搜索次序可以任意次序可以任意。即先按生成規(guī)則生成第一層節(jié)點，在該。即先按生成規(guī)則生成第一層節(jié)點，在該層全部節(jié)點中沿寬層全

39、部節(jié)點中沿寬(廣廣)度進(jìn)行橫向掃描，檢查目標(biāo)節(jié)點度進(jìn)行橫向掃描，檢查目標(biāo)節(jié)點Sg是否在這些子節(jié)點中。若沒有是否在這些子節(jié)點中。若沒有,則再將所有笫一層節(jié)則再將所有笫一層節(jié)點逐一擴(kuò)展，得到第二層節(jié)點。并逐一檢查第二層節(jié)點點逐一擴(kuò)展，得到第二層節(jié)點。并逐一檢查第二層節(jié)點中是否包含有中是否包含有Sg，如此依次按照先生成、先檢查、先，如此依次按照先生成、先檢查、先擴(kuò)展的原則進(jìn)行下去，直到發(fā)現(xiàn)擴(kuò)展的原則進(jìn)行下去，直到發(fā)現(xiàn)Sg為止為止 2022-3-1573寬度優(yōu)先寬度優(yōu)先實例實例2 31 8 47 6 52 8 31 47 6 5 2 31 8 47 6 52 31 8 47 6 52 8 31 47

40、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-1574寬度優(yōu)先搜索寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點的程度依次擴(kuò)展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索是逐層進(jìn)行的，在對下一層的任意節(jié)點進(jìn)行搜索之前，必須搜索完本層的所有節(jié)點。

41、“先產(chǎn)生的節(jié)點先擴(kuò)展”2022-3-1575 (1)把初始節(jié)點把初始節(jié)點S0，放入，放入OPEN表。表。 (2)如果如果OPEN表為空。則問題無解，失敗并退出。表為空。則問題無解，失敗并退出。 (3)把把OPEN表中的第一個節(jié)點取出放入表中的第一個節(jié)點取出放入CLOSE表中，表中，并按順序冠以編號并按順序冠以編號n； (4)考察節(jié)點考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問是否為目標(biāo)節(jié)點。若是，則求得了問題的解，成功并退出。題的解，成功并退出。 (5)若節(jié)點若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步；步； (6)擴(kuò)展節(jié)點擴(kuò)展節(jié)點n，將其子節(jié)點放到，將其子節(jié)點放到OPEN表的表的尾部尾部，

42、并為每一個子節(jié)點都配置指向父節(jié)點的指針，然并為每一個子節(jié)點都配置指向父節(jié)點的指針，然后轉(zhuǎn)第后轉(zhuǎn)第(2)步。步。采用隊列結(jié)構(gòu)，寬度優(yōu)先算法可以表示如下：采用隊列結(jié)構(gòu)，寬度優(yōu)先算法可以表示如下：2022-3-1576 例例 通過挪動積木塊，希望從初始狀態(tài)達(dá)到一個目的狀通過挪動積木塊，希望從初始狀態(tài)達(dá)到一個目的狀態(tài)，即三塊積木堆疊在一起。積木態(tài)，即三塊積木堆疊在一起。積木A在頂部，積木在頂部，積木B在頂中間，積木在頂中間，積木C在底部。請畫出按照寬度優(yōu)先搜索在底部。請畫出按照寬度優(yōu)先搜索策略所產(chǎn)生的搜索樹。策略所產(chǎn)生的搜索樹。 這個問題的唯一操作算子為這個問題的唯一操作算子為MOVE(X,Y)MOV

43、E(X,Y)，即積木，即積木X X搬到搬到Y(jié) Y（積木（積木或桌面）上面。如或桌面）上面。如“挪動積木挪動積木A A到桌面上表示為到桌面上表示為MOVE(A,Table)MOVE(A,Table)。該操作算子可運(yùn)用的先決條件是：該操作算子可運(yùn)用的先決條件是：（1 1）被挪動積木的頂部必須為空。）被挪動積木的頂部必須為空。（2 2）如）如Y Y是積木（不是桌面），則積木是積木（不是桌面），則積木Y Y的頂部也必須為空。的頂部也必須為空。（3 3）同一狀態(tài)下，運(yùn)用操作算子的次數(shù)不得多于一次。）同一狀態(tài)下，運(yùn)用操作算子的次數(shù)不得多于一次。2022-3-1577積木問題的寬度優(yōu)先搜索樹積木問題的寬度優(yōu)

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

45、多無用的節(jié)點，搜索效率低。低。o 寬度優(yōu)先搜索中，時間需求是一寬度優(yōu)先搜索中，時間需求是一個很大的問題，特別是當(dāng)搜索的個很大的問題，特別是當(dāng)搜索的深度比較大時，尤為嚴(yán)重，但是深度比較大時，尤為嚴(yán)重，但是空間需求是比執(zhí)行時間更嚴(yán)重的空間需求是比執(zhí)行時間更嚴(yán)重的問題。問題。 寬度優(yōu)先搜索優(yōu)寬度優(yōu)先搜索優(yōu)點：點：目標(biāo)節(jié)點如果存目標(biāo)節(jié)點如果存在，用寬度優(yōu)先在，用寬度優(yōu)先搜索算法總可以搜索算法總可以找到該目標(biāo)節(jié)點，找到該目標(biāo)節(jié)點，而且而且是最?。词亲钚。醋疃搪窂剑┑墓?jié)最短路徑）的節(jié)點。點。寬度優(yōu)先搜索的優(yōu)點和缺點寬度優(yōu)先搜索的優(yōu)點和缺點2022-3-1580o 深度優(yōu)先深度優(yōu)先擴(kuò)展當(dāng)前節(jié)點后生成的子

46、節(jié)點總是擴(kuò)展當(dāng)前節(jié)點后生成的子節(jié)點總是置置于于OPEN表的前端表的前端，即，即OPEN表表作為作為棧棧，后進(jìn)先出后進(jìn)先出，使使搜索優(yōu)先向縱深方向發(fā)展搜索優(yōu)先向縱深方向發(fā)展。o 過程：從初始節(jié)點過程：從初始節(jié)點S0開始，按生成規(guī)則生成下一級各開始，按生成規(guī)則生成下一級各子節(jié)點，檢查是否出現(xiàn)目標(biāo)節(jié)點子節(jié)點，檢查是否出現(xiàn)目標(biāo)節(jié)點Sg；若未出現(xiàn)，則按；若未出現(xiàn)，則按“最晚生成的子節(jié)點優(yōu)先擴(kuò)展最晚生成的子節(jié)點優(yōu)先擴(kuò)展”的原則，再用生成規(guī)則的原則，再用生成規(guī)則生成再下一級的子節(jié)點，再檢查是否出現(xiàn)生成再下一級的子節(jié)點，再檢查是否出現(xiàn)Sg；若仍未；若仍未出現(xiàn)，則再擴(kuò)展最晚生成的子節(jié)點。如此下去，沿著最出現(xiàn)，則

47、再擴(kuò)展最晚生成的子節(jié)點。如此下去，沿著最晚生成的子節(jié)點分枝，逐級晚生成的子節(jié)點分枝，逐級“縱向縱向”深入搜索。深入搜索。 2022-3-1581深度優(yōu)先深度優(yōu)先實例實例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 5

48、2 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81 4 37 6 52 8 31 4 57 612346891113141618191 2 3 8 47 6 5目標(biāo)目標(biāo)571012151720212022-3-1582深度優(yōu)先搜索深度優(yōu)先搜索o 在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的在深度優(yōu)先搜索中，首先擴(kuò)展最新產(chǎn)生的( (最最深的深的) )節(jié)點，深度節(jié)點，深度 相等的節(jié)點可以任意排列。相等的節(jié)點可以任意排列。o “最晚產(chǎn)生的節(jié)點最先擴(kuò)展最晚產(chǎn)生的節(jié)點最先擴(kuò)展” 起始節(jié)點深度為0 任何其他節(jié)點的深度等于其父輩節(jié)點深度加上1 :dn=dn-1+12022-3-1

49、583深度優(yōu)先搜索深度優(yōu)先搜索很明顯這樣做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴(kuò)展下去，這當(dāng)然是不允許的。為保證找到解，應(yīng)選擇適當(dāng)?shù)纳疃冉缦?，或者采取不斷加大深度界限的辦法，反復(fù)搜索，直到找到解。這種改進(jìn)的方法叫做迭代加深搜索。2022-3-1584(1)把初始節(jié)點S0放入OPEN表； (2)如果OPEN表為空，則問題無解，失敗并退出。 (3)把OPEN表中的第一個節(jié)點取出放入CLOSE表中，并按順序冠以編號n； (4)考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解，成功并退出。 (5)若節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第(2)步； (6)

50、擴(kuò)展節(jié)點n，將其子節(jié)點放到OPEN表的首部，并為其配置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。基于棧實現(xiàn)的深度優(yōu)先搜索算法： 2022-3-1585 例例 卒子穿陣問題卒子穿陣問題: 要求一卒子從頂部通過圖所示的列陣到達(dá)要求一卒子從頂部通過圖所示的列陣到達(dá)底部。要求卒子行進(jìn)中不可進(jìn)入到代表敵兵駐守的區(qū)域內(nèi)底部。要求卒子行進(jìn)中不可進(jìn)入到代表敵兵駐守的區(qū)域內(nèi)（標(biāo)注（標(biāo)注1），并不準(zhǔn)后退。），并不準(zhǔn)后退。假定限制值為假定限制值為5。請畫出按照深。請畫出按照深度優(yōu)先搜索策略所產(chǎn)生的搜索樹度優(yōu)先搜索策略所產(chǎn)生的搜索樹 2022-3-1586卒子穿陣的深度優(yōu)先搜索樹卒子穿陣的深度優(yōu)先搜索樹 2022-3-15

51、87o 一般不能保證找到最優(yōu)解一般不能保證找到最優(yōu)解o 當(dāng)深度限制不合理時，當(dāng)深度限制不合理時，可能找不到解可能找不到解，可以，可以將算法改為將算法改為可變深度限制可變深度限制o 最壞情況時，搜索空間等同于窮舉最壞情況時，搜索空間等同于窮舉o 是一個通用的與問題無關(guān)的方法是一個通用的與問題無關(guān)的方法2022-3-1588o 深度優(yōu)先搜索深度優(yōu)先搜索的的優(yōu)點優(yōu)點是是比寬度優(yōu)先搜索算比寬度優(yōu)先搜索算法需要較少的空間法需要較少的空間，該算法只需要保存搜，該算法只需要保存搜索樹的一部分，它由索樹的一部分，它由當(dāng)前正在搜索的路徑當(dāng)前正在搜索的路徑和該路徑上還沒有完全展開的節(jié)點標(biāo)志所和該路徑上還沒有完全展

52、開的節(jié)點標(biāo)志所組成組成。o 深度優(yōu)先搜索的存儲器要求是深度約束的深度優(yōu)先搜索的存儲器要求是深度約束的線性函數(shù)。線性函數(shù)。 2022-3-1589 既不是完備的，也不是最優(yōu)的。既不是完備的，也不是最優(yōu)的。 主要問題是可能主要問題是可能搜索到了錯誤的路徑上搜索到了錯誤的路徑上。很多。很多問題可能具有很深甚至是無限的搜索樹，如果不幸問題可能具有很深甚至是無限的搜索樹，如果不幸選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜選擇了一個錯誤的路徑，則深度優(yōu)先搜索會一直搜索下去，而不會回到正確的路徑上。這樣一來對于索下去，而不會回到正確的路徑上。這樣一來對于這些問題，深度優(yōu)先搜索要么陷入無限的循環(huán)而不這些問題

53、，深度優(yōu)先搜索要么陷入無限的循環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。很長而且不是最優(yōu)的答案。2022-3-1590比較比較 o 適用場合適用場合 深度優(yōu)先深度優(yōu)先當(dāng)一個問題有多個解答或多條解答路徑，當(dāng)一個問題有多個解答或多條解答路徑，且只須找到其中一個時；且只須找到其中一個時；往往應(yīng)對搜索深度加以限制往往應(yīng)對搜索深度加以限制。 寬度優(yōu)先寬度優(yōu)先確保搜索到確保搜索到最短的解答路徑最短的解答路徑。o 共同優(yōu)缺點：共同優(yōu)缺點： 可直接應(yīng)用一般圖搜索算法實現(xiàn)，不需要設(shè)計特別的可直接應(yīng)用一般圖搜索算法實現(xiàn)，不需要設(shè)計特別的節(jié)

54、點排序方法，從而簡單易行，適合于許多復(fù)雜度不高的問節(jié)點排序方法，從而簡單易行，適合于許多復(fù)雜度不高的問題求解任務(wù)。題求解任務(wù)。 節(jié)點排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導(dǎo)節(jié)點排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導(dǎo)排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點后才碰到解排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點后才碰到解答，所以也稱為答，所以也稱為盲目搜索盲目搜索。 2022-3-1591有界深度搜索和迭代加深搜索有界深度搜索和迭代加深搜索 有界深度優(yōu)先搜索有界深度優(yōu)先搜索過程總體上按深度優(yōu)先算過程總體上按深度優(yōu)先算法方法進(jìn)行，但對搜索深度需要給出一個深法方法進(jìn)行，但對搜索深度需要給出一個深

55、度限制度限制dmdm，當(dāng)深度達(dá)到了，當(dāng)深度達(dá)到了dmdm的時候，如果還的時候，如果還沒有找到解答，就停止對該分支的搜索，換沒有找到解答，就停止對該分支的搜索，換到另外一個分支進(jìn)行搜索。到另外一個分支進(jìn)行搜索。2022-3-1592(1)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表中，置表中，置S0的深度的深度d(S0)=0。 (2)如果如果OPEN表為空，則問題無解，失敗并退出。表為空，則問題無解，失敗并退出。 (3)把把OPEN表中的第一個節(jié)點取出放入表中的第一個節(jié)點取出放入CLOSE表中。并按順表中。并按順序冠以編號序冠以編號n。(4)考察節(jié)點考察節(jié)點n是否為目標(biāo)節(jié)點。若是，則求得了問題的解

56、，成是否為目標(biāo)節(jié)點。若是，則求得了問題的解，成功并退出。功并退出。 (5)如果節(jié)點如果節(jié)點n的深度的深度d(n)= dm，則轉(zhuǎn)第，則轉(zhuǎn)第(2)步步。 (6)如果節(jié)點如果節(jié)點n不可擴(kuò)展，則轉(zhuǎn)第不可擴(kuò)展，則轉(zhuǎn)第(2)步。步。 (7)擴(kuò)展節(jié)點擴(kuò)展節(jié)點n。將其子節(jié)點放入。將其子節(jié)點放入OPEN表的表的首部首部，并為其配置，并為其配置指向父節(jié)點的指針。然后轉(zhuǎn)第指向父節(jié)點的指針。然后轉(zhuǎn)第(2)步。步。 有界深度搜索算法有界深度搜索算法2022-3-1593策略說明策略說明: : o （1 1）深度限制深度限制dmdm很重要很重要。當(dāng)問題有解，且當(dāng)問題有解，且解的路徑長度小于或等于解的路徑長度小于或等于dm

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

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

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

60、然而對于很多問題，這種多次的擴(kuò)展負(fù)擔(dān)實際這種多次的擴(kuò)展負(fù)擔(dān)實際上很小上很小，直覺上可以想象，如果一棵樹的分支，直覺上可以想象，如果一棵樹的分支系數(shù)很大，幾乎所有的節(jié)點都在最底層上，則系數(shù)很大，幾乎所有的節(jié)點都在最底層上，則對于上面各層節(jié)點擴(kuò)展多次對整個系統(tǒng)來說影對于上面各層節(jié)點擴(kuò)展多次對整個系統(tǒng)來說影響不是很大。響不是很大。 2022-3-1598 Procedure Iterative-deepeningBegin(1)設(shè)置當(dāng)前深度限制設(shè)置當(dāng)前深度限制=1; (2)把初始節(jié)點壓入棧把初始節(jié)點壓入棧,并設(shè)置棧頂指針并設(shè)置棧頂指針; (3)While棧不空并且深度在給定的深度限制之內(nèi)棧不空并且深