人工智能原理之搜索技術(shù)課件

人工智能原理

第2章搜索技術(shù)

（上）

1人工智能原理

第2章搜索技術(shù)

（上）1

本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索策略

2.3啟發(fā)式搜索策略

2.4局部搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

附錄A*算法可采納性的證明第2章搜索技術(shù)2 本章內(nèi)容

2.1搜索與問題求解

2.2無信息2.1搜索與問題求解

2.1.1問題與問題的解

2.1.2問題實(shí)例

2.1.3搜索策略第2章搜索技術(shù)32.1搜索與問題求解

2.1.1問題與問題的解

2.1搜索與問題求解問題求解過程是搜索答案(目標(biāo))的過程/所以問題求解技術(shù)也叫搜索技術(shù)—通過對狀態(tài)空間的搜索而求解問題的技術(shù)問題求解智能體是一種基于目標(biāo)的智能體在尋找到達(dá)目標(biāo)的過程中，當(dāng)智能體面對多個(gè)未知的選項(xiàng)時(shí)，首先檢驗(yàn)各個(gè)不同的導(dǎo)致已知評價(jià)的狀態(tài)的可能行動(dòng)序列，然后選擇最佳序列—這個(gè)過程就是搜索第2章搜索技術(shù)4搜索與問題求解問題求解過程是搜索答案(目標(biāo))的過程/所以2.1.1問題與問題的解問題可以形式化地定義為4個(gè)組成部分智能體的初始狀態(tài)(即搜索的開始)后繼函數(shù)—智能體采取的可能行動(dòng)的描述，通常為<行動(dòng)，后繼狀態(tài)>/初始狀態(tài)和后繼函數(shù)隱含地定義了問題的狀態(tài)空間/狀態(tài)空間中的一條路徑是通過行動(dòng)序列連接起來的一個(gè)狀態(tài)序列目標(biāo)測試—檢查給定的狀態(tài)是不是目標(biāo)路徑耗散函數(shù)—每條路徑都有一個(gè)數(shù)值化的耗散值，反映了性能度量/求解問題的代價(jià)第2章搜索技術(shù)52.1.1問題與問題的解問題可以形式化地定義為4個(gè)組成部分問題的解問題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑解的優(yōu)劣由路徑耗散函數(shù)量度(代價(jià))最優(yōu)解就是路徑耗散函數(shù)值最小的路徑上述解題過程把解決一個(gè)問題的過程描述出來，稱之為解題知識(shí)的過程性表示過程性知識(shí)與陳述性知識(shí)相對搜索過程解題的特點(diǎn)—沒有直接的方法(公式)可以求解，而是一步一步的探索第2章搜索技術(shù)6問題的解問題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑第2章搜索技術(shù)狀態(tài)空間數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標(biāo)狀態(tài)也可能沒有狀態(tài)空間：在解題過程中的每一時(shí)刻，數(shù)據(jù)基都處于一定的狀態(tài)，數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間有向圖：若把每個(gè)狀態(tài)看成一個(gè)節(jié)點(diǎn)，則整個(gè)狀態(tài)空間是一個(gè)有向圖/該圖不一定全連通，即從某些狀態(tài)不一定能到達(dá)另外一些狀態(tài)第2章搜索技術(shù)7狀態(tài)空間數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標(biāo)問題的可解性可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將狀態(tài)改變/如果從代表初始狀態(tài)的節(jié)點(diǎn)出發(fā)，有一條路徑通向目標(biāo)狀態(tài)，則稱此目標(biāo)狀態(tài)所代表的問題在當(dāng)前初始狀態(tài)下是可解的搜索空間：在解題過程中達(dá)到過的所有狀態(tài)的集合，稱為搜索空間不同于狀態(tài)空間，搜索空間只是其中一部分狀態(tài)空間和搜索空間都屬于過程性知識(shí)表示第2章搜索技術(shù)8問題的可解性可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將2.1.2問題實(shí)例玩具問題八數(shù)碼游戲(九宮圖)河內(nèi)塔八皇后問題真空吸塵器世界現(xiàn)實(shí)問題旅行商問題超大規(guī)模集成電路的布局自動(dòng)裝配排序/蛋白質(zhì)設(shè)計(jì)互聯(lián)網(wǎng)搜索第2章搜索技術(shù)92.1.2問題實(shí)例玩具問題第2章搜索技術(shù)9八數(shù)碼游戲八數(shù)碼游戲：1-8數(shù)字(棋子)/9個(gè)方格(棋盤格)/1個(gè)空格可用如下形式的規(guī)則來表示數(shù)字通過空格進(jìn)行移動(dòng)：<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>共24條規(guī)則=4角*2+4邊*3+1中間*4搜索順序舉例： (1)優(yōu)先移動(dòng)行數(shù)小的棋子(數(shù)字) (2)同一行中優(yōu)先移動(dòng)列數(shù)大的棋子約束規(guī)則：不使離開既定位置的數(shù)字?jǐn)?shù)增加第2章搜索技術(shù)10八數(shù)碼游戲八數(shù)碼游戲：1-8數(shù)字(棋子)/9個(gè)方格(棋盤格)八數(shù)碼游戲的搜索樹第2章搜索技術(shù)既定位置=終態(tài)11八數(shù)碼游戲的搜索樹第2章搜索技術(shù)既定位置=終態(tài)11八數(shù)碼問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應(yīng)的位置，各位置上的初始數(shù)字后繼函數(shù)移動(dòng)規(guī)則—按照某條規(guī)則移動(dòng)數(shù)字，將得到的新向量目標(biāo)測試新向量是否是目標(biāo)狀態(tài)(也是向量形式)路徑耗散函數(shù)每次移動(dòng)代價(jià)為1第2章搜索技術(shù)12八數(shù)碼問題形式化初始狀態(tài)第2章搜索技術(shù)12河內(nèi)塔(1)河內(nèi)塔問題：n個(gè)大小不等的圓盤從一個(gè)柱子移到另一個(gè)柱子，共有3個(gè)柱子(n階河內(nèi)塔問題)約束：從第1根柱子移動(dòng)到第3根柱子上去，利用第2根柱子/每次移動(dòng)1個(gè)盤子，且移動(dòng)過程必須是小盤落大盤描述：設(shè)每個(gè)狀態(tài)為(a1,a2,a3,…,an),

ai=1,2,3—表示第i個(gè)盤子在第1/2/3根柱子上第2章搜索技術(shù)13河內(nèi)塔(1)河內(nèi)塔問題：n個(gè)大小不等的圓盤從一個(gè)柱子移到另一河內(nèi)塔(2)遞歸定義：{(a1,a2,a3,…,an)}為n階河內(nèi)塔的狀態(tài)集合，則{(a1,a2,a3,…,an,1),(a1,a2,a3,…,an,2),(a1,a2,a3,…,an,3)}是n+1階河內(nèi)塔的狀態(tài)集合1階河內(nèi)塔有3個(gè)狀態(tài)，2階河內(nèi)塔有9個(gè)狀態(tài)，n階河內(nèi)塔有3n個(gè)狀態(tài)，給出1/2/3階河內(nèi)塔的狀態(tài)圖第2章搜索技術(shù)14河內(nèi)塔(2)遞歸定義：{(a1,a2,a3,…,an河內(nèi)塔問題圖解第2章搜索技術(shù)15河內(nèi)塔問題圖解第2章搜索技術(shù)15河內(nèi)塔問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應(yīng)所有n個(gè)盤子，位置上數(shù)字代表3個(gè)柱子之一后繼函數(shù)移動(dòng)規(guī)則—依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài)目標(biāo)測試新向量是否是目標(biāo)狀態(tài)(也是向量形式)路徑耗散函數(shù)每移動(dòng)一個(gè)盤子的代價(jià)為1第2章搜索技術(shù)16河內(nèi)塔問題形式化初始狀態(tài)第2章搜索技術(shù)16河內(nèi)塔問題求解求最短路徑問題：狀態(tài)圖中從三角形1個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn)結(jié)論：(1)如果初始狀態(tài)或目標(biāo)狀態(tài)在三角形頂點(diǎn)上，則最短路徑唯一；(2)對于任意2個(gè)狀態(tài)，最短求解路徑至多為2條。(中國某大學(xué)研究生證明)求解過程—對狀態(tài)空間的搜索—以2階河內(nèi)塔為例第2章搜索技術(shù)17河內(nèi)塔問題求解求最短路徑問題：狀態(tài)圖中從三角形1個(gè)頂點(diǎn)走到另河內(nèi)塔問題的搜索樹第2章搜索技術(shù)1,12,13,11,12,31,13,23,32,1×2,2××√3,12,2×1,32,13,3××2,33,31,21,1××√2,21,23,13,3××√2,23,21,31,1××√18河內(nèi)塔問題的搜索樹第2章搜索技術(shù)1,12,13,11,12求解過程—樹搜索求解問題的過程使用搜索樹形式每個(gè)狀態(tài)對應(yīng)搜索樹中一個(gè)節(jié)點(diǎn)根節(jié)點(diǎn)對應(yīng)于初始狀態(tài)每次從搜索樹的上層節(jié)點(diǎn)出發(fā)，根據(jù)約束條件進(jìn)入下一個(gè)可能的狀態(tài)，即展開新的一層樹節(jié)點(diǎn)—節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)展開的順序即代表了不同的搜索策略當(dāng)展開的節(jié)點(diǎn)為目標(biāo)狀態(tài)時(shí)，就找到了問題的一個(gè)解第2章搜索技術(shù)19求解過程—樹搜索求解問題的過程使用搜索樹形式第2章搜索技術(shù)2.1.3搜索策略研究搜索過程考慮的若干問題 (1)有限搜索還是無限搜索 (2)已知目標(biāo)還是未知目標(biāo) (3)目標(biāo)或目標(biāo)+路徑 (4)有約束還是無約束 (5)數(shù)據(jù)驅(qū)動(dòng)(向前搜索)還是目標(biāo)驅(qū)動(dòng) (6)單向搜索還是雙向搜索第2章搜索技術(shù)202.1.3搜索策略研究搜索過程考慮的若干問題第2章搜索技搜索的分類搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空間搜索(層次方法)，博弈空間搜索無信息搜索與啟發(fā)式搜索啟發(fā)式：利用中間信息改進(jìn)控制策略啟發(fā)式：(1)任何有助于找到問題的解，但不能保證找到解的方法是啟發(fā)式方法(2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法啟發(fā)式也叫啟發(fā)函數(shù)第2章搜索技術(shù)21搜索的分類搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空搜索算法的性能4種途徑來評價(jià)搜索算法的性能完備性—當(dāng)問題有解時(shí)，算法是否保證找到一個(gè)解最優(yōu)性—算法是否能找到一個(gè)最優(yōu)解(路徑耗散函數(shù)值最小的路徑)時(shí)間復(fù)雜性—找到一個(gè)解需要花費(fèi)多少時(shí)間空間復(fù)雜性—在搜索過程中需要占用多少內(nèi)存第2章搜索技術(shù)22搜索算法的性能4種途徑來評價(jià)搜索算法的性能第2章搜索技術(shù)2性能量度時(shí)空復(fù)雜性的量度—由狀態(tài)空間圖的大小來衡量/相關(guān)度量如下：分支因子b (每次展開的平均節(jié)點(diǎn)個(gè)數(shù))目標(biāo)節(jié)點(diǎn)的深度d路徑的最大長度m 搜索深度限制l搜索耗散第2章搜索技術(shù)23性能量度時(shí)空復(fù)雜性的量度—由狀態(tài)空間圖的大小來衡量/相關(guān)2.2無信息搜索策略

2.2.1廣度優(yōu)先搜索

2.2.2深度優(yōu)先搜索和深度有限搜索

2.2.3疊代深入深度優(yōu)先搜索

2.2.4無信息搜索策略性能比較

2.2.5圖搜索算法第2章搜索技術(shù)242.2無信息搜索策略

2.2.1廣度優(yōu)先搜索

2.2.盲目搜索策略無信息搜索也稱盲目搜索：沒有任何附加信息，只有生成后繼和區(qū)分目標(biāo)與非目標(biāo)狀態(tài)有5種盲目搜索策略廣度優(yōu)先搜索代價(jià)一致搜索深度優(yōu)先搜索深度有限搜索迭代深入深度優(yōu)先搜索第2章搜索技術(shù)25盲目搜索策略無信息搜索也稱盲目搜索：沒有任何附加信息，只有生2.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索過程：首先擴(kuò)展根節(jié)點(diǎn)接著擴(kuò)展根節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)然后再擴(kuò)展后繼節(jié)點(diǎn)的后繼，依此類推在下一層任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上的本層深度的所有節(jié)點(diǎn)都已經(jīng)被擴(kuò)展廣度優(yōu)先搜索可以調(diào)用樹搜索算法(Tree-Search)實(shí)現(xiàn)其參數(shù)fringe(邊緣/擴(kuò)展分支)為先進(jìn)先出隊(duì)列FIFO第2章搜索技術(shù)262.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索過程：第2章搜索技術(shù)2樹搜索算法(1)functionTree-Search(problem,fringe)returnsolution/failure (initialfringe=empty,mode=FIFO) fringe←Insert(Make-Node(Initial-State[problem]),fringe)

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=GoalthenreturnSolution(node) fringe←Insert-All(Expend(node,problem), fringe)第2章搜索技術(shù)27樹搜索算法(1)functionTree-Search(p樹搜索算法(2)關(guān)鍵在于如何擴(kuò)展節(jié)點(diǎn)function

Expend(node,problem)returnsetofnodes successors←theemptyset

foreach<action,result>inSuccessor-Find[problem](State[node])do s←newNode/State[s]←result Parent-Node[s]=node/Action[s]=action Path-Cost[s]=Path-Cost[node]+Step-Cost[node, action,s] Depth[s]←Depth[node]+1 addstosuccessors

returnsuccessors第2章搜索技術(shù)28樹搜索算法(2)關(guān)鍵在于如何擴(kuò)展節(jié)點(diǎn)第2章搜索技術(shù)28廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Search(problem,FIFO-Queue)調(diào)用樹搜索算法從4種度量來評價(jià)廣度優(yōu)先搜索：完備性—總能找到一個(gè)解如果每步擴(kuò)展的耗散相同時(shí)，廣度優(yōu)先搜索能找到最優(yōu)解內(nèi)存消耗是比執(zhí)行時(shí)間消耗更大的問題指數(shù)級的時(shí)間消耗(空間和時(shí)間消耗的例子參見p60圖3.11)第2章搜索技術(shù)29廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Se2.2.2深度優(yōu)先搜索和深度有限搜索深度優(yōu)先搜索過程：總是擴(kuò)展搜索樹的當(dāng)前擴(kuò)展分支(邊緣)中最深的節(jié)點(diǎn)搜索直接伸展到搜索樹的最深層，直到那里的節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)那些沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)擴(kuò)展完畢就從邊緣中去掉然后搜索算法回退下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的上層節(jié)點(diǎn)繼續(xù)擴(kuò)展搜索算法參見深度有限搜索算法(l=∞)第2章搜索技術(shù)302.2.2深度優(yōu)先搜索和深度有限搜索深度優(yōu)先搜索過程：第2深度優(yōu)先搜索的性能深度優(yōu)先搜索通過后進(jìn)先出隊(duì)列LIFO(棧)調(diào)用Tree-Search實(shí)現(xiàn)/通常使用遞歸函數(shù)實(shí)現(xiàn)，依次對當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)調(diào)用該函數(shù)性能：內(nèi)存需求少—如分支因子=b/最大深度=m的狀態(tài)空間深度優(yōu)先搜索只需要存儲(chǔ)bm+1個(gè)節(jié)點(diǎn)(比較廣度優(yōu)先O(bd+1))不是完備的/不是最優(yōu)的最壞情況下時(shí)間復(fù)雜性也很高O(bm)第2章搜索技術(shù)31深度優(yōu)先搜索的性能深度優(yōu)先搜索通過后進(jìn)先出隊(duì)列LIFO(棧)深度有限搜索深度優(yōu)先搜索的無邊界問題可以通過提供一個(gè)預(yù)先設(shè)定的深度限制l來解決深度=l的節(jié)點(diǎn)當(dāng)作無后繼節(jié)點(diǎn)看待雖然解決了無限路徑問題，但如果l<d則找不到解如果選擇d>l則深度優(yōu)先搜索也不是最優(yōu)的時(shí)間復(fù)雜度O(bl)空間復(fù)雜度O(bl)深度優(yōu)先搜索可看作是一種特例即l=∞第2章搜索技術(shù)32深度有限搜索深度優(yōu)先搜索的無邊界問題可以通過提供一個(gè)預(yù)先設(shè)定非遞歸的深度有限搜索算法functionDepth-Limited-Search(problem,fringe,limit)returnsolution/failure/cutoff

fringe←Insert(Make-Node(Initial-State[problem]),fringe) (mode=LIFO)

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=Goalthenreturn Solution(node)

elseifDepth[node]=limitthenreturncutoff elsefringe←Insert-All(Expend (node,problem),fringe)

第2章搜索技術(shù)33非遞歸的深度有限搜索算法functionDepth-Lim搜索步數(shù)的限制上面算法中可能有兩類失敗cutoff表示到達(dá)了有限深度而無解failure表示一般的返回值無解有時(shí)深度有限搜索基于問題本身的知識(shí)，如狀態(tài)空間的直徑即問題求解的最大步數(shù)但對于大多數(shù)問題，不到問題解決時(shí)是無法知道求解步數(shù)的限制第2章搜索技術(shù)34搜索步數(shù)的限制上面算法中可能有兩類失敗第2章搜索技術(shù)342.2.3疊代深入深度優(yōu)先搜索如果每次改變限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深入深度優(yōu)先搜索算法其深度限制依次為0/1/2…這樣，當(dāng)搜索到達(dá)最淺的目標(biāo)節(jié)點(diǎn)深度時(shí)就可以發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)這種搜索結(jié)合了廣度優(yōu)先和深度優(yōu)先兩種算法的優(yōu)點(diǎn)(算法見p63)分支因子有限時(shí)是完備的/路徑耗散是節(jié)點(diǎn)深度的非遞增函數(shù)時(shí)是最優(yōu)的空間需求為O(bd)/時(shí)間復(fù)雜性為O(bd)第2章搜索技術(shù)352.2.3疊代深入深度優(yōu)先搜索如果每次改變限制深度，多次調(diào)狀態(tài)的生成疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次生成，看起來很浪費(fèi)但是因?yàn)樵诜种б蜃颖容^平衡的搜索樹中，多數(shù)節(jié)點(diǎn)都在最底層(即葉子節(jié)點(diǎn))，所以上層節(jié)點(diǎn)的多次生成影響不是很大/與廣度優(yōu)先搜索相比，效率還是更高一般來講，當(dāng)搜索空間很大而解的深度未知時(shí)，疊代深入搜索是一個(gè)首選的無信息搜索方法第2章搜索技術(shù)36狀態(tài)的生成疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次2.2.4無信息搜索策略比較第2章搜索技術(shù)評價(jià)標(biāo)準(zhǔn)廣度優(yōu)先代價(jià)一致深度優(yōu)先深度有限疊代深入雙向搜索是否完備時(shí)間空間是否最優(yōu)是A是A/B否否是A是A/D

O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)是C是否否是C是C/D

關(guān)于A/B/C/D的解釋：A—如果b有限則是完備的/B—單步耗散≥e則是完備的/C—如果單步耗散都是相同的則是最優(yōu)的/D—兩個(gè)方向上都使用廣度優(yōu)先搜索372.2.4無信息搜索策略比較第2章搜索技術(shù)評價(jià)標(biāo)準(zhǔn)廣度優(yōu)2.2.5圖搜索算法已經(jīng)看到搜索過程中會(huì)出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展，應(yīng)該避免/如果算法不檢測重復(fù)狀態(tài)的話，有可能使一個(gè)本來可解的問題變?yōu)椴豢山鈾z測就是把要擴(kuò)展的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)進(jìn)行比較，把遇到的相同狀態(tài)去掉所以要記錄已經(jīng)擴(kuò)展的節(jié)點(diǎn)—引入兩個(gè)表—存儲(chǔ)已擴(kuò)展的節(jié)點(diǎn)closed表和未擴(kuò)展的節(jié)點(diǎn)open表(即前述fringe)新算法稱為圖搜索算法第2章搜索技術(shù)382.2.5圖搜索算法已經(jīng)看到搜索過程中會(huì)出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展圖搜索算法第2章搜索技術(shù)functionGraph-Search(problem,fringe)returnsolutionorfailure

closed←emptyset fringe←Insert(Make-Node(Initial-State[problem]),fringe)

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=GoalthenreturnSolution(node)

ifState[node]!CLOSEDthen addState[node]toclosed fringe←Insert-All(Expend(node,problem),fringe)39圖搜索算法第2章搜索技術(shù)functionGraph-Se圖搜索算法的性能由樹到圖：存在不同分支節(jié)點(diǎn)的合并圖搜索算法與樹搜索算法比較：只是增加了對展開節(jié)點(diǎn)的判斷，因此由不同的待擴(kuò)展節(jié)點(diǎn)排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍然同樹搜索算法對于含很多重復(fù)狀態(tài)的問題，其搜索效率比樹搜索算法有效很多討論參見p67第2章搜索技術(shù)40圖搜索算法的性能由樹到圖：存在不同分支節(jié)點(diǎn)的合并第2章搜索例子：“農(nóng)夫過河”問題搜索農(nóng)夫過河問題用向量<人,狼,羊,白菜>表示在河岸兩邊的情況0表示此岸/1表示彼岸過河規(guī)則有8條(隱含了約束條件)1(0,*,*,*)→(1,*,*,*)/2(0,0,*,*)→(1,1,*,*) 3(0,*,0,*)→(1,*,1,*)/4(0,*,*,0)→(1,*,*,1) 5(1,*,*,*)→(0,*,*,*)/6(1,1,*,*)→(0,0,*,*)7(1,*,1,*)→(0,*,0,*)/8(1,*,*,1)→(0,*,*,0)

*=0/1表示任意岸邊但必須相同第2章搜索技術(shù)41例子：“農(nóng)夫過河”問題搜索農(nóng)夫過河問題第2章搜索技術(shù)41“農(nóng)夫過河”—廣度優(yōu)先搜索第2章搜索技術(shù)000010101100×00101110010011010101111110110001closed表<0000><1010><0010><1110><1011><0100><0001><1101>所用規(guī)則序列3/5/4/7/2所用規(guī)則序列3/5/2/7/4所用規(guī)則序列3/5/4/7/2/5/3所用規(guī)則序列3/5/2/7/4/5/342“農(nóng)夫過河”—廣度優(yōu)先搜索第2章搜索技術(shù)00001“農(nóng)夫過河”—深度優(yōu)先搜索第2章搜索技術(shù)000010101100×001011100100110101011111closed表<0000><1010><0010><1110><0100><1101>所用規(guī)則序列3/5/2/7/4所用規(guī)則序列3/5/2/7/4/5/3只使用一個(gè)搜索分支/所擴(kuò)展的第一個(gè)節(jié)點(diǎn)是最新節(jié)點(diǎn)43“農(nóng)夫過河”—深度優(yōu)先搜索第2章搜索技術(shù)000012.3啟發(fā)式搜索策略

2.3.1貪婪最佳優(yōu)先搜索

2.3.2A*搜索

2.3.3啟發(fā)函數(shù)

2.3.4聯(lián)機(jī)搜索第2章搜索技術(shù)442.3啟發(fā)式搜索策略

2.3.1貪婪最佳優(yōu)先搜索

2.啟發(fā)式搜索通用算法啟發(fā)式搜索也稱有信息搜索，其通用算法稱為最佳優(yōu)先搜索(Best-First-Search)最佳優(yōu)先搜索基于評價(jià)函數(shù)擴(kuò)展節(jié)點(diǎn)—按照距離目標(biāo)最短的評價(jià)值來擴(kuò)展并不是真正的最佳—只是表現(xiàn)得最佳/近似最佳算法的關(guān)鍵因素是啟發(fā)函數(shù)(Heuristicfunction)，記為f(n)/f(n)=從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的耗散估計(jì)值啟發(fā)函數(shù)引導(dǎo)搜索兩種方式—貪婪最佳優(yōu)先搜索/A*搜索(A*算法)第2章搜索技術(shù)45啟發(fā)式搜索通用算法啟發(fā)式搜索也稱有信息搜索，其通用算法稱為最2.3.1貪婪最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索的評價(jià)函數(shù)f(n)=h(n)在貪婪最佳優(yōu)先搜索中總是選擇當(dāng)前離目標(biāo)最近(最小代價(jià))的節(jié)點(diǎn)進(jìn)行擴(kuò)展(搜索)局部最佳未必全局最佳—不是最優(yōu)的(下例)使用貪婪最佳優(yōu)先搜索算法搜索從Arad到首都的行車最短路線Arad的下一站有3個(gè)城市S(253)/T(329)/Z(374)→擴(kuò)展Sibiu有3個(gè)城市F(176)/O(380)/R(193)→擴(kuò)展Fagaras直接可到目的地然而實(shí)際不是最優(yōu)的：S→F→B實(shí)際全長310/S→RV→P→B實(shí)際全長278，多了32km第2章搜索技術(shù)462.3.1貪婪最佳優(yōu)先搜索貪婪最佳優(yōu)先搜索的評價(jià)函數(shù)f(n問題實(shí)例—Romania公路圖第2章搜索技術(shù)47問題實(shí)例—Romania公路圖第2章搜索技術(shù)47問題實(shí)例(1)第2章搜索技術(shù)尋找從Arad到首都的行車最短路線評價(jià)函數(shù)f(n)=h(n)直線距離啟發(fā)式hSLD與實(shí)際距離相關(guān)但需另外給出，見下表Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161RimnicuVilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind37448問題實(shí)例(1)第2章搜索技術(shù)尋找從Arad到首都的行車最短問題實(shí)例(2)第2章搜索技術(shù)啟發(fā)函數(shù)h(n)最小化會(huì)對錯(cuò)誤的起點(diǎn)比較敏感例子：地圖中Iasi到Fagaras的行車路線(走入死路的可能)需要仔細(xì)檢查重復(fù)狀態(tài)，否則可能永遠(yuǎn)找不到解與深度優(yōu)先搜索類似，非最優(yōu)、非完備最壞情況下時(shí)空復(fù)雜度都是O(bm)/m為最大搜索深度49問題實(shí)例(2)第2章搜索技術(shù)啟發(fā)函數(shù)h(n)最小化會(huì)對錯(cuò)誤2.3.2A*搜索A*搜索的評價(jià)函數(shù)為f(n)=g(h)+h(n)g(n)是從初始節(jié)點(diǎn)到該節(jié)點(diǎn)n的路徑耗散h(n)是從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的估計(jì)耗散值，稱為啟發(fā)式或啟發(fā)函數(shù)因此，f(n)=經(jīng)過節(jié)點(diǎn)n、具有最低耗散值的解的估計(jì)耗散找到g(n)+h(n)值最小的節(jié)點(diǎn)當(dāng)然是合理的(參見書中p79圖4.3對于地圖的搜索)若啟發(fā)函數(shù)h(n)滿足一定條件，則A*搜索是完備的和最優(yōu)的第2章搜索技術(shù)502.3.2A*搜索A*搜索的評價(jià)函數(shù)為f(n)=g(h)+搜索算法的可采納性[定義]搜索算法的可采納性(可采用性)

(Hart,Nilsson,Raphel,1968)如果狀態(tài)空間中的目標(biāo)狀態(tài)存在，并且從初始狀態(tài)到目標(biāo)狀態(tài)有一條通路，而搜索算法一定能在有限步內(nèi)終止并找到一個(gè)最優(yōu)解(代價(jià)最低)，則這個(gè)狀態(tài)空間搜索算法稱為可采納的對于A*搜索來說，使用樹搜索算法(Tree-Search)，則它是可采納的如果對啟發(fā)函數(shù)h(n)作一定限制，則使用圖搜索算法(Graph-Search)也是可采納的第2章搜索技術(shù)51搜索算法的可采納性[定義]搜索算法的可采納性(可采用性)(可采納的啟發(fā)函數(shù)算法的可采納性取決于啟發(fā)函數(shù)的可采納性啟發(fā)函數(shù)h(n)是可采納的—h(n)從來不會(huì)過高地估計(jì)到達(dá)目標(biāo)的耗散值此即—h(n)滿足h(n)≤h*(n)，h*(n)是從當(dāng)前節(jié)點(diǎn)n到達(dá)目標(biāo)的最低耗散值此即—f(n)永遠(yuǎn)不會(huì)高估經(jīng)過節(jié)點(diǎn)n的解的實(shí)際耗散—f(n)≤f*(n)，所以是最優(yōu)解如果h(n)是可采納的，那么使用Tree-Search的A*算法是可采納的(最優(yōu)的)自己嘗試證明，參考附錄證明過程第2章搜索技術(shù)52可采納的啟發(fā)函數(shù)算法的可采納性取決于啟發(fā)函數(shù)的可采納性第2章A*搜索的Tree-Search算法functionTree-Search(problem,fringe)returnsolutionorfailure Selecth(n) Make-Node(Initial-State[problem]&gettheirf(n) Insert(nodes,fringe) Sort(fringe,f(n))

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=GoalthenreturnSolution(node) Expend(node,problem)&gettheirf(n)

Insert(nodes,fringe) Sort(fringe,f(n))第2章搜索技術(shù)53A*搜索的Tree-Search算法functionTreA*搜索的Graph-Search算法如果A*搜索使用圖搜索算法，則A*必然返回最優(yōu)解的結(jié)論就不成立—原因是如果最優(yōu)路徑不是第一個(gè)生成的，可能因?yàn)橛兄貜?fù)狀態(tài)而被丟棄解決方案：1)修改Graph-Search算法使得能夠進(jìn)行比較，只丟棄耗散值大的路徑2)保證到達(dá)任何重復(fù)狀態(tài)的最優(yōu)路徑總是第一條被追隨的路徑—要求h(n)保持一致性(單調(diào)性)算法—請自行給出第2章搜索技術(shù)54A*搜索的Graph-Search算法如果A*搜索使用圖搜索h(n)的一致性(1)[定義]啟發(fā)函數(shù)的一致性—如果對于每個(gè)節(jié)點(diǎn)n和通過任意行動(dòng)a生成n的每個(gè)后繼節(jié)點(diǎn)n’，從節(jié)點(diǎn)n到達(dá)目標(biāo)節(jié)點(diǎn)的估計(jì)耗散值h(n)不大于從n到n’的單步耗散與從n’到目標(biāo)節(jié)點(diǎn)的估計(jì)耗散值之和，則h(n)稱為一致的此即h(n)≤c(n,n’,a)+h(n’)/是三角不等式的某種形式每個(gè)一致的啟發(fā)函數(shù)都是可采納的證明要點(diǎn)：h(n)≤c(n,n’,a)+h(n’),h(n)≤c*(n,n’,a)+h(n’)可得h(n)–h*(n)≤h(n’)–h*(n’)目標(biāo)節(jié)點(diǎn)h(T)=h*(T)=0回退可得任意節(jié)點(diǎn)h(n)≤h*(n)第2章搜索技術(shù)55h(n)的一致性(1)[定義]啟發(fā)函數(shù)的一致性—如果對于每個(gè)h(n)的一致性(2)通常我們選擇的啟發(fā)函數(shù)h(n)都滿足一致性要求(因而必定是可采納的)關(guān)于一致性的結(jié)論：如果h(n)是一致的，那么使用Graph-Search的A*算法是最優(yōu)的附錄證明似乎沒有利用此條件如果h(n)是一致的，那么沿著任何路徑的f(n)值是非遞減的(由一致性定義可得)f(n)耗散值沿著任何路徑都是非遞減的結(jié)論允許在狀態(tài)空間中畫出等值線(見下圖)第2章搜索技術(shù)56h(n)的一致性(2)通常我們選擇的啟發(fā)函數(shù)h(n)都滿足一道路里程的等值線第2章搜索技術(shù)ZTLMDCGUONIVHE420A380BFPRS40057道路里程的等值線第2章搜索技術(shù)ZTLMDCGUONIVHEA*搜索節(jié)點(diǎn)的擴(kuò)展A*搜索由初始節(jié)點(diǎn)出發(fā)開始搜索，以同心帶狀增長f(n)耗散值的方式擴(kuò)展節(jié)點(diǎn)如果h(n)=0則為代價(jià)一致搜索(只按g(n)值排序)則同心帶為“圓型”，使用啟發(fā)函數(shù)則同心帶向目標(biāo)節(jié)點(diǎn)方向拉伸如果C*是最優(yōu)解路徑的耗散值，則有以下結(jié)論：A*算法擴(kuò)展所有f(n)≤C*的節(jié)點(diǎn)A*算法在到達(dá)目標(biāo)節(jié)點(diǎn)之前可能會(huì)擴(kuò)展一些正好處于“目標(biāo)等值線”上的節(jié)點(diǎn)A*算法不擴(kuò)展f(n)>C*的節(jié)點(diǎn)(均被剪枝)第2章搜索技術(shù)58A*搜索節(jié)點(diǎn)的擴(kuò)展A*搜索由初始節(jié)點(diǎn)出發(fā)開始搜索，以同心帶狀A(yù)*算法的性質(zhì)(1)A*算法是完備的—如果解存在，就一定能找到/因?yàn)檎业浇庵灰邢薏紸*算法是最優(yōu)的—即可采納的(一個(gè)普遍采用的證明見附錄)A*算法對于任何給定的啟發(fā)函數(shù)都是效率最優(yōu)的/沒有任何其他算法擴(kuò)展的節(jié)點(diǎn)少于A*算法但是，A*算法對于多數(shù)問題來說，搜索空間處于目標(biāo)等值線內(nèi)的節(jié)點(diǎn)數(shù)量是求解路徑長度的指數(shù)級第2章搜索技術(shù)59A*算法的性質(zhì)(1)A*算法是完備的—如果解存在，就一定能找A*算法的性質(zhì)(2)如果要求不以指數(shù)級增長，則啟發(fā)函數(shù)需要滿足條件對于幾乎所有的啟發(fā)函數(shù)來說，偏差至少都是與路徑耗散成正比的，而不是路徑耗散的對數(shù)/所以，在實(shí)際應(yīng)用中，往往不是堅(jiān)持找到最優(yōu)解，而是采用以下兩種方式：使用A*算法的變種算法快速找到非最優(yōu)解設(shè)計(jì)準(zhǔn)確而非嚴(yán)格可采納的啟發(fā)函數(shù)第2章搜索技術(shù)60A*算法的性質(zhì)(2)如果要求不以指數(shù)級增長，則啟發(fā)函數(shù)需要滿A*算法在空間方面的改進(jìn)A*算法在內(nèi)存中保留所有生成的節(jié)點(diǎn)，消耗極大—因而對于許多大規(guī)模問題時(shí)不實(shí)用的A*算法要減少對內(nèi)存的需求—改進(jìn)遞歸最佳優(yōu)先搜索RBFS—模仿標(biāo)準(zhǔn)的最佳優(yōu)先搜索的遞歸算法，只是用線性存儲(chǔ)空間如果h(n)是可采納的，則RBFS最優(yōu)MA*(存儲(chǔ)限制A*)和SMA*(簡化的MA*)—充分利用可用的內(nèi)存SMA*的思想—當(dāng)內(nèi)存放滿時(shí)，就丟棄最差的一個(gè)子節(jié)點(diǎn)而加入新節(jié)點(diǎn)如果任何最優(yōu)解是可到達(dá)的，則SMA*是最優(yōu)的第2章搜索技術(shù)61A*算法在空間方面的改進(jìn)A*算法在內(nèi)存中保留所有生成的節(jié)點(diǎn)，2.3.3啟發(fā)函數(shù)A*搜索的關(guān)鍵就是設(shè)計(jì)可采納的或者一致的(單調(diào)的)啟發(fā)函數(shù)如何評價(jià)啟發(fā)函數(shù)/如何設(shè)計(jì)啟發(fā)函數(shù)例子—八數(shù)碼問題關(guān)于八數(shù)碼問題的一些數(shù)據(jù)：隨機(jī)產(chǎn)生的八數(shù)碼游戲的平均解的步數(shù)=22分支因子約為3窮舉搜索(盲目搜索)考慮的狀態(tài)個(gè)數(shù)322≈3.1*1010實(shí)際可到達(dá)的不同狀態(tài)個(gè)數(shù)9!/2=181440第2章搜索技術(shù)622.3.3啟發(fā)函數(shù)A*搜索的關(guān)鍵就是設(shè)計(jì)可采納的或者一致的八數(shù)碼問題的啟發(fā)函數(shù)啟發(fā)函數(shù)的核心—決不高估到達(dá)目標(biāo)的步數(shù)/對于八數(shù)碼問題的常用候選：h1(n)=不在位棋子數(shù)—這是一個(gè)可采納的啟發(fā)函數(shù)，因?yàn)橐选安辉谖弧钡钠遄佣家苿?dòng)到正確位置上，每個(gè)錯(cuò)位的棋子至少要移動(dòng)一次/所以有h1(n)≤h*(n)h2(n)=所有棋子到達(dá)其目標(biāo)位置的距離和—計(jì)算水平距離(曼哈頓距離)/該函數(shù)也是可采納的，因?yàn)榈竭_(dá)其目標(biāo)位置至少要移動(dòng)這些距離長度第2章搜索技術(shù)63八數(shù)碼問題的啟發(fā)函數(shù)啟發(fā)函數(shù)的核心—決不高估到達(dá)目標(biāo)的步數(shù)啟發(fā)函數(shù)精確度對算法性能的影響刻畫啟發(fā)函數(shù)質(zhì)量的一個(gè)度量是有效分支因子b*b*是深度為d的一致搜索樹為了能夠包括N(生成的總節(jié)點(diǎn)數(shù))+1個(gè)節(jié)點(diǎn)所必需的分支因子N+1=1+b*+(b*)2+……+(b*)d例如：52個(gè)節(jié)點(diǎn)在第5層找到解，則b*=1.92有效分支因子可以根據(jù)問題實(shí)例發(fā)生變化，但是在足夠難的問題中是穩(wěn)定的/因此小規(guī)模實(shí)驗(yàn)中測得b*值可以為啟發(fā)函數(shù)的總體有效性提供指導(dǎo)第2章搜索技術(shù)64啟發(fā)函數(shù)精確度對算法性能的影響刻畫啟發(fā)函數(shù)質(zhì)量的一個(gè)度量是有八數(shù)碼問題啟發(fā)函數(shù)的比較良好設(shè)計(jì)的啟發(fā)函數(shù)使b*值接近1，允許對大規(guī)模的問題進(jìn)行求解啟發(fā)函數(shù)越接近于真實(shí)最優(yōu)解的值，則相應(yīng)的搜索算法效率越高/顯然此時(shí)有—如果h1(n)≤h2(n)，則h2(n)優(yōu)于h1(n)(此時(shí)h2(n)信息量比h1(n)多)p85頁給出了八數(shù)碼問題的啟發(fā)函數(shù)h1/h2的比較數(shù)據(jù)“優(yōu)于”的含義—使用h2的算法不會(huì)比使用h1的算法擴(kuò)展更多的節(jié)點(diǎn)第2章搜索技術(shù)65八數(shù)碼問題啟發(fā)函數(shù)的比較良好設(shè)計(jì)的啟發(fā)函數(shù)使b*值接近1，允如何設(shè)計(jì)啟發(fā)函數(shù)A*搜索的關(guān)鍵如何找到是一個(gè)合適的啟發(fā)函數(shù)尋找策略：從松弛問題中獲得—松弛問題的最優(yōu)解的耗散是原問題的一個(gè)可采納的啟發(fā)函數(shù)從給定問題子問題的解耗散中獲得—建立模式數(shù)據(jù)庫，存儲(chǔ)每個(gè)可能子問題實(shí)例從經(jīng)驗(yàn)中學(xué)習(xí)—使用歸納學(xué)習(xí)算法，使用相關(guān)狀態(tài)特征來預(yù)測第2章搜索技術(shù)66如何設(shè)計(jì)啟發(fā)函數(shù)A*搜索的關(guān)鍵如何找到是一個(gè)合適的啟發(fā)函數(shù)第松弛問題最優(yōu)解作為啟發(fā)函數(shù)松弛問題—降低了行動(dòng)限制的問題松弛問題的最優(yōu)解耗散是原問題的一個(gè)可采納的啟發(fā)函數(shù)根據(jù)定義，原始問題的最優(yōu)解也是該松弛問題的解，其耗散不低于松弛問題的最優(yōu)解松弛問題的最優(yōu)解是確切耗散，一定滿足三角不等式，因而是單調(diào)的，所以作為啟發(fā)函數(shù)一定是可采納的如果問題定義通過形式化語言描述，則自動(dòng)地構(gòu)造其松弛問題是可能的/例子—八數(shù)碼問題第2章搜索技術(shù)67松弛問題最優(yōu)解作為啟發(fā)函數(shù)松弛問題—降低了行動(dòng)限制的問題第2子問題的解耗散作為啟發(fā)函數(shù)子問題的最優(yōu)解耗散是完整問題的耗散下界建立模式數(shù)據(jù)庫—存儲(chǔ)每個(gè)可能子問題實(shí)例的精確解耗散從目標(biāo)狀態(tài)向后搜索并記錄下每個(gè)子問題模式的耗散，存儲(chǔ)于數(shù)據(jù)庫搜索中遇到的每個(gè)完整狀態(tài)通過在數(shù)據(jù)庫中查找出相應(yīng)子問題布局而設(shè)計(jì)出一個(gè)可采納的啟發(fā)函數(shù)對于八數(shù)碼問題，這樣的啟發(fā)函數(shù)要比曼哈頓距離精確得多(具體數(shù)值見p87)第2章搜索技術(shù)68子問題的解耗散作為啟發(fā)函數(shù)子問題的最優(yōu)解耗散是完整問題的耗散從經(jīng)驗(yàn)中學(xué)習(xí)啟發(fā)函數(shù)從實(shí)例中學(xué)習(xí)—每個(gè)實(shí)例包含了解路徑上的各狀態(tài)及其到達(dá)解的耗散每個(gè)最優(yōu)解實(shí)例提供了可學(xué)習(xí)h(n)的實(shí)例收集實(shí)際解消耗的統(tǒng)計(jì)數(shù)據(jù)，以此產(chǎn)生可預(yù)測其他狀態(tài)解消耗的啟發(fā)函數(shù)h(n)使用歸納學(xué)習(xí)方法八數(shù)碼問題的討論(p87)第2章搜索技術(shù)69從經(jīng)驗(yàn)中學(xué)習(xí)啟發(fā)函數(shù)從實(shí)例中學(xué)習(xí)—每個(gè)實(shí)例包含了解路徑上的各A*搜索的例子(1)積木塊移動(dòng)游戲初始狀態(tài)：目標(biāo)狀態(tài)：移動(dòng)規(guī)則：

(1)積木移到空格/代價(jià)=1 (2)積木跨越1個(gè)積木移到空格/代價(jià)=1 (3)積木跨越2個(gè)積木移到空格/代價(jià)=2第2章搜索技術(shù)70A*搜索的例子(1)積木塊移動(dòng)游戲第2章搜索技術(shù)70A*搜索的例子(2)A*搜索：至少代價(jià)=每個(gè)W左邊B的個(gè)數(shù)(B到W右邊的必須跨越W的代價(jià))令h(n)=至少代價(jià)，則h(n)≤h*(n)且滿足單調(diào)性

h(ni)≤h(ni+1)+g(ni+1)-g(ni)(實(shí)際是=)g(n)=到達(dá)當(dāng)前狀態(tài)實(shí)際付出的代價(jià)搜索過程中括號里的數(shù)字分別為h/g值第2章搜索技術(shù)71A*搜索的例子(2)A*搜索：至少代價(jià)=每個(gè)W左邊B的個(gè)數(shù)(A*搜索的例子(3)第2章搜索技術(shù)72A*搜索的例子(3)第2章搜索技術(shù)722.3.4

聯(lián)機(jī)搜索脫機(jī)搜索—不需感知，只要計(jì)算例子：簡單游戲，通過有限的規(guī)則作用即可推算出目標(biāo)所在聯(lián)機(jī)搜索—必須通過行動(dòng)/觀察與計(jì)算交叉進(jìn)行才能決定下一步搜索兩種情況：環(huán)境未知—只有行動(dòng)才能得知如何正確走向目標(biāo)/環(huán)境空間過大—雖然理論上已知，但是實(shí)際不可計(jì)算(如棋類比賽)第2章搜索技術(shù)732.3.4聯(lián)機(jī)搜索脫機(jī)搜索—不需感知，只要計(jì)算第2章搜索例子：迷宮問題第2章搜索技術(shù)GS321123

如左圖所示，聯(lián)機(jī)搜索問題只能通過行動(dòng)來解決，因?yàn)檎系K是不能事先預(yù)知的智能體初始位置在S，其已知信息為：ACTION(s)—狀態(tài)S下的行動(dòng)列表c(s,a,s’)—通過行動(dòng)a從s狀態(tài)到達(dá)s’狀態(tài)

Goal-Test(s)/G目標(biāo)位置智能體可使用曼哈頓距離啟發(fā)式74例子：迷宮問題第2章搜索技術(shù)GS312競爭率(1)代價(jià)—智能體實(shí)際走過的路經(jīng)總耗散理想耗散—沒有無用搜索步驟的走過路徑耗散/也就是應(yīng)該走過路徑的耗散競爭率—代價(jià)÷理想耗散該值要盡可能地小第2章搜索技術(shù)75競爭率(1)代價(jià)—智能體實(shí)際走過的路經(jīng)總耗散第2章搜索技術(shù)競爭率(2)影響競爭率的因素，使其無窮大行動(dòng)不可逆—進(jìn)入一個(gè)不可到達(dá)目標(biāo)的狀態(tài)又不可回溯沒有算法能夠在所有的狀態(tài)空間中避免死路(p98圖4.19a)因此，通常需要假設(shè)狀態(tài)空間是可安全探索的—具有可逆的狀態(tài)空間/從每個(gè)可達(dá)狀態(tài)出發(fā)都有可達(dá)的目標(biāo)狀態(tài)不過，在可逆狀態(tài)空間中，因?yàn)閷κ值拇嬖?，也?huì)出現(xiàn)無界競爭率的情況(p98圖4.19b)第2章搜索技術(shù)76競爭率(2)影響競爭率的因素，使其無窮大第2章搜索技術(shù)76聯(lián)機(jī)搜索智能體聯(lián)機(jī)搜索智能體需要行動(dòng)和感知，然后擴(kuò)展當(dāng)前狀態(tài)的環(huán)境地圖區(qū)別：聯(lián)機(jī)—規(guī)劃與行動(dòng)交叉/脫機(jī)—只要規(guī)劃例子：A*搜索在不同子空間節(jié)點(diǎn)的跳躍式擴(kuò)展，模擬而非實(shí)際行動(dòng)/聯(lián)機(jī)算法只擴(kuò)展目前實(shí)際占據(jù)的節(jié)點(diǎn)—采用深度優(yōu)先搜索聯(lián)機(jī)搜索必須維護(hù)一個(gè)回溯表第2章搜索技術(shù)77聯(lián)機(jī)搜索智能體聯(lián)機(jī)搜索智能體需要行動(dòng)和感知，然后擴(kuò)展當(dāng)前狀態(tài)人工智能原理

第2章搜索技術(shù)

（上）

78人工智能原理

第2章搜索技術(shù)

（上）1

本章內(nèi)容

2.1搜索與問題求解

2.2無信息搜索策略

2.3啟發(fā)式搜索策略

2.4局部搜索算法

2.5約束滿足問題

2.6博弈搜索

參考書目

附錄A*算法可采納性的證明第2章搜索技術(shù)79 本章內(nèi)容

2.1搜索與問題求解

2.2無信息2.1搜索與問題求解

2.1.1問題與問題的解

2.1.2問題實(shí)例

2.1.3搜索策略第2章搜索技術(shù)802.1搜索與問題求解

2.1.1問題與問題的解

2.1搜索與問題求解問題求解過程是搜索答案(目標(biāo))的過程/所以問題求解技術(shù)也叫搜索技術(shù)—通過對狀態(tài)空間的搜索而求解問題的技術(shù)問題求解智能體是一種基于目標(biāo)的智能體在尋找到達(dá)目標(biāo)的過程中，當(dāng)智能體面對多個(gè)未知的選項(xiàng)時(shí)，首先檢驗(yàn)各個(gè)不同的導(dǎo)致已知評價(jià)的狀態(tài)的可能行動(dòng)序列，然后選擇最佳序列—這個(gè)過程就是搜索第2章搜索技術(shù)81搜索與問題求解問題求解過程是搜索答案(目標(biāo))的過程/所以2.1.1問題與問題的解問題可以形式化地定義為4個(gè)組成部分智能體的初始狀態(tài)(即搜索的開始)后繼函數(shù)—智能體采取的可能行動(dòng)的描述，通常為<行動(dòng)，后繼狀態(tài)>/初始狀態(tài)和后繼函數(shù)隱含地定義了問題的狀態(tài)空間/狀態(tài)空間中的一條路徑是通過行動(dòng)序列連接起來的一個(gè)狀態(tài)序列目標(biāo)測試—檢查給定的狀態(tài)是不是目標(biāo)路徑耗散函數(shù)—每條路徑都有一個(gè)數(shù)值化的耗散值，反映了性能度量/求解問題的代價(jià)第2章搜索技術(shù)822.1.1問題與問題的解問題可以形式化地定義為4個(gè)組成部分問題的解問題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑解的優(yōu)劣由路徑耗散函數(shù)量度(代價(jià))最優(yōu)解就是路徑耗散函數(shù)值最小的路徑上述解題過程把解決一個(gè)問題的過程描述出來，稱之為解題知識(shí)的過程性表示過程性知識(shí)與陳述性知識(shí)相對搜索過程解題的特點(diǎn)—沒有直接的方法(公式)可以求解，而是一步一步的探索第2章搜索技術(shù)83問題的解問題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑第2章搜索技術(shù)狀態(tài)空間數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標(biāo)狀態(tài)也可能沒有狀態(tài)空間：在解題過程中的每一時(shí)刻，數(shù)據(jù)基都處于一定的狀態(tài)，數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間有向圖：若把每個(gè)狀態(tài)看成一個(gè)節(jié)點(diǎn)，則整個(gè)狀態(tài)空間是一個(gè)有向圖/該圖不一定全連通，即從某些狀態(tài)不一定能到達(dá)另外一些狀態(tài)第2章搜索技術(shù)84狀態(tài)空間數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標(biāo)問題的可解性可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將狀態(tài)改變/如果從代表初始狀態(tài)的節(jié)點(diǎn)出發(fā)，有一條路徑通向目標(biāo)狀態(tài)，則稱此目標(biāo)狀態(tài)所代表的問題在當(dāng)前初始狀態(tài)下是可解的搜索空間：在解題過程中達(dá)到過的所有狀態(tài)的集合，稱為搜索空間不同于狀態(tài)空間，搜索空間只是其中一部分狀態(tài)空間和搜索空間都屬于過程性知識(shí)表示第2章搜索技術(shù)85問題的可解性可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將2.1.2問題實(shí)例玩具問題八數(shù)碼游戲(九宮圖)河內(nèi)塔八皇后問題真空吸塵器世界現(xiàn)實(shí)問題旅行商問題超大規(guī)模集成電路的布局自動(dòng)裝配排序/蛋白質(zhì)設(shè)計(jì)互聯(lián)網(wǎng)搜索第2章搜索技術(shù)862.1.2問題實(shí)例玩具問題第2章搜索技術(shù)9八數(shù)碼游戲八數(shù)碼游戲：1-8數(shù)字(棋子)/9個(gè)方格(棋盤格)/1個(gè)空格可用如下形式的規(guī)則來表示數(shù)字通過空格進(jìn)行移動(dòng)：<a1,a2,a3,a4,a5,a6,a7,a8,a9>→<b1,b2,b3,b4,b5,b6,b7,b8,b9>共24條規(guī)則=4角*2+4邊*3+1中間*4搜索順序舉例： (1)優(yōu)先移動(dòng)行數(shù)小的棋子(數(shù)字) (2)同一行中優(yōu)先移動(dòng)列數(shù)大的棋子約束規(guī)則：不使離開既定位置的數(shù)字?jǐn)?shù)增加第2章搜索技術(shù)87八數(shù)碼游戲八數(shù)碼游戲：1-8數(shù)字(棋子)/9個(gè)方格(棋盤格)八數(shù)碼游戲的搜索樹第2章搜索技術(shù)既定位置=終態(tài)88八數(shù)碼游戲的搜索樹第2章搜索技術(shù)既定位置=終態(tài)11八數(shù)碼問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應(yīng)的位置，各位置上的初始數(shù)字后繼函數(shù)移動(dòng)規(guī)則—按照某條規(guī)則移動(dòng)數(shù)字，將得到的新向量目標(biāo)測試新向量是否是目標(biāo)狀態(tài)(也是向量形式)路徑耗散函數(shù)每次移動(dòng)代價(jià)為1第2章搜索技術(shù)89八數(shù)碼問題形式化初始狀態(tài)第2章搜索技術(shù)12河內(nèi)塔(1)河內(nèi)塔問題：n個(gè)大小不等的圓盤從一個(gè)柱子移到另一個(gè)柱子，共有3個(gè)柱子(n階河內(nèi)塔問題)約束：從第1根柱子移動(dòng)到第3根柱子上去，利用第2根柱子/每次移動(dòng)1個(gè)盤子，且移動(dòng)過程必須是小盤落大盤描述：設(shè)每個(gè)狀態(tài)為(a1,a2,a3,…,an),

ai=1,2,3—表示第i個(gè)盤子在第1/2/3根柱子上第2章搜索技術(shù)90河內(nèi)塔(1)河內(nèi)塔問題：n個(gè)大小不等的圓盤從一個(gè)柱子移到另一河內(nèi)塔(2)遞歸定義：{(a1,a2,a3,…,an)}為n階河內(nèi)塔的狀態(tài)集合，則{(a1,a2,a3,…,an,1),(a1,a2,a3,…,an,2),(a1,a2,a3,…,an,3)}是n+1階河內(nèi)塔的狀態(tài)集合1階河內(nèi)塔有3個(gè)狀態(tài)，2階河內(nèi)塔有9個(gè)狀態(tài)，n階河內(nèi)塔有3n個(gè)狀態(tài)，給出1/2/3階河內(nèi)塔的狀態(tài)圖第2章搜索技術(shù)91河內(nèi)塔(2)遞歸定義：{(a1,a2,a3,…,an河內(nèi)塔問題圖解第2章搜索技術(shù)92河內(nèi)塔問題圖解第2章搜索技術(shù)15河內(nèi)塔問題形式化初始狀態(tài)初始狀態(tài)向量—規(guī)定向量中各分量對應(yīng)所有n個(gè)盤子，位置上數(shù)字代表3個(gè)柱子之一后繼函數(shù)移動(dòng)規(guī)則—依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài)目標(biāo)測試新向量是否是目標(biāo)狀態(tài)(也是向量形式)路徑耗散函數(shù)每移動(dòng)一個(gè)盤子的代價(jià)為1第2章搜索技術(shù)93河內(nèi)塔問題形式化初始狀態(tài)第2章搜索技術(shù)16河內(nèi)塔問題求解求最短路徑問題：狀態(tài)圖中從三角形1個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn)結(jié)論：(1)如果初始狀態(tài)或目標(biāo)狀態(tài)在三角形頂點(diǎn)上，則最短路徑唯一；(2)對于任意2個(gè)狀態(tài)，最短求解路徑至多為2條。(中國某大學(xué)研究生證明)求解過程—對狀態(tài)空間的搜索—以2階河內(nèi)塔為例第2章搜索技術(shù)94河內(nèi)塔問題求解求最短路徑問題：狀態(tài)圖中從三角形1個(gè)頂點(diǎn)走到另河內(nèi)塔問題的搜索樹第2章搜索技術(shù)1,12,13,11,12,31,13,23,32,1×2,2××√3,12,2×1,32,13,3××2,33,31,21,1××√2,21,23,13,3××√2,23,21,31,1××√95河內(nèi)塔問題的搜索樹第2章搜索技術(shù)1,12,13,11,12求解過程—樹搜索求解問題的過程使用搜索樹形式每個(gè)狀態(tài)對應(yīng)搜索樹中一個(gè)節(jié)點(diǎn)根節(jié)點(diǎn)對應(yīng)于初始狀態(tài)每次從搜索樹的上層節(jié)點(diǎn)出發(fā)，根據(jù)約束條件進(jìn)入下一個(gè)可能的狀態(tài)，即展開新的一層樹節(jié)點(diǎn)—節(jié)點(diǎn)擴(kuò)展節(jié)點(diǎn)展開的順序即代表了不同的搜索策略當(dāng)展開的節(jié)點(diǎn)為目標(biāo)狀態(tài)時(shí)，就找到了問題的一個(gè)解第2章搜索技術(shù)96求解過程—樹搜索求解問題的過程使用搜索樹形式第2章搜索技術(shù)2.1.3搜索策略研究搜索過程考慮的若干問題 (1)有限搜索還是無限搜索 (2)已知目標(biāo)還是未知目標(biāo) (3)目標(biāo)或目標(biāo)+路徑 (4)有約束還是無約束 (5)數(shù)據(jù)驅(qū)動(dòng)(向前搜索)還是目標(biāo)驅(qū)動(dòng) (6)單向搜索還是雙向搜索第2章搜索技術(shù)972.1.3搜索策略研究搜索過程考慮的若干問題第2章搜索技搜索的分類搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空間搜索(層次方法)，博弈空間搜索無信息搜索與啟發(fā)式搜索啟發(fā)式：利用中間信息改進(jìn)控制策略啟發(fā)式：(1)任何有助于找到問題的解，但不能保證找到解的方法是啟發(fā)式方法(2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法啟發(fā)式也叫啟發(fā)函數(shù)第2章搜索技術(shù)98搜索的分類搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空搜索算法的性能4種途徑來評價(jià)搜索算法的性能完備性—當(dāng)問題有解時(shí)，算法是否保證找到一個(gè)解最優(yōu)性—算法是否能找到一個(gè)最優(yōu)解(路徑耗散函數(shù)值最小的路徑)時(shí)間復(fù)雜性—找到一個(gè)解需要花費(fèi)多少時(shí)間空間復(fù)雜性—在搜索過程中需要占用多少內(nèi)存第2章搜索技術(shù)99搜索算法的性能4種途徑來評價(jià)搜索算法的性能第2章搜索技術(shù)2性能量度時(shí)空復(fù)雜性的量度—由狀態(tài)空間圖的大小來衡量/相關(guān)度量如下：分支因子b (每次展開的平均節(jié)點(diǎn)個(gè)數(shù))目標(biāo)節(jié)點(diǎn)的深度d路徑的最大長度m 搜索深度限制l搜索耗散第2章搜索技術(shù)100性能量度時(shí)空復(fù)雜性的量度—由狀態(tài)空間圖的大小來衡量/相關(guān)2.2無信息搜索策略

2.2.1廣度優(yōu)先搜索

2.2.2深度優(yōu)先搜索和深度有限搜索

2.2.3疊代深入深度優(yōu)先搜索

2.2.4無信息搜索策略性能比較

2.2.5圖搜索算法第2章搜索技術(shù)1012.2無信息搜索策略

2.2.1廣度優(yōu)先搜索

2.2.盲目搜索策略無信息搜索也稱盲目搜索：沒有任何附加信息，只有生成后繼和區(qū)分目標(biāo)與非目標(biāo)狀態(tài)有5種盲目搜索策略廣度優(yōu)先搜索代價(jià)一致搜索深度優(yōu)先搜索深度有限搜索迭代深入深度優(yōu)先搜索第2章搜索技術(shù)102盲目搜索策略無信息搜索也稱盲目搜索：沒有任何附加信息，只有生2.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索過程：首先擴(kuò)展根節(jié)點(diǎn)接著擴(kuò)展根節(jié)點(diǎn)的所有后繼節(jié)點(diǎn)然后再擴(kuò)展后繼節(jié)點(diǎn)的后繼，依此類推在下一層任何節(jié)點(diǎn)擴(kuò)展之前搜索樹上的本層深度的所有節(jié)點(diǎn)都已經(jīng)被擴(kuò)展廣度優(yōu)先搜索可以調(diào)用樹搜索算法(Tree-Search)實(shí)現(xiàn)其參數(shù)fringe(邊緣/擴(kuò)展分支)為先進(jìn)先出隊(duì)列FIFO第2章搜索技術(shù)1032.2.1廣度優(yōu)先搜索廣度優(yōu)先搜索過程：第2章搜索技術(shù)2樹搜索算法(1)functionTree-Search(problem,fringe)returnsolution/failure (initialfringe=empty,mode=FIFO) fringe←Insert(Make-Node(Initial-State[problem]),fringe)

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=GoalthenreturnSolution(node) fringe←Insert-All(Expend(node,problem), fringe)第2章搜索技術(shù)104樹搜索算法(1)functionTree-Search(p樹搜索算法(2)關(guān)鍵在于如何擴(kuò)展節(jié)點(diǎn)function

Expend(node,problem)returnsetofnodes successors←theemptyset

foreach<action,result>inSuccessor-Find[problem](State[node])do s←newNode/State[s]←result Parent-Node[s]=node/Action[s]=action Path-Cost[s]=Path-Cost[node]+Step-Cost[node, action,s] Depth[s]←Depth[node]+1 addstosuccessors

returnsuccessors第2章搜索技術(shù)105樹搜索算法(2)關(guān)鍵在于如何擴(kuò)展節(jié)點(diǎn)第2章搜索技術(shù)28廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Search(problem,FIFO-Queue)調(diào)用樹搜索算法從4種度量來評價(jià)廣度優(yōu)先搜索：完備性—總能找到一個(gè)解如果每步擴(kuò)展的耗散相同時(shí)，廣度優(yōu)先搜索能找到最優(yōu)解內(nèi)存消耗是比執(zhí)行時(shí)間消耗更大的問題指數(shù)級的時(shí)間消耗(空間和時(shí)間消耗的例子參見p60圖3.11)第2章搜索技術(shù)106廣度優(yōu)先搜索的性能在上述算法中，廣度優(yōu)先搜索以Tree-Se2.2.2深度優(yōu)先搜索和深度有限搜索深度優(yōu)先搜索過程：總是擴(kuò)展搜索樹的當(dāng)前擴(kuò)展分支(邊緣)中最深的節(jié)點(diǎn)搜索直接伸展到搜索樹的最深層，直到那里的節(jié)點(diǎn)沒有后繼節(jié)點(diǎn)那些沒有后繼節(jié)點(diǎn)的節(jié)點(diǎn)擴(kuò)展完畢就從邊緣中去掉然后搜索算法回退下一個(gè)還有未擴(kuò)展后繼節(jié)點(diǎn)的上層節(jié)點(diǎn)繼續(xù)擴(kuò)展搜索算法參見深度有限搜索算法(l=∞)第2章搜索技術(shù)1072.2.2深度優(yōu)先搜索和深度有限搜索深度優(yōu)先搜索過程：第2深度優(yōu)先搜索的性能深度優(yōu)先搜索通過后進(jìn)先出隊(duì)列LIFO(棧)調(diào)用Tree-Search實(shí)現(xiàn)/通常使用遞歸函數(shù)實(shí)現(xiàn)，依次對當(dāng)前節(jié)點(diǎn)的子節(jié)點(diǎn)調(diào)用該函數(shù)性能：內(nèi)存需求少—如分支因子=b/最大深度=m的狀態(tài)空間深度優(yōu)先搜索只需要存儲(chǔ)bm+1個(gè)節(jié)點(diǎn)(比較廣度優(yōu)先O(bd+1))不是完備的/不是最優(yōu)的最壞情況下時(shí)間復(fù)雜性也很高O(bm)第2章搜索技術(shù)108深度優(yōu)先搜索的性能深度優(yōu)先搜索通過后進(jìn)先出隊(duì)列LIFO(棧)深度有限搜索深度優(yōu)先搜索的無邊界問題可以通過提供一個(gè)預(yù)先設(shè)定的深度限制l來解決深度=l的節(jié)點(diǎn)當(dāng)作無后繼節(jié)點(diǎn)看待雖然解決了無限路徑問題，但如果l<d則找不到解如果選擇d>l則深度優(yōu)先搜索也不是最優(yōu)的時(shí)間復(fù)雜度O(bl)空間復(fù)雜度O(bl)深度優(yōu)先搜索可看作是一種特例即l=∞第2章搜索技術(shù)109深度有限搜索深度優(yōu)先搜索的無邊界問題可以通過提供一個(gè)預(yù)先設(shè)定非遞歸的深度有限搜索算法functionDepth-Limited-Search(problem,fringe,limit)returnsolution/failure/cutoff

fringe←Insert(Make-Node(Initial-State[problem]),fringe) (mode=LIFO)

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=Goalthenreturn Solution(node)

elseifDepth[node]=limitthenreturncutoff elsefringe←Insert-All(Expend (node,problem),fringe)

第2章搜索技術(shù)110非遞歸的深度有限搜索算法functionDepth-Lim搜索步數(shù)的限制上面算法中可能有兩類失敗cutoff表示到達(dá)了有限深度而無解failure表示一般的返回值無解有時(shí)深度有限搜索基于問題本身的知識(shí)，如狀態(tài)空間的直徑即問題求解的最大步數(shù)但對于大多數(shù)問題，不到問題解決時(shí)是無法知道求解步數(shù)的限制第2章搜索技術(shù)111搜索步數(shù)的限制上面算法中可能有兩類失敗第2章搜索技術(shù)342.2.3疊代深入深度優(yōu)先搜索如果每次改變限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深入深度優(yōu)先搜索算法其深度限制依次為0/1/2…這樣，當(dāng)搜索到達(dá)最淺的目標(biāo)節(jié)點(diǎn)深度時(shí)就可以發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn)這種搜索結(jié)合了廣度優(yōu)先和深度優(yōu)先兩種算法的優(yōu)點(diǎn)(算法見p63)分支因子有限時(shí)是完備的/路徑耗散是節(jié)點(diǎn)深度的非遞增函數(shù)時(shí)是最優(yōu)的空間需求為O(bd)/時(shí)間復(fù)雜性為O(bd)第2章搜索技術(shù)1122.2.3疊代深入深度優(yōu)先搜索如果每次改變限制深度，多次調(diào)狀態(tài)的生成疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次生成，看起來很浪費(fèi)但是因?yàn)樵诜种б蜃颖容^平衡的搜索樹中，多數(shù)節(jié)點(diǎn)都在最底層(即葉子節(jié)點(diǎn))，所以上層節(jié)點(diǎn)的多次生成影響不是很大/與廣度優(yōu)先搜索相比，效率還是更高一般來講，當(dāng)搜索空間很大而解的深度未知時(shí)，疊代深入搜索是一個(gè)首選的無信息搜索方法第2章搜索技術(shù)113狀態(tài)的生成疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次2.2.4無信息搜索策略比較第2章搜索技術(shù)評價(jià)標(biāo)準(zhǔn)廣度優(yōu)先代價(jià)一致深度優(yōu)先深度有限疊代深入雙向搜索是否完備時(shí)間空間是否最優(yōu)是A是A/B否否是A是A/D

O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)O(bd+1)O(bC/e)O(bm)O(bl)O(bd)O(bd/2)是C是否否是C是C/D

關(guān)于A/B/C/D的解釋：A—如果b有限則是完備的/B—單步耗散≥e則是完備的/C—如果單步耗散都是相同的則是最優(yōu)的/D—兩個(gè)方向上都使用廣度優(yōu)先搜索1142.2.4無信息搜索策略比較第2章搜索技術(shù)評價(jià)標(biāo)準(zhǔn)廣度優(yōu)2.2.5圖搜索算法已經(jīng)看到搜索過程中會(huì)出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展，應(yīng)該避免/如果算法不檢測重復(fù)狀態(tài)的話，有可能使一個(gè)本來可解的問題變?yōu)椴豢山鈾z測就是把要擴(kuò)展的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)進(jìn)行比較，把遇到的相同狀態(tài)去掉所以要記錄已經(jīng)擴(kuò)展的節(jié)點(diǎn)—引入兩個(gè)表—存儲(chǔ)已擴(kuò)展的節(jié)點(diǎn)closed表和未擴(kuò)展的節(jié)點(diǎn)open表(即前述fringe)新算法稱為圖搜索算法第2章搜索技術(shù)1152.2.5圖搜索算法已經(jīng)看到搜索過程中會(huì)出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展圖搜索算法第2章搜索技術(shù)functionGraph-Search(problem,fringe)returnsolutionorfailure

closed←emptyset fringe←Insert(Make-Node(Initial-State[problem]),fringe)

dowhile(1)

iffringe=Emptythenreturnfailure node←Remove-First(fringe)

ifState[node]=GoalthenreturnSolution(node)

ifState[node]!CLOSEDthen addState[node]toclosed fringe←Insert-All(Expend(node,problem),fringe)116圖搜索算法第2章搜索技術(shù)functionGraph-Se圖搜索算法的性能由樹到圖：存在不同分支節(jié)點(diǎn)的合并圖搜索算法與樹搜索算法比較：只是增加了對展開節(jié)點(diǎn)的判斷，因此由不同的待擴(kuò)展節(jié)點(diǎn)排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍然同樹搜索算法對于含很多重復(fù)狀態(tài)的問題，其搜索效率比樹搜索算法有效很多討論參見p67第2章搜索技術(shù)117圖搜索算法的性能由樹到圖：存在不同分支節(jié)點(diǎn)的合并第2章搜索例子：“農(nóng)夫過河”問題搜索農(nóng)夫過河問題用向量<人,狼,羊,白菜>表示在河岸兩邊的情況0表示此岸/1表示彼岸過河規(guī)則有8條(隱含了約束條件)1(0,*,*,*)→(1,*,*,*)/2(0,0,*,*)→(1,1,*,*) 3(0,*,0,*)→(1,*,1,*)/4(0,*,*,0)→(1,*,*,1) 5(1,*,*,*)→(0,*,*,*)/6(1,1,*,*)→(0,0,*,*)7(1,*,1,*)→(0,*,0,*)/8(1,*,*,1)→(0,*,*,0)

*=0/1表示任意岸邊但必須相同第2章搜索技術(shù)118例子：“農(nóng)夫過河”問題搜索農(nóng)夫過河問題第2章搜索技術(shù)41“農(nóng)夫過河”—廣度優(yōu)先搜索