第3章圖搜索與問題求解

第3章圖搜索與問題求解搜索與求解概述（2）符號智能中的搜索（第3章圖搜索與問題求解）運用領(lǐng)域知識，以符號推演的方式，順序地在問題空間（可以表示為某種狀態(tài)圖或者是與或圖）上進行，這種搜索也叫圖搜索。模擬人腦分析問題、解決問題的過程而實現(xiàn)的搜索和問題求解技術(shù)。比如啟發(fā)式搜索算法A和A*.計算智能中的搜索（第4章基于遺傳算法的隨機優(yōu)化搜索）以計算的方法，隨機地在問題的解空間中進行模擬和借鑒某些自然現(xiàn)象或生命現(xiàn)象而實現(xiàn)的搜索和問題求解技術(shù)。比如模擬退火算法、遺傳算法、免疫算法、蟻群算法、粒群算法等4/5/20232蟻群算法(antcolonyoptimization,ACO)又稱螞蟻算法，是一種用來在圖中尋找優(yōu)化路徑的機率型技術(shù)。它由MarcoDorigo于1992年在他的博士論文中引入，其靈感來源于螞蟻在尋找食物過程中發(fā)現(xiàn)路徑的行為。

蟻群算法是一種模擬進化算法,初步的研究表明該算法具有許多優(yōu)良的性質(zhì).針對PID控制器參數(shù)優(yōu)化設(shè)計問題,將蟻群算法設(shè)計的結(jié)果與遺傳算法設(shè)計的結(jié)果進行了比較,數(shù)值仿真結(jié)果表明,蟻群算法具有一種新的模擬進化優(yōu)化方法的有效性和應(yīng)用價值.

蟻群算法是一種求解組合最優(yōu)化問題的新型通用啟發(fā)式方法，該方法具有正反饋、分布式計算和富于建設(shè)性的貪婪啟發(fā)式搜索的特點。4/5/20233模擬退火算法（SimulateAnnealArithmetic，SAA）退火：是把工件放在爐中緩慢加熱到臨界點以上的某一溫度，保溫一段時間，隨爐緩慢冷卻下來的一種熱處理工藝。目的是使金屬內(nèi)部組織達到或接近平衡狀態(tài)，獲得良好的工藝性能和使用性能。

模擬退火算法（SimulateAnnealArithmetic，SAA）是一種通用概率演算法，用來在一個大的搜尋空間內(nèi)找尋命題的最優(yōu)解。模擬退火是S.Kirkpatrick,和在1983年所發(fā)明的，是解決TSP問題的有效方法之一。4/5/20234第3章圖搜索與問題求解4/5/20235推理與搜索圖搜索技術(shù)是人工智能的核心技術(shù)之一。任一搜索過程也都是一個推理過程。隱式圖的搜索過程是一種利用局部性知識構(gòu)造全局性答案的過程。在各種搜索過程中，人工智能最感興趣的是那些具有很強選擇性的啟發(fā)式方法，即那些利用很局部的狀態(tài)空間可以有效地找到問題的解的方法。機器學(xué)習(xí)等很多過程都是在假設(shè)空間中搜索目標的過程。4/5/20236第3章圖搜索與問題求解3.1狀態(tài)圖知識表示(3.2.1)3.2狀態(tài)圖搜索(3.1)3.3與或圖知識表示(3.4.1)3.4與或圖搜索(3.3)3.5博弈樹搜索4/5/202373.1.1狀態(tài)圖知識表示3.1問題的狀態(tài)圖表示（教材）

例3.7：迷宮問題的狀態(tài)圖表示

補充例1：翻錢幣問題的狀態(tài)圖表示

補充例2：修道士和野人的狀態(tài)圖表示

例3.8：八數(shù)碼難題的狀態(tài)圖表示

例3.9：梵塔問題的狀態(tài)圖表示

例3.10旅行商問題的狀態(tài)圖表示

總結(jié)：問題求解的基本框架4/5/20238問題的狀態(tài)圖表示（1）例3.1走迷宮走迷宮問題就是從該有向圖的初始節(jié)點出發(fā)，尋找目標節(jié)點的問題，或者是尋找通向目標節(jié)點的路徑問題。4/5/202393.1.1問題的狀態(tài)圖表示（2）例3.2八數(shù)碼難題(重排九宮問題)

2831476512384765初始棋局目標棋局以上兩個問題抽象來看，都是在某個有向圖中尋找目標或路徑的問題，在人工智能技術(shù)中，把這種描述問題的有向圖稱為狀態(tài)空間圖，簡稱狀態(tài)圖。棋局作為節(jié)點，相鄰節(jié)點通過移動數(shù)碼一個一個產(chǎn)生出來，所有節(jié)點由他們的相鄰關(guān)系連成一個有向圖。4/5/2023103.1.1問題的狀態(tài)圖表示（3）狀態(tài)（State）P62問題在任一確定時刻的狀況，它表征了問題特征和結(jié)構(gòu)等。狀態(tài)一般用一組數(shù)據(jù)表示，在程序中用字符、數(shù)字、記錄、數(shù)組、結(jié)構(gòu)、對象等表示表示成矢量形式：一組變量q的有序組合狀態(tài)在狀態(tài)圖中表示為節(jié)點。4/5/2023113.1.1問題的狀態(tài)圖表示（4）狀態(tài)轉(zhuǎn)換規(guī)則（操作operator）能使問題狀態(tài)改變（從一個具體狀態(tài)變化到另一個具體狀態(tài)）的某種操作、規(guī)則、行為、變化、關(guān)系、函數(shù)、算子、過程等。問題的狀態(tài)只能通過狀態(tài)轉(zhuǎn)換規(guī)則而改變。狀態(tài)轉(zhuǎn)換規(guī)則在狀態(tài)圖中表示為邊。在程序中狀態(tài)轉(zhuǎn)換規(guī)則可用數(shù)據(jù)對、條件語句、規(guī)則、函數(shù)、過程等表示。4/5/2023123.1.1問題的狀態(tài)圖表示（5）狀態(tài)空間（StateSpace）問題的狀態(tài)空間是一個表示該問題全部的可能狀態(tài)及相互關(guān)系的構(gòu)成的空間，稱為狀態(tài)空間圖或狀態(tài)圖。狀態(tài)圖一般用一個三元組表示，記為：（S，F(xiàn)，G）S：問題的可能有的初始狀態(tài)的集合；F：問題的狀態(tài)轉(zhuǎn)換規(guī)則（操作）的集合；G：問題的目標狀態(tài)的集合。4/5/2023133.1.1問題的狀態(tài)圖表示（6）狀態(tài)空間中問題求解在狀態(tài)空間表示法中，問題求解過程轉(zhuǎn)化為在圖中尋找從初始狀態(tài)S0出發(fā)到達目標狀態(tài)Sg的路徑問題，也就是尋找操作序列的問題。狀態(tài)空間的解為三元組<S0,O,Sg>S0：某個初始狀態(tài)Sg：某個目標狀態(tài)O：把Ss變換成Sg的有限的操作序列{O1,O2,…,On}狀態(tài)轉(zhuǎn)換圖S1S3S2…O1O2O3O4S0SgOn4/5/202314例3.7迷宮問題的狀態(tài)圖表示迷宮問題的狀態(tài)空間(S,F,G)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é)點和邊。類似于這樣羅列出全部節(jié)點和邊的狀態(tài)圖稱為顯式狀態(tài)圖，或者說狀態(tài)圖的顯式表示。4/5/202315補充例1：翻錢幣問題的狀態(tài)圖表示（1）補充例1：三枚錢幣，能否從下面狀態(tài)翻動三次后出現(xiàn)全正或全反狀態(tài)。反正反正正正反反反初始狀態(tài)Q5目標狀態(tài)集合{Q0,Q7}4/5/202316補充例1：翻錢幣問題的狀態(tài)圖表示（2）引入一個三元組(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)的算子，即F＝{a,b,c}a:把錢幣q0翻轉(zhuǎn)一次b:把錢幣q1翻轉(zhuǎn)一次c:把錢幣q2翻轉(zhuǎn)一次翻錢幣問題的狀態(tài)空間為({Q5},{a,b,c},{Q0Q7})4/5/202317補充例1：翻錢幣問題的狀態(tài)圖表示（3）翻錢幣問題的狀態(tài)圖（0，0，0）（1，0，1）（0，0，1）（0，1，0）（1，1，0）（1，0，0）（0，1，1）（1，1，1）acabacabcbbc翻錢幣問題狀態(tài)圖的解：<{Q5},{b,b,b},{Q7}><{Q5},{a,b,a},{Q7}><{Q5},{c,b,c},{Q7}>4/5/202318補充例2：修道士和野人問題的狀態(tài)圖表示（1）補充例2修道士和野人問題。在河的左岸有三個修道士、三個野人和一條船，修道士們想用這條船將所有的人都運過河去，但受到以下條件的限制：（1）修道士和野人都會劃船，但船一次最多只能運兩個人；（2）在任何岸邊野人數(shù)目都不得超過修道士，否則修道士就會被野人吃掉。假定野人會服從任何一種過河安排，試規(guī)劃出一種確保修道士安全過河方案。4/5/202319補充例2：修道士和野人問題的狀態(tài)圖表示（2）解：先建立問題的狀態(tài)空間。問題的狀態(tài)可以用一個三元數(shù)組來描述：S＝(m,c,b)m：左岸的修道士數(shù)c：左岸的野人數(shù)b：左岸的船數(shù)右岸的狀態(tài)不必標出，因為：右岸的修道士數(shù)m’＝3－m右岸的野人數(shù)c’＝3－c右岸的船數(shù)b’=1-b4/5/202320補充例2：修道士和野人問題的狀態(tài)圖表示（3）狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,b狀態(tài)m,c,bS0331S8131S16330S24130S1321S9121S17320S25120S2311S10111S18310S26110S3301S11101S19300S27100S4231S12031S20230S28

030S5221S13021S21220S29020S6211S14011S22210S30010S7201S15001S23200S31000狀態(tài)不合法由合理的狀態(tài)轉(zhuǎn)換規(guī)則無法退出4/5/202321補充例2：修道士和野人問題的狀態(tài)圖表示（4）問題的狀態(tài)空間為({S0},{p01,p10,p11,p02,p20,q01,q10,q11,q02,q20},{S31})q20b=0,(m=0,c=2)或(m=1,c=1)b=1,m=m+2q02b=0,m=0或3,c≤2b=1,c=c+2q11b=0,m=c,c≤2b=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,c≤2b=1,c=c+1p20b=1,(m=3,c=1)或(m=2,c=2)b=0,m=m-2p02b=1,m=0或3,c≥2b=0,c=c-2p11b=1,m=c,c≥1b=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,c≥1b=0,c=c-1操作符條件動作4/5/202322補充例2：修道士和野人問題的狀態(tài)圖表示（5）S0(3,3,1)S18(3,1,0)p02q02S17(3,2,0)p01q01S21(2,2,0)q11p11S1(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)q11p11修道士和野人過河問題狀態(tài)圖的解：<{S0},{p02,q01,p02,q01,p20,q11,p20,q01,p02,q01,p02},{S31}><{S0},{p02,q01,p02,q01,p20,q11,p20,q01,p02,q10,p11},{S31}><{S0},{p11,q10,p02,q01,p20,q11,p20,q01,p02,q01,p02},{S31}><{S0},{p11,q10,p02,q01,p20,q11,p20,q01,p02,q10,p11},{S31}>4/5/202323野人傳教士過河問題設(shè)有3個傳教士（Missionaries）和3個野人(Cannibals)來到河邊，打算乘一只船從右岸渡到左岸去。該船的最大負荷能力為兩個人（k=2）。在任何情況下：如果野人人數(shù)超過傳教士人數(shù)，那么野人就會把傳教士吃掉。他們怎樣才能用這條船安全地把所有人都渡過河去呢？（提示：用狀態(tài)空間來描述，其綜合數(shù)據(jù)庫：用三元數(shù)組表示。即（M，C，L），其中0≤M，C≤3,k=2;L∈{0,1}(0-船在左岸,1-船在右岸)問題描述簡化為：（3，3，1）→（0，0，0）請分析給出（1）完整的規(guī)則集合（2）符合規(guī)則的狀態(tài)數(shù)量是多少？分別就“達不到”和“不合法”狀態(tài)給予說明？（3）渡法說明（做出推理圖）4/5/202324(1)完整的規(guī)則集合if(MR,CR,LR=1)then(MR-1,CR,LR-1);if(MR,CR,LR=1)then(MR,CR-1,LR-1);if(MR,CR,LR=1)then(MR-1,CR-1,LR-1);if(MR,CR,LR=1)then(MR-2,CR,LR-1);if(MR,CR,LR=1)then(MR,CR-2,LR-1);if(MR,CR,LR=0)then(MR+1,CR,LR+1);if(MR,CR,LR=0)then(MR,CR+1,LR+1);if(MR,CR,LR=0)then(MR+1,CR+1,LR+1);if(MR,CR,LR=0)then(MR+2,CR,LR+1);if(MR,CR,LR=0)then(MR,CR+2,LR+1);4/5/202325(2)狀態(tài)空間(總狀態(tài)數(shù)為4×4×2=32，只有20個合法狀態(tài)，其中有4個合法狀態(tài)達不到，最終解空間由16個狀態(tài)組成，下面給出說明(M,C,L)(M,C,L)(001)達不到(000)(011)(010)(021)(020)(031)(030)達不到(101)不合法(100)不合法(111)(110)(121)不合法(120)不合法(131)不合法(130)不合法(201)不合法(200)不合法(211)不合法(210)不合法(221)(220)(231)不合法(230)不合法(301)達不到(300)(311)(310)(321)(320)(331)(330)達不到4/5/202326(3)渡法說明2個野人去，1個野人回2個野人去，1個野人回2個傳教士去，1個野人與1個傳教士回2個傳教士去，1個野人回2個野人去，1個野人回2個野人去，完成4/5/202327例3.8：八數(shù)碼難題的狀態(tài)圖表示（1）也叫重排九宮問題X1X2X3X8X0X4X7X6X5將棋局用向量A＝(X0，X1，

X2，

X3，

X4，

X5，

X6，

X7，

X8)表示，其中Xi為變量，值表示方格Xi內(nèi)的數(shù)字。初始狀態(tài)S0＝（0，2，8，3，4，5，6，7，1）目標狀態(tài)Sg＝（0，1，2，3，4，5，6，7，8）數(shù)碼的移動規(guī)則就是該問題的狀態(tài)變化規(guī)則。經(jīng)分析，該問題共有24條規(guī)則，分為9組。2831476512384765初始棋局目標棋局4/5/202328例3.8：八數(shù)碼難題的狀態(tài)圖表示（2）0組規(guī)則r1(X0=0

)(X2=n

)X0=nX2=0；r2(X0=0

)(X4=n

)X0=nX4=0；r3(X0=0

)(X6=n

)X0=nX6=0；r4(X0=0

)(X8=n

)X0=nX8=0；1組規(guī)則r5(X1=0

)(X2=n

)X1=nX2=0；r6(X1=0

)(X8=n

)X1=nX8=0；8組規(guī)則:r22(X8=0

)(X1=n

)X8=nX1=0；r23(X8=0

)(X0=n

)X8=nX0=0；r24(X8=0

)(X7=n

)X8=nX7=0；……4/5/202329例3.8：八數(shù)碼難題的狀態(tài)圖表示（3）八數(shù)碼難題的狀態(tài)圖可表示為（{S0},{r1,r2,…,r24},{Sg}）八數(shù)碼問題狀態(tài)圖僅給出了初始節(jié)點和目標節(jié)點，其余節(jié)點需用狀態(tài)轉(zhuǎn)換規(guī)則來產(chǎn)生。類似于這樣表示的狀態(tài)圖稱為隱式狀態(tài)圖，或者說狀態(tài)圖的隱式表示。4/5/202330例3.9：梵塔問題的狀態(tài)圖表示（1）例3.9二階梵塔問題一號桿有A、B兩個金盤，A小于B。要求將A、B移至三號桿，每次只可移動一個盤子，任何時刻B不能在A上。

用二元組（SA，SB）表示狀態(tài)，SA表示A所在桿號，SB表示B所在桿號，全部狀態(tài)如下：（1，1），（1，2），（1，3）（2，1），（2，2），（2，3）（3，1），（3，2），（3，3）4/5/202331例3.9：梵塔問題的狀態(tài)圖表示（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)AAAAABABBBBB4/5/202332例3.9：梵塔問題的狀態(tài)圖表示（3）轉(zhuǎn)換規(guī)則：A（i，j）表示金盤A從第i號桿移到j(luò)號桿B（i，j）表示金盤B從第i號桿移到j(luò)號桿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），B（3，1），B（3，2）初始狀態(tài)（1，1），目標狀態(tài)（3，3）梵塔問題用狀態(tài)圖表示為：<{(1,1)},{A(1,2),…，B(3,2)},{(3,3)}>4/5/202333例3.9：梵塔問題的狀態(tài)圖表示（4）1,12,13,12,33,31,33,21,22,2A(1,2)A(1,3)B(1,2)A(3,2)A(1,2)B(2,3)A(3,1)B(1,3)A(2,3)梵塔問題狀態(tài)圖的解：<{(1,1)},{A(1,2),B(1,3),A(2,3)},{(3,3)}><{(1,1)},{A(1,3),B(1,2),A(3,1),B(2,3),A(1,3)},{(3,3)}>………………A(3,1)A(1,2)A(2,3)B(3,2)B(2,1)A(3,1)B(3,1)4/5/202334例3.9的擴展-n階梵塔問題（n≥3）假設(shè)金片Pk從小片到大片按下標k順序編號，即k=1，2，3，…，n，n階梵塔問題狀態(tài)空間可用矢量表示為：(P1,P2,P3,…,Pk,…,Pn)Pk表示第k個金片穿在編號為Pk的寶石針上，Pk={1，2，3}初始狀態(tài)S0=(1,1,1,…,1,…,1)目標狀態(tài)Sg1=(2,2,2,…,2,…,2)Sg2=(3,3,3,…,3,…,3)4/5/202335例3.9的擴展-n階梵塔問題（n≥3）n階梵塔問題的操作集合表示為：F={Rk(i,j)|i,j={1,2,3}，k={1，2，…，n}}全部可能狀態(tài)數(shù)為3n個，最佳解長度為2n-1。三階梵塔問題狀態(tài)圖S0=(1,1,1)Sg2=(3,3,3)Sg1=(2,2,2)4/5/202336例3.10旅行商問題旅行商問題(TravelingSalesmanProblem，簡稱TSP)。設(shè)有n個互相可直達的城市，某推銷商準備從其中的A城出發(fā)，周游各城市一遍，最后又回到A城。要求為該推銷商規(guī)劃一條最短的旅行路線。其狀態(tài)空間為：以A打頭的已訪問過的城市序列:A…初始狀態(tài)：S0:A。目標狀態(tài)：Sg:A,…,A。其中“…”為其余n-1個城市的一個序列。狀態(tài)轉(zhuǎn)換規(guī)則F：規(guī)則1:如果當(dāng)前城市的下一個城市還未去過，則去該城市，并把該城市名排在已去過的城市名序列后端。規(guī)則2:如果所有城市都去過一次，則從當(dāng)前城市返回A城，把A也添在去過的城市名序列后端。4/5/202337總結(jié)：問題求解的基本框架（1）問題求解所需要的知識與描述問題的狀態(tài)有關(guān)的各種敘述性知識。描述狀態(tài)之間的變換關(guān)系的各種過程性知識。一般以一組操作的形式出現(xiàn)。任一操作都含有條件和動作兩部分條件給定了操作的適用范圍動作描述了由于操作而引起的狀態(tài)中某些分量的變化情形。描述如何根據(jù)當(dāng)前狀態(tài)和目標狀態(tài)選擇合適的操作的控制性知識。根據(jù)敘述性和過程性知識可以構(gòu)造問題的狀態(tài)空間。狀態(tài)空間是一個有向圖，節(jié)點對應(yīng)著問題的狀態(tài)，邊對應(yīng)操作。4/5/202338總結(jié)：問題求解的基本框架（2）問題求解就是在圖中尋找一條從初始節(jié)點到達目標節(jié)點的路徑或操作序列。首先從操作集中選擇可作用在當(dāng)前狀態(tài)上的操作；如果符合條件的操作有許多個，則要從挑選出最有希望導(dǎo)致目標狀態(tài)的操作施加到當(dāng)前狀態(tài)上，以克服組合爆炸；如果解的長度很大，還需要更為復(fù)雜的克服組合爆炸的技術(shù)。4/5/2023393.1狀態(tài)圖搜索3.1.2狀態(tài)圖搜索3.1.3窮舉式搜索3.1.4啟發(fā)式搜索3.1.5加權(quán)狀態(tài)圖搜索3.1.6啟發(fā)式圖搜索的A算法和A*算法3.1.7狀態(tài)圖搜索策略小結(jié)4/5/2023403.1.2狀態(tài)圖搜索搜索：從初始節(jié)點出發(fā)，沿著與之相連的邊試探地前進，尋找目標節(jié)點的過程。搜索過程中經(jīng)過的節(jié)點和邊，按原圖的連接關(guān)系，便會構(gòu)成一個樹型的有向圖，這種樹型有向圖稱為搜索樹。搜索進行中，搜索樹會不斷增長，直到當(dāng)搜索樹中出現(xiàn)目標節(jié)點，搜索便停止。這時從搜索樹中就可很容易地找出從初始節(jié)點到目標節(jié)點的路徑（解）來。

4/5/2023413.1.2狀態(tài)圖搜索-搜索方式1搜索方式樹式搜索：在搜索過程中記錄所經(jīng)過的所有節(jié)點和邊。樹式搜索所記錄的軌跡始終是一棵樹，這棵樹也就是搜索過程中所產(chǎn)生的搜索樹。搜索過程中擴展節(jié)點時需記錄結(jié)點間的父子關(guān)系。問題的解：搜索成功后，從目標結(jié)點反向沿搜索樹按所作標記追溯一直到初始結(jié)點，所得到一條從初始結(jié)點到目標結(jié)點的路徑就是問題的一個解。線式搜索：在搜索過程中只記錄那些當(dāng)前認為在所找路徑上的節(jié)點和邊。不回溯線式搜索可回溯線式搜索問題的解：搜索成功后，搜索線（CLOSED表）就是問題的解。4/5/2023423.1.2狀態(tài)圖搜索-搜索策略2搜索策略盲目搜索：無向?qū)У乃阉?，樹式盲目搜索就是窮舉搜索，不回溯的線式搜索是隨機碰撞式搜索，回溯的線式搜索也是窮舉式搜索。啟發(fā)式(heuristic)搜索：有向?qū)У乃阉鳎抢脝l(fā)性信息引導(dǎo)的搜索策略。啟發(fā)性信息：就是與問題有關(guān)的有利于盡快找到問題解的信息或知識。啟發(fā)式搜索策略分為：全局擇優(yōu)局部擇優(yōu)最佳圖搜索。按搜索范圍的擴展順序不同分為廣度優(yōu)先和深度優(yōu)先。樹式搜索可以分為廣度優(yōu)先和深度優(yōu)先兩種類型線式搜索只能按深度優(yōu)先進行。4/5/2023433.1.2狀態(tài)圖搜索-搜索算法3

搜索算法搜索的目的是為了尋找初始節(jié)點到目標節(jié)點的路徑，搜索過程中就得隨時記錄搜索軌跡。OPEN表的動態(tài)數(shù)據(jù)結(jié)構(gòu)來專門登記當(dāng)前待考查的節(jié)點。ClOSED表動態(tài)數(shù)據(jù)結(jié)構(gòu)來記錄考察過的節(jié)點。節(jié)點父節(jié)點編號編號節(jié)點父節(jié)點編號OPEN表CLOSED表4/5/2023443.1.2狀態(tài)圖搜索-樹式搜索算法步1把初始節(jié)點S0放入OPEN表中。步2若OPEN表為空，則搜索失敗，退出。步3取OPEN表中第一個節(jié)點N放在CLOSED表中并冠以順序編號n；步4若目標節(jié)點Sg=N，成功退出。步5若N不可擴展，轉(zhuǎn)步2。步6擴展N，生成一組節(jié)點，對這組子節(jié)點作如下處理：（1）刪除N的先輩節(jié)點（如果有的話）。（2）對已存在于OPEN表中的節(jié)點（如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點在OPEN表中的原返回指針，使其沿新路徑返回。（3）對已存在于CLOSED表的節(jié)點（如果有的話），作與（2）同樣的處理，并且將其移出CLOSED表，放入OPEN表中重新擴展。（4）對其余子節(jié)點配上指向N的返回指針后放入OPEN表中某處，或?qū)PEN表進行重新排序，轉(zhuǎn)步2。4/5/2023453.1.2狀態(tài)圖搜索-樹式搜索算法流程圖4/5/2023463.1.2狀態(tài)圖搜索-修改返回指針示例圖3-5修改返回指針示例

4/5/2023473.1.2狀態(tài)圖搜索-樹式搜索示例樹式搜索例對于已存在于OPEN表中的節(jié)點（如果有的話）也刪除之；刪除之前要比較其返回初始節(jié)點的新路徑與原路徑，如果新路徑短，則修改這些節(jié)點在OPEN表中的原返回指針，使其沿新路徑返回。P在n之前已是某一節(jié)點m的后繼如圖所示：說明從S0→P至少有兩條路，有兩種情況：f(Path2)<f(Path1)，Path2較好，要修改P的指針(原指向m)，使其指向n，即搜索之后的最佳路徑。f(Path2)>f(Path1)

，原路徑當(dāng)前最優(yōu)。Path1Path2S0mn先擴展后擴展P4/5/2023483.1.2狀態(tài)圖搜索-樹式搜索示例對已存在于CLOSED表的節(jié)點（如果有的話），作與（2）同樣的處理，并將其移出CLOSED表，放入OPEN表中重新擴展。S0過去生成P的路徑現(xiàn)在生成P的路徑過去對Ps的最優(yōu)路徑PsPmnFa.P在n之前已是某一節(jié)點m的后繼，所以需要做如同（2）同樣的處理，如圖右部所示。b.P在CLOSED表中，說明P的后繼也在n之前已經(jīng)生成，稱為Ps。對Ps而言,由于n→P這一路徑的加入，又必須比較多條路徑之后而取代價小的一條，如圖左部所示。4/5/2023493.1.2狀態(tài)圖搜索-樹式搜索示例例：設(shè)當(dāng)前搜索圖和搜索樹如下所示S0nPmPs’PsS0nPmPs’PsFF搜索圖搜索樹4/5/2023503.1.2狀態(tài)圖搜索-樹式搜索示例若啟發(fā)函數(shù)f(n)為從S0到節(jié)點n的最短路徑的長度，用邊的數(shù)目來考察，當(dāng)前擴展的節(jié)點是搜索圖中的n,P是n的后繼S0nPmPs’PsnPPs’PsS0mFF搜索圖搜索樹4/5/2023513.1.2狀態(tài)圖搜索-樹式搜索示例P的指針改變后(其雙親從m改成n)，修改搜索樹結(jié)果如下：nPPsS0FmPs’nPPs’PsS0mF修改前修改后4/5/2023523.1.2狀態(tài)圖搜索-樹式搜索的說明樹式算法的幾點說明返回指針指的是父節(jié)點在CLOSED表中的編號。步6中修改指針的原因是返回初始節(jié)點的路徑有兩條，要選擇“短”的那條路徑。這里路徑長短以節(jié)點數(shù)來衡量，在后面將會看到以代價來衡量。按代價衡量修改返回指針的同時還要修改相應(yīng)的代價值。4/5/2023533.1.2狀態(tài)圖搜索-不回溯線式搜索算法步1把初始節(jié)點S0放入CLOSED表中；步2令N＝S0；步3若N是目標節(jié)點，則搜索成功，結(jié)束。步4若N不可擴展，則搜索失敗，退出。步5擴展N，選取其一個未在CLOSED表中出現(xiàn)過的子節(jié)點N1放入CLOSED表中，令N＝N1，轉(zhuǎn)步3。4/5/2023543.1.2狀態(tài)圖搜索-可回溯的線式搜索步1把初始節(jié)點S0放入CLOSED表中；步2令N＝S0；步3若N是目標節(jié)點，則搜索成功，結(jié)束。步4若N不可擴展，則移出CLOSED表中的末端節(jié)點Ne，若Ne＝S0，則搜索失敗，退出。否則以CLOSED表新的末端節(jié)點Ne作為N，即令N＝Ne，轉(zhuǎn)步4；步5擴展N，選取其一個未在CLOSED表中出現(xiàn)過的子節(jié)點N1放入CLOSED表中，令N＝N1，轉(zhuǎn)步3。4/5/2023553.1.3窮舉式搜索（1）僅討論樹式結(jié)構(gòu)的狀態(tài)圖的樹式搜索。樹式窮舉搜索分類廣度優(yōu)先搜索深度優(yōu)先搜索4/5/2023563.1.3窮舉式搜索-廣度優(yōu)先搜索算法廣度優(yōu)先搜索（算法A?ed）策略始終在同一級節(jié)點中考查，當(dāng)同一級節(jié)點考查完了之后，才考查下一級節(jié)點。搜索樹自頂向下一層一層逐漸生成。算法

步1把初始節(jié)點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出。步3取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以順序編號n；步4若節(jié)點N為目標節(jié)點，成功退出。步5若N不可擴展，轉(zhuǎn)步2；步6擴展N，將其所有子節(jié)點配上指向N的指針放入OPEN尾部，轉(zhuǎn)步2。4/5/2023573.1.3窮舉式搜索-廣度優(yōu)先搜索算法流程圖4/5/2023583.1.3窮舉式搜索-廣度優(yōu)先搜索示例八數(shù)碼問題28314765初始狀態(tài)81324765目標狀態(tài)4/5/2023593.1.3窮舉式搜索-廣度優(yōu)先搜索示例28314765S023184765S823184765S728143765S928371465S683214765S528314576S1028314765S123184765S228314765S328316475S1128316475S1283214765S1328371465S1423418765S1512384765S1628143765S1728314576S1828364175S1928316754S2083214765S2128316475S481324765Sg八數(shù)碼廣度優(yōu)先搜索4/5/2023603.1.3窮舉式搜索-廣度優(yōu)先搜索特點廣度優(yōu)先搜索的特點廣度優(yōu)先中OPEN表是一個隊列，CLOSED表是一個順序表，表中各節(jié)點按順序編號，正被考察的節(jié)點在表中編號最大。廣度優(yōu)先搜索又稱為寬度優(yōu)先或橫向搜索。廣度優(yōu)先策略是完備的，即如果問題的解存在，則它一定可以找到解，并且找到的解還是最優(yōu)解。廣度優(yōu)先搜索策略與問題無關(guān)，具有通用性。缺點搜索效率低。4/5/2023613.1.3窮舉式搜索-深度優(yōu)先搜索深度優(yōu)先搜索（過程Apd）搜索策略

在搜索樹的每一層始終先擴展一個子節(jié)點，不斷地向縱深前進，直到不能再前進，才從當(dāng)前節(jié)點返回到上一級節(jié)點，從另一方向繼續(xù)前進。算法步1

把初始節(jié)點S0放入OPEN表中；步2

若OPEN表為空，則搜索失敗，退出。步3

取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以編號n；

步4

節(jié)點N為目標節(jié)點，成功退出。步5

若N不可擴展，轉(zhuǎn)步2；步6

擴展N，將其所有子節(jié)點配上指向N的指針放入OPEN首部，轉(zhuǎn)步2。4/5/2023623.1.3窮舉式搜索-深度優(yōu)先搜索算法流程圖4/5/2023633.1.3窮舉式搜索-深度優(yōu)先搜索示例2318476528314765283147652831647528314765S028316475S228316754S328316475S12831675428163754S4…八數(shù)碼深度優(yōu)先搜索4/5/2023643.1.3窮舉式搜索-深度優(yōu)先搜索特點深度優(yōu)先搜索的特點OPEN表為一個堆棧。深度優(yōu)先又稱縱向搜索。一般不能保證找到最優(yōu)解。當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制，即有界深度優(yōu)先搜索。最壞情況時，搜索空間等同于窮舉。4/5/2023653.1.3窮舉式搜索-深度優(yōu)先搜索改進有界深度優(yōu)先搜索（過程Acd）搜索策略給出搜索樹深度的限制，當(dāng)從初始節(jié)點出發(fā)沿某一分支擴展到一定深度限制時，就不能再繼續(xù)往下擴展，而只能改變方向繼續(xù)搜索。算法步1把初始節(jié)點S0放入OPEN表中，置S0的深度d(S0)＝0；步2若OPEN表為空，則搜索失敗，退出。步3取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以編號n；步4若節(jié)點N為目標節(jié)點，成功退出。步5若N的深度d(N)＝dm（深度限制值），或者若N無子節(jié)點，則轉(zhuǎn)步2；步6擴展N，將其所有子節(jié)點Ni配上指向N的指針放入OPEN首部，置的d(Ni)＝d(N)＋1，轉(zhuǎn)步2。4/5/2023663.1.3窮舉式搜索-有界深度優(yōu)先搜索示例a1a2a3a6b1b2b4b3b5S假設(shè)dm=34/5/2023673.1.3窮舉式搜索-有界深度優(yōu)先搜索有界深度優(yōu)先搜索存在的問題深度界限的選擇很重要dm若太小，則達不到解的深度，得不到解；若太大，既浪費了計算機的存儲空間與時間，又降低了搜索效率。由于解的路徑長度事先難以預(yù)料，所以要恰當(dāng)?shù)亟o出dm的值是比較困難的。即使能求出解，它也不一定是最優(yōu)解。4/5/2023683.1.3窮舉式搜索-有界深度優(yōu)先搜索改進有界深度優(yōu)先搜索改進dm隨搜索深度不斷加大（迭代加深搜索）

先任意給定一個較小的數(shù)作為dm，然后進行上述的有界深度優(yōu)先搜索，當(dāng)搜索達到了指定的深度界限dm仍未發(fā)現(xiàn)目標節(jié)點，并且CLOSED表中仍有待擴展節(jié)點時．就將這些節(jié)點送回OPEN表，同時增大深度界限dm，繼續(xù)向下搜索。如此不斷地增大dm，只要問題有解，就一定可以找到它。增加一個R表此時找到的解不一定是最優(yōu)解。為找到最優(yōu)解，可增設(shè)一個表(R)，每找到一個目標節(jié)點Sg后，就把它放入到R的前面，并令dm等于該目標節(jié)點所對應(yīng)的路徑長度，然后繼續(xù)搜索。由于后求得的解的路徑長度不會超過先求得的解的路徑長度，所以最后求得的解一定是最優(yōu)解。4/5/2023693.1.3窮舉式搜索-迭代加深搜索迭代加深搜索過程：步1把初始節(jié)點S0放入OPEN表中，置S0的深度d（S0）＝0，dm為任意初值。步2若OPEN表為空，則考查CLOSED表是否有待擴展節(jié)點：

①若無，則問題無解，退出。②若有，則取出CLOSED表中待擴展節(jié)點放入到OPEN表中，令dm=dm+⊿d。步3取OPEN表中第一個節(jié)點N放在CLOSED表中；并冠以編號n；步4若節(jié)點N為目標節(jié)點，成功退出。步5若N的深度d(N)＞dm（深度限制值），則標N為待擴展節(jié)點，則轉(zhuǎn)步2；步6N無子節(jié)點，則轉(zhuǎn)步2；步7擴展N，將其所有子節(jié)點Ni配上指向N的指針放入OPEN首部，置d（Ni）＝d（N）＋1，轉(zhuǎn)步2。4/5/2023704/5/202371狀態(tài)圖搜索策略樹式搜索盲目搜索窮舉式廣度優(yōu)先深度優(yōu)先有界深度優(yōu)先啟發(fā)式搜索全局擇優(yōu)(最好優(yōu)先，基于啟發(fā)函數(shù)h(x))局部擇優(yōu)(瞎子爬山，基于h(x))分支界限(全局最小代價優(yōu)先，基于代價g(x))最近擇優(yōu)(瞎子爬山，局部最小代價優(yōu)先，基于g(x))A算法(基于估價函數(shù)f(x)＝g(x)＋h(x))A*算法(最佳圖搜索，h(x)<=h*(x))線式搜索盲目搜索隨機碰撞回溯窮舉（生成－測試法）啟發(fā)式搜索不回溯（瞎子爬山，基于h(x)、g(x)、f(x)）智能回溯（啟發(fā)式生成－測試法）4/5/2023723.1.4啟發(fā)式搜索（1）啟發(fā)式搜索的提出窮舉式搜索只能解決一些狀態(tài)空間很小的簡單問題啟發(fā)式搜索的目的利用啟發(fā)式信息來引導(dǎo)搜索，達到減少搜索范圍，降低問題復(fù)雜度的目的。啟發(fā)式信息：有利于盡快找到問題的解的信息啟發(fā)性信息的強弱

強：降低搜索的工作量，但可能導(dǎo)致找不到最優(yōu)解。弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解。啟發(fā)性信息的類型用于擴展節(jié)點的選擇用于生成節(jié)點的選擇用于刪除節(jié)點的選擇4/5/2023733.1.4啟發(fā)式搜索（2）啟發(fā)函數(shù)啟發(fā)函數(shù)是用來估計搜索樹節(jié)點x與目標節(jié)點接近程度的一種函數(shù)，通常記為h(x)。定義啟發(fā)函數(shù)的參考思路一個節(jié)點到目標節(jié)點的某種距離或差異的量度。一個節(jié)點處在最佳路徑上的概率根據(jù)主觀經(jīng)驗的主觀打分等。啟發(fā)式搜索算法啟發(fā)式搜索要用啟發(fā)函數(shù)來導(dǎo)航，其搜索算法就要在狀態(tài)圖一般搜索算法基礎(chǔ)上再增加啟發(fā)函數(shù)值的計算與傳播過程，并且由啟發(fā)函數(shù)值來確定節(jié)點的擴展順序。4/5/2023743.1.4啟發(fā)式搜索-全局擇優(yōu)搜索全局擇優(yōu)搜索全局擇優(yōu)搜索就是利用啟發(fā)函數(shù)制導(dǎo)的一種啟發(fā)式搜索方法。該方法亦稱為最好優(yōu)先搜索法?；舅枷耄涸贠PEN表中保留所有已生成而未考查的節(jié)點，并用啟發(fā)函數(shù)h(x)對它們?nèi)窟M行估價，從中選出最優(yōu)節(jié)點進行擴展，而不管這個節(jié)點出現(xiàn)在搜索樹的什么地方。4/5/2023753.1.4啟發(fā)式搜索-全局擇優(yōu)搜索算法步1把初始節(jié)點S0放入OPEN表中，計算h(S0)；步2若OPEN表為空，則搜索失敗，退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以序號n；步4若目標節(jié)點Sg＝N，則搜索成功結(jié)束。步5若N不可擴展，則轉(zhuǎn)步2。步6擴展N，計算每個子節(jié)點x的函數(shù)值h(x)，并將所有子節(jié)點配以指向N的返回指針后放入OPEN表中，再對OPEN表中所有子節(jié)點按其啟發(fā)函數(shù)值的大小以升序排列，轉(zhuǎn)步2。4/5/2023763.1.4啟發(fā)式搜索-全局擇優(yōu)搜索示例啟發(fā)函數(shù)h(x)為節(jié)點x與目標格局相比數(shù)碼不同的位置個數(shù)。從圖看出解為：S0，S1，S5，S9，

Sg。283147655231847654283164755283714655832147653383214765S5283214765S9081324765Sg28314765S0283147654S1Sg81324765S2S3S4S6S10231847654231837655S7S84/5/2023773.1.4啟發(fā)式搜索-局部擇優(yōu)搜索局部擇優(yōu)搜索局部擇優(yōu)搜索是一種啟發(fā)式搜索方法，是對深度優(yōu)先搜索方法的一種改進?；舅枷胧钱?dāng)每一個節(jié)點被擴展后，按h(x)對每一個子節(jié)點計算啟發(fā)值，并選擇最小者作為下一個要考察的節(jié)點，由于每次都只是在子節(jié)點的范圍內(nèi)選擇下一個要考察的節(jié)點，范圍比較狹窄，所以稱為局部擇優(yōu)搜索。4/5/2023783.1.4啟發(fā)式搜索-局部擇優(yōu)搜索算法局部擇優(yōu)搜索算法步1把初始節(jié)點S0放入OPEN表中，計算h(S0)；步2若OPEN表為空，則搜索失敗，退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以序號n；步4若目標節(jié)點Sg＝N，則搜索成功結(jié)束。步5若N不可擴展，則轉(zhuǎn)步2。步6擴展N，計算N每個子節(jié)點x的函數(shù)值h(x)，并將N的子節(jié)點按估計值升序排列放入OPEN表的首部，為每個子節(jié)點配置指向節(jié)點N的指針，轉(zhuǎn)步

2。4/5/2023793.1.4啟發(fā)式搜索-局部擇優(yōu)搜索示例啟發(fā)函數(shù)h(x)為節(jié)點x與目標格局相比數(shù)碼不同的離家路程長度。從圖看出解為：S0，S1，S5，S7，

Sg。283147654231847655283164755283714654832147652283214765S5183214765S7081324765Sg28314765S0283147653S1Sg81324765S2S4S3S8S64/5/2023803.1.5加權(quán)狀態(tài)圖搜索（1）例3.6是一個交通圖，A城是出發(fā)地，E是目的地，邊上數(shù)字表示兩城之間交通費用（也可表示距離）。求A到E的最小費用的旅行路線。ADCEB4643324/5/2023813.1.5加權(quán)狀態(tài)圖搜索（2）加權(quán)狀態(tài)圖與代價樹加權(quán)狀態(tài)圖：邊上附有數(shù)值的狀態(tài)圖稱為加權(quán)狀態(tài)圖或賦權(quán)狀態(tài)圖，這種數(shù)值稱為權(quán)值。加權(quán)狀態(tài)圖的搜索：搜索與權(quán)值有關(guān)，并且要用權(quán)值來導(dǎo)航。加權(quán)狀態(tài)圖的搜索算法，要在一般狀態(tài)圖搜索算法基礎(chǔ)上再增加權(quán)值的計算與傳播過程，并且要由權(quán)值來確定節(jié)點的擴展順序。代價樹：樹型的加權(quán)狀態(tài)圖。代價指兩點之間的距離、交通費用或所需時間等。代價的計算：g(x)表示從初始節(jié)點S0到節(jié)點x的代價。c(xi,xj)表示父節(jié)點xi到子節(jié)點xj的代價g(xj)＝g(xi)＋c(xi,xj)g(S0)＝04/5/2023823.1.5加權(quán)狀態(tài)圖搜索（3）加權(quán)狀態(tài)圖轉(zhuǎn)換為代價樹從初始節(jié)點出發(fā)，先把每一個與初始節(jié)點相鄰的節(jié)點作為該節(jié)點的子節(jié)點。然后對其他節(jié)點依次類推，但對其他節(jié)點x，不能將其父節(jié)點及祖先再作為x的子節(jié)點。ADCEB464332323462344632C1B1D1D2E3C2E4D3C3B2E2E16B3A加權(quán)狀態(tài)圖代價樹4/5/2023833.1.5加權(quán)狀態(tài)圖搜索-分支界限搜索分支界限法(最小代價優(yōu)先法，A*eg)其基本思想是：每次從OPEN表中選出g(x)值最小的節(jié)點進行考察，而不管這個節(jié)點在搜索樹的什么位置上。與全局擇優(yōu)法（最好優(yōu)先法）的區(qū)別選取擴展節(jié)點標準計算方法分支界限法代價值g(x)g(x)與節(jié)點所處的位置有關(guān)，與邊也有關(guān)系，從初始節(jié)點S0計算而來。全局擇優(yōu)法啟發(fā)函數(shù)值h(x)h(x)與節(jié)點有關(guān)，與邊可能有關(guān)或無關(guān)，從目標節(jié)點方向計算而來。4/5/2023843.1.5加權(quán)狀態(tài)圖搜索-分支界限搜索算法分支界限搜索算法步1把初始節(jié)點S0放入OPEN表中，計算g(S0)；步2若OPEN表為空，則搜索失敗，退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以序號n；步4若目標節(jié)點Sg＝N，則搜索成功結(jié)束。步5若N不可擴展，則轉(zhuǎn)步2。步6擴展N，并將所有子節(jié)點配以指向N的返回指針后放

OPEN表中；計算每個子節(jié)點x的函數(shù)值g(x)，再對OPEN表中所有子節(jié)點按g(x)值的大小以升序排列，轉(zhuǎn)步2。4/5/2023853.1.5加權(quán)狀態(tài)圖搜索-分支界限搜索示例323462344632C1B1D1D2E1C2E3D3C3B2E4E26B3編號節(jié)點父節(jié)點編號代價1A*02C1133B1144D1255D2386E248ACLOSED表OPEN表節(jié)點父節(jié)點編號代價A*0C113B114D125D238E248B249E1310C2510E25114/5/2023863.1.5加權(quán)狀態(tài)圖搜索-最近擇優(yōu)搜索最近擇優(yōu)法（瞎子爬山法，Apg）基本思想：每次僅考察N的子節(jié)點的g(x)，選取N的子節(jié)點中代價最小的子節(jié)點進行擴展。最近擇優(yōu)法與局部擇優(yōu)法的區(qū)別：選取擴展節(jié)點標準計算方法最近擇優(yōu)法代價值g(x)g(x)與節(jié)點所處的位置有關(guān)，與邊也有關(guān)系，從初始節(jié)點S0計算而來。局部擇優(yōu)法啟發(fā)函數(shù)h(x)h(x)與節(jié)點有關(guān)，與邊可能有關(guān)或無關(guān)，從目標節(jié)點方向計算而來。4/5/2023873.1.5加權(quán)狀態(tài)圖搜索-最近擇優(yōu)搜索示例323462344632C1B1D1D2E1C2E3D3C3B2E4E26B3A編號節(jié)點父節(jié)點編號代價1A*02C1133D1254E238CLOSED表OPEN表節(jié)點父節(jié)點編號代價E238B238D125C113B114A*04/5/2023883.1.5加權(quán)狀態(tài)圖搜索-有界深度優(yōu)先代價樹的有界深度優(yōu)先法與直接樹的有界深度優(yōu)先相比，用gm來代替最大深度dm代價樹深度優(yōu)先搜索的解為A-〉C-〉D-〉E323462344632C1B1D1D2E1C2E3D3C3B2E4E26B34/5/202389內(nèi)容回顧：樹形圖樹式搜索策略比較全局局部深度d(x)寬度優(yōu)先搜索深度優(yōu)先搜索啟發(fā)值h(x)全局擇優(yōu)搜索局部擇優(yōu)搜索代價值g(x)分支界限法瞎子爬山法范圍標準S0Sg23ab4615cdgfhijk5f543789h(x)，有利于搜索縱向發(fā)展，提高搜索效率，但影響完備性。g(x)，有利于搜索橫向發(fā)展，提高完備性，但影響搜索效率。窮舉式搜索啟發(fā)式搜索加權(quán)狀態(tài)圖搜索4/5/202390問題空間可表示成或圖（狀態(tài)圖）與或圖知識表示搜索窮舉式搜索啟發(fā)式搜索知識表示搜索啟發(fā)式與或樹搜索博弈樹搜索加權(quán)狀態(tài)圖搜索廣度優(yōu)先深度優(yōu)先全局擇優(yōu)局部擇優(yōu)分支界限最近優(yōu)先A算法和A*算法第3章知識結(jié)構(gòu)圖4/5/2023913.1.6A算法和A*算法-估價函數(shù)啟發(fā)函數(shù)的問題：單獨利用啟發(fā)函數(shù)h(x)制導(dǎo)的啟發(fā)式搜索，是一種深度優(yōu)先的搜索策略，高效但有可能誤入歧途。估價函數(shù)：

將啟發(fā)函數(shù)與代價函數(shù)相結(jié)合，一般形式如下：f(x)＝g(x)＋h(x)代價函數(shù)g(x):從初始節(jié)點S0到節(jié)點x已付出的代價啟發(fā)函數(shù)h(x):從節(jié)點x到達目標節(jié)點Sg的接近程度估計值估價函數(shù)f(x)：是初始節(jié)點S0到達節(jié)點x處已付出的代價與節(jié)點x到達目標節(jié)點Sg的接近程度估計值的總和。4/5/2023923.1.6A算法和A*算法-估價函數(shù)估價函數(shù)可以表示成：f(x)＝g(x)＋h(x)或f(x)＝d(x)＋h(x)g(x)或d(x)（代表節(jié)點x的深度）有利于搜索的橫向發(fā)展，可提高搜索的完備性，但影響搜索效率。h(x)有利于搜索的縱向發(fā)展，可提高搜索效率，但影響搜索的完備性。f(x)是g(x)與h(x)的折中。適當(dāng)選擇g(x)和h(x)比重使結(jié)果偏重效率或偏重完備性。4/5/2023933.1.6A算法和A*算法-A算法A算法：基于估價函數(shù)f(x)的一種加權(quán)狀態(tài)圖啟發(fā)式搜索算法。其本質(zhì)是圖搜索一般算法中的樹式搜索算法，再增加了估價函數(shù)f(x)的計算和傳播的一種啟發(fā)式搜索算法。搜索算法中估價函數(shù)f(x)的計算方法如下：g(xi)：表示從初始節(jié)點S0到節(jié)點xi的代價。c(xi,xj)：表示父節(jié)點xi到子節(jié)點xj的代價。h(x)：由具體問題而定f(xj)=g(xj)＋h(xj)（假定xi是xj的父節(jié)點）=g(xi)+c(xi,xj)+h(xj)4/5/2023943.1.6A算法和A*算法-A算法步1把附有f(S0)的初始節(jié)點S0放入OPEN表中；步2若OPEN表為空，則搜索失敗，退出。步3移出OPEN表中第一個節(jié)點N放入CLOSED表中，并冠以順序編號n；步4若目標節(jié)點Sg＝N，則搜索成功，結(jié)束。步5若N不可擴展，則轉(zhuǎn)步2；步6擴展N，生成一組附有f(x)的子節(jié)點，對這組子節(jié)點作如下處理：（1）考察是否有已在OPEN表或CLOSED表中存在的節(jié)點；若有則再考察其中有無N的先輩節(jié)點，若有則刪除之；對于其余節(jié)點，也刪除之，但由于它們被第二次生成，需考慮是否修改已經(jīng)存在于OPEN表或CLOSED表中的這些節(jié)點及其后裔的返回指針和f(x)的值，修改原則是”抄f(x)值小的路走”。（2）對其余子節(jié)點配上指向N的返回指針后放入OPEN表中，并對OPEN表按f(x)以升序排列，轉(zhuǎn)步2。4/5/2023953.1.6A算法和A*算法-估價函數(shù)定義探討f(x)＝g(x)＋h(x)估價函數(shù)的設(shè)計：g(x)：對某一確定的節(jié)點，是確定的值。h(x)：

不同的問題啟發(fā)函數(shù)的定義不同，相同的問題也可以定義出不同的啟發(fā)函數(shù)。衡量h(x)優(yōu)劣的標準是看其是否能夠準確反映出節(jié)點x到達目標的難易程度（距離）。4/5/2023963.1.6A算法和A*算法-八數(shù)碼問題回顧九宮重排問題（八數(shù)碼難題）X1X2X3X8X0X4X7X6X5將棋局用向量A＝(X0，X1，

X2，

X3，

X4，

X5，

X6，

X7，

X8)表示，其中Xi為變量，值表示方格Xi內(nèi)的數(shù)字。初始狀態(tài)S0＝（0，2，8，3，4，5，6，7，1）目標狀態(tài)Sg＝（0，1，2，3，4，5，6，7，8）數(shù)碼的移動規(guī)則就是該問題的狀態(tài)變化規(guī)則。經(jīng)分析，該問題共有24條規(guī)則，分為9組。2831476512384765初始棋局目標棋局4/5/2023973.1.6A算法和A*算法-八數(shù)碼問題回顧0組規(guī)則r1(X0=0

)(X2=n

)X0=nX2=0；r2(X0=0

)(X4=n

)X0=nX4=0；r3(X0=0

)(X6=n

)X0=nX6=0；r4(X0=0

)(X8=n

)X0=nX8=0；1組規(guī)則r5(X1=0

)(X2=n

)X1=nX2=0；r6(X1=0

)(X8=n

)X1=nX8=0；8組規(guī)則:r22(X8=0

)(X1=n

)X8=nX1=0；r23(X8=0

)(X0=n

)X8=nX0=0；r24(X8=0

)(X7=n

)X8=nX7=0；……4/5/2023983.1.6A算法和A*算法-估價函數(shù)定義探討(1)28314765S012384765Sg九宮重排問題：如下圖所示初始節(jié)點S0與目標節(jié)點Sg。估價函數(shù)f(x)＝g(x)＋h(x)g(x)用節(jié)點深度d(x)來衡量h(x)的設(shè)計：考慮因素1：格局中將牌是否在家h(x)用x的格局與目標節(jié)點格局相比，不在家的將牌數(shù)目w(x)來衡量。4/5/2023992

8314765342365283

14765442318476528314765552831647556

832147652837146546231

84765231847654123

847651237

8465612384765412384765Sg1擴展順序f(x)值S04/5/20231003.1.6A算法和A*算法-估價函數(shù)定義探討(2)

8126