第3章-搜索策略

1、2021-12-151第3章 搜索策略n問題求解系統(tǒng)劃分為兩大類n知識貧乏系統(tǒng) n依靠搜索技術(shù)解決問題 n知識貧乏、缺乏針對性n效率低 n知識豐富系統(tǒng) n依靠推理技術(shù)解決問題n基于豐富知識的推理技術(shù)，直截了當 n效率高 2021-12-152 n對于給定的問題，智能系統(tǒng)的行為一般是找對于給定的問題，智能系統(tǒng)的行為一般是找到能夠達到所希望目標的動作序列，并使其所到能夠達到所希望目標的動作序列，并使其所付出的付出的代價最小、性能最好代價最小、性能最好。n基于給定的問題，問題求解的第一步是目標基于給定的問題，問題求解的第一步是目標的表示。的表示。n搜索就是找到智能系統(tǒng)的動作序列的過程。搜索就是找到智

2、能系統(tǒng)的動作序列的過程。 2021-12-153n和通常的搜索空間不同，人工智能中大多數(shù)問題和通常的搜索空間不同，人工智能中大多數(shù)問題的狀態(tài)空間在問題求解之前不是全部知道的。的狀態(tài)空間在問題求解之前不是全部知道的。 在人工智能中，搜索問題一般包括兩個重在人工智能中，搜索問題一般包括兩個重要的問題：要的問題：v搜索什么搜索什么搜索什么通常指的就是目標。搜索什么通常指的就是目標。v在哪里搜索在哪里搜索在哪里搜索就是在哪里搜索就是“搜索空間搜索空間”。搜索空間通常。搜索空間通常是指一系列狀態(tài)的匯集，因此稱為狀態(tài)空間。是指一系列狀態(tài)的匯集，因此稱為狀態(tài)空間。2021-12-154n所以，人工智能中的搜

3、索可以分成兩個所以，人工智能中的搜索可以分成兩個階段：階段：n狀態(tài)空間的生成階段狀態(tài)空間的生成階段n在該狀態(tài)空間中對所求問題狀態(tài)的搜索在該狀態(tài)空間中對所求問題狀態(tài)的搜索搜索可以根據(jù)是否使用啟發(fā)式信息分搜索可以根據(jù)是否使用啟發(fā)式信息分為為v盲目搜索盲目搜索v啟發(fā)式搜索啟發(fā)式搜索 2021-12-155n盲目搜索盲目搜索 只是可以區(qū)分出哪個只是可以區(qū)分出哪個是目標狀態(tài)。是目標狀態(tài)。 一般是按預定的搜索一般是按預定的搜索策略進行搜索。策略進行搜索。 沒有考慮到問題本身沒有考慮到問題本身的特性，這種搜索具有的特性，這種搜索具有很大的盲目性，效率不很大的盲目性，效率不高，不便于復雜問題的高，不便于復雜問

4、題的求解。求解。 o啟發(fā)式搜索啟發(fā)式搜索是在搜索過程中加入了與問題有關(guān)的啟發(fā)式信息，用于指導搜索朝著最有希望的方向前進，加速問題的求解并找到最優(yōu)解。 2021-12-156n根據(jù)問題的表示方式分為根據(jù)問題的表示方式分為n狀態(tài)空間搜索狀態(tài)空間搜索n與或樹搜索與或樹搜索狀態(tài)空間狀態(tài)空間搜索是用搜索是用狀態(tài)空間狀態(tài)空間法來求解法來求解問題所進問題所進行的搜索行的搜索與與/ /或樹搜或樹搜索是指用問索是指用問題規(guī)約方法題規(guī)約方法來求解問題來求解問題時所進行的時所進行的搜索。搜索。2021-12-157n考慮一個問題的狀態(tài)空考慮一個問題的狀態(tài)空間為一棵樹的形式。間為一棵樹的形式。n寬度優(yōu)先搜索寬度優(yōu)先搜

5、索n深度優(yōu)先搜索深度優(yōu)先搜索如果根節(jié)點首先如果根節(jié)點首先擴展，然后是擴擴展，然后是擴展根節(jié)點生成的展根節(jié)點生成的所有節(jié)點，然后所有節(jié)點，然后是這些節(jié)點的后是這些節(jié)點的后繼，如此反復下繼，如此反復下去。去。在樹的最深一層的節(jié)在樹的最深一層的節(jié)點中擴展一個節(jié)點。點中擴展一個節(jié)點。只有當搜索遇到一個只有當搜索遇到一個死亡節(jié)點（非目標節(jié)死亡節(jié)點（非目標節(jié)點并且是無法擴展的點并且是無法擴展的節(jié)點）的時候，才返節(jié)點）的時候，才返回上一層選擇其他的回上一層選擇其他的節(jié)點搜索。節(jié)點搜索。2021-12-158n無論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，無論是寬度優(yōu)先搜索還是深度優(yōu)先搜索，遍歷節(jié)點的順序一般都是固定的

6、，即一遍歷節(jié)點的順序一般都是固定的，即一旦搜索空間給定，節(jié)點遍歷的順序就固旦搜索空間給定，節(jié)點遍歷的順序就固定了。這種類型的遍歷稱為定了。這種類型的遍歷稱為“確定性確定性”的，也就是盲目搜索。的，也就是盲目搜索。n對于啟發(fā)式搜索，在計算每個節(jié)點的參對于啟發(fā)式搜索，在計算每個節(jié)點的參數(shù)之前無法確定先選擇哪個節(jié)點擴展，數(shù)之前無法確定先選擇哪個節(jié)點擴展，這種搜索一般也稱為非確定的。這種搜索一般也稱為非確定的。 2021-12-159n完備性：完備性：n如果存在一個解答，該策略是否保證能夠找如果存在一個解答，該策略是否保證能夠找到？到？n時間復雜性：時間復雜性：n需要多長時間可以找到解答？需要多長時間

7、可以找到解答？n空間復雜性：空間復雜性：n執(zhí)行搜索需要多少存儲空間？執(zhí)行搜索需要多少存儲空間？n最優(yōu)性：最優(yōu)性：n如果存在不同的幾個解答，該策略是否可以如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？發(fā)現(xiàn)最高質(zhì)量的解答？搜索策略評價標準搜索策略評價標準: :2021-12-1510有許多智力問題有許多智力問題( (如梵塔問題、旅行商問題、八皇如梵塔問題、旅行商問題、八皇后問題、農(nóng)夫過河問題等后問題、農(nóng)夫過河問題等) )和實際問題（如路徑規(guī)和實際問題（如路徑規(guī)劃、機器人行動規(guī)劃等）都可以歸結(jié)為劃、機器人行動規(guī)劃等）都可以歸結(jié)為狀態(tài)空間搜狀態(tài)空間搜索索。用用狀態(tài)空間搜索狀態(tài)空間搜索來求解

8、問題的系統(tǒng)均定義一個來求解問題的系統(tǒng)均定義一個狀態(tài)狀態(tài)空間空間，并通過適當?shù)?，并通過適當?shù)乃阉魉惴ㄋ阉魉惴ㄔ谠跔顟B(tài)空間狀態(tài)空間中搜索中搜索解解答路徑答路徑。2021-12-1511n顯式圖與隱式圖顯式圖與隱式圖 n顯式圖顯式圖n把問題有關(guān)的全部狀態(tài)空間圖，即相應的全部有關(guān)知識(敘述性知識、過程性知識和控制性知識)，都直接存入知識庫 n隱式圖隱式圖n只存儲與問題求解有關(guān)的部分知識(即部分狀態(tài)空間)。這種存儲方式稱為隱式存儲。2021-12-1512n圖搜索的基本思想圖搜索的基本思想 n圖搜索圖搜索-一種在圖中尋找路徑的方法一種在圖中尋找路徑的方法 n從圖中的初始節(jié)點開始，至目標節(jié)點為止。n初始節(jié)

9、點和目標節(jié)點分別代表產(chǎn)生式系統(tǒng)的初始數(shù)據(jù)庫和滿足終止條件的數(shù)據(jù)庫。n方法：把問題的初始狀態(tài)作為當前狀態(tài)，選擇適用的算符對其進行操作，生成一組子狀態(tài)，檢查目標狀態(tài)是否在其中出現(xiàn)。若出現(xiàn)，則搜索成功，找到了問題的解；若不出現(xiàn)，則按某種搜索策略從已生成的狀態(tài)中再選一個狀態(tài)作為當前狀態(tài)。重復上述過程，直到目標狀態(tài)出現(xiàn)或者不再有可供操作的狀態(tài)及算符時為止。 2021-12-1513 n三個錢幣可能出現(xiàn)的狀態(tài)有8種組合： 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)。202

10、1-12-1514三枚錢幣問題的狀態(tài)空間圖三枚錢幣問題的狀態(tài)空間圖 2021-12-1515nS問題求解（即搜索）過程中所有可能到達的合法狀態(tài)構(gòu)成的集合；nO操作算子的集合，操作算子的執(zhí)行會導致問題狀態(tài)的變遷 ；n狀態(tài)用于記載問題求解（即搜索）過程中某一時刻問題現(xiàn)狀的快照；n抽象為矢量形式 Q=q0,q1,qnTn每個元素qi稱為狀態(tài)分量 n給定每個狀態(tài)分量qi的值就得到一個具體的狀態(tài) Qk=q0k,q1k,qnkT2021-12-1516狀態(tài)狀態(tài)表示狀態(tài)的變遷表示狀態(tài)的變遷操作算子操作算子問題的狀態(tài)空間問題的狀態(tài)空間是一個表示該問題的全部可能狀態(tài)是一個表示該問題的全部可能狀態(tài)及其變遷的及其變

11、遷的有向圖有向圖。 n節(jié)點n狀態(tài)n有向弧n狀態(tài)的變遷 n弧上的標簽n導致狀態(tài)變遷的操作算子 用用狀態(tài)空間搜索狀態(tài)空間搜索來求解問題的系統(tǒng)均定義一個來求解問題的系統(tǒng)均定義一個狀態(tài)狀態(tài)空間空間，并通過適當?shù)模⑼ㄟ^適當?shù)乃阉魉惴ㄋ阉魉惴ㄔ谠跔顟B(tài)空間狀態(tài)空間中搜索中搜索解解答路徑答路徑。2021-12-1517：n1)船上人數(shù)不得超過載重限量，設(shè)為K個人； n2)任何時刻（包括兩岸、船上）野人數(shù)目不得超過傳教士； n3)允許在河的某一岸或者在船上只有野人而沒有傳教士；2021-12-15182021-12-1519可能到達的合法狀態(tài)：442=32 n(0,0,1),(0,3,0),(3,0,1),(

12、3,3,0)2021-12-1520(2)狀態(tài)空間表示的經(jīng)典例子“傳教士和野人問題”n定義2類操作算子：nL(x,y)指示從左岸到右岸的劃船操作 nR(x,y)指示從右岸到左岸的劃船操作nx + y K=2(船的載重限制)；nx和y取值的可能組合只有5個n10，20，11，01，02 n( 允許在船上只有野人而沒有傳教士 )n共有10個操作算子2021-12-15212021-12-1522 2021-12-1523 2021-12-1524 例例:在一個在一個33的方格棋盤上放置著的方格棋盤上放置著1,2,3,4,5,6,7,8八個數(shù)碼，每個數(shù)碼占一格，且有一個空格。這些八個數(shù)碼，每個數(shù)碼占

13、一格，且有一個空格。這些數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰數(shù)碼可在棋盤上移動，其移動規(guī)則是：與空格相鄰的數(shù)碼方可移入空格。的數(shù)碼方可移入空格?，F(xiàn)在的現(xiàn)在的問題問題是：對于指定的是：對于指定的初始棋局初始棋局和和目標棋局目標棋局，給出給出數(shù)碼的移動序列數(shù)碼的移動序列。該問題稱為。該問題稱為八數(shù)碼問題八數(shù)碼問題。 2831476581324765初始棋局初始棋局目標棋局目標棋局移動數(shù)碼移動數(shù)碼2021-12-15252 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

14、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 52021-12-1526n或圖（一般圖）或圖（一般圖）n一個狀態(tài)可以有多個可供選擇的操作算子；n操作算子間的選擇是一種“或”的關(guān)系;n這樣的有向圖稱為或圖。2021-12-1527n或

15、圖（一般圖）或圖（一般圖）n一個狀態(tài)可以有多個可供選擇的操作算子；n操作算子間的選擇是一種“或”的關(guān)系，這樣的有向圖稱為或圖。n狀態(tài)空間一般都表示為或圖（一般圖）n搜索圖在搜索解答路徑的過程中畫出搜索時涉及到的節(jié)點和弧線，構(gòu)成所謂的搜索圖。狀態(tài)空間搜索狀態(tài)空間搜索一般圖搜索一般圖搜索2021-12-1528n符號說明：ns-初始狀態(tài)節(jié)點nG-搜索圖nOPEN-存放待擴展節(jié)點的表nCLOSE-存放已被擴展的節(jié)點的表nMOVE-FIRST(OPEN)-取OPEN表首的節(jié)點作為當前要被擴展的節(jié)點n，同時將節(jié)點n移至CLOSE表n一般圖搜索算法劃分為二個階段：n1、初始化 n2、搜索循環(huán) 一般圖搜索算

16、法2021-12-1529n算法劃分為二個階段：n1、初始化 n建立只包含初始狀態(tài)節(jié)點s的搜索圖G:=snOPEN:=snCLOSE:= n2、搜索循環(huán)nMOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點n作為擴展的節(jié)點，同時將其移到close表 n擴展出n的子節(jié)點,插入搜索圖G和OPEN表 n適當?shù)臉擞浐托薷闹羔榥排序OPEN表n通過循環(huán)地執(zhí)行該算法，搜索圖G會因不斷有新節(jié)點加入而逐步長大，直到搜索到目標節(jié)點。 一般圖搜索算法2021-12-1530初始布局初始布局目標布局目標布局移動數(shù)碼移動數(shù)碼2021-12-15315864273012021-12-1532586427301202

17、1-12-15335864273015864270315864073215864273102021-12-15345864273015864270315864073215864273102021-12-15355864273015864270315864073215864273102021-12-15365864273015864270315864073215864273105064873215864703215860473212021-12-15375864273015864270315864073215864273105064873215864703215860473212021-12-1

18、5385864273015864270315864073215864273105064873215864703215860473215864273102021-12-15395864273015864270315864073215864273105064873215864703215860473215604873210564873212021-12-15405864273015864270315864073215864273105064873215864703215860473215604873210564873212021-12-1541586427301586427031586407321

19、5864273105064873215864703215860473215604873210564873212021-12-15425864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212021-12-15435864273015864270315864073215864273105064873215864703215860473215604873210564873215674803212021-12-1544586427301586427031586407321586

20、4273105064873215864703215860473215604873210564873215674803212021-12-15455864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212021-12-1546586427301586427031586407321586427310506487321586470321586047321560487321056487321567480321567481320567408321

21、2021-12-15475864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212021-12-15485864273015864270315864073215864273105064873215864703215860473215604873210564873215674803215674813205674083212021-12-1549586427301586427031586407321586427310506487321586

22、4703215860473215604873210564873215674803215674813205674083212021-12-1550n節(jié)點n擴展后的子節(jié)點分為3類：n(i)全新節(jié)點n(ii)已出現(xiàn)在OPEN表中的節(jié)點n(iii)已出現(xiàn)的CLOSE表中的節(jié)點n指針標記和修改的方法：n(i)類節(jié)點：加入OPEN表，建立從子節(jié)點到父節(jié)點n的指針n(ii)類節(jié)點、 (iii)類節(jié)點n比較經(jīng)由老父節(jié)點、新父節(jié)點n到達初始狀態(tài)節(jié)點的路徑代價 n經(jīng)由節(jié)點n的代價比較小，則移動子節(jié)點指向老父節(jié)點的指針，改為指向新父節(jié)點nn (iii)類節(jié)點還得從CLOSE表中移出，重新加入OPEN表。搜索過程中的

23、指針修改2021-12-1551Sn4ninjn1n2n3n31n32n節(jié)點ni是當前擴展的節(jié)點；n擴展出4個后續(xù)節(jié)點；nn1、n2是新節(jié)點，只需建立指向父節(jié)點的指針，并加入OPEN表；2021-12-1552Sn4ninjn1n2n3n31n32nn4已經(jīng)存在于OPEN表，并且已有父節(jié)點njnn4經(jīng)nj的路徑代價大n取消n4指向nj的指針n改為建立n4指向新父節(jié)點ni的指針nn3已經(jīng)存在于CLOSE表，并且已有父節(jié)點njn需要做和n4同樣的比較和指針修改工作。并且要重新加入open表。2021-12-1553 n一般圖搜索算法中，提高搜索效率的關(guān)鍵在于一般圖搜索算法中，提高搜索效率的關(guān)鍵在于

24、優(yōu)化優(yōu)化OPEN表中節(jié)點的排序方式表中節(jié)點的排序方式 。n若每次排在表首的節(jié)點都在最終搜索到的若每次排在表首的節(jié)點都在最終搜索到的解答路徑上，則算法不會擴展任何多余的解答路徑上，則算法不會擴展任何多余的節(jié)點就可快速結(jié)束搜索。節(jié)點就可快速結(jié)束搜索。 n一種簡單的排序策略就是按預先確定的順一種簡單的排序策略就是按預先確定的順序或序或隨機地隨機地排序新加入到排序新加入到OPEN表中的節(jié)表中的節(jié)點，常用的方式是點，常用的方式是深度優(yōu)先深度優(yōu)先和和寬度優(yōu)先寬度優(yōu)先。2021-12-1554 nOPEN表中節(jié)點簡單的排序方式：n寬度優(yōu)先擴展當前節(jié)點后生成的子節(jié)點總是置于OPEN表的后端，即OPEN表作為隊

25、列，先進先出，使搜索優(yōu)先向橫向方向發(fā)展。2021-12-1555寬度優(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 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目標目標82 3 41 8 7 6 5491011121314151

26、6172021-12-1556寬度優(yōu)先搜索 如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的，那么這種搜索就叫做寬度優(yōu)先搜索。這種搜索是逐層進行的，在對下一層的任意節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。“先產(chǎn)生的節(jié)點先擴展”2021-12-1557(1)把初始節(jié)點S0，放入OPEN表。(2)如果OPEN表為空。則問題無解，失敗并退出。(3)把OPEN表中的第一個節(jié)點取出放入CLOSE表中，并按順序冠以編號n；(4)考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。(5)若節(jié)點n不可擴展，則轉(zhuǎn)第(2)步；(6)擴展節(jié)點n，將其子節(jié)點放到OPEN表的尾部，并為每一個子節(jié)點都配置指向父

27、節(jié)點的指針，然后轉(zhuǎn)第(2)步。采用隊列結(jié)構(gòu)，寬度優(yōu)先過程如下：采用隊列結(jié)構(gòu)，寬度優(yōu)先過程如下：2021-12-1558n寬度優(yōu)先搜索算法原理：n如果當前的節(jié)點不是目標節(jié)點，則把當點節(jié)點的子孫以任意順序增加到隊列的后面，并把隊列的前端元素定義為current。n如果目標發(fā)現(xiàn)，則算法終止。 2021-12-1559 2021-12-15602021-12-1561寬度優(yōu)先搜索的性質(zhì)n當問題有解時，一定能找到解n當問題為單位代價時，且問題有解時，一定能找到最優(yōu)解n方法與問題無關(guān)，具有通用性n效率較低n屬于圖搜索方法2021-12-1562n寬度優(yōu)先搜索是一種盲目搜索，時間和空間復雜度都比較高，當目標

28、節(jié)點距離初始節(jié)點較遠時會產(chǎn)生許多無用的節(jié)點，搜索效率低。n寬度優(yōu)先搜索中，時間需求是一個很大的問題，特別是當搜索的深度比較大時，尤為嚴重，但是空間需求是比執(zhí)行時間更嚴重的問題。 寬度優(yōu)先搜索優(yōu)點：目標節(jié)點如果存在，用寬度優(yōu)先搜索算法總可以找到該目標節(jié)點，而且是最?。醋疃搪窂剑┑墓?jié)點。寬度優(yōu)先搜索的優(yōu)點和缺點2021-12-1563nOPEN表中節(jié)點簡單的排序方式：n深度優(yōu)先擴展當前節(jié)點后生成的子節(jié)點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優(yōu)先向縱深方向發(fā)展。2021-12-1564深度優(yōu)先深度優(yōu)先實例實例2 31 8 47 6 5 2 31 8 47 6 52 8 31

29、 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 612346891113141618191 2 3 8 47 6 5目標目標571012151720212

30、021-12-1565深度優(yōu)先搜索n在深度優(yōu)先搜索中，首先擴展最新產(chǎn)生的(最深的)節(jié)點，深度 相等的節(jié)點可以任意排列。n“最晚產(chǎn)生的節(jié)點最先擴展” 起始節(jié)點深度為0 任何其他節(jié)點的深度等于其父輩節(jié)點深度加上1 :dn=dn-1+12021-12-1566深度優(yōu)先搜索很明顯這樣做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴展下去，這當然是不允許的。為保證找到解，應選擇適當?shù)纳疃冉缦?，或者采取不斷加大深度界限的辦法，反復搜索，直到找到解。這種改進的方法叫做迭代加深搜索。2021-12-15671)把初始節(jié)點把初始節(jié)點S0放入放入OPEN表；

31、表； (2)如果如果OPEN表為空，則問題無解，失敗并退出。表為空，則問題無解，失敗并退出。 (3)把把OPEN表中的第一個節(jié)點取出放入表中的第一個節(jié)點取出放入CLOSE表中，表中，并按順序冠以編號并按順序冠以編號n； (4)考察節(jié)點考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。解，成功并退出。 (5)若節(jié)點若節(jié)點n不可擴展，則轉(zhuǎn)第不可擴展，則轉(zhuǎn)第(2)步；步； (6)擴展節(jié)點擴展節(jié)點n，將其予節(jié)點放到，將其予節(jié)點放到OPEN表的首部，并為表的首部，并為其配置指向父節(jié)點的指針，然后轉(zhuǎn)第其配置指向父節(jié)點的指針，然后轉(zhuǎn)第(2)步。步?；跅崿F(xiàn)的

32、深度優(yōu)先搜索流程： 2021-12-1568n初始節(jié)點放到棧中，棧指針指向棧的最上邊的元素。n為了對該節(jié)點進行檢測，需要從棧中彈出該節(jié)點，如果是目標，該算法結(jié)束，否則把其子節(jié)點以任何順序壓入棧中。該過程直到棧變成為空。一棵樹的過程（下圖）。 2021-12-1569 2021-12-15702021-12-1571n一般不能保證找到最優(yōu)解n當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制n最壞情況時，搜索空間等同于窮舉n是一個通用的與問題無關(guān)的方法2021-12-1572n深度優(yōu)先搜索的優(yōu)點是比寬度優(yōu)先搜索算法需要較少的空間，該算法只需要保存搜索樹的一部分，它由當前正在搜索的路徑和

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

34、環(huán)而不能給出一個答案，要么最后找到一個答案，但路徑能給出一個答案，要么最后找到一個答案，但路徑很長而且不是最優(yōu)的答案。很長而且不是最優(yōu)的答案。2021-12-1574總結(jié) n適用場合 深度優(yōu)先當一個問題有多個解答或多條解答路徑，且只須找到其中一個時；往往應對搜索深度加以限制。 寬度優(yōu)先確保搜索到最短的解答路徑。n共同優(yōu)缺點： 可直接應用一般圖搜索算法實現(xiàn)，不需要設(shè)計特別的節(jié)點排序方法，從而簡單易行，適合于許多復雜度不高的問題求解任務。 節(jié)點排序的盲目性，由于不采用領(lǐng)域?qū)ｉT知識去指導排序，往往會在白白搜索了大量無關(guān)的狀態(tài)節(jié)點后才碰到解答，所以也稱為盲目搜索。 2021-12-1575 有界深度優(yōu)

35、先搜索過程總體上按深度優(yōu)先算法方法進行，但對搜索深度需要給出一個深度限制dm，當深度達到了dm的時候，如果還沒有找到解答，就停止對該分支的搜索，換到另外一個分支進行搜索。2021-12-1576(1)把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)=0。(2)如果OPEN表為空，則問題無解，失敗并退出。(3)把OPEN表中的第一個節(jié)點取出放入CLOSE表中。并按順序冠以編號n。(4)考察節(jié)點n是否為目標節(jié)點。若是，則求得了問題的解，成功并退出。(5)如果節(jié)點n的深度d(n)= dm，則轉(zhuǎn)第(2)步。(6)如果節(jié)點n不可擴展，則轉(zhuǎn)第(2)步。(7)擴展節(jié)點n。將其子節(jié)點放入OPEN表的首部

36、，并為其配置指向父節(jié)點的指針。然后轉(zhuǎn)第(2)步。有限深度優(yōu)先搜索的搜索過程如下有限深度優(yōu)先搜索的搜索過程如下 ：2021-12-1577策略說明: n（1）深度限制dm很重要。 當問題有解，且解的路徑長度小于或等于dm時，則搜索過程一定能夠找到解，但是和深度優(yōu)先搜索一樣這并不能保證最先找到的是最優(yōu)解。 但是當dm取得太小，解的路徑長度大于dm時，則搜索過程中就找不到解，即這時搜索過程甚至是不完備的。2021-12-1578（2）深度限制dm不能太大。 當dm太大時，搜索過程會產(chǎn)生過多的無用節(jié)點，既浪費了計算機資源，又降低了搜索效率。（3）有界深度搜索的主要問題是深度限制值dm的選取。 2021

37、-12-1579改進方法： （迭代加深搜索） 先任意給定一個較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結(jié)束；如在此限制內(nèi)沒有找到問題的解，則增大深度限制dm，繼續(xù)搜索。2021-12-1580n迭代加深搜索，試圖嘗試所有可能的深度限制：n首先深度為0，n然后深度為1，n然后為2，等等。n如果初始深度為0，則該算法只生成根節(jié)點，并檢測它。n如果根節(jié)點不是目標，則深度加1，通過典型的深度優(yōu)先算法，生成深度為1的樹。n當深度限制為m時，樹的深度為m。 2021-12-1581n迭代加深搜索看起來會很浪費，因為很多節(jié)點都可能擴展多次。n然而對于很多問題，這種多次的擴展負

38、擔實際上很小，直覺上可以想象，如果一棵樹的分支系數(shù)很大，幾乎所有的節(jié)點都在最底層上，則對于上面各層節(jié)點擴展多次對整個系統(tǒng)來說影響不是很大。 2021-12-1582n表注：b是分支系數(shù)，d是解答的深度，m是搜索樹的最大深度，l是深度限制。2021-12-1583n寬度優(yōu)先搜索、深度優(yōu)先搜索和迭代加深搜索都可以用于生成和測試算法。n寬度優(yōu)先搜索需要指數(shù)數(shù)量的空間，深度優(yōu)先搜索的空間復雜度和最大搜索深度呈線性關(guān)系。 2021-12-1584n迭代加深搜索對一棵深度受控的樹采用深度優(yōu)先的搜索。它結(jié)合了寬度優(yōu)先和深度優(yōu)先搜索的優(yōu)點。n和寬度優(yōu)先搜索一樣，它是最優(yōu)的，也是完備的。但對空間要求和深度優(yōu)先搜

39、索一樣是適中的。 2021-12-1585（2）一般圖搜索算法n常用的簡單方式：n深度優(yōu)先n寬度優(yōu)先n【缺點：節(jié)點排序的盲目性】n在白白搜索了大量無關(guān)的狀態(tài)節(jié)點后才碰到解答，效率低n提高一般圖搜索效率的關(guān)鍵n優(yōu)化OPEN表中節(jié)點的排序方式盲目搜索盲目搜索2021-12-1586586427031586407321586427310506487321586470321586047321560487321056487321567480321567481320567408321586427301125634最理想情況：最理想情況：每次排序后每次排序后OPEN表表表首元素表首元素n n總在解答路徑上總

40、在解答路徑上2021-12-1587n啟發(fā)式知識指導OPEN表排序的一般圖搜索：n全局排序?qū)PEN表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首。nA算法， A*算法（掌握?。﹏局部排序僅對新擴展出來的子節(jié)點排序，使這些新節(jié)點中最有希望者能優(yōu)先取出考察和擴展；n爬山法（了解，對深度優(yōu)先法的改進）；2021-12-1588n【基本思想】n設(shè)計體現(xiàn)啟發(fā)式知識的評價函數(shù)f(n)；n指導一般圖搜索中OPEN表待擴展節(jié)點的排序：n【評價函數(shù)f(n)=g(n)+h(n) （掌握） 】nn-搜索圖G中的節(jié)點；nf(n)- G中從初始狀態(tài)節(jié)點s，經(jīng)由節(jié)點n到達目標節(jié)點ng，估計的最小路徑代價；ng(n)- G

41、中從s到n，目前實際的路徑代價；nh(n)-從n到ng，估計的最小路徑代價；2021-12-1589Snng搜索圖搜索圖G Gh(n): n-ng的估計最小路徑代價的估計最小路徑代價 g(n):s-n的實際路徑代價的實際路徑代價 f(n):s-n-ng的的估計估計最小路徑代價最小路徑代價 2021-12-1590n【評價函數(shù)f(n)=g(n)+h(n) （掌握） 】nn-搜索圖G中的節(jié)點；nf(n)- G中從s經(jīng)n到ng，估計的最小路徑代價；ng(n)- G中從s到n，目前實際的路徑代價；nh(n)-從n到ng，估計的最小路徑代價； nh(n)值-依賴于啟發(fā)式知識加以計算；nh(n)稱為啟發(fā)式

42、函數(shù)（掌握意義?。如何用評價函數(shù)來實現(xiàn)A算法? （ 掌握?。?2021-12-1591nA算法的設(shè)計與一般圖搜索相同，劃分為二個階段：n1、初始化 n建立只包含初始狀態(tài)節(jié)點s的搜索圖G:=snOPEN:=snCLOSE:= n2、搜索循環(huán)nMOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點n n擴展出n的子節(jié)點,插入搜索圖G和OPEN表 n適當?shù)臉擞浐托薷闹羔槪ㄗ庸?jié)點父節(jié)點）n排序OPEN表（評價函數(shù)f(n)的值排序）n通過循環(huán)地執(zhí)行該算法，搜索圖會因不斷有新節(jié)點加入而逐步長大，直到搜索到目標節(jié)點。2021-12-1592n算法A的設(shè)計與一般圖搜索類似，劃分為二個階段：n1、初始化

43、n2、搜索循環(huán)nMOVE-FIRST(OPEN)-取出OPEN表首的節(jié)點n n擴展出n的子節(jié)點,插入搜索圖G和OPEN表 n對每個子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni)n適當?shù)臉擞浐托薷闹羔槪ㄗ庸?jié)點父節(jié)點）n排序OPEN表（評價函數(shù)f(n)的值排序）2021-12-1593n擴展出n的子節(jié)點,插入搜索圖G和OPEN表 n對每個子節(jié)點ni,計算f(n,ni)=g(n,ni)+h(ni)n適當?shù)臉擞浐托薷闹羔槪ㄗ庸?jié)點父節(jié)點）n(i)全新節(jié)點：f(ni)=f(n,ni)n(ii)已出現(xiàn)在OPEN表中的節(jié)點n(iii)已出現(xiàn)的CLOSE表中的節(jié)點nIF f(ni)f(n,ni) T

44、HENn 修改指針指向新父結(jié)點nn f(ni)=f(n,ni)n排序OPEN表（f(n)值從小到大排序）2021-12-15942.若OPEN表是空表，則失敗退出；算法算法A3.3.選擇選擇OPENOPEN表上的第一表上的第一個節(jié)點，把它從個節(jié)點，把它從OPENOPEN表表移出并放進移出并放進CLOSECLOSE表中，表中，稱此節(jié)點為節(jié)點稱此節(jié)點為節(jié)點n n； 1.建立一個只包含起始節(jié)只包含起始節(jié)點點S S的搜索圖G,把S放到一個叫OPEN的未擴展節(jié)點表中；建立一個叫做CLOSE的已擴展節(jié)點表，其初始為空表；5.擴展節(jié)點n，同時生成不是n的祖先的那些子節(jié)點的集合M,把M的這些成員作為n的后繼節(jié)

45、點添入圖G中；對于對于MM中每個中每個子節(jié)點子節(jié)點n ni i, ,計算計算f(n,f(n,n ni i) = ) = g(n,ng(n,ni i) + h(n) + h(ni i); );4.若n為一目標節(jié)點，則有解成功退出，此解是追蹤圖G中沿著指針從n到S這條路徑而得到的；2021-12-15956.6.對那些未曾在對那些未曾在G G中出現(xiàn)過的中出現(xiàn)過的MM成員（全新結(jié)點）設(shè)置一個成員（全新結(jié)點）設(shè)置一個通向通向n n的指針。把的指針。把MM的這些成的這些成員加進員加進OPENOPEN表。對已經(jīng)在表。對已經(jīng)在OPENOPEN表上的每一個表上的每一個MM成員，成員，比較子節(jié)點比較子節(jié)點n n

46、i i經(jīng)由新、老父節(jié)經(jīng)由新、老父節(jié)點的評價函數(shù)值點的評價函數(shù)值f(n,nf(n,ni i) )、f(nf(ni i); );若若f(n,nf(n,ni i) f(n) =g*(n)nh(n)盡可能靠近h*(n) A算法的關(guān)鍵。2021-12-15114n4)改進啟發(fā)式函數(shù)八數(shù)碼游戲nf(n)=d(n)+w(n),其中nw(n)-表示錯位的棋牌個數(shù)，不夠貼切，錯誤的擴展了節(jié)點d；np(n)-節(jié)點n與目標狀態(tài)節(jié)點比較，錯位棋牌在不受阻攔的情況下，移動到目標狀態(tài)相應位置所需走步（移動次數(shù)）的總和；np(n)比w(n)更接近于h*(n)-p(n)不僅考慮了棋牌的錯位因素，還考慮了錯位的距離（移動距離）

47、2021-12-151154)改進啟發(fā)式函數(shù)八數(shù)碼游戲nf(s)計算實例初始布局初始布局s目標布局目標布局ngw(s):錯位的棋牌個數(shù)錯位的棋牌個數(shù)d(s):當前節(jié)點深度當前節(jié)點深度 f(s)0 4 4 p(s):錯位棋牌移動距離錯位棋牌移動距離d(s):當前節(jié)點深度當前節(jié)點深度 f(s)0 5 5 1 1 1 2 2021-12-15116)5(586427301s初始化初始化OPEN:=s5 CLOSE:= 2021-12-15117)5(586427301s)7(586427031a)5(586407321b)7(586427310c循環(huán)循環(huán)1CLOSE:=s5 OPEN:=a b c

48、OPEN:=a7 b5 c7 OPEN:=b5 a7 c7 2021-12-15118)5(586427301s)7(586427031a)5(586407321b)7(586427310c)5(506487321e)7(586470321d)7(586047321i循環(huán)循環(huán)2CLOSE:=s5 b5 OPEN:=a7 c7 d e i OPEN:=a7 c7 d7 e5 i7 OPEN:=e5 a7 c7 d7 i7 2021-12-15119)4(586427301s循環(huán)循環(huán)3)7(586427031a)5(586407321b)7(586427310c)5(506487321e)7(58

49、6470321d)7(586047321i)5(560487321l)7(056487321mCLOSE:=s5 b5 e5 OPEN:=a7 c7 d7 i7 l m OPEN:=a7 c7 d7 i7 l5 m7 OPEN:=l5 a7 c7 d7 i7 m7 2021-12-15120)5(567480321nCLOSE:=s5,b5,e5,l5 循環(huán)循環(huán)4)4(586427301s)7(586427031a)5(586407321b)7(586427310c)5(506487321e)7(586470321d)7(586047321i)5(560487321l)7(056487321m

50、OPEN:=a7 c7 d7 i7 m7 n OPEN:=a7 c7 d7 i7 m7 n5 OPEN:=n5 a7 c7 d7 i7 m7 2021-12-15121)5(567480321nCLOSE:=s5,b5,e5,l5,n5 循環(huán)循環(huán)5)4(586427301s)7(586427031a)5(586407321b)7(586427310c)5(506487321e)7(586470321d)7(586047321i)5(560487321l)7(056487321mOPEN:=a7 c7 d7 i7 m7 o g )7(567481320o)5(567408321gOPEN:=a7

51、 c7 d7 i7 m7 o7 g5 OPEN:=g5 a7 c7 d7 i7 m7 o7 2021-12-15122循環(huán)循環(huán)6成功結(jié)束成功結(jié)束)5(567480321n)4(586427301s)7(586427031a)5(586407321b)7(586427310c)5(506487321e)7(586470321d)7(586047321i)5(560487321l)7(056487321m)7(567481320o)5(567408321g最理想搜索圖最理想搜索圖G2021-12-15123)6(586471320j)8(580476321k避免了錯誤選擇避免了錯誤選擇)5(567

52、480321n)4(586427301s)7(586427031a)5(586407321b)7(586427310c)5(506487321e)7(586470321d)7(586047321i)5(560487321l)7(056487321m)7(567481320o)5(567408321g2021-12-15124n5) A*算法定義：n1、在A算法中，規(guī)定h(n)h*(n);n2、經(jīng)如此限制以后的A算法就是A*算法。nA*算法是可采納的，即總能搜索到最短解答路徑n【回顧：八數(shù)碼游戲的h(n)】nw(n)-錯位的棋牌個數(shù)np(n)-錯位棋牌在不受阻攔的情況下，移動到目標狀態(tài)相應位置所

53、需走步（移動次數(shù)）的總和；2021-12-15125n5) A*算法定義：n1、在A算法中，規(guī)定h(n)h*(n);n2、經(jīng)如此限制以后的A算法就是A*算法。nA*算法是可采納的，即總能搜索到最短解答路徑n證明：n1）如果存在一條從初始狀態(tài)到目標狀態(tài)的解答路徑，則一定存在一條最短解答通路；n2）設(shè)狀態(tài)n是最短解答路徑上的一個狀態(tài)，那么經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點；n3）因為最短解答路徑只有有限個節(jié)點n，所以有限步后算法必然因到達目標狀態(tài)ng。這就是最優(yōu)解。n證明完畢。2021-12-15126n5)滿足可采納性條件的算法A*算法n證明：n2）設(shè)狀態(tài)n是最短解答路徑上的一個狀

54、態(tài)，那么經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點；nf(n)=g(n)+h(n)n根據(jù)假設(shè)，n在最短解答路徑上n 經(jīng)過有限步驟后，g(n)= g*(n)nf(n)=g*(n)+h(n)n h(n)h*(n)nf(n)=g*(n)+h(n) g*(n)+h*(n)=f*(n)n f*(n)= f*(ng)n f(n) f*(ng)2021-12-15127n5)滿足可采納性條件的算法A*算法n證明：n2）設(shè)狀態(tài)n是最短解答路徑上的一個狀態(tài)，那么經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點；n設(shè)OPEN表中n之前的節(jié)點只有有限個，設(shè)為N個，其中估計值最小者為a1，并稱之為第一代節(jié)點；由

55、第一代節(jié)點生成的節(jié)點稱為第二代節(jié)點，其中估計值最小者為a2；na2a1+e(其中，e0，表示每擴展一次起碼的代價)n擴展j代后， aj a1+(j-1)en當j足夠大時一定有aj f*(ng)nf(n) f*(ng)且OPEN表中n之前的節(jié)點經(jīng)過j次擴展后的最小估計值aj f*(ng) f(n) n經(jīng)過有限步后，n必然會成為OPEN表的第一個節(jié)點2021-12-151282.啟發(fā)式函數(shù)的強弱及其影響nh(n)接近h*(n)的程度衡量啟發(fā)式函數(shù)的強弱nh(n)h*(n)，h(n)過強，A算法失去可采納性，不能確保找到最短解答路徑；nh(n)=h*(n)是最理想的， OPEN表中節(jié)點排序沒有誤差，

56、可以確保產(chǎn)生最小的搜索圖，搜索到最短解答路徑；n無法設(shè)計nA*算法搜索問題解答的關(guān)鍵nh(n)在滿足h(n) h*(n)的條件下，越大越好！2021-12-151292.啟發(fā)式函數(shù)的強弱及其影響n定理：解決同一問題的兩個A*算法A1和A2，n若h1(n) h2(n) h*(n)且g1(n)=g2(n)n則t(A1) t(A2)n其中，h1、h2分別是算法A1、A2的啟發(fā)式函數(shù)，t指示相應算法到達目標狀態(tài)時搜索圖含的節(jié)點總數(shù)。n【證明： 人工智能 上冊陸汝鈐 P250）】n八數(shù)碼游戲：w(n)p(n) h*(n)np(n)擴展出的節(jié)點總數(shù)t(w(n)2021-12-15130 n由于A*算法把所

57、有生成的節(jié)點保存在內(nèi)存中，所以A*算法在耗盡計算時間之前一般早已經(jīng)把空間耗盡了。n目前開發(fā)了一些新的算法，它們的目的是為了克服空間問題。n但一般不滿足最優(yōu)性或完備性，如迭代加深A*算法IDA*、簡化內(nèi)存受限A*算法SMA*等。n下面簡單介紹IDA*算法。 2021-12-15131n迭代加深搜索算法，它以深度優(yōu)先的方式在有限制的深度內(nèi)搜索目標節(jié)點。n在每個深度上，該算法在每個深度上檢查目標節(jié)點是否出現(xiàn)，如果出現(xiàn)則停止，否則深度加1繼續(xù)搜索。n而A*算法是選擇具有最小估價函數(shù)值的節(jié)點擴展。2021-12-15132n迭代加深A* 搜索算法IDA*是上述兩種算法的結(jié)合。n這里啟發(fā)式函數(shù)用做深度的限

58、制，而不是選擇擴展節(jié)點的排序。2021-12-15133迭代加深迭代加深A*算法算法Procedure IDA*算法算法Begin (1) 初始化當前的深度限制初始化當前的深度限制c=1 (2) 把初始節(jié)點壓入棧把初始節(jié)點壓入棧; 并假定并假定 (3) While 棧不空橋棧不空橋do Begin 彈出棧頂元素彈出棧頂元素n If n=goal, Then 結(jié)束結(jié)束, 返回返回n以及從初始節(jié)點到以及從初始節(jié)點到n的路徑的路徑 Else do Begin For n 的每個子節(jié)點的每個子節(jié)點 If , Then 把把 壓入棧壓入棧 Else End for End End While (4) I

59、f 棧為空并且棧為空并且 , Then 停止并退出停止并退出 (5) If 棧為空并且棧為空并且 , Then , 并返回并返回2 End cncnf)(n)(,min(nfcc c ccc2021-12-15134nIDAIDA* *算法和算法和A A* *算法相比，主要優(yōu)點是對于內(nèi)存算法相比，主要優(yōu)點是對于內(nèi)存的需求。的需求。A A* *算法需要指數(shù)級數(shù)量的存儲空間，算法需要指數(shù)級數(shù)量的存儲空間，因為沒有深度方面的限制。而因為沒有深度方面的限制。而IDAIDA* *算法只有當算法只有當節(jié)點節(jié)點n n的所有子節(jié)點的所有子節(jié)點 的的 小于限制值小于限制值c c時才時才擴展它擴展它, ,這樣就可

60、以節(jié)省大量的內(nèi)存。這樣就可以節(jié)省大量的內(nèi)存。n另一問題是當啟發(fā)式函數(shù)是最優(yōu)的時候，另一問題是當啟發(fā)式函數(shù)是最優(yōu)的時候，IDAIDA* *算法和算法和A A* *算法擴展相同的節(jié)點，并且可以找到算法擴展相同的節(jié)點，并且可以找到最優(yōu)路徑。最優(yōu)路徑。n)(nf2021-12-15135n啟發(fā)式知識指導OPEN表排序的一般圖搜索：n全局排序?qū)PEN表中的所有節(jié)點排序，使最有希望的節(jié)點排在表首。nA算法， A*算法n局部排序僅對新擴展出來的子節(jié)點排序，使這些新節(jié)點中最有希望者能優(yōu)先取出考察和擴展；n爬山法（對深度優(yōu)先法的改進）；2021-12-15136 簡單的搜索策略： g(n)0, f(n)= h