【正文】 100 Eforie 161 Rimnicu Vilcea 193 Fagaras 176 Sibiu 253 Giurgiu 77 Timisoara 329 Hirsova 151 Urziceni 80 Iasi 226 Vaslui 199 Lugoj 244 Zerind 374 48 問題實例 (2) 第 2章 搜索技術(shù) ? 啟發(fā)函數(shù) h(n)最小化會對錯誤的起點比較敏感 ? 例子：地圖中 Iasi到 Fagaras的行車路線 (走入死路的可能 ) ? 需要仔細(xì)檢查重復(fù)狀態(tài)，否則可能永遠(yuǎn)找不到解 ? 與深度優(yōu)先搜索類似，非最優(yōu)、非完備 ? 最壞情況下時空復(fù)雜度都是 O(bm) / m為最大搜索深度 49 A*搜索 ? A*搜索的評價函數(shù)為 f(n)=g(h)+h(n) ? g(n)是從初始節(jié)點到該節(jié)點 n的路徑耗散 ? h(n)是從節(jié)點 n到目標(biāo)節(jié)點的最低耗散路徑的估計 耗散值，稱為啟發(fā)式或啟發(fā)函數(shù) ? 因此， f(n)=經(jīng)過節(jié)點 n、具有最低耗散值的解的估計耗散 ? 找到 g(n)+h(n)值最小的節(jié)點當(dāng)然是合理的 (參見書中 p79圖 ) ? 若啟發(fā)函數(shù) h(n)滿足一定條件，則 A*搜索是完備的和最優(yōu)的 第 2章 搜索技術(shù) 50 搜索算法的可采納性 ? [定義 ]搜索算法的可采納性 (可采用性 ) (Hart, Nilsson, Raphel, 1968) ? 如果狀態(tài)空間中的目標(biāo)狀態(tài)存在，并且從初始狀態(tài)到目標(biāo)狀態(tài)有一條通路，而搜索算法一定能在有限步內(nèi)終止并找到一個最優(yōu)解(代價最低 )，則這個狀態(tài)空間搜索算法稱為可采納的 ? 對于 A*搜索來說，使用樹搜索算法 (TreeSearch)，則它是可采納的 ? 如果對啟發(fā)函數(shù) h(n)作一定限制，則使用圖搜索算法 (GraphSearch)也是可采納的 第 2章 搜索技術(shù) 51 可采納的啟發(fā)函數(shù) ? 算法的可采納性取決于啟發(fā)函數(shù)的可采納性 ? 啟發(fā)函數(shù) h(n)是可采納的 —h(n)從來不會過高地估計到達(dá)目標(biāo)的耗散值 ? 此即 —h(n)滿足 h(n)≤h*(n)， h*(n)是從當(dāng)前節(jié)點 n到達(dá)目標(biāo)的最低耗散值 ? 此即 —f(n)永遠(yuǎn)不會高估經(jīng)過節(jié)點 n的解的實際耗散 —f(n)≤f*(n)，所以是最優(yōu)解 ? 如果 h(n)是可采納的，那么使用 TreeSearch的 A*算法是可采納的 (最優(yōu)的 ) ? 自己嘗試證明，參考附錄證明過程 第 2章 搜索技術(shù) 52 A*搜索的 TreeSearch算法 function TreeSearch(problem,fringe) return solution or failure Select h(n) MakeNode(InitialState[problem] get their f(n) Insert(nodes, fringe) Sort(fringe, f(n)) do while(1) if fringe=Empty then return failure node← RemoveFirst(fringe) if State[node]=Goal then return Solution(node) Expend(node, problem) get their f(n) Insert(nodes, fringe) Sort(fringe, f(n)) 第 2章 搜索技術(shù) 53 A*搜索的 GraphSearch算法 ? 如果 A*搜索使用圖搜索算法，則 A*必然返回最優(yōu)解的結(jié)論就不成立 —原因是如果最優(yōu)路徑不是第一個生成的，可能因為有重復(fù)狀態(tài)而被丟棄 ? 解決方案： ? 1)修改 GraphSearch算法使得能夠進行比較，只丟棄耗散值大的路徑 ? 2)保證到達(dá)任何重復(fù)狀態(tài)的最優(yōu)路徑總是第一條被追隨的路徑 —要求 h(n)保持一致性 (單調(diào)性 ) ? 算法 —請自行給出 第 2章 搜索技術(shù) 54 h(n)的一致性 (1) ? [定義 ]啟發(fā)函數(shù)的一致性 —如果對于每個節(jié)點 n和通過任意行動 a生成 n的每個后繼節(jié)點 n’，從節(jié)點 n到達(dá)目標(biāo)節(jié)點的估計耗散值 h(n)不大于從 n到n’的單步耗散與從 n’到目標(biāo)節(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’) ? 目標(biāo)節(jié)點 h(T)=h*(T)=0回退可得任意節(jié)點 h(n)≤h*(n) 第 2章 搜索技術(shù) 55 h(n)的一致性 (2) ? 通常我們選擇的啟發(fā)函數(shù) h(n)都 滿足一致性要求 (因而必定是可采納的 ) ? 關(guān)于一致性的結(jié)論： ? 如果 h(n)是一致的，那么使用 GraphSearch的 A*算法是最優(yōu)的 ? 附錄證明似乎沒有利用此條件 ? 如果 h(n)是一致的，那么沿著任何路徑的f(n)值是非遞減的 (由一致性定義可得 ) ? f(n)耗散值沿著任何路徑都是非遞減的結(jié)論允許在狀態(tài)空間中畫出等值線 (見下圖 ) 第 2章 搜索技術(shù) 56 道路里程的等值線 第 2章 搜索技術(shù) Z T L M D C G U O N I V H E 420 A 380 B F P R S 400 57 A*搜索節(jié)點的擴展 ? A*搜索由初始節(jié)點出發(fā)開始搜索，以同心帶狀增長 f(n)耗散值的方式擴展節(jié)點 ? 如果 h(n)=0則為代價一致搜索 (只按 g(n)值排序 )則同心帶為“圓型”，使用啟發(fā)函數(shù)則同心帶向目標(biāo)節(jié)點方向拉伸 ? 如果 C*是最優(yōu)解路徑的耗散值，則有以下結(jié)論： ? A*算法擴展所有 f(n)≤C*的節(jié)點 ? A*算法在到達(dá)目標(biāo)節(jié)點之前可能會擴展一些正好處于“目標(biāo)等值線 ”上的節(jié)點 ? A*算法不擴展 f(n)C*的節(jié)點 (均被剪枝 ) 第 2章 搜索技術(shù) 58 A*算法的性質(zhì) (1) ? A*算法是完備的 —如果解存在，就一定能找到 / 因為找到解只要有限步 ? A*算法是最優(yōu)的 —即可采納的 (一個普遍采用的證明見附錄 ) ? A*算法對于任何給定的啟發(fā)函數(shù)都是效率最優(yōu)的 / 沒有任何其他算法擴展的節(jié)點少于 A*算法 ? 但是， A*算法對于多數(shù)問題來說，搜索空間處于目標(biāo)等值線內(nèi)的 節(jié)點數(shù)量 是 求解路徑長度的指數(shù)級 第 2章 搜索技術(shù) 59 A*算法的性質(zhì) (2) ? 如果要求不以指數(shù)級增長，則啟發(fā)函數(shù)需要滿足條件 ? 對于幾乎所有的啟發(fā)函數(shù)來說，偏差至少都是與路徑耗散成正比的，而不是路徑耗散的對數(shù) / 所以，在實際應(yīng)用中，往往不是堅持找到最優(yōu)解，而是采用以下兩種方式： ? 使用 A*算法的變種算法快速找到非最優(yōu)解 ? 設(shè)計準(zhǔn)確而非嚴(yán)格可采納的啟發(fā)函數(shù) 第 2章 搜索技術(shù) ))(*(log|)(*)(| nhOnhnh ??60 A*算法在空間方面的改進 ? A*算法在內(nèi)存中保留所有生成的節(jié)點，消耗極大 —因而對于許多大規(guī)模問題時不實用的 ? A*算法要減少對內(nèi)存的需求 —改進 ? 遞歸最佳優(yōu)先搜索 RBFS—模仿標(biāo)準(zhǔn)的最佳優(yōu)先搜索的遞歸算法，只是用線性存儲空間 ? 如果 h(n)是可采納的，則 RBFS最優(yōu) ? MA*(存儲限制 A*)和 SMA*(簡化的 MA*)—充分利用可用的內(nèi)存 ? SMA*的思想 —當(dāng)內(nèi)存放滿時，就丟棄最差的一個子節(jié)點而加入新節(jié)點 ? 如果任何最優(yōu)解是可到達(dá)的，則 SMA*是最優(yōu)的 第 2章 搜索技術(shù) 61 啟發(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ù)322≈ *1010 ? 實際可到達(dá)的不同狀態(tài)個數(shù) 9!/2=181440 第 2章 搜索技術(shù) 62 八數(shù)碼問題的啟發(fā)函數(shù) ? 啟