圖搜索與問題求解

1、第第3 3章章 圖搜索與問題求解圖搜索與問題求解2022-3-6人工智能2推理與搜索推理與搜索n圖搜索技術是人工智能的核心技術之一。圖搜索技術是人工智能的核心技術之一。n任一搜索過程也都是一個推理過程。任一搜索過程也都是一個推理過程。n隱式圖的搜索過程是一種利用局部性知識構隱式圖的搜索過程是一種利用局部性知識構造全局性答案的過程。造全局性答案的過程。n在各種搜索過程中，人工智能最感興趣的是在各種搜索過程中，人工智能最感興趣的是那些具有很強選擇性的啟發(fā)式方法，即那些那些具有很強選擇性的啟發(fā)式方法，即那些利用很局部的狀態(tài)空間可以有效地找到問題利用很局部的狀態(tài)空間可以有效地找到問題的解的方法。的解的

2、方法。n機器學習等很多過程都是在假設空間中搜索機器學習等很多過程都是在假設空間中搜索目標的過程。目標的過程。2022-3-6人工智能3第第3 3章章 圖搜索與問題求解圖搜索與問題求解3.1 3.1 狀態(tài)圖知識表示狀態(tài)圖知識表示（狀態(tài)圖搜索問題求解）（狀態(tài)圖搜索問題求解）3.2 3.2 狀態(tài)圖搜索狀態(tài)圖搜索3.3 3.3 與或圖知識表示與或圖知識表示（與或圖搜索問題求解（與或圖搜索問題求解 ）3.4 3.4 與或圖搜索與或圖搜索3.5 3.5 博弈樹搜索博弈樹搜索2022-3-6人工智能43.1 3.1 狀態(tài)圖知識表示狀態(tài)圖知識表示3.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間狀態(tài)、操作和狀態(tài)空間

3、3.1.2 3.1.2 修道士和野人的狀態(tài)空間修道士和野人的狀態(tài)空間3.1.3 3.1.3 梵塔問題的狀態(tài)空間梵塔問題的狀態(tài)空間3.1.4 3.1.4 重排九宮問題和隱式圖重排九宮問題和隱式圖3.1.5 3.1.5 問題求解的基本框架問題求解的基本框架2022-3-6人工智能53.1.13.1.1狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（1 1）例例3.13.1走迷宮走迷宮走迷宮問題就是從該有向圖的初始節(jié)點出發(fā)，走迷宮問題就是從該有向圖的初始節(jié)點出發(fā)，尋找目尋找目標節(jié)點標節(jié)點的問題，或者是的問題，或者是尋找尋找通向目標節(jié)點的通向目標節(jié)點的路徑路徑問題。問題。2022-3-6人工智能63.1.

4、1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（2 2）例例3.23.2八數碼難題八數碼難題( (重排九宮問題重排九宮問題) ) 2 83147 6512384765初始棋局目標棋局以上兩個問題抽象來看，都是某個有向圖中尋找目標以上兩個問題抽象來看，都是某個有向圖中尋找目標或路徑的問題，在人工智能技術中，把這種描述問題或路徑的問題，在人工智能技術中，把這種描述問題的有向圖稱為的有向圖稱為狀態(tài)空間圖，狀態(tài)空間圖，簡稱簡稱狀態(tài)圖狀態(tài)圖。棋局作為節(jié)點，相鄰節(jié)點通過移動數碼一個一個產生棋局作為節(jié)點，相鄰節(jié)點通過移動數碼一個一個產生出來，所有節(jié)點由它們的相鄰關系連成一個有向圖。出來，所有節(jié)點

5、由它們的相鄰關系連成一個有向圖。2022-3-6人工智能73.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（3 3）n狀態(tài)狀態(tài)（StateState）p62p62n為了描述某一類事物中各個不同事物之間為了描述某一類事物中各個不同事物之間的差異而引入的最少的一組變量的差異而引入的最少的一組變量q q的有序的有序組合，表征了問題的特征和結構。組合，表征了問題的特征和結構。n表示成矢量形式：表示成矢量形式：n狀態(tài)在狀態(tài)圖中表示為狀態(tài)在狀態(tài)圖中表示為節(jié)點節(jié)點。T210210Q，qqqqqq2022-3-6人工智能83.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（4

6、 4）n狀態(tài)轉換規(guī)則（操作狀態(tài)轉換規(guī)則（操作 operatoroperator）n引起狀態(tài)中某些分量發(fā)生改變，從而使一個引起狀態(tài)中某些分量發(fā)生改變，從而使一個具體狀態(tài)變化到另一個具體狀態(tài)的作用。具體狀態(tài)變化到另一個具體狀態(tài)的作用。n它可以是一個機械性的步驟、過程、規(guī)則或它可以是一個機械性的步驟、過程、規(guī)則或算子。算子。n操作描述了狀態(tài)之間的關系。操作描述了狀態(tài)之間的關系。n狀態(tài)轉換規(guī)則在狀態(tài)圖中表示為狀態(tài)轉換規(guī)則在狀態(tài)圖中表示為邊邊。在程序。在程序中狀態(tài)轉換規(guī)則可用數據對、條件語句、規(guī)中狀態(tài)轉換規(guī)則可用數據對、條件語句、規(guī)則、函數、過程等表示。則、函數、過程等表示。2022-3-6人工智能93

7、.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（5 5）n狀態(tài)空間（狀態(tài)空間（State SpaceState Space）n問題的狀態(tài)空間是一個表示該問題全部的可問題的狀態(tài)空間是一個表示該問題全部的可能狀態(tài)及相互關系的圖。能狀態(tài)及相互關系的圖。n狀態(tài)空間一般用賦值有向圖表示，記為：狀態(tài)空間一般用賦值有向圖表示，記為： （S S，F F，G G）nS S：問題的可能有的初始狀態(tài)的集合；：問題的可能有的初始狀態(tài)的集合；nF F：操作的集合；：操作的集合；nG G：目標狀態(tài)的集合。：目標狀態(tài)的集合。2022-3-6人工智能103.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操

8、作和狀態(tài)空間（6 6）n狀態(tài)空間中問題求解狀態(tài)空間中問題求解n在狀態(tài)空間表示法中，問題求解過程轉化為在圖中在狀態(tài)空間表示法中，問題求解過程轉化為在圖中尋找從初始狀態(tài)尋找從初始狀態(tài)Q Qs s出發(fā)到達目標狀態(tài)出發(fā)到達目標狀態(tài)Q Qg g的路徑問題，的路徑問題，也就是尋找操作序列的問題。也就是尋找操作序列的問題。n狀態(tài)空間的解為三元組狀態(tài)空間的解為三元組 Q nQ Qs s ：某個初始狀態(tài)：某個初始狀態(tài)nQ Qg g ：某個目標狀態(tài)：某個目標狀態(tài)na a：把：把Q Qs s變換成變換成Q Qg g的有限的操作序列的有限的操作序列n狀態(tài)轉換圖狀態(tài)轉換圖S1S3S2O1O2O3O4QsQgOn2022

9、-3-6人工智能113.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（7 7）例例 3.7 3.7 迷宮問題的狀態(tài)圖表示。迷宮問題的狀態(tài)圖表示。 S：SoF：(So, S4), (S4, So), (S4, S1), (S1, S4), (S1,S2), (S2, S1), (S2, S3), (S3, S2), (S4, S7), (S7, S4), (S4, S5), (S5, S4), (S5, S6), (S6, S5), (S5, S8), (S8, S5), (S8, S9), (S9, S8), (S9, Sg)G：Sg 迷宮問題規(guī)則集描述了圖中所有節(jié)點和邊。類

10、似于迷宮問題規(guī)則集描述了圖中所有節(jié)點和邊。類似于這樣羅列出全部節(jié)點和邊的狀態(tài)圖稱為這樣羅列出全部節(jié)點和邊的狀態(tài)圖稱為顯式狀態(tài)圖顯式狀態(tài)圖，或者說或者說狀態(tài)圖狀態(tài)圖的的顯式顯式表示。表示。2022-3-6人工智能123.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（8 8）補充例補充例1 1 三枚錢幣，能否從下面狀態(tài)翻動三次后三枚錢幣，能否從下面狀態(tài)翻動三次后出現全正或全反狀態(tài)。出現全正或全反狀態(tài)。反正反正正正反反反初始狀態(tài)s目標狀態(tài)集合0, 72022-3-6人工智能133.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（9 9）引入一個三元組引入一個三元組(

11、q(q0 0,q,q1 1,q,q2 2) )來描述總狀態(tài)，錢幣正面為來描述總狀態(tài)，錢幣正面為0 0，反面，反面為為1 1，全部可能的狀態(tài)為：，全部可能的狀態(tài)為： Q Q0 0=(0,0,0)=(0,0,0) ; Q ; Q1 1=(0,0,1); Q=(0,0,1); Q2 2=(0,1,0)=(0,1,0) Q Q3 3=(0,1,1) ; Q=(0,1,1) ; Q4 4=(1,0,0); =(1,0,0); Q Q5 5=(1,0,1)=(1,0,1) Q Q6 6=(1,1,0) ; =(1,1,0) ; Q Q7 7=(1,1,1)=(1,1,1)。翻動錢幣的操作抽象為改變上述狀態(tài)

12、的算子，翻動錢幣的操作抽象為改變上述狀態(tài)的算子， 即即F Fa, b, ca, b, c a: a:把錢幣把錢幣q q0 0翻轉一次翻轉一次 b:b:把錢幣把錢幣q q1 1翻轉一次翻轉一次 c:c:把錢幣把錢幣q q2 2翻轉一次翻轉一次 問題的狀態(tài)空間為問題的狀態(tài)空間為 2022-3-6人工智能143.1.1 3.1.1 狀態(tài)、操作和狀態(tài)空間（狀態(tài)、操作和狀態(tài)空間（1010）狀態(tài)空間圖（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，0）（1，1，1）acabacabcbbc2022-3-6人工智能153.1.2 3.1.2 修道士和野人問題的狀

13、態(tài)空間（修道士和野人問題的狀態(tài)空間（1 1）補充例補充例2 2 修道士和野人問題。在河的左岸有三個修道士和野人問題。在河的左岸有三個修道士、三個野人和一條船，修道士們想用這修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但受到以下條件條船將所有的人都運過河去，但受到以下條件的限制：的限制： （1 1）修道士和野人都會劃船，但船一次）修道士和野人都會劃船，但船一次最最多多只能只能運兩個人運兩個人； （2 2）在任何岸邊）在任何岸邊野人數目野人數目都都不得超過修道不得超過修道士士，否則修道士就會被野人吃掉。，否則修道士就會被野人吃掉。 假定野人會服從任何一種過河安排，試規(guī)劃假定野

14、人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。出一種確保修道士安全過河方案。2022-3-6人工智能163.1.2 3.1.2 修道士和野人問題的狀態(tài)空間（修道士和野人問題的狀態(tài)空間（2 2）解：先建立問題的狀態(tài)空間。問題的狀態(tài)可以用解：先建立問題的狀態(tài)空間。問題的狀態(tài)可以用一個三元數組來描述：一個三元數組來描述： S S(m, c, b)(m, c, b) m m：左岸的修道士數：左岸的修道士數 c c：左岸的野人數：左岸的野人數 b b：左岸的船數：左岸的船數 右岸的狀態(tài)不必標出，因為：右岸的狀態(tài)不必標出，因為： 右岸的修道士數右岸的修道士數mm3 3m m 右岸的野人數右

15、岸的野人數cc3 3c c 右岸的船數右岸的船數b=1-bb=1-b2022-3-6人工智能173.1.2 3.1.2 修道士和野人問題的狀態(tài)空間（修道士和野人問題的狀態(tài)空間（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 1S163 3 0S241 3 0S13 2 1S91 2 1S173 2 0S251 2 0S23 1 1S101 1 1S183 1 0S261 1 0S33 0 1S111 0 1S193 0 0S271 0 0S42 3 1S120 3 1S202 3 0S28 0 3 0S52 2 1S130 2 1S21

16、2 2 0S290 2 0S62 1 1S140 1 1S222 1 0S300 1 0S72 0 1S150 0 1S232 0 0S310 0 02022-3-6人工智能183.1.2 3.1.2 修道士和野人問題的狀態(tài)空間（修道士和野人問題的狀態(tài)空間（4 4）操作集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

17、)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, 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操作符條 件動 作2022-3-6人工智能193.1.2 3.1.2 修道士和野人問題的狀態(tài)空間（修道士和野人問題的狀態(tài)空間（5 5）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)

18、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(0,2,0)p20q20S5(2,2,1)q11p112022-3-6人工智能203.1.3 3.1.3 梵塔問題的狀態(tài)空間（梵塔問題的狀態(tài)空間（1 1） 例例3.9 3.9 二階梵塔問題二階梵塔問題 一號

19、桿有一號桿有A A、B B兩個金盤，兩個金盤，A A小于小于B B。要求將。要求將ABAB移至三號桿，每次只可移動移至三號桿，每次只可移動一個盤子，任何時刻一個盤子，任何時刻B B不能在不能在A A上。上。 用二元組用二元組（S SA A，S SB B）表示狀態(tài)，表示狀態(tài)，S SA A表示表示A A所在所在桿號，桿號，S SB B表示表示B B所在桿號，全部狀態(tài)如下：所在桿號，全部狀態(tài)如下： （1 1，1 1），（），（1 1，2 2），（），（1 1，3 3） （2 2，1 1），（），（2 2，2 2），（），（2 2，3 3） （3 3，1 1），（），（3 3，2 2），（），（3 3

20、，3 3）2022-3-6人工智能213.1.3 3.1.3 梵塔問題的狀態(tài)空間（梵塔問題的狀態(tài)空間（2 2）AB123S0：（：（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）AAAAABABBBBB2022-3-6人工智能223.1.3 3.1.3 梵塔問題的狀態(tài)空間（梵塔問題的狀態(tài)空間（3 3）轉換規(guī)則：轉換規(guī)則：A A（i i，j j）表示金盤）表示金盤A A從第從第i i號桿移到號桿移到j j號桿號桿 B B（i

21、 i，j j）表示金盤）表示金盤B B從第從第i i號桿移到號桿移到j j號桿號桿 A A（1 1，2 2），），A A（1 1，3 3），）， A A（2 2，1 1） A A（2 2，3 3），），A A（3 3，1 1），）， A A（3 3，2 2） B（1 1，2 2），），B B（1 1，3 3），）， B B（2 2，1 1） B B（2 2，3 3），），B B（3 3，1 1），）， B B（3 3，2 2）初始狀態(tài)初始狀態(tài)（1 1，1 1），目標狀態(tài)，目標狀態(tài)（3 3，3 3）梵塔問題用狀態(tài)圖表示為梵塔問題用狀態(tài)圖表示為： (1,1),A(1,2),B(3,2),(3,3)

22、2022-3-6人工智能233.1.3 3.1.3 梵塔問題的狀態(tài)空間（梵塔問題的狀態(tài)空間（4 4）1,12,13,12,33,31,33,21,22,2A(1,3)A(2,1)B(3,1)A(3,2)A(1,3)B(1,3)A(2,1)B(1,2)A(3,2)2022-3-6人工智能24n n（n3n3）階梵塔問題）階梵塔問題n假設金片假設金片PkPk從小片到大片按下標從小片到大片按下標k k順序編號，順序編號，即即k=1k=1，2 2，3 3，n n，n n階梵塔問題狀態(tài)空間階梵塔問題狀態(tài)空間可用矢量表示為：可用矢量表示為： (P(P1 1, P, P2 2, P, P3 3, P, Pk

23、 k, P, Pn n) ) P Pk k表示第表示第k k個金片穿在編號為個金片穿在編號為P Pk k的寶石針上，的寶石針上， P Pk k=1=1，2 2，33n初始狀態(tài)初始狀態(tài) S S0 0=(1,1,1,1,1)=(1,1,1,1,1)n目標狀態(tài)目標狀態(tài) S Sg1g1 =(2,2,2,2,2) =(2,2,2,2,2) S Sg2g2 =(3,3,3,3,3) =(3,3,3,3,3)2022-3-6人工智能25n n（n3n3）階梵塔問題）階梵塔問題nn階梵塔問題的操作集合表示為：階梵塔問題的操作集合表示為： F=RF=Rk k(i,j) | i,j(i,j) | i,j=1,2,

24、3=1,2,3，k=1k=1，2 2，nnn全部可能狀態(tài)數為全部可能狀態(tài)數為3n個，最佳解長度為個，最佳解長度為2n-1。n三階梵塔問題狀態(tài)圖三階梵塔問題狀態(tài)圖S S0 0=(1,1,1)=(1,1,1)S Sg2g2=(3,3,3)=(3,3,3)S Sg1g1=(2,2,2)=(2,2,2)2022-3-6人工智能263.1.4 3.1.4 重排九宮問題和隱式圖（重排九宮問題和隱式圖（1 1）例例3.83.8重排九宮問題（八數碼難題）重排九宮問題（八數碼難題）X1X2X3X8X0X4X7X6X5將棋局用向量將棋局用向量A A(X(X0 0，X X1 1 ， X X2 2 ， X X3 3

25、， X X4 4 ， X X5 5 ， X X6 6 ， X X7 7 ， X X8 8) )表示，其中表示，其中X Xi i為變量，值表示方格為變量，值表示方格X Xi i內的數字。內的數字。 初始狀態(tài)初始狀態(tài) S S0 0 （0 0，2 2，8 8，3 3，4 4，5 5，6 6，7 7，1 1） 目標狀態(tài)目標狀態(tài) S Sg g （0 0，1 1，2 2，3 3，4 4，5 5，6 6，7 7，8 8）數碼的移動規(guī)則就是該問題的狀態(tài)變化規(guī)則。經分析，該問題共有數碼的移動規(guī)則就是該問題的狀態(tài)變化規(guī)則。經分析，該問題共有2424條規(guī)則，分為條規(guī)則，分為9 9組。組。2 83147 651238

26、4765初始棋局初始棋局目標棋局目標棋局2022-3-6人工智能273.1.4 3.1.4 重排九宮問題和隱式圖（重排九宮問題和隱式圖（2 2）0 0組規(guī)則組規(guī)則 r r1 1(X(X0 0=0=0 ) ) (X(X2 2=n=n ) ) X X0 0 = n = n X X2 2 =0 =0； r r2 2(X(X0 0=0=0 ) ) (X(X4 4=n=n ) ) X X0 0 = n = n X X4 4 =0 =0； r r3 3(X(X0 0=0=0 ) ) (X(X6 6=n=n ) ) X X0 0 = n = n X X6 6 =0 =0； r r4 4(X(X0 0=0=0

27、 ) ) (X(X8 8=n=n ) ) X X0 0 = n = n X X8 8 =0 =0；1 1組規(guī)則組規(guī)則 r r5 5(X(X1 1=0=0 ) ) (X(X2 2=n=n ) ) X X1 1 = n = n X X2 2 =0 =0； r r6 6(X(X1 1=0=0 ) ) (X(X8 8=n=n ) ) X X1 1 = n = n X X8 8 =0 =0；8 8組規(guī)則組規(guī)則: : r r2222(X(X8 8=0=0 ) ) (X(X1 1=n=n ) ) X X8 8 = n = n X X1 1 =0 =0； r r2323(X(X8 8=0=0 ) ) (X(X

28、0 0=n=n ) ) X X8 8 = n = n X X0 0=0=0； r r2424(X(X8 8=0=0 ) ) (X(X7 7=n=n ) ) X X8 8 = n = n X X7 7 =0 =0；2022-3-6人工智能283.1.4 3.1.4 重排九宮問題和隱式圖（重排九宮問題和隱式圖（3 3）八數碼的狀態(tài)圖可表示為八數碼的狀態(tài)圖可表示為 （SS0 0, r, r1 1 , r , r2 2 , , r , , r2424 , S , Sg g ） 八數碼問題狀態(tài)圖僅給出了初始節(jié)點八數碼問題狀態(tài)圖僅給出了初始節(jié)點和目標節(jié)點，其余節(jié)點需用狀態(tài)轉換規(guī)則和目標節(jié)點，其余節(jié)點需用狀

29、態(tài)轉換規(guī)則來產生。類似于這樣表示的狀態(tài)圖稱為來產生。類似于這樣表示的狀態(tài)圖稱為隱隱式狀態(tài)圖式狀態(tài)圖，或者說，或者說狀態(tài)圖狀態(tài)圖的的隱式表示隱式表示。2022-3-6人工智能293.1.4 3.1.4 重排九宮問題和隱式圖（重排九宮問題和隱式圖（4 4）n如何隱式的描述一個狀態(tài)空間如何隱式的描述一個狀態(tài)空間n有描述問題狀態(tài)的有關知識，包括該問題的有描述問題狀態(tài)的有關知識，包括該問題的各狀態(tài)分量的取值情況，開始條件、結束條各狀態(tài)分量的取值情況，開始條件、結束條件、各種約束條件等等。件、各種約束條件等等。n需要由任何一個狀態(tài)生成其所有直接后繼節(jié)需要由任何一個狀態(tài)生成其所有直接后繼節(jié)點的的有關知識。點

30、的的有關知識。2022-3-6人工智能303.1.4 3.1.4 重排九宮問題和隱式圖（重排九宮問題和隱式圖（5 5）例例3.10 旅行商問題旅行商問題(Traveling(TravelingSalesmanProblemSalesmanProblem，簡，簡稱稱TSP)TSP)。設有。設有n n個互相可直達的城市，某推銷商準備從個互相可直達的城市，某推銷商準備從其中的其中的A A城出發(fā)，周游各城市一遍，最后又回到城出發(fā)，周游各城市一遍，最后又回到A A城。城。要求為該推銷商規(guī)劃一條最短的旅行路線。要求為該推銷商規(guī)劃一條最短的旅行路線。 該問題的狀態(tài)為以該問題的狀態(tài)為以A A打頭的已訪問過的城

31、市序打頭的已訪問過的城市序列列:A:A S S0 0:A:A。 S Sg g:A:A, ,A,A。其中。其中“”為其余為其余n-1n-1個城市的一個序列。個城市的一個序列。狀態(tài)轉換規(guī)則：狀態(tài)轉換規(guī)則： 規(guī)則規(guī)則1 1 如果當前城市的下一個城市還未去過，則去該如果當前城市的下一個城市還未去過，則去該城市，并把該城市名排在已去過的城市名序列后端。城市，并把該城市名排在已去過的城市名序列后端。 規(guī)則規(guī)則2 2 如果所有城市都去過一次，則從當前城市返回如果所有城市都去過一次，則從當前城市返回A A城，把城，把A A也添在去過的城市名序列后端。也添在去過的城市名序列后端。2022-3-6人工智能313.

32、1.5 3.1.5 問題求解的基本框架（問題求解的基本框架（1 1）n問題求解所需要的知識問題求解所需要的知識n與描述問題的狀態(tài)有關的各種與描述問題的狀態(tài)有關的各種敘述性知識敘述性知識。n描述狀態(tài)之間的變換關系的各種描述狀態(tài)之間的變換關系的各種過程性知識過程性知識。n一般以一組一般以一組操作操作的形式出現的。任何一個操作都含有的形式出現的。任何一個操作都含有條件和動作兩部分，條件和動作兩部分，條件條件給定了操作的適用范圍，給定了操作的適用范圍，動作動作描述了由于操作而引起的狀態(tài)中某些分量的變化情形。描述了由于操作而引起的狀態(tài)中某些分量的變化情形。n描述如何根據當前狀態(tài)和目標狀態(tài)選擇合適的操描述

33、如何根據當前狀態(tài)和目標狀態(tài)選擇合適的操作的作的控制性知識控制性知識。n根據敘述性和過程性知識可以構造問題的狀態(tài)空根據敘述性和過程性知識可以構造問題的狀態(tài)空間。一般講間。一般講狀態(tài)空間狀態(tài)空間是一個賦值有向圖，節(jié)點對應是一個賦值有向圖，節(jié)點對應著問題的狀態(tài)，邊對應操作。著問題的狀態(tài)，邊對應操作。2022-3-6人工智能323.1.5 3.1.5 問題求解的基本框架（問題求解的基本框架（2 2）n問題求解問題求解就是在圖中尋找一條從初始節(jié)點到就是在圖中尋找一條從初始節(jié)點到達目標節(jié)點的通路或操作序列。達目標節(jié)點的通路或操作序列。n首先從操作集中選擇可作用在當前狀態(tài)上首先從操作集中選擇可作用在當前狀態(tài)

34、上的操作；的操作；n如果符合條件的操作有許多個，則要從挑如果符合條件的操作有許多個，則要從挑選出最有希望導致目標狀態(tài)的操作施加到當選出最有希望導致目標狀態(tài)的操作施加到當前狀態(tài)上，以便克服組合爆炸；前狀態(tài)上，以便克服組合爆炸；n如果解的長度很大，還需要更為復雜的克如果解的長度很大，還需要更為復雜的克服組合爆炸的技術。服組合爆炸的技術。2022-3-6人工智能333.2 3.2 狀態(tài)圖搜索狀態(tài)圖搜索3.2.13.2.1狀態(tài)圖搜索狀態(tài)圖搜索3.2.23.2.2窮舉式搜索窮舉式搜索3.2.33.2.3啟發(fā)式搜索啟發(fā)式搜索3.2.43.2.4加權狀態(tài)圖搜索加權狀態(tài)圖搜索3.2.53.2.5啟發(fā)式圖搜索的

35、啟發(fā)式圖搜索的A A算法和算法和A A* *算法算法3.2.63.2.6狀態(tài)圖搜索策略小結狀態(tài)圖搜索策略小結2022-3-6人工智能343.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（1 1）n搜索搜索：從初始節(jié)點出發(fā)，沿著與之相連的邊試：從初始節(jié)點出發(fā)，沿著與之相連的邊試探地前進，尋找目標節(jié)點的過程。探地前進，尋找目標節(jié)點的過程。n搜索過程中經過的節(jié)點和邊，按原圖的連接關搜索過程中經過的節(jié)點和邊，按原圖的連接關系，便會構成一個樹型的有向圖，這種樹型有系，便會構成一個樹型的有向圖，這種樹型有向圖稱為向圖稱為搜索樹搜索樹。n搜索進行中，搜索樹會不斷增長，直到當搜索搜索進行中，搜索樹會不斷增長，直

36、到當搜索樹中出現目標節(jié)點，搜索便停止。這時從搜索樹中出現目標節(jié)點，搜索便停止。這時從搜索樹中就可很容易地找出從初始節(jié)點到目標節(jié)點樹中就可很容易地找出從初始節(jié)點到目標節(jié)點的路徑（的路徑（解解）來。）來。 2022-3-6人工智能353.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（2 2）1 1 搜索方式搜索方式n樹式搜索樹式搜索 在搜索過程中記錄所經過的在搜索過程中記錄所經過的所有節(jié)點和邊所有節(jié)點和邊。樹式。樹式搜索所記錄的搜索所記錄的軌跡軌跡始終是一棵始終是一棵樹樹，這棵樹也就是搜，這棵樹也就是搜索過程中所產生的搜索樹。索過程中所產生的搜索樹。n線式搜索線式搜索 在搜索過程中只記錄那些在搜索過

37、程中只記錄那些當前當前認為在所找路徑上認為在所找路徑上的的節(jié)點和邊節(jié)點和邊。n不回溯線式搜索不回溯線式搜索n可回溯線式搜索可回溯線式搜索 2022-3-6人工智能363.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（3 3）2 2 搜索策略搜索策略n盲目搜索盲目搜索 無向導的搜索，樹式盲目搜索就是窮舉搜索，不無向導的搜索，樹式盲目搜索就是窮舉搜索，不回溯的線式搜索是隨機碰撞式搜索，回溯的線式搜回溯的線式搜索是隨機碰撞式搜索，回溯的線式搜索也是窮舉式搜索。索也是窮舉式搜索。n啟發(fā)式搜索啟發(fā)式搜索 是利用是利用“啟發(fā)性信息啟發(fā)性信息”引導的搜索策略。引導的搜索策略?！皢l(fā)啟發(fā)性信息性信息”就是與問題

38、有關的有利于盡快找到問題解就是與問題有關的有利于盡快找到問題解的信息或知識。啟發(fā)式搜索分為不同的策略，如全的信息或知識。啟發(fā)式搜索分為不同的策略，如全局擇優(yōu)，局部擇優(yōu)，最佳圖搜索。局擇優(yōu)，局部擇優(yōu)，最佳圖搜索。n按按擴展順序擴展順序不同分為不同分為廣度優(yōu)先廣度優(yōu)先和和深度優(yōu)先深度優(yōu)先。2022-3-6人工智能373.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（4 4）3 3 搜索算法搜索算法n搜索的目的是為了尋找初始節(jié)點到目標節(jié)點的路徑，搜索的目的是為了尋找初始節(jié)點到目標節(jié)點的路徑，搜索過程中就得隨時記錄搜索軌跡。搜索過程中就得隨時記錄搜索軌跡。nClOSEDClOSED表表動態(tài)數據結構來記錄

39、考察過的節(jié)點。動態(tài)數據結構來記錄考察過的節(jié)點。nOPENOPEN表表的動態(tài)數據結構來專門登記當前待考查的節(jié)的動態(tài)數據結構來專門登記當前待考查的節(jié)點。點。節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號OPEN表表CLOSED表表2022-3-6人工智能383.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（5 5）n樹式搜索算法 步步1 把初始節(jié)點把初始節(jié)點S0放入放入OPEN表中。表中。 步步2 若若OPEN表為空，則搜索失敗，退出。表為空，則搜索失敗，退出。 步步3 取取OPEN表中表中第一個節(jié)點第一個節(jié)點N放在放在CLOSED表中；表中；并冠以順序編號并冠以順序編號n； 步步4 若目標節(jié)點若目標節(jié)點Sg=N

40、，成功退出。，成功退出。 步步5 若若N不可擴展，轉步不可擴展，轉步2。 步步6 擴展擴展N，生成一組節(jié)點，對這組子節(jié)點作如下處，生成一組節(jié)點，對這組子節(jié)點作如下處理：理：2022-3-6人工智能393.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（6 6）（1）刪除）刪除N的先輩節(jié)點的先輩節(jié)點（如果有的話）。（如果有的話）。（2）對）對已存在于已存在于OPEN表中的節(jié)點表中的節(jié)點（如果有的話）也刪（如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑路徑，如果新路徑“短短”，則修改這些節(jié)點在，則修改這些節(jié)點在OPEN表中的

41、原返回指針，使其沿新路徑返回。表中的原返回指針，使其沿新路徑返回。（3）對）對已存在于已存在于CLOSED表的節(jié)點表的節(jié)點，作與（，作與（2）同樣的）同樣的處理，并且將其移出處理，并且將其移出CLOSED表，放入表，放入OPEN表中重表中重新擴展。新擴展。（4）對）對其余子節(jié)點其余子節(jié)點配上指向配上指向N的返回指針后放入的返回指針后放入OPEN表中表中某處某處，或對，或對OPEN表進行表進行重新排序重新排序，轉步，轉步2。2022-3-6人工智能403.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（7 7）n樹式算法的幾點說明樹式算法的幾點說明n返回指針返回指針指的是父節(jié)點在指的是父節(jié)點在CLO

42、SEDCLOSED表中的編號。表中的編號。n步步6 6中中修改指針修改指針的原因是返回初始節(jié)點的路徑有兩的原因是返回初始節(jié)點的路徑有兩條，要選擇條，要選擇“短短”的那條路徑。的那條路徑。n這里這里路徑長短路徑長短以節(jié)點數來衡量，在后面將會看到以以節(jié)點數來衡量，在后面將會看到以代價來衡量。按代價衡量修改返回指針的同時還要代價來衡量。按代價衡量修改返回指針的同時還要修改相應的代價值。修改相應的代價值。2022-3-6人工智能413.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（8 8）圖 3-5 修改返回指針示例 2022-3-6人工智能423.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（9 9）n

43、樹式搜索例樹式搜索例n對于對于已存在于已存在于OPENOPEN表中的節(jié)點表中的節(jié)點（如果有的話）也刪除之；刪（如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點在徑短，則修改這些節(jié)點在OPENOPEN表中的原返回指針，使其沿原表中的原返回指針，使其沿原路徑返回。路徑返回。Path1Path2S0mnP先擴展后擴展P P在在n n之前已是某一節(jié)點之前已是某一節(jié)點m m的后繼的后繼如圖所示：說明從如圖所示：說明從S S0 0PP至至少有兩條路，這時有兩少有兩條路，這時有兩種情況：種情況：f f（Pat

44、h2Path2） f f（Path1Path1），），當前路徑較好，要修改當前路徑較好，要修改P P的指針，使其指向的指針，使其指向n n，即，即搜索之后的最佳路徑。搜索之后的最佳路徑。否則，原路徑好。否則，原路徑好。2022-3-6人工智能433.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（1010）n對對已存在于已存在于CLOSEDCLOSED表的節(jié)點表的節(jié)點，作與（，作與（2 2）同樣的處理，并將其）同樣的處理，并將其移出移出CLOSEDCLOSED表，放入表，放入OPENOPEN表中重新擴展。表中重新擴展。S0過去生成P的路徑現在生成P的路徑過去對Ps的最優(yōu)路徑PsPmnka.Pa.P

45、在在n n之前已是某一節(jié)點之前已是某一節(jié)點m m的的后繼，所以需要做如同（后繼，所以需要做如同（2 2）同樣的處理，如圖右部所示。同樣的處理，如圖右部所示。b.Pb.P在在ClosedClosed表中，說明表中，說明P P的后的后繼也在繼也在n n之前已經生成，稱為之前已經生成，稱為PsPs。對。對PsPs而言同樣可能而言同樣可能 由于由于nPnP這一路徑的加入，又必須這一路徑的加入，又必須比較多條路徑之后而取代價小比較多條路徑之后而取代價小的一條，如圖左部所示。的一條，如圖左部所示。2022-3-6人工智能443.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（1111）例：設當前搜索圖和搜索樹

46、如圖所示例：設當前搜索圖和搜索樹如圖所示S0nPmPsPsS0nPmPsPsFF2022-3-6人工智能453.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（1212）n若啟發(fā)函數若啟發(fā)函數f(n)f(n)為從為從S0S0到節(jié)點到節(jié)點n n的最短路徑的長度，用的最短路徑的長度，用邊的數目來考察，當前擴展的節(jié)點是搜索圖中的邊的數目來考察，當前擴展的節(jié)點是搜索圖中的n,Pn,P是是n n的后繼的后繼S0nPmPsPsnPPsPsS0mFF2022-3-6人工智能463.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（1313）nP P的指針改變后，修改搜索樹結果如下：的指針改變后，修改搜索樹結果如下：n

47、PPsS0FmPs2022-3-6人工智能473.2.1 3.2.1 狀態(tài)圖搜索（狀態(tài)圖搜索（1414）n不回溯線式搜索算法不回溯線式搜索算法 步步1 把初始節(jié)點把初始節(jié)點S0放入放入CLOSED表中；表中； 步步2 令令N S0 ； 步步3 若若N是目標節(jié)點，則搜索成功，結束。是目標節(jié)點，則搜索成功，結束。 步步4 若若N不可擴展，則搜索失敗，退出。不可擴展，則搜索失敗，退出。 步步5 擴展擴展N，選取其一個未在，選取其一個未在CLOSED表中出現過的表中出現過的 子節(jié)點子節(jié)點N1放入放入 CLOSED表中，令表中，令NN1，轉步，轉步3。2022-3-6人工智能483.2.1 3.2.1

48、狀態(tài)圖搜索（狀態(tài)圖搜索（1515）n可回溯的線式搜索可回溯的線式搜索步步1 把初始節(jié)點把初始節(jié)點S0放入放入CLOSED表中；表中；步步2 令令N S0 ；步步3 若若N是目標節(jié)點，則搜索成功，結束。是目標節(jié)點，則搜索成功，結束。步步4 若若N不可擴展，則移出不可擴展，則移出CLOSED表中的末端節(jié)點表中的末端節(jié)點Ne ，若，若NeS0， 則搜索失敗，退出。否則以則搜索失敗，退出。否則以CLOSED表新的末端節(jié)點表新的末端節(jié)點Ne作為作為 N，即令，即令N Ne，轉步，轉步4；步步5 擴展擴展N，選取其一個未在，選取其一個未在CLOSED表中出現過的子節(jié)點表中出現過的子節(jié)點N1放入放入 CLO

49、SED表中，令表中，令N N1 ，轉步，轉步3。2022-3-6人工智能493.2.2 3.2.2 窮舉式搜索（窮舉式搜索（1 1）n廣度優(yōu)先搜索（算法廣度優(yōu)先搜索（算法A A?eded）n策略策略 始終在始終在同一級節(jié)點同一級節(jié)點中考查，當同一級節(jié)點考查完了之后，才中考查，當同一級節(jié)點考查完了之后，才 考查下一級節(jié)點。搜索樹考查下一級節(jié)點。搜索樹自頂向下一層一層自頂向下一層一層逐漸生成。逐漸生成。n算法算法 步步1 把初始節(jié)點把初始節(jié)點S0S0放入放入OPENOPEN表中；表中； 步步2 2 若若OPENOPEN表為空，則搜索失敗，退出。表為空，則搜索失敗，退出。 步步3 3 取取OPENO

50、PEN表中第一個節(jié)點表中第一個節(jié)點N N放在放在CLOSEDCLOSED表中；并冠以順序編號表中；并冠以順序編號n n； 步步4 4 若節(jié)點若節(jié)點N N為目標節(jié)點，成功退出。為目標節(jié)點，成功退出。 步步5 5 若若N N不可擴展，轉步不可擴展，轉步2 2； 步步6 6 擴展擴展N N，將其所有子節(jié)點配上指向，將其所有子節(jié)點配上指向N N的指針放入的指針放入OPENOPEN尾部尾部，轉步，轉步2 2。2022-3-6人工智能503.2.2 3.2.2 窮舉式搜索（窮舉式搜索（2 2）2022-3-6人工智能513.2.2 3.2.2 窮舉式搜索（窮舉式搜索（3 3）n廣度優(yōu)先搜索的特點廣度優(yōu)先搜

51、索的特點n廣度優(yōu)先中廣度優(yōu)先中OPENOPEN表表是一個是一個隊列隊列，CLOSEDCLOSED表表是一個是一個順順序表序表，表中各節(jié)點按順序編號，正被考察的節(jié)點在，表中各節(jié)點按順序編號，正被考察的節(jié)點在表中編號最大。表中編號最大。n廣度優(yōu)先搜索又稱為廣度優(yōu)先搜索又稱為寬度優(yōu)先寬度優(yōu)先或或橫向搜索橫向搜索。n廣度優(yōu)先策略是廣度優(yōu)先策略是完備完備的，即如果問題的解存在，則的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。它一定可以找到解，并且找到的解還是最優(yōu)解。n廣度優(yōu)先搜索策略與問題無關，具有通用性。廣度優(yōu)先搜索策略與問題無關，具有通用性。n缺點搜索缺點搜索效率低效率低。20

52、22-3-6人工智能523.2.2 3.2.2 窮舉式搜索（窮舉式搜索（4 4）n八數碼問題2 8 31 47 6 5初始狀態(tài)8 1 32 47 6 5目標狀態(tài)2022-3-6人工智能533.2.2 3.2.2 窮舉式搜索（窮舉式搜索（5 5）2 8 31 47 6 51 2 3 1 8 47 6 592 31 8 47 6 582 81 4 37 6 5102 8 37 1 4 6 57 8 32 1 47 6 562 8 31 4 57 6112 8 3 1 47 6 522 31 8 47 6 532 8 31 47 6 542 8 31 6 4 7 5122 8 31 6 47 513

53、8 32 1 47 6 5142 8 37 1 46 5152 3 41 87 6 5161 2 3 8 47 6 5172 81 4 37 6 5182 8 31 4 57 6192 8 3 6 41 7 5202 8 31 6 7 5 4218 32 1 47 6 5222 8 31 6 47 558 1 32 47 6 523八數碼廣度優(yōu)先搜索八數碼廣度優(yōu)先搜索2022-3-6人工智能543.2.2 3.2.2 窮舉式搜索（窮舉式搜索（6 6）n深度優(yōu)先搜索（過程深度優(yōu)先搜索（過程A Apdpd ）n搜索策略搜索策略 在搜索樹的每一層始終先擴展一個子節(jié)點，不斷地向縱深前在搜索樹的每一層始

54、終先擴展一個子節(jié)點，不斷地向縱深前進，直到不能再前進，才從當前節(jié)點返回到上一級節(jié)點，從另一進，直到不能再前進，才從當前節(jié)點返回到上一級節(jié)點，從另一方向繼續(xù)前進。方向繼續(xù)前進。n算法 步步1 把初始節(jié)點把初始節(jié)點S0放入放入OPEN表中；表中； 步步2 若若OPEN表為空，則搜索失敗，退出。表為空，則搜索失敗，退出。 步步3 取取OPEN表中第一個節(jié)點表中第一個節(jié)點N放在放在CLOSED表中；并冠以編號表中；并冠以編號n； 步步4 節(jié)點節(jié)點N為目標節(jié)點，成功退出。為目標節(jié)點，成功退出。 步步5 若若N不可擴展，轉步不可擴展，轉步2； 步步6 擴展擴展N，將其所有子節(jié)點配上指向，將其所有子節(jié)點配上

55、指向N的指針放入的指針放入OPEN首部首部，轉，轉 步步2。2022-3-6人工智能553.2.2 3.2.2 窮舉式搜索（窮舉式搜索（7 7）2022-3-6人工智能563.2.2 3.2.2 窮舉式搜索（窮舉式搜索（8 8）n深度優(yōu)先搜索的特點深度優(yōu)先搜索的特點nOPENOPEN表為一個表為一個堆棧堆棧。n深度優(yōu)先又稱深度優(yōu)先又稱縱向搜索縱向搜索。n一般一般不能保證找到最優(yōu)解不能保證找到最優(yōu)解。n當深度限制不合理時，可能找不到解，可以將算當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制，即有界深度優(yōu)先搜索。法改為可變深度限制，即有界深度優(yōu)先搜索。n最壞情況時，搜索空間等同于窮舉

56、。最壞情況時，搜索空間等同于窮舉。2022-3-6人工智能573.2.2 3.2.2 窮舉式搜索（窮舉式搜索（9 9）2 31 8 47 6 52 8 31 47 6 52 8 3 1 47 6 52 8 31 6 47 52 8 31 47 6 512 8 31 6 47 532 8 31 6 7 5 442 8 31 6 47 522 8 31 6 7 5 42 81 6 37 5 45八數碼深度優(yōu)先搜索2022-3-6人工智能583.2.2 3.2.2 窮舉式搜索（窮舉式搜索（1010）n有界深度優(yōu)先搜索（過程有界深度優(yōu)先搜索（過程A Acdcd ）n搜索策略搜索策略 給出搜索樹給出搜索

57、樹深度深度的的限制限制，當從初始節(jié)點出發(fā)沿某一分支擴展到一定，當從初始節(jié)點出發(fā)沿某一分支擴展到一定深度限制時，就不能再繼續(xù)往下擴展，而只能改變方向繼續(xù)搜索深度限制時，就不能再繼續(xù)往下擴展，而只能改變方向繼續(xù)搜索。n算法算法 步步1 把初始節(jié)點把初始節(jié)點S0放入放入OPEN表中，置表中，置S0的深度的深度d（ S0 ）0； 步步2 若若OPEN表為空，則搜索失敗，退出。表為空，則搜索失敗，退出。 步步3 取取OPEN表中第一個節(jié)點表中第一個節(jié)點N放在放在CLOSED表中；并冠以編號表中；并冠以編號n； 步步4 若節(jié)點若節(jié)點N為目標節(jié)點，成功退出。為目標節(jié)點，成功退出。 步步5 若若N的深度的深度

58、d（N）dm（深度限制值），或者若（深度限制值），或者若N無子節(jié)點，無子節(jié)點， 則轉步則轉步2； 步步6 擴展擴展N，將其所有子節(jié)點，將其所有子節(jié)點Ni配上指向配上指向N的指針放入的指針放入OPEN首部首部， 置的置的d（ Ni ）d（N）1，轉步，轉步2。2022-3-6人工智能593.2.2 3.2.2 窮舉式搜索（窮舉式搜索（1111）a1a2a3a6b1b2b4b3b5S2022-3-6人工智能603.2.2 3.2.2 窮舉式搜索（窮舉式搜索（1212）n有界深度優(yōu)先搜索存在的問題有界深度優(yōu)先搜索存在的問題n深度界限的選擇很重要深度界限的選擇很重要 d dm m 若太小，則達不到解的

59、深度，得不到解；若太若太小，則達不到解的深度，得不到解；若太大，既浪費了計算機的存儲空間與時間，又降低了搜大，既浪費了計算機的存儲空間與時間，又降低了搜索效率。由于解的路徑長度事先難以預料，所以要恰索效率。由于解的路徑長度事先難以預料，所以要恰當地給出當地給出d dm m的值是比較困難的。的值是比較困難的。n即使能求出解，它也不一定是最優(yōu)解。即使能求出解，它也不一定是最優(yōu)解。2022-3-6人工智能613.2.2 3.2.2 窮舉式搜索（窮舉式搜索（1313）n有界深度優(yōu)先搜索改進有界深度優(yōu)先搜索改進nd dm m隨搜索深度不斷加大（隨搜索深度不斷加大（迭代加深搜索迭代加深搜索） 先任意給定一

60、個較小的數作為先任意給定一個較小的數作為d dm m，然后進行上述的有界深，然后進行上述的有界深 度優(yōu)先搜索，當搜索達到了指定的深度界限度優(yōu)先搜索，當搜索達到了指定的深度界限d dm m仍未發(fā)現目標節(jié)點，仍未發(fā)現目標節(jié)點，并且并且CLOSEDCLOSED表中仍有待擴展節(jié)點時就將這些節(jié)點送回表中仍有待擴展節(jié)點時就將這些節(jié)點送回OPENOPEN表，表，同時增大深度界限同時增大深度界限d dm m，繼續(xù)向下搜索。如此不斷地增大，繼續(xù)向下搜索。如此不斷地增大d dm m，只要，只要問題有解，就一定可以找到它。問題有解，就一定可以找到它。n增加一個增加一個R R表表 此時找到的解不一定是最優(yōu)解。為找到最