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

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

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

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

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

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

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

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

9、點和目標節點分別代表產生式系統的初始數據庫和滿足終止條件的數據庫。n方法：把問題的初始狀態作為當前狀態，選擇適用的算符對其進行操作，生成一組子狀態，檢查目標狀態是否在其中出現。若出現，則搜索成功，找到了問題的解；若不出現，則按某種搜索策略從已生成的狀態中再選一個狀態作為當前狀態。重復上述過程，直到目標狀態出現或者不再有可供操作的狀態及算符時為止。 2021-12-1513 n三個錢幣可能出現的狀態有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三枚錢幣問題的狀態空間圖三枚錢幣問題的狀態空間圖 2021-12-1515nS問題求解（即搜索）過程中所有可能到達的合法狀態構成的集合；nO操作算子的集合，操作算子的執行會導致問題狀態的變遷 ；n狀態用于記載問題求解（即搜索）過程中某一時刻問題現狀的快照；n抽象為矢量形式 Q=q0,q1,qnTn每個元素qi稱為狀態分量 n給定每個狀態分量qi的值就得到一個具體的狀態 Qk=q0k,q1k,qnkT2021-12-1516狀態狀態表示狀態的變遷表示狀態的變遷操作算子操作算子問題的狀態空間問題的狀態空間是一個表示該問題的全部可能狀態是一個表示該問題的全部可能狀態及其變遷的及其變

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

12、3,3,0)2021-12-1520(2)狀態空間表示的經典例子“傳教士和野人問題”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八個數碼，每個數碼占一格，且有一個空格。這些八個數碼，每個數碼占

13、一格，且有一個空格。這些數碼可在棋盤上移動，其移動規則是：與空格相鄰數碼可在棋盤上移動，其移動規則是：與空格相鄰的數碼方可移入空格。的數碼方可移入空格。現在的現在的問題問題是：對于指定的是：對于指定的初始棋局初始棋局和和目標棋局目標棋局，給出給出數碼的移動序列數碼的移動序列。該問題稱為。該問題稱為八數碼問題八數碼問題。 2831476581324765初始棋局初始棋局目標棋局目標棋局移動數碼移動數碼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一個狀態可以有多個可供選擇的操作算子；n操作算子間的選擇是一種“或”的關系;n這樣的有向圖稱為或圖。2021-12-1527n或

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

16、法2021-12-1529n算法劃分為二個階段：n1、初始化 n建立只包含初始狀態節點s的搜索圖G:=snOPEN:=snCLOSE:= n2、搜索循環nMOVE-FIRST(OPEN)-取出OPEN表首的節點n作為擴展的節點，同時將其移到close表 n擴展出n的子節點,插入搜索圖G和OPEN表 n適當的標記和修改指針n排序OPEN表n通過循環地執行該算法，搜索圖G會因不斷有新節點加入而逐步長大，直到搜索到目標節點。 一般圖搜索算法2021-12-1530初始布局初始布局目標布局目標布局移動數碼移動數碼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節點n擴展后的子節點分為3類：n(i)全新節點n(ii)已出現在OPEN表中的節點n(iii)已出現的CLOSE表中的節點n指針標記和修改的方法：n(i)類節點：加入OPEN表，建立從子節點到父節點n的指針n(ii)類節點、 (iii)類節點n比較經由老父節點、新父節點n到達初始狀態節點的路徑代價 n經由節點n的代價比較小，則移動子節點指向老父節點的指針，改為指向新父節點nn (iii)類節點還得從CLOSE表中移出，重新加入OPEN表。搜索過程中的

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

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

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

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

28、節點距離初始節點較遠時會產生許多無用的節點，搜索效率低。n寬度優先搜索中，時間需求是一個很大的問題，特別是當搜索的深度比較大時，尤為嚴重，但是空間需求是比執行時間更嚴重的問題。 寬度優先搜索優點：目標節點如果存在，用寬度優先搜索算法總可以找到該目標節點，而且是最小（即最短路徑）的節點。寬度優先搜索的優點和缺點2021-12-1563nOPEN表中節點簡單的排序方式：n深度優先擴展當前節點后生成的子節點總是置于OPEN表的前端，即OPEN表作為棧，后進先出，使搜索優先向縱深方向發展。2021-12-1564深度優先深度優先實例實例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深度優先搜索n在深度優先搜索中，首先擴展最新產生的(最深的)節點，深度 相等的節點可以任意排列。n“最晚產生的節點最先擴展” 起始節點深度為0 任何其他節點的深度等于其父輩節點深度加上1 :dn=dn-1+12021-12-1566深度優先搜索很明顯這樣做，不一定找到最佳解，而且由于深度的限制，可能找不到解，然而，若不加深度限制，可能沿著一條路線無限制地擴展下去，這當然是不允許的。為保證找到解，應選擇適當的深度界限，或者采取不斷加大深度界限的辦法，反復搜索，直到找到解。這種改進的方法叫做迭代加深搜索。2021-12-15671)把初始節點把初始節點S0放入放入OPEN表；

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

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

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

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

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

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

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

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

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

40、在解答路徑上2021-12-1587n啟發式知識指導OPEN表排序的一般圖搜索：n全局排序對OPEN表中的所有節點排序，使最有希望的節點排在表首。nA算法， A*算法（掌握！）n局部排序僅對新擴展出來的子節點排序，使這些新節點中最有希望者能優先取出考察和擴展；n爬山法（了解，對深度優先法的改進）；2021-12-1588n【基本思想】n設計體現啟發式知識的評價函數f(n)；n指導一般圖搜索中OPEN表待擴展節點的排序：n【評價函數f(n)=g(n)+h(n) （掌握） 】nn-搜索圖G中的節點；nf(n)- G中從初始狀態節點s，經由節點n到達目標節點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【評價函數f(n)=g(n)+h(n) （掌握） 】nn-搜索圖G中的節點；nf(n)- G中從s經n到ng，估計的最小路徑代價；ng(n)- G中從s到n，目前實際的路徑代價；nh(n)-從n到ng，估計的最小路徑代價； nh(n)值-依賴于啟發式知識加以計算；nh(n)稱為啟發式

42、函數（掌握意義！）。n如何用評價函數來實現A算法? （ 掌握！） 2021-12-1591nA算法的設計與一般圖搜索相同，劃分為二個階段：n1、初始化 n建立只包含初始狀態節點s的搜索圖G:=snOPEN:=snCLOSE:= n2、搜索循環nMOVE-FIRST(OPEN)-取出OPEN表首的節點n n擴展出n的子節點,插入搜索圖G和OPEN表 n適當的標記和修改指針（子節點父節點）n排序OPEN表（評價函數f(n)的值排序）n通過循環地執行該算法，搜索圖會因不斷有新節點加入而逐步長大，直到搜索到目標節點。2021-12-1592n算法A的設計與一般圖搜索類似，劃分為二個階段：n1、初始化

43、n2、搜索循環nMOVE-FIRST(OPEN)-取出OPEN表首的節點n n擴展出n的子節點,插入搜索圖G和OPEN表 n對每個子節點ni,計算f(n,ni)=g(n,ni)+h(ni)n適當的標記和修改指針（子節點父節點）n排序OPEN表（評價函數f(n)的值排序）2021-12-1593n擴展出n的子節點,插入搜索圖G和OPEN表 n對每個子節點ni,計算f(n,ni)=g(n,ni)+h(ni)n適當的標記和修改指針（子節點父節點）n(i)全新節點：f(ni)=f(n,ni)n(ii)已出現在OPEN表中的節點n(iii)已出現的CLOSE表中的節點nIF f(ni)f(n,ni) T

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

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

46、i i經由新、老父節經由新、老父節點的評價函數值點的評價函數值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算法的關鍵。2021-12-15114n4)改進啟發式函數八數碼游戲nf(n)=d(n)+w(n),其中nw(n)-表示錯位的棋牌個數，不夠貼切，錯誤的擴展了節點d；np(n)-節點n與目標狀態節點比較，錯位棋牌在不受阻攔的情況下，移動到目標狀態相應位置所需走步（移動次數）的總和；np(n)比w(n)更接近于h*(n)-p(n)不僅考慮了棋牌的錯位因素，還考慮了錯位的距離（移動距離）

47、2021-12-151154)改進啟發式函數八數碼游戲nf(s)計算實例初始布局初始布局s目標布局目標布局ngw(s):錯位的棋牌個數錯位的棋牌個數d(s):當前節點深度當前節點深度 f(s)0 4 4 p(s):錯位棋牌移動距離錯位棋牌移動距離d(s):當前節點深度當前節點深度 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循環循環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循環循環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循環循環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 循環循環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 循環循環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循環循環6成功結束成功結束)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算法中，規定h(n)h*(n);n2、經如此限制以后的A算法就是A*算法。nA*算法是可采納的，即總能搜索到最短解答路徑n【回顧：八數碼游戲的h(n)】nw(n)-錯位的棋牌個數np(n)-錯位棋牌在不受阻攔的情況下，移動到目標狀態相應位置所

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

54、態，那么經過有限步后，n必然會成為OPEN表的第一個節點；nf(n)=g(n)+h(n)n根據假設，n在最短解答路徑上n 經過有限步驟后，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）設狀態n是最短解答路徑上的一個狀態，那么經過有限步后，n必然會成為OPEN表的第一個節點；n設OPEN表中n之前的節點只有有限個，設為N個，其中估計值最小者為a1，并稱之為第一代節點；由

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

56、可以確保產生最小的搜索圖，搜索到最短解答路徑；n無法設計nA*算法搜索問題解答的關鍵nh(n)在滿足h(n) h*(n)的條件下，越大越好！2021-12-151292.啟發式函數的強弱及其影響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的啟發式函數，t指示相應算法到達目標狀態時搜索圖含的節點總數。n【證明： 人工智能 上冊陸汝鈐 P250）】n八數碼游戲：w(n)p(n) h*(n)np(n)擴展出的節點總數t(w(n)2021-12-15130 n由于A*算法把所

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

58、制，而不是選擇擴展節點的排序。2021-12-15133迭代加深迭代加深A*算法算法Procedure IDA*算法算法Begin (1) 初始化當前的深度限制初始化當前的深度限制c=1 (2) 把初始節點壓入棧把初始節點壓入棧; 并假定并假定 (3) While 棧不空橋棧不空橋do Begin 彈出棧頂元素彈出棧頂元素n If n=goal, Then 結束結束, 返回返回n以及從初始節點到以及從初始節點到n的路徑的路徑 Else do Begin For n 的每個子節點的每個子節點 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* *算法相比，主要優點是對于內存算法相比，主要優點是對于內存的需求。的需求。A A* *算法需要指數級數量的存儲空間，算法需要指數級數量的存儲空間，因為沒有深度方面的限制。而因為沒有深度方面的限制。而IDAIDA* *算法只有當算法只有當節點節點n n的所有子節點的所有子節點 的的 小于限制值小于限制值c c時才時才擴展它擴展它, ,這樣就可

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