狀態(tài)空間分析方法知識表示和問題的求解

1、1狀態(tài)空間分析方法知識表示和問題的求解22.2 知識表示與問題求解知識表示與問題求解2.2.1 一階謂詞知識表示法2.2.2 產(chǎn)生式知識表示法2.2.3 狀態(tài)空間法32.2 知識表示與問題求解知識表示與問題求解2.2.1 一階謂詞知識表示法2.2.2 產(chǎn)生式知識表示法2.2.3 狀態(tài)空間法-2.2.3.1 基于狀態(tài)空間法的問題描述例:三數(shù)碼難題（3 puzzle problem）123123123312312312初始棋局目標(biāo)棋局2.2.3 狀態(tài)空間法5狀態(tài)空間表示法就是以“狀態(tài)空間”的形式來表示問題及其搜索過程的一種方法。狀態(tài)空間表示法是人工智能中最基本的形式化方法，是討論問題求解技術(shù)的基礎(chǔ)

2、。2.2.3 狀態(tài)空間法61. 狀態(tài)是描述問題求解過程中不同時刻狀況的數(shù)據(jù)結(jié)構(gòu)。一般用一組變量的有序集合表示： Q=(q0，q1，.，qn) 其中每個元素qi(i=0，l，2，n) 為狀態(tài)變量。2.2.3.1 問題狀態(tài)空間的構(gòu)成當(dāng)給每一個變量以確定的值時，就得到了一個具體的狀態(tài)。2.2.3 狀態(tài)空間法7算符：引起狀態(tài)中某些變量發(fā)生變化，從而使問題由一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作。2. 算符算符可分為走步、過程、規(guī)則、數(shù)學(xué)算子、運(yùn)算符號、邏輯符號等。例如：在產(chǎn)生式系統(tǒng)中，每一條產(chǎn)生式規(guī)則就是一個算符；而在下棋程序中，一個算符就是一個走步。2.2.3.1 問題狀態(tài)空間的構(gòu)成2.2.3 狀態(tài)空間法8狀

3、態(tài)空間：一個問題的全部狀態(tài)及一切可用算符構(gòu)成的集合。3. 狀態(tài)空間狀態(tài)空間由三部分構(gòu)成：問題的所有可能初始狀態(tài)構(gòu)成的集合S；算符集合F；目標(biāo)狀態(tài)集合G。用一個三元組表示為：(S，F(xiàn)，G)2.2.3.1 問題狀態(tài)空間的構(gòu)成2.2.3 狀態(tài)空間法9狀態(tài)空間圖：狀態(tài)空間的圖示形式。其中節(jié)點(diǎn)表示狀態(tài)；有向邊(弧)表示算符。3. 狀態(tài)空間2.2.3.1 問題狀態(tài)空間的構(gòu)成2.2.3 狀態(tài)空間法10狀態(tài)空間的問題求解就是從問題的初始狀態(tài)集S出發(fā)，經(jīng)過一系列的算符運(yùn)算，到達(dá)目標(biāo)狀態(tài)。4. 問題的解由初始狀態(tài)到目標(biāo)狀態(tài)所用算符的序列就構(gòu)成了問題的一個解。2.2.3.1 問題狀態(tài)空間的構(gòu)成2.2.3 狀態(tài)空間法

4、11(1)定義狀態(tài)的描述形式。用狀態(tài)空間表示問題的步驟(2)用所定義的狀態(tài)描述形式把問題的所有可能的狀態(tài)都表示出來，并確定出問題的初始狀態(tài)集合描述和目標(biāo)狀態(tài)集合描述。(3)定義一組算符，使得利用這組算符可把問題由一種狀態(tài)轉(zhuǎn)變?yōu)榱硪环N狀態(tài)。問題求解過程是一個不斷把算符作用于狀態(tài)的過程2.2.3 狀態(tài)空間法(4) 首先將適用算符作用于初始狀態(tài)，以產(chǎn)生新的狀態(tài)；(5) 然后再把一些適用的算符作用于新的狀態(tài)；這樣繼續(xù)下去，直到產(chǎn)生的狀態(tài)為目標(biāo)狀態(tài)為止。(6 )這時，就得到了問題的一個解，這個解是從初始狀態(tài)到目標(biāo)狀態(tài)所用算符構(gòu)成的序列。問題：最優(yōu)解問題；搜索策略問題。用狀態(tài)空間表示問題的步驟2.2.3

5、狀態(tài)空間法13例如下棋、迷宮及各種游戲。OriginalStateMiddleStateGoalState用狀態(tài)空間表示問題的步驟2.2.3 狀態(tài)空間法14Hanoi塔2.2.3 狀態(tài)空間法在梵城（Hana）地下有一個僧侶的秘密組織，他們有3個大型的塔柱，左邊的塔柱上由方到小套著64個金盤。僧侶們的工作是要把這64個金盤從左邊塔柱轉(zhuǎn)移到右邊塔柱上去。但轉(zhuǎn)移過程有規(guī)定的：1、每次只能搬動一只盤子，盤十只能在3個塔柱上安放，不允許放在地上；2、在每個塔柱上，只允許把小盤十疊在大盤上，反之不允許。據(jù)傳說，僧侶們完成這個任務(wù)時，世界的末日就來臨了。15Hanoi塔2.2.3 狀態(tài)空間法19世紀(jì)，法國的

6、一位數(shù)學(xué)家douard Lucas (18421891) 對該課題進(jìn)行過研究，他指示，要完成這個任務(wù)，僧侶們搬動金盤的總次數(shù)：（20位）假設(shè)僧侶們個個身強(qiáng)力壯，每天24小時不知頭疲倦地工作，而且一秒鐘移動一個金盤，那么，完成這個任務(wù)也得花5800億年。16Hanoi塔2.2.3 狀態(tài)空間法觀自在菩薩，行深般若波羅蜜多時，照見五蘊(yùn)皆空，度一切苦厄。舍利子，色不異空，空不異色；色即是空，空即是色。受想行識，亦復(fù)如是。舍利子，是諸法空相，不生不滅，不垢不凈，不增不減。19世紀(jì)，法國的一位數(shù)學(xué)家douard Lucas (18421891) 對該課題進(jìn)行過研究，他指示，要完成這個任務(wù)，僧侶們搬動金盤的

7、總次數(shù)：（20位）假設(shè)僧侶們個個身強(qiáng)力壯，每天24小時不知頭疲倦地工作，而且一秒鐘移動一個金盤，那么，完成這個任務(wù)也得花5800億年。17已知3個柱子l、2、3和兩個盤子A、B(A比B小)。初始狀態(tài)下，A、B依次放在1柱上；目標(biāo)狀態(tài)是A、B依次放在柱子3上。條件是每次可移動一個盤子，盤子上方是空頂方可移動，而且任何時候都不允許大盤在小盤之上。例2.2.3.1 二階Hanoi塔問題2.2.3 狀態(tài)空間法18定義問題狀態(tài)的描述形式 設(shè)用Sk=(SkA，SkB)表示問題的狀態(tài)，SkA表示盤子A所在的柱號，SkB表示盤子B所在的柱號。第一步：用狀態(tài)空間表示問題用狀態(tài)描述形式把問題的所有可能的狀態(tài)都表示

8、出來。本問題共有九種可能狀態(tài): S0=(1，1)， S1=(1，2)， S2=(1，3) S3=(2，1)， S4=(2，2)， S5=(2，3) S6=(3，1)， S7=(3，2)， S8=(3，3) 問題的初始狀態(tài)集合為S=S0，目標(biāo)狀態(tài)集合為G=S8。2.2.3 狀態(tài)空間法192.2.3 狀態(tài)空間法算符A(i，j)表示把盤子A從第i號柱子移到第j號柱子上的操作；算符B(i，j)表示把盤子B從第i號柱子移到第j號柱子上的操作。算符組F中共有12個算符:A(1，2)，A(1，3)，A(2，1)，A(2，3)，A(3，1)，A(3，2)B(1，2)，B(1，3)，B(2，1)，B(2，3)，

9、B(3，1)，B(3，2)問題的狀態(tài)空間(S，F(xiàn)，G)構(gòu)造完成。定義一組算符F2.2.3 狀態(tài)空間法21根據(jù)狀態(tài)空間的9種可能狀態(tài)和12種算符，構(gòu)造它的狀態(tài)空間圖：第二步：問題求解2.2.3 狀態(tài)空間法22在狀態(tài)空間圖中，從初始節(jié)點(diǎn)(1，1)(狀態(tài)S0)到目標(biāo)節(jié)點(diǎn)(3，3)(狀態(tài)S8)的任何一條通路都是問題的一個解。最短的路徑長度是3，它由3個算符組成：A(1，2)、B(1，3)、A(2，3)。2.2.3 狀態(tài)空間法三枚錢幣處于反、正、反狀態(tài)，每次只許翻動一枚錢幣，問連續(xù)翻動三次后，能否出現(xiàn)全正或全反狀態(tài)。 初始狀態(tài)Qs目標(biāo)狀態(tài)集合Q0, Q7例1：翻轉(zhuǎn)錢幣問題2.2.3 狀態(tài)空間法引入一個三

10、元組(q0,q1,q2)來描述總狀態(tài)，錢幣正面為0，反面為1，全部可能的狀態(tài)為： 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)。翻動錢幣的操作抽象為改變上述狀態(tài)的算子， 即Fa, b, c a:把錢幣q0翻轉(zhuǎn)一次 b:把錢幣q1翻轉(zhuǎn)一次 c:把錢幣q2翻轉(zhuǎn)一次 問題的狀態(tài)空間為 例：翻轉(zhuǎn)錢幣問題2.2.3 狀態(tài)空間法問題的狀態(tài)空間為： 構(gòu)造狀態(tài)空間圖： aabababaabbbbcccbcccb例：翻轉(zhuǎn)錢幣問題2.2.3 狀態(tài)空間法圖2-5 翻動三次

11、后三枚錢幣問題的狀態(tài)變化翻轉(zhuǎn)錢幣問題狀態(tài)空間圖的另一種表示：例：翻轉(zhuǎn)錢幣問題2.2.3 狀態(tài)空間法例：修道士和野人問題在河的左岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運(yùn)過河去，但受到以下條件的限制：1）修道士和野人都會劃船，但船一次最多只能運(yùn)兩個人；2）在任何岸邊野人數(shù)目都不得超過修道士，否則修道士就會被野人吃掉。2.2.3 狀態(tài)空間法1、問題的狀態(tài)可以用一個三元數(shù)組來描述： S(m, c, b) m：左岸的修道士數(shù) c：左岸的野人數(shù) b：左岸的船數(shù) 右岸的狀態(tài)不必標(biāo)出，因?yàn)椋?右岸的修道士數(shù) m 3m 右岸的野人數(shù) c 3c 右岸的船數(shù) b 1b例：修道士和野人問題2

12、.2.3 狀態(tài)空間法狀態(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 1S212 2 0S290 2 0S62 1 1S140 1 1S222 1 0S300 1 0S72 0 1S150 0 1S232 0 0S310 0 0狀態(tài)不合法2.

13、2.3 狀態(tài)空間法例：修道士和野人問題2.操作集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)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=

14、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操作符條 件動 作2.2.3 狀態(tài)空間法例：修道士和野人問題3.狀態(tài)空間給出狀態(tài)和操作的描述之后，該問題的狀態(tài)空間是：S0， P 01，P 10，P 11，P 02，P 20，Q01，Q 10，Q 11，Q 02，Q 20，S31。2.2.3 狀態(tài)空間法例：修道士和野人問題S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)p11q11S1(3,2,1)q01p01p10q1

15、0S19(3,0,0)q02p02S2(3,1,1)q01p01S26(1,1,0)q20p20S0(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)q11p114.狀態(tài)空間圖：四條S0到S31長度相等的最短路徑，對應(yīng)的操作序列就是該問題的四個最優(yōu)解2.2.3 狀態(tài)空間法例：修道士和野人問題 思考題：(猴子摘香蕉)2.2.3 狀態(tài)空間法 猴子香蕉箱子 猴子香蕉箱子 Ha!Ha!2.2.3 狀態(tài)空間法

16、 思考題：(猴子摘香蕉)隱式狀態(tài)空間圖：利用有關(guān)狀態(tài)描述和狀態(tài)轉(zhuǎn)換（操作）的知識定義的狀態(tài)空間圖。在計算機(jī)中僅存儲描述問題狀態(tài)及操作的有關(guān)知識，包括該問題的各狀態(tài)分量的取值情況、分量之間的約束條件、開始狀態(tài)、終止?fàn)顟B(tài)，以及全部操作的條件和動作等。隱式狀態(tài)空間圖也稱為是狀態(tài)空間圖的隱式表示或隱式圖。顯式狀態(tài)空間圖 vs 隱式狀態(tài)空間圖顯式狀態(tài)空間圖：表示了問題所有可能的狀態(tài)及狀態(tài)之間的關(guān)系，這種表示方式稱為顯式狀態(tài)空間圖，或稱為狀態(tài)空間圖的顯示表示。2.2.3 狀態(tài)空間法 重排九宮問題的狀態(tài)表示顯式狀態(tài)空間圖 vs 隱式狀態(tài)空間圖重排九宮問題的隱式圖描述為： 2.2.3 狀態(tài)空間法（1）有關(guān)狀態(tài)

17、的知識： 顯式狀態(tài)空間圖 vs 隱式狀態(tài)空間圖重排九宮問題的隱式圖描述為： 初始狀態(tài)： S0 （0，1，2，3，5，6，4，7，8） 目標(biāo)狀態(tài)： Sg （0，1，2，3，4，5，6，7，8）狀態(tài)S的定義：S(X0，X1，X2，X3，X4 ，X5， X6 ，X7 ，X8) 其中， Xi0，1，2，3，4，5，6，7，8， 2.2.3 狀態(tài)空間法0組規(guī)則 R1(X0=0 ) (X2=n ) X0 = n X2 =0； R2(X0=0 ) (X4=n ) X0 = n X4 =0； R3(X0=0 ) (X6=n ) X0 = n X6 =0； R4(X0=0 ) (X8=n ) X0 = n X8

18、 =0；1組規(guī)則 R5(X1=0 ) (X2=n ) X1 = n X2 =0； R6(X1=0 ) (X8=n ) X1 = n X8 =0；顯式狀態(tài)空間圖 vs 隱式狀態(tài)空間圖重排九宮問題的隱式圖描述為： （2）有關(guān)操作的知識（規(guī)則）：2.2.3 狀態(tài)空間法（S0, r1 , r2 , , r24 , Sg）顯式狀態(tài)空間圖 vs 隱式狀態(tài)空間圖重排九宮問題的隱式圖描述為： 這里僅給出了初始節(jié)點(diǎn)和目標(biāo)節(jié)點(diǎn)，其余節(jié)點(diǎn)需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表示。2.2.3 狀態(tài)空間法402.2 知識表示與問題求解知識表示與問題求解2.2.1 一階謂詞知識

19、表示法2.2.2 產(chǎn)生式知識表示法2.2.3 狀態(tài)空間法-2.2.3.2 基于狀態(tài)空間法的搜索策略-2.2.3.1 基于狀態(tài)空間法的問題描述狀態(tài)空間圖搜索中的通用數(shù)據(jù)結(jié)構(gòu)CLOSED表：用來記錄考察過的節(jié)點(diǎn)以及節(jié)點(diǎn)之間的關(guān)系，如每個節(jié)點(diǎn)指向父節(jié)點(diǎn)的編號（返回指針）。CLOSED表中存放的就是一定搜索策略下的搜索樹。節(jié)點(diǎn)父節(jié)點(diǎn)編號編號節(jié)點(diǎn)父節(jié)點(diǎn)編號OPEN表CLOSED表OPEN表：專門登記已經(jīng)生成但還沒有考察的節(jié)點(diǎn)，即待考察節(jié)點(diǎn)。2.2.3 狀態(tài)空間法盲目搜索盲目搜索:搜索時不參考與具體待求解問題相關(guān)的任何信息，只是按預(yù)先設(shè)定的順序逐個考察節(jié)點(diǎn)。盲目搜索與問題無關(guān)，具有通用性。狀態(tài)空間圖搜索廣

20、度優(yōu)先搜索深度優(yōu)先搜索迭代加深搜索2.2.3 狀態(tài)空間法盲目搜索-廣度優(yōu)先搜索算法廣度優(yōu)先搜索（Aed）基本思想廣度優(yōu)先搜索是嚴(yán)格按節(jié)點(diǎn)在樹中的出現(xiàn)位置一層一層向下的搜索過程。通過將OPEN表設(shè)計為一個隊列來實(shí)現(xiàn)，將新生成的子節(jié)點(diǎn)放在OPEN表的后面，保證先生成的節(jié)點(diǎn)先考察。2.2.3 狀態(tài)空間法步1 把初始結(jié)點(diǎn)S0放入OPEN表中；步2 若OPEN表為空，則搜索失敗，退出；步3 否則，取OPEN表中第一個結(jié)點(diǎn)N放在CLOSED表中；并冠以順序編號n；步4 若結(jié)點(diǎn)N為目標(biāo)結(jié)點(diǎn)，則搜索成功。利用CLOSED表中的返回指針找出S0到N的路徑即為所求解，退出；步5 若N不可擴(kuò)展，轉(zhuǎn)步2；步6 否則，

21、擴(kuò)展N，將其所有子結(jié)點(diǎn)配上指向N的返回指針放入OPEN表的尾部，轉(zhuǎn)步2。廣度優(yōu)先搜索算法盲目搜索-廣度優(yōu)先搜索算法2.2.3 狀態(tài)空間法廣度優(yōu)先搜索算法流程圖盲目搜索-廣度優(yōu)先搜索算法2.2.3 狀態(tài)空間法1 2 38 57 4 611 2 38 5 67 481 38 2 57 4 6101 2 38 4 5 7 671 2 38 4 57 6 6 1 38 2 57 4 6111 2 38 4 57 621 2 38 5 7 4 631 2 38 4 57 641 2 37 8 5 4 612 2 31 8 57 4 6131 2 38 47 6 5141 2 3 4 58 7 6151

22、28 5 37 4 6171 3 58 27 4 6188 1 3 2 57 4 6191 2 37 8 54 6202 31 8 5 7 4 6211 28 4 37 6 5221 2 3 8 57 4 651 2 38 47 6 523八數(shù)碼廣度優(yōu)先搜索1 28 5 37 4 69161 2 38 5 67 4使用廣度優(yōu)先搜索算法求解重排九宮問題盲目搜索-廣度優(yōu)先搜索算法2.2.3 狀態(tài)空間法缺點(diǎn)搜索效率低。廣度優(yōu)先搜索的特點(diǎn)：廣度優(yōu)先中OPEN表是一個隊列，CLOSED表是一個順 序表，表中各節(jié)點(diǎn)按順序編號，正被考察的節(jié)點(diǎn)在表中編號最大。廣度優(yōu)先搜索又稱為寬度優(yōu)先或橫向搜索。廣度優(yōu)先策略

23、是完備的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。盲目搜索-廣度優(yōu)先搜索算法2.2.3 狀態(tài)空間法盲目搜索-深度優(yōu)先搜索算法深度優(yōu)先搜索的基本思想深度優(yōu)先搜索是一種一直向下的搜索過程，它優(yōu)先在自己的子結(jié)點(diǎn)集合中選擇下一個被考察的結(jié)點(diǎn)，不斷向縱深方向前進(jìn)，直到到達(dá)葉子結(jié)點(diǎn)或受到深度限制時，才返回到上一級結(jié)點(diǎn)沿另一方向繼續(xù)前進(jìn)。2.2.3 狀態(tài)空間法與廣度優(yōu)先搜索策略的唯一不同點(diǎn)就是OPEN表被設(shè)計成后進(jìn)先出的棧，新生成的子結(jié)點(diǎn)放在OPEN表的前面，后生成的結(jié)點(diǎn)優(yōu)先被考察。深度優(yōu)先搜索算法只需將寬度優(yōu)先搜索算法步6修改為：步6 否則，

24、擴(kuò)展N，將其所有子結(jié)點(diǎn)配上指向N的指針放入OPEN表的首部，轉(zhuǎn)步2。 盲目搜索-深度優(yōu)先搜索算法深度優(yōu)先搜索算法2.2.3 狀態(tài)空間法1 2 38 57 4 611 2 38 4 5 7 631 2 38 4 57 6 1 2 38 4 57 61 2 38 5 7 4 61 2 38 4 57 61 2 38 47 6 541 28 4 37 6 51 2 3 8 57 4 621 2 38 47 6 55使用深度優(yōu)先搜索算法求解重排九宮問題盲目搜索-深度優(yōu)先搜索算法2.2.3 狀態(tài)空間法深度優(yōu)先搜索的特點(diǎn)：OPEN表為一個堆棧。深度優(yōu)先又稱縱向搜索。一般不能保證找到最優(yōu)解。如下圖所示：圖

25、深度優(yōu)先搜索不具有完備性示意圖深度優(yōu)先搜索的特點(diǎn)：盲目搜索-深度優(yōu)先搜索算法2.2.3 狀態(tài)空間法為克服深度優(yōu)先搜索的不足，可對其深度進(jìn)行限制盲目搜索-有界深度優(yōu)先搜索算法有界深度優(yōu)先搜索的提出：即使能求出解，它也不一定是最優(yōu)解。深度界限的選擇很重要dm 若太小，則達(dá)不到解的深度，得不到解；若太大，既浪費(fèi)了計算機(jī)的存儲空間與時間，又降低了搜索效率。由于解的路徑長度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出dm的值是比較困難的。2.2.3 狀態(tài)空間法當(dāng)在dm界限之內(nèi)找不到解時，可以將深度界限dm不斷擴(kuò)大，每次增加一個深度增量d，直到找到解，或者搜索完整棵樹。這樣算法的完備性得到了保證，稱為可變界深度優(yōu)先搜索

26、算法(或迭代加深搜索)。 盲目搜索-有界深度優(yōu)先搜索算法有界深度優(yōu)先搜索的思路-迭代加深 當(dāng)d =1時，算法開始蛻變?yōu)閺V度優(yōu)先搜索算法。2.2.3 狀態(tài)空間法人工智能盲目搜索-迭代加深優(yōu)先搜索算法2.2.3 狀態(tài)空間法步1 把初始結(jié)點(diǎn)S0放入OPEN表中，置d(S0)=0，dm=dm0，G=NULL。步2 若OPEN表為空，則考察CLOSED表是否有待擴(kuò)展結(jié)點(diǎn)： （1）若無待擴(kuò)展結(jié)點(diǎn)，則判斷G表是否為空： 若為空，搜索失敗，退出； 否則，取出G表最后面的結(jié)點(diǎn)Sg， Sg即為所求最優(yōu)解，搜索成功，退出； （2）若有待擴(kuò)展結(jié)點(diǎn)，則取出CLOSED表中待擴(kuò)展結(jié)點(diǎn)放入到OPEN表中，令dm=dm+d，

27、轉(zhuǎn)步2；有界深度優(yōu)先搜索的思路-迭代加深盲目搜索-迭代加深優(yōu)先搜索算法2.2.3 狀態(tài)空間法步3 取OPEN表中首部的結(jié)點(diǎn)N放在CLOSED表中；并冠以順序編號n； 步4 若d（N）dm，則標(biāo)N為待擴(kuò)展結(jié)點(diǎn)，轉(zhuǎn)步2；步5 若N是目標(biāo)結(jié)點(diǎn)Sg ，則令dmd（ Sg ）-1 ，把Sg放到G 表的尾部，轉(zhuǎn)步2。步6 若N不可擴(kuò)展，則轉(zhuǎn)步2； 步7 否則，擴(kuò)展N，將其所有子結(jié)點(diǎn)Ni配上指向N的返回指針放入OPEN表首部， 置d（ Ni ）d（N）1 ，轉(zhuǎn)步2。 有界深度優(yōu)先搜索的思路-迭代加深盲目搜索-迭代加深優(yōu)先搜索算法2.2.3 狀態(tài)空間法八數(shù)碼難題的深度優(yōu)先搜索樹(深度約束=4)12384567

28、1238456712384567123845671238456712384567123845671345612367812384567123845671238456712384567Goal123845671238456741238567對n應(yīng)用一個算符以產(chǎn)生該節(jié)點(diǎn)的一個后繼節(jié)點(diǎn)放入OPEN表的前端81324567Goal:58Combines depth- and breadth firstOptimal and complete, memory efficient迭代加深(深度約束=1)123845671238456712384567123845671238456781324567Goal

29、:迭代加深算法 Demo 59迭代加深(深度約束=2)1238456712384567123845671238456741238567123845671238456712384567123845671238456712384567123845675671238481324567Goal:60迭代加深(深度約束=3)1238456712384567123845671238456741238567123845671238456712384567123845671238456712384567123845671238456712384567123845671238456712384567123845

30、6712384567123845675671238481324567Goal:61迭代加深(深度約束=4)123845671238456712384567123845671238456712384567123845671345612367812384567123845671238456712384567Goal12384567123845674123856781324567Goal:問題：當(dāng)d 1 時， 是否能保證找到最優(yōu)解？有界深度優(yōu)先搜索的思路-迭代加深盲目搜索-迭代加深優(yōu)先搜索算法2.2.3 狀態(tài)空間法盲目搜索&啟發(fā)式搜索狀態(tài)空間圖搜索廣度優(yōu)先搜索深度優(yōu)先搜索迭代加深搜索A搜索A*搜索狀

31、態(tài)組合爆炸2.2.3 狀態(tài)空間法64隱式部分(362866 states)顯式部分(14 states)5714563123845671238456712384567（4）（6）（6）2123845671238456712384567（6）（5）（5）1238456712384567（5）（7）1238456712384567（6）（7）12384567（5）8132456712384567（7）123846（4）75Initial StateGoal 8數(shù)碼問題 9! =362,880 states 15數(shù)碼問題 1.3 x 1012 states24數(shù)碼問題 1025 states100

32、millions states/sec 109 years盲目搜索的困境-狀態(tài)組合爆炸！2.2.3 狀態(tài)空間法啟發(fā)性知識 就是與被求解問題自身特性相關(guān)的知識，包括被求解問題的解的特性、解的分布規(guī)律和在實(shí)際當(dāng)中求解此類問題的經(jīng)驗(yàn)、技巧等，對應(yīng)于問題求解框架中的控制性知識。啟發(fā)式搜索的基本思想啟發(fā)函數(shù) 要實(shí)現(xiàn)啟發(fā)式搜索，需要把啟發(fā)性知識形式化，即用一定的函數(shù)表示出來，通過函數(shù)計算來評價每種選擇的價值大小，用以指導(dǎo)搜索過程，這樣的函數(shù)稱為啟發(fā)函數(shù)。 啟發(fā)式搜索2.2.3 狀態(tài)空間法啟發(fā)式搜索的基本思想用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計算與傳播過程，并且由啟

33、發(fā)函數(shù)值來確定節(jié)點(diǎn)的擴(kuò)展順序。啟發(fā)式搜索2.2.3 狀態(tài)空間法在很多實(shí)際問題中，已經(jīng)付出的實(shí)際代價是必須考慮的，如TSP問題等。將兩者同時考慮，用于指導(dǎo)搜索的算法稱為A算法和A*算法。啟發(fā)函數(shù)是對當(dāng)前結(jié)點(diǎn)到達(dá)目標(biāo)結(jié)點(diǎn)未來可能要付出的代價的估計。在全局擇優(yōu)和局部擇優(yōu)搜索算法中，都沒有考慮從初始結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)已經(jīng)付出的實(shí)際代價。啟發(fā)函數(shù)/代價函數(shù)/估價函數(shù)啟發(fā)式搜索2.2.3 狀態(tài)空間法為了防止在單獨(dú)利用啟發(fā)函數(shù)的時候誤入歧途，將啟發(fā)函數(shù)h（x）與代價函數(shù)g（x）相結(jié)合，即初始節(jié)點(diǎn)S0到達(dá)節(jié)點(diǎn)x處已付出的代價與節(jié)點(diǎn)x 到達(dá)目標(biāo)節(jié)點(diǎn)Sg的接近程度估計值總和。估價函數(shù)初始節(jié)點(diǎn)節(jié)點(diǎn)n 目標(biāo)節(jié)點(diǎn)g(n)

34、h(n) f（x） g（x）h（x）啟發(fā)式搜索2.2.3 狀態(tài)空間法Algorithm A (A算法)Uniform-Cost search （等代價搜索）分支界限/瞎子爬山Greedy Search （貪婪搜索）Algorithm A* (A星算法) f(n) = g(n) f(n) = h(n) f(n) = g(n) + h(n) f(n) = g(n) + h(n) , h(n) = h*(n) 估價函數(shù)及其相應(yīng)算法啟發(fā)式搜索2.2.3 狀態(tài)空間法開始把S放入OPEN表OPEN表為空表？把第一個節(jié)點(diǎn)(n)從OPEN表移至CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？把n的后繼節(jié)點(diǎn)放入OPEN表的末端，

35、提供返回節(jié)點(diǎn)n的指針修改指針方向根據(jù)最佳優(yōu)先重排OPEN表失敗成功是是否否(1)(3)(4)(5)(6)(7)(7)(8)(9)OPENCLOSED(1)(2)啟發(fā)式搜索2.2.3 狀態(tài)空間法1.全局擇優(yōu)搜索基本思想：在OPEN表中保留所有已生成而未考察的節(jié)點(diǎn)，并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M(jìn)行估價，從中選出最優(yōu)節(jié)點(diǎn)進(jìn)行擴(kuò)展，而不管這個節(jié)點(diǎn)出現(xiàn)在搜索樹的什么地方。2.局部擇優(yōu)搜索基本思想：局部擇優(yōu)搜索是在啟發(fā)性知識導(dǎo)航下的深度優(yōu)先搜索，在OPEN表中保留所有已生成而未考察的結(jié)點(diǎn)，對其中新生成的每個子結(jié)點(diǎn)x計算啟發(fā)函數(shù)，從全部子結(jié)點(diǎn)中選出最優(yōu)結(jié)點(diǎn)進(jìn)行擴(kuò)展，其選擇下一個要考察結(jié)點(diǎn)的范圍是剛剛生成的

36、全部子結(jié)點(diǎn)，啟發(fā)式搜索的兩類基本策略啟發(fā)式搜索2.2.3 狀態(tài)空間法f（x） g（x）h（x）g（x）：對某一確定的節(jié)點(diǎn)，是確定的值。h（x）：不同的問題啟發(fā)函數(shù)的定義不同，相同的問題也可以定義出不同的啟發(fā)函數(shù)。估價函數(shù)定義探討啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？衡量啟發(fā)式函數(shù)h（x）優(yōu)劣的標(biāo)準(zhǔn)是看其是否能夠準(zhǔn)確反映出節(jié)點(diǎn)x到達(dá)目標(biāo)的難易程度（距離）。2.2.3 狀態(tài)空間法（3）根據(jù)主觀經(jīng)驗(yàn)的主觀打分等。在實(shí)際設(shè)計過程中，啟發(fā)函數(shù)是用來估計搜索樹節(jié)點(diǎn)x與目標(biāo)節(jié)點(diǎn)接近程度的一種函數(shù)，通常根據(jù)下列思路來選擇啟發(fā)函數(shù)：（1）一個結(jié)點(diǎn)到目標(biāo)結(jié)點(diǎn)的某種距離或差異的量度；（2）一個結(jié)點(diǎn)處在最佳路徑上的概率；

37、啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？2.2.3 狀態(tài)空間法啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？帶有比原問題在操作上更少約束條件的問題稱問原問題的一個松弛問題松弛問題原問題的解松弛問題的解2.2.3 狀態(tài)空間法啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？帶有比原問題在操作上更少約束條件的問題稱問原問題的一個松弛問題松弛問題松弛問題中最優(yōu)解的代價函數(shù)是一個admissible的啟發(fā)函數(shù)?。ù鷥r函數(shù)的獲取可通過移除原問題操作中的約束條件來得到）2.2.3 狀態(tài)空間法啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？如果一個啟發(fā)函數(shù)h(x)滿足h(x)=h*(x),則該函數(shù)為一個admissible的啟發(fā)函數(shù)，其中h*(x)為原問

38、題的最優(yōu)解代價函數(shù)Admissibility原問題的解松弛問題的解2.2.3 狀態(tài)空間法1 48 3 27 6 5S01 2 38 47 6 5Sg估價函數(shù)f（x）g（x）h（x）g(x)用節(jié)點(diǎn)深度d（x）來衡量如何定義？例 重排九宮問題中的啟發(fā)式函數(shù)的設(shè)計 啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？2.2.3 狀態(tài)空間法將某個數(shù)字從位置A移動到位置B的操作所需滿足的條件為：啟發(fā)式搜索例 重排九宮問題中的啟發(fā)式函數(shù)的設(shè)計 如何設(shè)計合理的啟發(fā)函數(shù)？條件1：在A處有一個數(shù)字條件2: 在B處有一個空格條件3: 位置A和位置B水平相連或垂直相連2.2.3 狀態(tài)空間法將某個數(shù)字從位置A移動到位置B的操作所需滿足

39、的條件為：啟發(fā)式搜索例 重排九宮問題中的啟發(fā)式函數(shù)的設(shè)計 如何設(shè)計合理的啟發(fā)函數(shù)？條件1：在A處有一個數(shù)字條件2: 在B處有一個空格條件3: 位置A和位置B水平相連或垂直相連h(x)=m(x)=所有錯放位置的數(shù)字到目標(biāo)位置的Manhattan距離之和在移除條件2的情況下，松弛問題的最優(yōu)解為：2.2.3 狀態(tài)空間法m(x) = 3+1+2+2+2+3+3+2 = 18位置A= (i,j) 到位置B= (k,l)的Manhattan距離定義為： |i - k| + |j - l|. Manhattan距離啟發(fā)式搜索如何設(shè)計合理的啟發(fā)函數(shù)？2.2.3 狀態(tài)空間法將某個數(shù)字從位置A移動到位置B的操作所需滿足的條件為：啟發(fā)式搜索例 重排九宮問題中的啟發(fā)式函數(shù)的設(shè)計 如何設(shè)計合理的啟發(fā)函數(shù)？條件1：