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

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

3、描述出來，稱之為解題知識的過程性表示 過程性知識與陳述性知識相對 搜索過程解題的特點沒有直接的方法(公式)可以求解，而是一步一步的探索,第2章 搜索技術(shù),7,狀態(tài)空間,數(shù)據(jù)基：代表了所要解決的問題，有初始狀態(tài)，可能有目標狀態(tài)也可能沒有 狀態(tài)空間：在解題過程中的每一時刻，數(shù)據(jù)基都處于一定的狀態(tài)，數(shù)據(jù)基所有可能狀態(tài)的集合稱為狀態(tài)空間 有向圖：若把每個狀態(tài)看成一個節(jié)點，則整個狀態(tài)空間是一個有向圖 / 該圖不一定全連通，即從某些狀態(tài)不一定能到達另外一些狀態(tài),第2章 搜索技術(shù),8,問題的可解性,可解的：在每個連通部分，每個弧代表一個運算符，將狀態(tài)改變 / 如果從代表初始狀態(tài)的節(jié)點出發(fā)，有一條路徑通向目標

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

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

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

7、術(shù),16,河內(nèi)塔問題形式化,初始狀態(tài) 初始狀態(tài)向量規(guī)定向量中各分量對應(yīng)所有n個盤子，位置上數(shù)字代表3個柱子之一 后繼函數(shù) 移動規(guī)則依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài) 目標測試 新向量是否是目標狀態(tài)(也是向量形式) 路徑耗散函數(shù) 每移動一個盤子的代價為1,第2章 搜索技術(shù),17,河內(nèi)塔問題求解,求最短路徑問題：狀態(tài)圖中從三角形1個頂點走到另一個頂點 結(jié)論： (1)如果初始狀態(tài)或目標狀態(tài)在三角形頂點上，則最短路徑唯一； (2)對于任意2個狀態(tài)，最短求解路徑至多為2條。(中國某大學研究生證明) 求解過程對狀態(tài)空間的搜索以2階河內(nèi)塔為例,第2章 搜索技術(shù),18,河內(nèi)塔問題的搜索樹,第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,求解過程樹搜索,求解問題的過程使用搜索樹形式 每個狀態(tài)對應(yīng)搜索樹中一個節(jié)點 根節(jié)點對應(yīng)于初始狀態(tài) 每次從搜索樹的上層節(jié)點出發(fā)，根據(jù)約束條件進入下一個可能的狀態(tài)，即展開新的一層樹節(jié)點節(jié)點擴展 節(jié)點展開的順序即代表了不同的搜索策略 當展開的節(jié)點為目標狀態(tài)時，就找到了問題的一個解,第2章 搜索技術(shù),20,2.1.3 搜索策略,研究搜索過程考慮的若干問題 (1)有限搜索還是無限搜索 (

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

10、找到一個最優(yōu)解(路徑耗散函數(shù)值最小的路徑) 時間復雜性找到一個解需要花費多少時間 空間復雜性在搜索過程中需要占用多少內(nèi)存,第2章 搜索技術(shù),23,性能量度,時空復雜性的量度由狀態(tài)空間圖的大小來衡量 / 相關(guān)度量如下： 分支因子 b(每次展開的平均節(jié)點個數(shù)) 目標節(jié)點的深度 d 路徑的最大長度 m 搜索深度限制 l 搜索耗散,第2章 搜索技術(shù),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ù),25,盲目搜索策略,無信息搜索也稱盲目搜索：沒有任何附加信息，只

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

13、點 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)用樹搜索算法 從4種度量來評價廣度優(yōu)先搜索： 完備性總能找到一個解 如果每步擴展的耗散相同時，廣度優(yōu)先搜索能找到最優(yōu)解 內(nèi)存消耗是比執(zhí)行時間消耗更大的問題 指數(shù)級的時間消耗(空間和時間消耗的例子參見p60圖3.11),第2章 搜索技術(shù),30,2.2.2 深度優(yōu)先搜索和深度有限搜索,深度優(yōu)先搜索過程： 總是擴展搜索樹的當前擴展分支(邊緣)中最深的節(jié)點 搜索直接伸展到搜索樹的最深層，直到那里的節(jié)點沒有后繼節(jié)點 那些沒有后繼節(jié)點的節(jié)點擴展完畢就從邊緣中去掉 然后搜索算法回退下一個還有未

15、擴展后繼節(jié)點的上層節(jié)點繼續(xù)擴展 搜索算法參見深度有限搜索算法(l=),第2章 搜索技術(shù),31,深度優(yōu)先搜索的性能,深度優(yōu)先搜索通過后進先出隊列LIFO(棧)調(diào)用Tree-Search實現(xiàn) / 通常使用遞歸函數(shù)實現(xiàn)，依次對當前節(jié)點的子節(jié)點調(diào)用該函數(shù) 性能： 內(nèi)存需求少如分支因子=b/最大深度=m的狀態(tài)空間深度優(yōu)先搜索只需要存儲bm+1個節(jié)點(比較廣度優(yōu)先O(bd+1) 不是完備的 / 不是最優(yōu)的 最壞情況下時間復雜性也很高O(bm),第2章 搜索技術(shù),32,深度有限搜索,深度優(yōu)先搜索的無邊界問題可以通過提供一個預先設(shè)定的深度限制l來解決 深度=l的節(jié)點當作無后繼節(jié)點看待 雖然解決了無限路徑問題，

16、但如果ll則深度優(yōu)先搜索也不是最優(yōu)的 時間復雜度O(bl) 空間復雜度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表示到達了有限深度而無解 failure表示一般的返回值無解 有時深度有限搜索基于問題本身的知識，如狀態(tài)空間的直徑即問題求解的最大步數(shù) 但對于大多數(shù)問題，不到問題解決時是無法知道求解步數(shù)的限制,第2章 搜索技術(shù),35,2.2.3 疊

18、代深入深度優(yōu)先搜索,如果每次改變限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深入深度優(yōu)先搜索算法 其深度限制依次為0/1/2這樣，當搜索到達最淺的目標節(jié)點深度時就可以發(fā)現(xiàn)目標節(jié)點 這種搜索結(jié)合了廣度優(yōu)先和深度優(yōu)先兩種算法的優(yōu)點(算法見p63) 分支因子有限時是完備的 / 路徑耗散是節(jié)點深度的非遞增函數(shù)時是最優(yōu)的 空間需求為O(bd) / 時間復雜性為O(bd),第2章 搜索技術(shù),36,狀態(tài)的生成,疊代深入搜索中因為多次重復搜索，因此部分狀態(tài)被多次生成，看起來很浪費 但是因為在分支因子比較平衡的搜索樹中，多數(shù)節(jié)點都在最底層(即葉子節(jié)點)，所以上層節(jié)點的多次生成影響不是很大 / 與廣度優(yōu)先搜索

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

20、losed表和未擴展的節(jié)點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,圖搜索算法的性能,由樹到圖：存在不同分支節(jié)點的合并 圖搜索算法與樹搜索算法比較：只是增加了對展開節(jié)點的判斷，因此由不同的待擴展節(jié)點排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍然同樹搜索算法 對于含很多重復狀態(tài)的問題，其搜索效率比樹搜索算法有效很多 討論參見p67,第2章 搜索技術(shù),41,例子：“農(nóng)夫過河”問題搜索,農(nóng)夫過河問題 用向量表示在河岸兩邊

22、的情況 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ù),42,“農(nóng)夫過河”廣度優(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)夫過河”深度優(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,只使用一個搜索分支 / 所擴展的第一個節(jié)點是最新節(jié)點,2.3 啟發(fā)式搜索策略2.3.1 貪婪最佳優(yōu)先搜索2.3.2 A*搜索2.3.3 啟發(fā)函數(shù)2.3.4 聯(lián)機搜索,第2章 搜索技術(shù),45,啟發(fā)式搜索通用算法,啟發(fā)式搜索也稱有信息搜索，其通用算法稱為最佳優(yōu)先搜索(Best-First-Search) 最佳優(yōu)先搜索基于評價函數(shù)擴展節(jié)點按照距離目標最短的評價值來擴展 并不是真正的最佳只是表現(xiàn)得最佳/近似最佳 算法的關(guān)鍵因素是啟發(fā)函數(shù)(Heuristic function)，記為f(n) / f(n)=從節(jié)點n到目標節(jié)點的最低耗散路徑的耗散估計值

25、 啟發(fā)函數(shù)引導搜索兩種方式貪婪最佳優(yōu)先搜索 / A*搜索(A*算法),第2章 搜索技術(shù),46,2.3.1 貪婪最佳優(yōu)先搜索,貪婪最佳優(yōu)先搜索的評價函數(shù)f(n)=h(n) 在貪婪最佳優(yōu)先搜索中總是選擇當前離目標最近(最小代價)的節(jié)點進行擴展(搜索) 局部最佳未必全局最佳不是最優(yōu)的(下例) 使用貪婪最佳優(yōu)先搜索算法搜索從Arad到首都的行車最短路線 Arad的下一站有3個城市S(253)/T(329)/ Z(374) 擴展Sibiu有3個城市F(176)/O(380) /R(193) 擴展Fagaras直接可到目的地 然而實際不是最優(yōu)的：SFB實際全長310 / SRVPB實際全長278，多了32

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

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

28、，則這個狀態(tài)空間搜索算法稱為可采納的 對于A*搜索來說，使用樹搜索算法(Tree-Search)，則它是可采納的 如果對啟發(fā)函數(shù)h(n)作一定限制，則使用圖搜索算法(Graph-Search)也是可采納的,第2章 搜索技術(shù),52,可采納的啟發(fā)函數(shù),算法的可采納性取決于啟發(fā)函數(shù)的可采納性 啟發(fā)函數(shù)h(n)是可采納的h(n)從來不會過高地估計到達目標的耗散值 此即h(n)滿足h(n)h*(n)，h*(n)是從當前節(jié)點n到達目標的最低耗散值 此即f(n)永遠不會高估經(jīng)過節(jié)點n的解的實際耗散f(n)f*(n)，所以是最優(yōu)解 如果h(n)是可采納的，那么使用Tree-Search的A*算法是可采納的(最

29、優(yōu)的) 自己嘗試證明，參考附錄證明過程,第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)路徑不是第一個生成的，可能因為有重復狀態(tài)而被丟棄 解決方案： 1)修改Graph-Search算法使得能夠進行比較，只丟棄耗散值大的路徑 2)保證到達任何重復狀態(tài)的最優(yōu)路徑總是第一條被追隨的路徑要求h(n)保持一致性(單調(diào)性) 算法請自

31、行給出,第2章 搜索技術(shù),55,h(n)的一致性(1),定義啟發(fā)函數(shù)的一致性如果對于每個節(jié)點n和通過任意行動a生成n的每個后繼節(jié)點n，從節(jié)點n到達目標節(jié)點的估計耗散值h(n)不大于從n到n的單步耗散與從n到目標節(jié)點的估計耗散值之和，則h(n)稱為一致的 此即h(n)c(n,n,a)+h(n) / 是三角不等式的某種形式 每個一致的啟發(fā)函數(shù)都是可采納的 證明要點：h(n)c(n,n,a)+h(n), h(n)c*(n,n,a)+h(n) 可得h(n)h*(n)h(n)h*(n) 目標節(jié)點h(T)=h*(T)=0回退可得任意節(jié)點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)的 附錄證明似乎沒有利用此條件 如果h(n)是一致的，那么沿著任何路徑的f(n)值是非遞減的(由一致性定義可得) f(n)耗散值沿著任何路徑都是非遞減的結(jié)論允許在狀態(tài)空間中畫出等值線(見下圖),第2章 搜索技術(shù),57,道路里程的等值線,第2章 搜索技術(shù),58,A*搜索節(jié)點的擴展,A*搜索由初始節(jié)點出發(fā)開始搜索，以同心帶狀增長f(n)耗散值的方式擴展節(jié)點 如果h(n)=0則為代價一致搜索(只按g(n)值排序)則同心帶為“圓型”，使用啟發(fā)函數(shù)

33、則同心帶向目標節(jié)點方向拉伸 如果C*是最優(yōu)解路徑的耗散值，則有以下結(jié)論： A*算法擴展所有f(n)C*的節(jié)點 A*算法在到達目標節(jié)點之前可能會擴展一些正好處于“目標等值線”上的節(jié)點 A*算法不擴展f(n)C*的節(jié)點(均被剪枝),第2章 搜索技術(shù),59,A*算法的性質(zhì)(1),A*算法是完備的如果解存在，就一定能找到 / 因為找到解只要有限步 A*算法是最優(yōu)的即可采納的(一個普遍采用的證明見附錄) A*算法對于任何給定的啟發(fā)函數(shù)都是效率最優(yōu)的 / 沒有任何其他算法擴展的節(jié)點少于A*算法 但是，A*算法對于多數(shù)問題來說，搜索空間處于目標等值線內(nèi)的節(jié)點數(shù)量是求解路徑長度的指數(shù)級,第2章 搜索技術(shù),60

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

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

36、于八數(shù)碼問題的常用候選： h1(n)=不在位棋子數(shù)這是一個可采納的啟發(fā)函數(shù)，因為要把“不在位”的棋子都移動到正確位置上，每個錯位的棋子至少要移動一次 / 所以有h1(n)h*(n) h2(n)=所有棋子到達其目標位置的距離和計算水平距離(曼哈頓距離) / 該函數(shù)也是可采納的，因為到達其目標位置至少要移動這些距離長度,第2章 搜索技術(shù),64,啟發(fā)函數(shù)精確度對算法性能的影響,刻畫啟發(fā)函數(shù)質(zhì)量的一個度量是有效分支因子b* b*是深度為d的一致搜索樹為了能夠包括N(生成的總節(jié)點數(shù))+1個節(jié)點所必需的分支因子 N+1=1+b*+(b*)2+(b*)d 例如：52個節(jié)點在第5層找到解，則b*=1.92 有

37、效分支因子可以根據(jù)問題實例發(fā)生變化，但是在足夠難的問題中是穩(wěn)定的 / 因此小規(guī)模實驗中測得b*值可以為啟發(fā)函數(shù)的總體有效性提供指導,第2章 搜索技術(shù),65,八數(shù)碼問題啟發(fā)函數(shù)的比較,良好設(shè)計的啟發(fā)函數(shù)使b*值接近1，允許對大規(guī)模的問題進行求解 啟發(fā)函數(shù)越接近于真實最優(yōu)解的值，則相應(yīng)的搜索算法效率越高 / 顯然此時有如果h1(n)h2(n)，則h2(n)優(yōu)于h1(n) (此時h2(n)信息量比h1(n)多) p85頁給出了八數(shù)碼問題的啟發(fā)函數(shù)h1/h2的比較數(shù)據(jù) “優(yōu)于”的含義使用h2的算法不會比使用h1的算法擴展更多的節(jié)點,第2章 搜索技術(shù),66,如何設(shè)計啟發(fā)函數(shù),A*搜索的關(guān)鍵如何找到是一個

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