人工智能原理77

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

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

3、以求解，而是一步一步的探索第2章 搜索技術(shù)6 數(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ù)7 可解的：在每個連通部分，每個弧代表一個運算符，將狀態(tài)改變 / 如果從代表初始狀態(tài)的節(jié)點出發(fā)，有一條路徑通向目標狀態(tài)，則稱此目標狀態(tài)所代表的問題在當前初始狀態(tài)下是可解的 搜索空間：在解題過程中達到過的所有狀態(tài)的集合，稱為搜索空間 不同于狀態(tài)空間，搜索空

4、間只是其中一部分 狀態(tài)空間和搜索空間都屬于過程性知識表示第2章 搜索技術(shù)8 玩具問題 八數(shù)碼游戲(九宮圖) 河內(nèi)塔 八皇后問題 真空吸塵器世界 現(xiàn)實問題 旅行商問題 超大規(guī)模集成電路的布局 自動裝配排序 / 蛋白質(zhì)設(shè)計 互聯(lián)網(wǎng)搜索第2章 搜索技術(shù)9 八數(shù)碼游戲：1-8數(shù)字(棋子)/9個方格(棋盤格)/1個空格 可用如下形式的規(guī)則來表示數(shù)字通過空格進行移動： 共24條規(guī)則=4角*2+4邊*3+1中間*4 搜索順序舉例：(1)優(yōu)先移動行數(shù)小的棋子(數(shù)字)(2)同一行中優(yōu)先移動列數(shù)大的棋子 約束規(guī)則：不使離開既定位置的數(shù)字數(shù)增加第2章 搜索技術(shù)10第2章 搜索技術(shù) Begin * * * * * *

5、 End *1524367812453678152436781524736815243678124536781245367815432678152438671234567841253678154326781524386712345678412536784126537813542678既定位置=終態(tài)11 初始狀態(tài) 初始狀態(tài)向量規(guī)定向量中各分量對應(yīng)的位置，各位置上的初始數(shù)字 后繼函數(shù) 移動規(guī)則按照某條規(guī)則移動數(shù)字，將得到的新向量 目標測試 新向量是否是目標狀態(tài)(也是向量形式) 路徑耗散函數(shù) 每次移動代價為1第2章 搜索技術(shù)12 河內(nèi)塔問題：n個大小不等的圓盤從一個柱子移到另一個柱子，共有3個柱子(

6、n階河內(nèi)塔問題) 約束：從第1根柱子移動到第3根柱子上去，利用第2根柱子 / 每次移動1個盤子，且移動過程必須是小盤落大盤 描述：設(shè)每個狀態(tài)為(a1, a2, a3, , an), ai=1, 2, 3表示第i個盤子在第1/2/3根柱子上第2章 搜索技術(shù)13 遞歸定義：(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章

7、搜索技術(shù)14第2章 搜索技術(shù) (3,3,2) (2,3,2) (1,3,2) (2,1,2) (2,3,2) (1,1,2) (3,1,2) (3,2,2) (2,2,2) (1,1,1) (3,1,1) (3,2,1) (2,2,1) (1,2,1) (2,2,3) (1,2,3) (1,3,3)(3,3,3) (2,3,3) (2,1,3) (1,1,3) (3,3,1)(1,3,1) (2,1,1) (2,3,1) (3,1) (2,1)(3,2) (2,3)(2,2)(1,2) (1,3)(3,3)(1) (1,1)(2)(3)15 初始狀態(tài) 初始狀態(tài)向量規(guī)定向量中各分量對應(yīng)所有n個盤

8、子，位置上數(shù)字代表3個柱子之一 后繼函數(shù) 移動規(guī)則依據(jù)約束條件給出的各狀態(tài)的后繼狀態(tài) 目標測試 新向量是否是目標狀態(tài)(也是向量形式) 路徑耗散函數(shù) 每移動一個盤子的代價為1第2章 搜索技術(shù)16 求最短路徑問題：狀態(tài)圖中從三角形1個頂點走到另一個頂點 結(jié)論：(1)如果初始狀態(tài)或目標狀態(tài)在三角形頂點上，則最短路徑唯一；(2)對于任意2個狀態(tài)，最短求解路徑至多為2條。(中國某大學(xué)研究生證明) 求解過程對狀態(tài)空間的搜索以2階河內(nèi)塔為例第2章 搜索技術(shù)17第2章 搜索技術(shù)1,12,13,11,12,31,13,23,32,12,2 3,12,21,32,13,32,33,31,21,12,21,23,1

9、3,3 2,23,21,31,118 求解問題的過程使用搜索樹形式 每個狀態(tài)對應(yīng) 根節(jié)點對應(yīng)于初始狀態(tài) 每次從搜索樹的上層節(jié)點出發(fā)，根據(jù)約束條件進入下一個可能的狀態(tài)，即展開新的一層樹節(jié)點節(jié)點擴展 節(jié)點展開的順序即代表了不同的搜索策略 當展開的節(jié)點為目標狀態(tài)時，就找到了問題的一個解第2章 搜索技術(shù)19 研究搜索過程考慮的若干問題(1)有限搜索還是無限搜索(2)已知目標還是未知目標(3)目標或目標+路徑(4)有約束還是無約束(5)數(shù)據(jù)驅(qū)動(向前搜索)還是目標驅(qū)動(6)單向搜索還是雙向搜索第2章 搜索技術(shù)20 搜索過程的分類：狀態(tài)空間搜索(圖搜索方式)，問題空間搜索(層次方法)，博弈空間搜索 無信息

10、搜索與啟發(fā)式搜索 啟發(fā)式：利用中間信息改進控制策略 啟發(fā)式：(1)任何有助于找到問題的解，但不能保證找到解的方法是啟發(fā)式方法 (2)有助于加速求解過程和找到較優(yōu)解的方法是啟發(fā)式方法 啟發(fā)式也叫啟發(fā)函數(shù)第2章 搜索技術(shù)21 4種途徑來評價搜索算法的性能 完備性當問題有解時，算法是否保證找到一個解 最優(yōu)性算法是否能找到一個最優(yōu)解(路徑耗散函數(shù)值最小的路徑) 時間復(fù)雜性找到一個解需要花費多少時間 空間復(fù)雜性在搜索過程中需要占用多少內(nèi)存第2章 搜索技術(shù)22 時空復(fù)雜性的量度由狀態(tài)空間圖的大小來衡量 / 相關(guān)度量如下： 分支因子 b (每次展開的平均節(jié)點個數(shù)) 目標節(jié)點的深度 d 路徑的最大長度 m 搜

11、索深度限制 l 搜索耗散第2章 搜索技術(shù)232.2 無信息搜索策略2.2.1 廣度優(yōu)先搜索2.2.2 深度優(yōu)先搜索和深度有限搜索2.2.3 疊代深入深度優(yōu)先搜索2.2.4 無信息搜索策略性能比較2.2.5 圖搜索算法第2章 搜索技術(shù)24 無信息搜索也稱盲目搜索：沒有任何附加信息，只有生成后繼和區(qū)分目標與非目標狀態(tài) 有5種盲目搜索策略 廣度優(yōu)先搜索 代價一致搜索 深度優(yōu)先搜索 深度有限搜索 迭代深入深度優(yōu)先搜索第2章 搜索技術(shù)25 廣度優(yōu)先搜索過程： 首先擴展根節(jié)點 接著擴展根節(jié)點的所有后繼節(jié)點 然后再擴展后繼節(jié)點的后繼，依此類推 在下一層任何節(jié)點擴展之前搜索樹上的本層深度的所有節(jié)點都已經(jīng)被擴展

12、 廣度優(yōu)先搜索可以調(diào)用樹搜索算法(Tree-Search)實現(xiàn) 其參數(shù)fringe(邊緣/擴展分支)為先進先出隊列FIFO第2章 搜索技術(shù)26function Tree-Search(problem,fringe) return solution /failure(initial fringe=empty, mode=FIFO)fringeInsert(Make-Node(Initial-Stateproblem),fringe)do while(1)if fringe=Empty then return failurenodeRemove-First(fringe)if Statenode=

13、Goal then return Solution(node)fringeInsert-All(Expend(node,problem), fringe)第2章 搜索技術(shù)27 關(guān)鍵在于如何擴展節(jié)點function Expend(node,problem) return set of nodessuccessorsthe empty setfor each in Successor-Findproblem (Statenode) dosnew Node / StatesresultParent-Nodes=node / Actions=actionPath-Costs=Path-Costnode

14、+Step-Costnode, action,sDepthsDepthnode+1add s to successorsreturn successors第2章 搜索技術(shù)28 在上述算法中，廣度優(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ù)29 深度優(yōu)先搜索過程： 總是擴展搜索樹的當前擴展分支(邊緣)中最深的節(jié)點 搜索直接伸展到搜索樹的最

15、深層，直到那里的節(jié)點沒有后繼節(jié)點 那些沒有后繼節(jié)點的節(jié)點擴展完畢就從邊緣中去掉 然后搜索算法回退下一個還有未擴展后繼節(jié)點的上層節(jié)點繼續(xù)擴展 搜索算法參見深度有限搜索算法(l=)第2章 搜索技術(shù)30 深度優(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)的 最壞情況下時間復(fù)雜性也很高O(bm)第2章 搜索技術(shù)31 深度優(yōu)先搜索的無邊界問題可以通過提供一個預(yù)先設(shè)定的深度限制l

16、來解決 深度=l的節(jié)點當作無后繼節(jié)點看待 雖然解決了無限路徑問題，但如果ll則深度優(yōu)先搜索也不是最優(yōu)的 時間復(fù)雜度O(bl) 空間復(fù)雜度O(bl) 深度優(yōu)先搜索可看作是一種特例即l=第2章 搜索技術(shù)32function Depth-Limited-Search(problem,fringe,limit) return solution/failure/cutofffringeInsert(Make-Node(Initial-Stateproblem),fringe)(mode=LIFO)do while(1)if fringe=Empty then return failurenodeRemo

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

18、深度，多次調(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) / 時間復(fù)雜性為O(bd)第2章 搜索技術(shù)35 疊代深入搜索中因為多次重復(fù)搜索，因此部分狀態(tài)被多次生成，看起來很浪費 但是因為在分支因子比較平衡的搜索樹中，多數(shù)節(jié)點都在最底層(即葉子節(jié)點)，所以上層節(jié)點的多次生成影響不是很大 / 與廣度優(yōu)先搜索相比，效率還是更高 一般來講，當搜索空間很大而解的深

19、度未知時，疊代深入搜索是一個首選的無信息搜索方法第2章 搜索技術(shù)36第2章 搜索技術(shù)評價標準廣度優(yōu)先 代價一致 深度優(yōu)先 深度有限 疊代深入 雙向搜索是否完備時間空間是否最優(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兩個方向上都使用廣度優(yōu)先搜索37 已經(jīng)看到搜

20、索過程中會出現(xiàn)重復(fù)的狀態(tài)擴展，應(yīng)該避免 / 如果算法不檢測重復(fù)狀態(tài)的話，有可能使一個本來可解的問題變?yōu)椴豢山?檢測就是把要擴展的節(jié)點與已擴展的節(jié)點進行比較，把遇到的相同狀態(tài)去掉 所以要記錄已經(jīng)擴展的節(jié)點引入兩個表存儲已擴展的節(jié)點closed表和未擴展的節(jié)點open表(即前述fringe) 新算法稱為圖搜索算法第2章 搜索技術(shù)38第2章 搜索技術(shù)function Graph-Search(problem,fringe) return solution or failureclosedempty setfringeInsert(Make-Node(Initial-Stateproblem),fri

21、nge)do while(1)if fringe=Empty then return failurenodeRemove-First(fringe)if Statenode=Goal then return Solution(node)if Statenode !CLOSED then add Statenode to closed fringeInsert-All(Expend(node,problem),fringe)39 由樹到圖：存在不同分支節(jié)點的合并 圖搜索算法與樹搜索算法比較：只是增加了對展開節(jié)點的判斷，因此由不同的待擴展節(jié)點排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先)的性能仍

22、然同樹搜索算法 對于含很多重復(fù)狀態(tài)的問題，其搜索效率比樹搜索算法有效很多 討論參見p67第2章 搜索技術(shù)40 農(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, *)

23、 / 8 (1, *, *, 1)(0, *, *, 0) *=0/1表示任意岸邊但必須相同第2章 搜索技術(shù)41第2章 搜索技術(shù)0 0 0 01 0 1 01 1 0 00 0 1 01 1 1 00 1 0 01 1 0 10 1 0 11 1 1 11 0 1 10 0 0 1closed表所用規(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第2章 搜索技術(shù)0 0 0 01 0 1 01 1 0 00 0 1 01 1 1 00 1 0 01 1 0 10 1 0 11 1 1 1closed表

24、所用規(guī)則序列 3/5/2/7/4所用規(guī)則序列 3/5/2/7/4/5/3只使用一個搜索分支 / 所擴展的第一個節(jié)點是最新節(jié)點432.3 啟發(fā)式搜索策略2.3.1 貪婪最佳優(yōu)先搜索2.3.2 A*搜索2.3.3 啟發(fā)函數(shù)2.3.4 聯(lián)機搜索第2章 搜索技術(shù)44 啟發(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ù)引導(dǎo)搜索兩種方式貪婪最佳優(yōu)先搜索 / A*搜索(A*算法)第2章 搜索技術(shù)45 貪婪最佳優(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，多了32km第2章 搜索技術(shù)46第2章 搜索技

26、術(shù)47第2章 搜索技術(shù) 尋找從Arad到首都的行車最短路線 評價函數(shù)f(n)=h(n) 直線距離啟發(fā)式hSLD 與實際距離相關(guān)但需另外給出，見下表Arad366Mehadia241Bucharest0Neamt234Craiova160Oradea380Dobreta242Pitesti100Eforie161Rimnicu Vilcea193Fagaras176Sibiu253Giurgiu77Timisoara329Hirsova151Urziceni80Iasi226Vaslui199Lugoj244Zerind37448第2章 搜索技術(shù) 啟發(fā)函數(shù)h(n)最小化會對錯誤的起點比較敏感 例

27、子：地圖中Iasi到Fagaras的行車路線(走入死路的可能) 需要仔細檢查重復(fù)狀態(tài)，否則可能永遠找不到解 與深度優(yōu)先搜索類似，非最優(yōu)、非完備 最壞情況下時空復(fù)雜度都是O(bm) / m為最大搜索深度49 A*搜索的評價函數(shù)為f(n)=g(h)+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ù)50

28、 定義搜索算法的可采納性(可采用性) (Hart, Nilsson, Raphel, 1968) 如果狀態(tài)空間中的目標狀態(tài)存在，并且從初始狀態(tài)到目標狀態(tài)有一條通路，而搜索算法一定能在有限步內(nèi)終止并找到一個最優(yōu)解(代價最低)，則這個狀態(tài)空間搜索算法稱為可采納的 對于A*搜索來說，使用樹搜索算法(Tree-Search)，則它是可采納的 如果對啟發(fā)函數(shù)h(n)作一定限制，則使用圖搜索算法(Graph-Search)也是可采納的第2章 搜索技術(shù)51 算法的可采納性取決于啟發(fā)函數(shù)的可采納性 啟發(fā)函數(shù)h(n)是可采納的h(n)從來不會過高地估計到達目標的耗散值 此即h(n)滿足h(n)h*(n)，h*(

29、n)是從當前節(jié)點n到達目標的最低耗散值 此即f(n)永遠不會高估經(jīng)過節(jié)點n的解的實際耗散f(n)f*(n)，所以是最優(yōu)解 如果h(n)是可采納的，那么使用Tree-Search的A*算法是可采納的(最優(yōu)的) 自己嘗試證明，參考附錄證明過程第2章 搜索技術(shù)52function Tree-Search(problem,fringe) return solution or failureSelect h(n)Make-Node(Initial-Stateproblem & get their f(n)Insert(nodes, fringe)Sort(fringe, f(n)do while

30、(1)if fringe=Empty then return failurenodeRemove-First(fringe)if Statenode=Goal then return Solution(node)Expend(node, problem) & get their f(n)Insert(nodes, fringe)Sort(fringe, f(n)第2章 搜索技術(shù)53 如果A*搜索使用圖搜索算法，則A*必然返回最優(yōu)解的結(jié)論就不成立原因是如果最優(yōu)路徑不是第一個生成的，可能因為有重復(fù)狀態(tài)而被丟棄 解決方案： 1)修改Graph-Search算法使得能夠進行比較，只丟棄耗散值大

31、的路徑 2)保證到達任何重復(fù)狀態(tài)的最優(yōu)路徑總是第一條被追隨的路徑要求h(n)保持一致性(單調(diào)性) 算法請自行給出第2章 搜索技術(shù)54 定義啟發(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回退可得

32、任意節(jié)點h(n)h*(n)第2章 搜索技術(shù)55 通常我們選擇的啟發(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ù)56第2章 搜索技術(shù)ZTLMDCGUONIVHE420A380BFPRS40057 A*搜索由初始節(jié)點出發(fā)開始搜索，以同心帶狀增長f(n)耗散值的方式擴展節(jié)點 如果h(n)=0則為代價

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

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

35、 MA*(存儲限制A*)和SMA*(簡化的MA*)充分利用可用的內(nèi)存 SMA*的思想當內(nèi)存放滿時，就丟棄最差的一個子節(jié)點而加入新節(jié)點 如果任何最優(yōu)解是可到達的，則SMA*是最優(yōu)的第2章 搜索技術(shù)61 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ù)62 啟發(fā)函數(shù)的核心決不高估到達目標的步數(shù) / 對于八數(shù)碼問題的常用候選： h

36、1(n)=不在位棋子數(shù)這是一個可采納的啟發(fā)函數(shù)，因為要把“不在位”的棋子都移動到正確位置上，每個錯位的棋子至少要移動一次 / 所以有h1(n)h*(n) h2(n)=所有棋子到達其目標位置的距離和計算水平距離(曼哈頓距離) / 該函數(shù)也是可采納的，因為到達其目標位置至少要移動這些距離長度第2章 搜索技術(shù)63 刻畫啟發(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 有效分支因子可以根據(jù)問題實例發(fā)生變化，但是在足夠難的問題中是穩(wěn)定的

37、 / 因此小規(guī)模實驗中測得b*值可以為啟發(fā)函數(shù)的總體有效性提供指導(dǎo)第2章 搜索技術(shù)64 良好設(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ù)65 A*搜索的關(guān)鍵如何找到是一個合適的啟發(fā)函數(shù) 尋找策略： 從松弛問題中獲得松弛問題的最優(yōu)解的耗散是原問題的一個可采納的啟發(fā)函數(shù) 從給定問題子問題的

38、解耗散中獲得建立模式數(shù)據(jù)庫，存儲每個可能子問題實例 從經(jīng)驗中學(xué)習使用歸納學(xué)習算法，使用相關(guān)狀態(tài)特征來預(yù)測第2章 搜索技術(shù)66 松弛問題降低了行動限制的問題 松弛問題的最優(yōu)解耗散是原問題的一個可采納的啟發(fā)函數(shù) 根據(jù)定義，原始問題的最優(yōu)解也是該松弛問題的解，其耗散不低于松弛問題的最優(yōu)解 松弛問題的最優(yōu)解是確切耗散，一定滿足三角不等式，因而是單調(diào)的，所以作為啟發(fā)函數(shù)一定是可采納的 如果問題定義通過形式化語言描述，則自動地構(gòu)造其松弛問題是可能的 / 例子八數(shù)碼問題第2章 搜索技術(shù)67 子問題的最優(yōu)解耗散是完整問題的耗散下界 建立模式數(shù)據(jù)庫存儲每個可能子問題實例的精確解耗散 從目標狀態(tài)向后搜索并記錄下每個子問題模式的耗散，存儲于數(shù)據(jù)庫 搜索中遇到的每個完整狀態(tài)通過在數(shù)據(jù)庫中查找出相應(yīng)子問題布局而設(shè)計出一個可采納的啟發(fā)函數(shù) 對于八數(shù)碼問題，這樣的啟發(fā)函數(shù)要比曼哈頓距離精確得多(具體數(shù)值見p87