人工智能原理搜索技術(shù)上.ppt

1、人工智能原理第2章 搜索技術(shù)（上）,本章內(nèi)容2.1 搜索與問(wèn)題求解2.2 無(wú)信息搜索策略2.3 啟發(fā)式搜索策略2.4 局部搜索算法2.5 約束滿足問(wèn)題2.6 博弈搜索參考書(shū)目附錄 A*算法可采納性的證明,第2章 搜索技術(shù),2.1 搜索與問(wèn)題求解2.1.1 問(wèn)題與問(wèn)題的解2.1.2 問(wèn)題實(shí)例2.1.3 搜索策略,第2章 搜索技術(shù),4,搜索與問(wèn)題求解,問(wèn)題求解過(guò)程是搜索答案(目標(biāo))的過(guò)程 / 所以問(wèn)題求解技術(shù)也叫搜索技術(shù)通過(guò)對(duì)狀態(tài)空間的搜索而求解問(wèn)題的技術(shù) 問(wèn)題求解智能體是一種基于目標(biāo)的智能體 在尋找到達(dá)目標(biāo)的過(guò)程中，當(dāng)智能體面對(duì)多個(gè)未知的選項(xiàng)時(shí)，首先檢驗(yàn)各個(gè)不同的導(dǎo)致已知評(píng)價(jià)的狀態(tài)的可能行動(dòng)序列

2、，然后選擇最佳序列這個(gè)過(guò)程就是搜索,第2章 搜索技術(shù),5,2.1.1 問(wèn)題與問(wèn)題的解,問(wèn)題可以形式化地定義為4個(gè)組成部分 智能體的初始狀態(tài)(即搜索的開(kāi)始) 后繼函數(shù)智能體采取的可能行動(dòng)的描述，通常為 / 初始狀態(tài)和后繼函數(shù)隱含地定義了問(wèn)題的狀態(tài)空間 / 狀態(tài)空間中的一條路徑是通過(guò)行動(dòng)序列連接起來(lái)的一個(gè)狀態(tài)序列 目標(biāo)測(cè)試檢查給定的狀態(tài)是不是目標(biāo) 路徑耗散函數(shù)每條路徑都有一個(gè)數(shù)值化的耗散值，反映了性能度量 / 求解問(wèn)題的代價(jià),第2章 搜索技術(shù),6,問(wèn)題的解,問(wèn)題的解就是初始狀態(tài)到目標(biāo)狀態(tài)的路徑 解的優(yōu)劣由路徑耗散函數(shù)量度(代價(jià)) 最優(yōu)解就是路徑耗散函數(shù)值最小的路徑 上述解題過(guò)程把解決一個(gè)問(wèn)題的過(guò)程

3、描述出來(lái)，稱之為解題知識(shí)的過(guò)程性表示 過(guò)程性知識(shí)與陳述性知識(shí)相對(duì) 搜索過(guò)程解題的特點(diǎn)沒(méi)有直接的方法(公式)可以求解，而是一步一步的探索,第2章 搜索技術(shù),7,狀態(tài)空間,數(shù)據(jù)基：代表了所要解決的問(wèn)題，有初始狀態(tài)，可能有目標(biāo)狀態(tài)也可能沒(méi)有 狀態(tài)空間：在解題過(guò)程中的每一時(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ù),8,問(wèn)題的可解性,可解的：在每個(gè)連通部分，每個(gè)弧代表一個(gè)運(yùn)算符，將狀態(tài)改變 / 如果從代表初始狀態(tài)的節(jié)點(diǎn)出發(fā)，有一條路徑通向目標(biāo)

4、狀態(tài)，則稱此目標(biāo)狀態(tài)所代表的問(wèn)題在當(dāng)前初始狀態(tài)下是可解的 搜索空間：在解題過(guò)程中達(dá)到過(guò)的所有狀態(tài)的集合，稱為搜索空間 不同于狀態(tài)空間，搜索空間只是其中一部分 狀態(tài)空間和搜索空間都屬于過(guò)程性知識(shí)表示,第2章 搜索技術(shù),9,2.1.2 問(wèn)題實(shí)例,玩具問(wèn)題 八數(shù)碼游戲(九宮圖) 河內(nèi)塔 八皇后問(wèn)題 真空吸塵器世界 現(xiàn)實(shí)問(wèn)題 旅行商問(wèn)題 超大規(guī)模集成電路的布局 自動(dòng)裝配排序 / 蛋白質(zhì)設(shè)計(jì) 互聯(lián)網(wǎng)搜索,第2章 搜索技術(shù),10,八數(shù)碼游戲,八數(shù)碼游戲：1-8數(shù)字(棋子)/9個(gè)方格(棋盤(pán)格)/1個(gè)空格 可用如下形式的規(guī)則來(lái)表示數(shù)字通過(guò)空格進(jìn)行移動(dòng)： 共24條規(guī)則=4角*2+4邊*3+1中間*4 搜索順序舉

5、例： (1)優(yōu)先移動(dòng)行數(shù)小的棋子(數(shù)字) (2)同一行中優(yōu)先移動(dòng)列數(shù)大的棋子 約束規(guī)則：不使離開(kāi)既定位置的數(shù)字?jǐn)?shù)增加,第2章 搜索技術(shù),11,八數(shù)碼游戲的搜索樹(shù),第2章 搜索技術(shù),既定位置=終態(tài),12,八數(shù)碼問(wèn)題形式化,初始狀態(tài) 初始狀態(tài)向量規(guī)定向量中各分量對(duì)應(yīng)的位置，各位置上的初始數(shù)字 后繼函數(shù) 移動(dòng)規(guī)則按照某條規(guī)則移動(dòng)數(shù)字，將得到的新向量 目標(biāo)測(cè)試 新向量是否是目標(biāo)狀態(tài)(也是向量形式) 路徑耗散函數(shù) 每次移動(dòng)代價(jià)為1,第2章 搜索技術(shù),13,河內(nèi)塔(1),河內(nèi)塔問(wèn)題：n個(gè)大小不等的圓盤(pán)從一個(gè)柱子移到另一個(gè)柱子，共有3個(gè)柱子(n階河內(nèi)塔問(wèn)題) 約束：從第1根柱子移動(dòng)到第3根柱子上去，利用第2

6、根柱子 / 每次移動(dòng)1個(gè)盤(pán)子，且移動(dòng)過(guò)程必須是小盤(pán)落大盤(pán) 描述：設(shè)每個(gè)狀態(tài)為(a1, a2, a3, , an), ai=1, 2, 3表示第i個(gè)盤(pán)子在第1/2/3根柱子上,第2章 搜索技術(shù),14,河內(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ù),15,河內(nèi)塔問(wèn)題圖解,第2章 搜索技

7、術(shù),16,河內(nèi)塔問(wèn)題形式化,初始狀態(tài) 初始狀態(tài)向量規(guī)定向量中各分量對(duì)應(yīng)所有n個(gè)盤(pán)子，位置上數(shù)字代表3個(gè)柱子之一 后繼函數(shù) 移動(dòng)規(guī)則依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài) 目標(biāo)測(cè)試 新向量是否是目標(biāo)狀態(tài)(也是向量形式) 路徑耗散函數(shù) 每移動(dòng)一個(gè)盤(pán)子的代價(jià)為1,第2章 搜索技術(shù),17,河內(nèi)塔問(wèn)題求解,求最短路徑問(wèn)題：狀態(tài)圖中從三角形1個(gè)頂點(diǎn)走到另一個(gè)頂點(diǎn) 結(jié)論： (1)如果初始狀態(tài)或目標(biāo)狀態(tài)在三角形頂點(diǎn)上，則最短路徑唯一； (2)對(duì)于任意2個(gè)狀態(tài)，最短求解路徑至多為2條。(中國(guó)某大學(xué)研究生證明) 求解過(guò)程對(duì)狀態(tài)空間的搜索以2階河內(nèi)塔為例,第2章 搜索技術(shù),18,河內(nèi)塔問(wèn)題的搜索樹(shù),第2章 搜索技術(shù),1

8、,1,2,1,3,1,1,1,2,3,1,1,3,2,3,3,2,1,2,2,3,1,2,2,1,3,2,1,3,3,2,3,3,3,1,2,1,1,2,2,1,2,3,1,3,3,2,2,3,2,1,3,1,1,19,求解過(guò)程樹(shù)搜索,求解問(wèn)題的過(guò)程使用搜索樹(shù)形式 每個(gè)狀態(tài)對(duì)應(yīng)搜索樹(shù)中一個(gè)節(jié)點(diǎn) 根節(jié)點(diǎn)對(duì)應(yīng)于初始狀態(tài) 每次從搜索樹(shù)的上層節(jié)點(diǎn)出發(fā)，根據(jù)約束條件進(jìn)入下一個(gè)可能的狀態(tài)，即展開(kāi)新的一層樹(shù)節(jié)點(diǎn)節(jié)點(diǎn)擴(kuò)展 節(jié)點(diǎn)展開(kāi)的順序即代表了不同的搜索策略 當(dāng)展開(kāi)的節(jié)點(diǎn)為目標(biāo)狀態(tài)時(shí)，就找到了問(wèn)題的一個(gè)解,第2章 搜索技術(shù),20,2.1.3 搜索策略,研究搜索過(guò)程考慮的若干問(wèn)題 (1)有限搜索還是無(wú)限搜索 (

9、2)已知目標(biāo)還是未知目標(biāo) (3)目標(biāo)或目標(biāo)+路徑 (4)有約束還是無(wú)約束 (5)數(shù)據(jù)驅(qū)動(dòng)(向前搜索)還是目標(biāo)驅(qū)動(dòng) (6)單向搜索還是雙向搜索,第2章 搜索技術(shù),21,搜索的分類,搜索過(guò)程的分類：狀態(tài)空間搜索(圖搜索方式)，問(wèn)題空間搜索(層次方法)，博弈空間搜索 無(wú)信息搜索與啟發(fā)式搜索 啟發(fā)式：利用中間信息改進(jìn)控制策略 啟發(fā)式：(1)任何有助于找到問(wèn)題的解，但不能保證找到解的方法是啟發(fā)式方法 (2)有助于加速求解過(guò)程和找到較優(yōu)解的方法是啟發(fā)式方法 啟發(fā)式也叫啟發(fā)函數(shù),第2章 搜索技術(shù),22,搜索算法的性能,4種途徑來(lái)評(píng)價(jià)搜索算法的性能 完備性當(dāng)問(wèn)題有解時(shí)，算法是否保證找到一個(gè)解 最優(yōu)性算法是否能

10、找到一個(gè)最優(yōu)解(路徑耗散函數(shù)值最小的路徑) 時(shí)間復(fù)雜性找到一個(gè)解需要花費(fèi)多少時(shí)間 空間復(fù)雜性在搜索過(guò)程中需要占用多少內(nèi)存,第2章 搜索技術(shù),23,性能量度,時(shí)空復(fù)雜性的量度由狀態(tài)空間圖的大小來(lái)衡量 / 相關(guān)度量如下： 分支因子 b(每次展開(kāi)的平均節(jié)點(diǎn)個(gè)數(shù)) 目標(biāo)節(jié)點(diǎn)的深度 d 路徑的最大長(zhǎng)度 m 搜索深度限制 l 搜索耗散,第2章 搜索技術(shù),2.2 無(wú)信息搜索策略2.2.1 廣度優(yōu)先搜索2.2.2 深度優(yōu)先搜索和深度有限搜索2.2.3 疊代深入深度優(yōu)先搜索2.2.4 無(wú)信息搜索策略性能比較2.2.5 圖搜索算法,第2章 搜索技術(shù),25,盲目搜索策略,無(wú)信息搜索也稱盲目搜索：沒(méi)有任何附加信息，只

11、有生成后繼和區(qū)分目標(biāo)與非目標(biāo)狀態(tài) 有5種盲目搜索策略 廣度優(yōu)先搜索 代價(jià)一致搜索 深度優(yōu)先搜索 深度有限搜索 迭代深入深度優(yōu)先搜索,第2章 搜索技術(shù),26,2.2.1 廣度優(yōu)先搜索,廣度優(yōu)先搜索過(guò)程： 首先擴(kuò)展根節(jié)點(diǎn) 接著擴(kuò)展根節(jié)點(diǎn)的所有后繼節(jié)點(diǎn) 然后再擴(kuò)展后繼節(jié)點(diǎn)的后繼，依此類推 在下一層任何節(jié)點(diǎn)擴(kuò)展之前搜索樹(shù)上的本層深度的所有節(jié)點(diǎn)都已經(jīng)被擴(kuò)展 廣度優(yōu)先搜索可以調(diào)用樹(shù)搜索算法(Tree-Search)實(shí)現(xiàn) 其參數(shù)fringe(邊緣/擴(kuò)展分支)為先進(jìn)先出隊(duì)列FIFO,第2章 搜索技術(shù),27,樹(shù)搜索算法(1),function Tree-Search(problem,fringe) return

12、 solution /failure(initial fringe=empty, mode=FIFO) fringeInsert(Make-Node(Initial-Stateproblem),fringe) do while(1) if fringe=Empty then return failure nodeRemove-First(fringe) if Statenode=Goal then return Solution(node) fringeInsert-All(Expend(node,problem), fringe),第2章 搜索技術(shù),28,樹(shù)搜索算法(2),關(guān)鍵在于如何擴(kuò)展節(jié)

13、點(diǎn) function Expend(node,problem) return set of nodes successorsthe empty set for each in Successor-Findproblem (Statenode) do snew Node / Statesresult Parent-Nodes=node / Actions=action Path-Costs=Path-Costnode+Step-Costnode, action,s DepthsDepthnode+1 add s to successors return successors,第2章 搜索技術(shù),2

14、9,廣度優(yōu)先搜索的性能,在上述算法中，廣度優(yōu)先搜索以Tree-Search(problem,FIFO-Queue)調(diào)用樹(shù)搜索算法 從4種度量來(lái)評(píng)價(jià)廣度優(yōu)先搜索： 完備性總能找到一個(gè)解 如果每步擴(kuò)展的耗散相同時(shí)，廣度優(yōu)先搜索能找到最優(yōu)解 內(nèi)存消耗是比執(zhí)行時(shí)間消耗更大的問(wèn)題 指數(shù)級(jí)的時(shí)間消耗(空間和時(shí)間消耗的例子參見(jiàn)p60圖3.11),第2章 搜索技術(shù),30,2.2.2 深度優(yōu)先搜索和深度有限搜索,深度優(yōu)先搜索過(guò)程： 總是擴(kuò)展搜索樹(shù)的當(dāng)前擴(kuò)展分支(邊緣)中最深的節(jié)點(diǎn) 搜索直接伸展到搜索樹(shù)的最深層，直到那里的節(jié)點(diǎn)沒(méi)有后繼節(jié)點(diǎn) 那些沒(méi)有后繼節(jié)點(diǎn)的節(jié)點(diǎn)擴(kuò)展完畢就從邊緣中去掉 然后搜索算法回退下一個(gè)還有未

15、擴(kuò)展后繼節(jié)點(diǎn)的上層節(jié)點(diǎn)繼續(xù)擴(kuò)展 搜索算法參見(jiàn)深度有限搜索算法(l=),第2章 搜索技術(shù),31,深度優(yōu)先搜索的性能,深度優(yōu)先搜索通過(guò)后進(jìn)先出隊(duì)列LIFO(棧)調(diào)用Tree-Search實(shí)現(xiàn) / 通常使用遞歸函數(shù)實(shí)現(xiàn)，依次對(duì)當(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ù),32,深度有限搜索,深度優(yōu)先搜索的無(wú)邊界問(wèn)題可以通過(guò)提供一個(gè)預(yù)先設(shè)定的深度限制l來(lái)解決 深度=l的節(jié)點(diǎn)當(dāng)作無(wú)后繼節(jié)點(diǎn)看待 雖然解決了無(wú)限路徑問(wèn)題，

16、但如果ll則深度優(yōu)先搜索也不是最優(yōu)的 時(shí)間復(fù)雜度O(bl) 空間復(fù)雜度O(bl) 深度優(yōu)先搜索可看作是一種特例即l=,第2章 搜索技術(shù),33,非遞歸的深度有限搜索算法,function Depth-Limited-Search(problem,fringe,limit) return solution/failure/cutoff fringeInsert(Make-Node(Initial-Stateproblem),fringe)(mode=LIFO) do while(1) if fringe=Empty then return failure nodeRemove-First(frin

17、ge) if Statenode=Goal then return Solution(node) else if Depthnode=limit then return cutoff else fringeInsert-All(Expend(node, problem), fringe),第2章 搜索技術(shù),34,搜索步數(shù)的限制,上面算法中可能有兩類失敗 cutoff表示到達(dá)了有限深度而無(wú)解 failure表示一般的返回值無(wú)解 有時(shí)深度有限搜索基于問(wèn)題本身的知識(shí)，如狀態(tài)空間的直徑即問(wèn)題求解的最大步數(shù) 但對(duì)于大多數(shù)問(wèn)題，不到問(wèn)題解決時(shí)是無(wú)法知道求解步數(shù)的限制,第2章 搜索技術(shù),35,2.2.3 疊

18、代深入深度優(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)(算法見(jiàn)p63) 分支因子有限時(shí)是完備的 / 路徑耗散是節(jié)點(diǎn)深度的非遞增函數(shù)時(shí)是最優(yōu)的 空間需求為O(bd) / 時(shí)間復(fù)雜性為O(bd),第2章 搜索技術(shù),36,狀態(tài)的生成,疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次生成，看起來(lái)很浪費(fèi) 但是因?yàn)樵诜种б蜃颖容^平衡的搜索樹(shù)中，多數(shù)節(jié)點(diǎn)都在最底層(即葉子節(jié)點(diǎn))，所以上層節(jié)點(diǎn)的多次生成影響不是很大 / 與廣度優(yōu)先搜索

19、相比，效率還是更高 一般來(lái)講，當(dāng)搜索空間很大而解的深度未知時(shí)，疊代深入搜索是一個(gè)首選的無(wú)信息搜索方法,第2章 搜索技術(shù),37,2.2.4 無(wú)信息搜索策略比較,第2章 搜索技術(shù),關(guān)于A/B/C/D的解釋：A如果b有限則是完備的 / B單步耗散e則是完備的 / C如果單步耗散都是相同的則是最優(yōu)的 / D兩個(gè)方向上都使用廣度優(yōu)先搜索,38,2.2.5 圖搜索算法,已經(jīng)看到搜索過(guò)程中會(huì)出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展，應(yīng)該避免 / 如果算法不檢測(cè)重復(fù)狀態(tài)的話，有可能使一個(gè)本來(lái)可解的問(wèn)題變?yōu)椴豢山?檢測(cè)就是把要擴(kuò)展的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)進(jìn)行比較，把遇到的相同狀態(tài)去掉 所以要記錄已經(jīng)擴(kuò)展的節(jié)點(diǎn)引入兩個(gè)表存儲(chǔ)已擴(kuò)展的節(jié)點(diǎn)c

20、losed表和未擴(kuò)展的節(jié)點(diǎn)open表(即前述fringe) 新算法稱為圖搜索算法,第2章 搜索技術(shù),39,圖搜索算法,第2章 搜索技術(shù),function Graph-Search(problem,fringe) return solution or failure closedempty set fringeInsert(Make-Node(Initial-Stateproblem),fringe) do while(1) if fringe=Empty then return failure nodeRemove-First(fringe) if Statenode=Goal then re

21、turn Solution(node) if Statenode !CLOSED then add Statenode to closed fringeInsert-All(Expend(node,problem),fringe),40,圖搜索算法的性能,由樹(shù)到圖：存在不同分支節(jié)點(diǎn)的合并 圖搜索算法與樹(shù)搜索算法比較：只是增加了對(duì)展開(kāi)節(jié)點(diǎn)的判斷，因此由不同的待擴(kuò)展節(jié)點(diǎn)排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍然同樹(shù)搜索算法 對(duì)于含很多重復(fù)狀態(tài)的問(wèn)題，其搜索效率比樹(shù)搜索算法有效很多 討論參見(jiàn)p67,第2章 搜索技術(shù),41,例子：“農(nóng)夫過(guò)河”問(wèn)題搜索,農(nóng)夫過(guò)河問(wèn)題 用向量表示在河岸兩邊

22、的情況 0表示此岸 / 1表示彼岸 過(guò)河規(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ù),42,“農(nóng)夫過(guò)河”廣度優(yōu)先搜索

23、,第2章 搜索技術(shù),0 0 0 0,1 0 1 0,1 1 0 0,0 0 1 0,1 1 1 0,0 1 0 0,1 1 0 1,0 1 0 1,1 1 1 1,1 0 1 1,0 0 0 1,closed表 ,所用規(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/3,43,“農(nóng)夫過(guò)河”深度優(yōu)先搜索,第2章 搜索技術(shù),0 0 0 0,1 0 1 0,1 1 0 0,0 0 1 0,1 1 1 0,0 1 0 0,1 1 0 1,0 1 0 1,1 1 1 1,closed表 ,所用規(guī)則序列 3/5/

24、2/7/4,所用規(guī)則序列 3/5/2/7/4/5/3,只使用一個(gè)搜索分支 / 所擴(kuò)展的第一個(gè)節(jié)點(diǎn)是最新節(jié)點(diǎn),2.3 啟發(fā)式搜索策略2.3.1 貪婪最佳優(yōu)先搜索2.3.2 A*搜索2.3.3 啟發(fā)函數(shù)2.3.4 聯(lián)機(jī)搜索,第2章 搜索技術(shù),45,啟發(fā)式搜索通用算法,啟發(fā)式搜索也稱有信息搜索，其通用算法稱為最佳優(yōu)先搜索(Best-First-Search) 最佳優(yōu)先搜索基于評(píng)價(jià)函數(shù)擴(kuò)展節(jié)點(diǎn)按照距離目標(biāo)最短的評(píng)價(jià)值來(lái)擴(kuò)展 并不是真正的最佳只是表現(xiàn)得最佳/近似最佳 算法的關(guān)鍵因素是啟發(fā)函數(shù)(Heuristic function)，記為f(n) / f(n)=從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的耗散估計(jì)值

25、 啟發(fā)函數(shù)引導(dǎo)搜索兩種方式貪婪最佳優(yōu)先搜索 / A*搜索(A*算法),第2章 搜索技術(shù),46,2.3.1 貪婪最佳優(yōu)先搜索,貪婪最佳優(yōu)先搜索的評(píng)價(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)的：SFB實(shí)際全長(zhǎng)310 / SRVPB實(shí)際全長(zhǎng)278，多了32

26、km,第2章 搜索技術(shù),47,問(wèn)題實(shí)例Romania公路圖,第2章 搜索技術(shù),48,問(wèn)題實(shí)例(1),第2章 搜索技術(shù),尋找從Arad到首都的行車最短路線 評(píng)價(jià)函數(shù)f(n)=h(n) 直線距離啟發(fā)式hSLD 與實(shí)際距離相關(guān)但需另外給出，見(jiàn)下表,49,問(wèn)題實(shí)例(2),第2章 搜索技術(shù),啟發(fā)函數(shù)h(n)最小化會(huì)對(duì)錯(cuò)誤的起點(diǎn)比較敏感 例子：地圖中Iasi到Fagaras的行車路線(走入死路的可能) 需要仔細(xì)檢查重復(fù)狀態(tài)，否則可能永遠(yuǎn)找不到解 與深度優(yōu)先搜索類似，非最優(yōu)、非完備 最壞情況下時(shí)空復(fù)雜度都是O(bm) / m為最大搜索深度,50,2.3.2 A*搜索,A*搜索的評(píng)價(jià)函數(shù)為f(n)=g(h)+

27、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)過(guò)節(jié)點(diǎn)n、具有最低耗散值的解的估計(jì)耗散 找到g(n)+h(n)值最小的節(jié)點(diǎn)當(dāng)然是合理的(參見(jiàn)書(shū)中p79圖4.3對(duì)于地圖的搜索) 若啟發(fā)函數(shù)h(n)滿足一定條件，則A*搜索是完備的和最優(yōu)的,第2章 搜索技術(shù),51,搜索算法的可采納性,定義搜索算法的可采納性(可采用性) (Hart, Nilsson, Raphel, 1968) 如果狀態(tài)空間中的目標(biāo)狀態(tài)存在，并且從初始狀態(tài)到目標(biāo)狀態(tài)有一條通路，而搜索算法一定能在有限步內(nèi)終止并找到一個(gè)最優(yōu)解(代價(jià)最低)

28、，則這個(gè)狀態(tài)空間搜索算法稱為可采納的 對(duì)于A*搜索來(lái)說(shuō)，使用樹(shù)搜索算法(Tree-Search)，則它是可采納的 如果對(duì)啟發(fā)函數(shù)h(n)作一定限制，則使用圖搜索算法(Graph-Search)也是可采納的,第2章 搜索技術(shù),52,可采納的啟發(fā)函數(shù),算法的可采納性取決于啟發(fā)函數(shù)的可采納性 啟發(fā)函數(shù)h(n)是可采納的h(n)從來(lái)不會(huì)過(guò)高地估計(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)過(guò)節(jié)點(diǎn)n的解的實(shí)際耗散f(n)f*(n)，所以是最優(yōu)解 如果h(n)是可采納的，那么使用Tree-Search的A*算法是可采納的(最

29、優(yōu)的) 自己嘗試證明，參考附錄證明過(guò)程,第2章 搜索技術(shù),53,A*搜索的Tree-Search算法,function Tree-Search(problem,fringe) return solution or failure Select h(n) Make-Node(Initial-Stateproblem & get their f(n) Insert(nodes, fringe) Sort(fringe, f(n) do while(1) if fringe=Empty then return failure nodeRemove-First(fringe) if Statenode

30、=Goal then return Solution(node) Expend(node, problem) & get their f(n) Insert(nodes, fringe) Sort(fringe, f(n),第2章 搜索技術(shù),54,A*搜索的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)性) 算法請(qǐng)自

31、行給出,第2章 搜索技術(shù),55,h(n)的一致性(1),定義啟發(fā)函數(shù)的一致性如果對(duì)于每個(gè)節(jié)點(diǎn)n和通過(guò)任意行動(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ù),56,h(n)的一致性(2),通

32、常我們選擇的啟發(fā)函數(shù)h(n)都滿足一致性要求(因而必定是可采納的) 關(guān)于一致性的結(jié)論： 如果h(n)是一致的，那么使用Graph-Search的A*算法是最優(yōu)的 附錄證明似乎沒(méi)有利用此條件 如果h(n)是一致的，那么沿著任何路徑的f(n)值是非遞減的(由一致性定義可得) f(n)耗散值沿著任何路徑都是非遞減的結(jié)論允許在狀態(tài)空間中畫(huà)出等值線(見(jiàn)下圖),第2章 搜索技術(shù),57,道路里程的等值線,第2章 搜索技術(shù),58,A*搜索節(jié)點(diǎn)的擴(kuò)展,A*搜索由初始節(jié)點(diǎn)出發(fā)開(kāi)始搜索，以同心帶狀增長(zhǎng)f(n)耗散值的方式擴(kuò)展節(jié)點(diǎn) 如果h(n)=0則為代價(jià)一致搜索(只按g(n)值排序)則同心帶為“圓型”，使用啟發(fā)函數(shù)

33、則同心帶向目標(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ù),59,A*算法的性質(zhì)(1),A*算法是完備的如果解存在，就一定能找到 / 因?yàn)檎业浇庵灰邢薏?A*算法是最優(yōu)的即可采納的(一個(gè)普遍采用的證明見(jiàn)附錄) A*算法對(duì)于任何給定的啟發(fā)函數(shù)都是效率最優(yōu)的 / 沒(méi)有任何其他算法擴(kuò)展的節(jié)點(diǎn)少于A*算法 但是，A*算法對(duì)于多數(shù)問(wèn)題來(lái)說(shuō)，搜索空間處于目標(biāo)等值線內(nèi)的節(jié)點(diǎn)數(shù)量是求解路徑長(zhǎng)度的指數(shù)級(jí),第2章 搜索技術(shù),60

34、,A*算法的性質(zhì)(2),如果要求不以指數(shù)級(jí)增長(zhǎng)，則啟發(fā)函數(shù)需要滿足條件 對(duì)于幾乎所有的啟發(fā)函數(shù)來(lái)說(shuō)，偏差至少都是與路徑耗散成正比的，而不是路徑耗散的對(duì)數(shù) / 所以，在實(shí)際應(yīng)用中，往往不是堅(jiān)持找到最優(yōu)解，而是采用以下兩種方式： 使用A*算法的變種算法快速找到非最優(yōu)解 設(shè)計(jì)準(zhǔn)確而非嚴(yán)格可采納的啟發(fā)函數(shù),第2章 搜索技術(shù),61,A*算法在空間方面的改進(jìn),A*算法在內(nèi)存中保留所有生成的節(jié)點(diǎn)，消耗極大因而對(duì)于許多大規(guī)模問(wèn)題時(shí)不實(shí)用的 A*算法要減少對(duì)內(nèi)存的需求改進(jìn) 遞歸最佳優(yōu)先搜索RBFS模仿標(biāo)準(zhǔn)的最佳優(yōu)先搜索的遞歸算法，只是用線性存儲(chǔ)空間 如果h(n)是可采納的，則RBFS最優(yōu) MA*(存儲(chǔ)限制A*)

35、和SMA*(簡(jiǎn)化的MA*)充分利用可用的內(nèi)存 SMA*的思想當(dāng)內(nèi)存放滿時(shí)，就丟棄最差的一個(gè)子節(jié)點(diǎn)而加入新節(jié)點(diǎn) 如果任何最優(yōu)解是可到達(dá)的，則SMA*是最優(yōu)的,第2章 搜索技術(shù),62,2.3.3 啟發(fā)函數(shù),A*搜索的關(guān)鍵就是設(shè)計(jì)可采納的或者一致的(單調(diào)的)啟發(fā)函數(shù) 如何評(píng)價(jià)啟發(fā)函數(shù) / 如何設(shè)計(jì)啟發(fā)函數(shù) 例子八數(shù)碼問(wèn)題 關(guān)于八數(shù)碼問(wèn)題的一些數(shù)據(jù)： 隨機(jī)產(chǎn)生的八數(shù)碼游戲的平均解的步數(shù)=22 分支因子約為3 窮舉搜索(盲目搜索)考慮的狀態(tài)個(gè)數(shù)3223.1*1010 實(shí)際可到達(dá)的不同狀態(tài)個(gè)數(shù)9!/2=181440,第2章 搜索技術(shù),63,八數(shù)碼問(wèn)題的啟發(fā)函數(shù),啟發(fā)函數(shù)的核心決不高估到達(dá)目標(biāo)的步數(shù) / 對(duì)

36、于八數(shù)碼問(wèn)題的常用候選： 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)這些距離長(zhǎng)度,第2章 搜索技術(shù),64,啟發(fā)函數(shù)精確度對(duì)算法性能的影響,刻畫(huà)啟發(fā)函數(shù)質(zhì)量的一個(gè)度量是有效分支因子b* b*是深度為d的一致搜索樹(shù)為了能夠包括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 有

37、效分支因子可以根據(jù)問(wèn)題實(shí)例發(fā)生變化，但是在足夠難的問(wèn)題中是穩(wěn)定的 / 因此小規(guī)模實(shí)驗(yàn)中測(cè)得b*值可以為啟發(fā)函數(shù)的總體有效性提供指導(dǎo),第2章 搜索技術(shù),65,八數(shù)碼問(wèn)題啟發(fā)函數(shù)的比較,良好設(shè)計(jì)的啟發(fā)函數(shù)使b*值接近1，允許對(duì)大規(guī)模的問(wèn)題進(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頁(yè)給出了八數(shù)碼問(wèn)題的啟發(fā)函數(shù)h1/h2的比較數(shù)據(jù) “優(yōu)于”的含義使用h2的算法不會(huì)比使用h1的算法擴(kuò)展更多的節(jié)點(diǎn),第2章 搜索技術(shù),66,如何設(shè)計(jì)啟發(fā)函數(shù),A*搜索的關(guān)鍵如何找到是一個(gè)

38、合適的啟發(fā)函數(shù) 尋找策略： 從松弛問(wèn)題中獲得松弛問(wèn)題的最優(yōu)解的耗散是原問(wèn)題的一個(gè)可采納的啟發(fā)函數(shù) 從給定問(wèn)題子問(wèn)題的解耗散中獲得建立模式數(shù)據(jù)庫(kù)，存儲(chǔ)每個(gè)可能子問(wèn)題實(shí)例 從經(jīng)驗(yàn)中學(xué)習(xí)使用歸納學(xué)習(xí)算法，使用相關(guān)狀態(tài)特征來(lái)預(yù)測(cè),第2章 搜索技術(shù),67,松弛問(wèn)題最優(yōu)解作為啟發(fā)函數(shù),松弛問(wèn)題降低了行動(dòng)限制的問(wèn)題 松弛問(wèn)題的最優(yōu)解耗散是原問(wèn)題的一個(gè)可采納的啟發(fā)函數(shù) 根據(jù)定義，原始問(wèn)題的最優(yōu)解也是該松弛問(wèn)題的解，其耗散不低于松弛問(wèn)題的最優(yōu)解 松弛問(wèn)題的最優(yōu)解是確切耗散，一定滿足三角不等式，因而是單調(diào)的，所以作為啟發(fā)函數(shù)一定是可采納的 如果問(wèn)題定義通過(guò)形式化語(yǔ)言描述，則自動(dòng)地構(gòu)造其松弛問(wèn)題是可能的 / 例子八數(shù)碼問(wèn)題,第2章 搜索技術(shù),68,子問(wèn)題的解耗散作為啟發(fā)函數(shù),子問(wèn)題的最優(yōu)解耗散是完整問(wèn)題的耗散下界 建立模式數(shù)據(jù)庫(kù)存儲(chǔ)每個(gè)可能子問(wèn)題實(shí)例的精確解耗散