【正文】 個可采納的啟發(fā)函數，因為要把 “不在位”的棋子都移動到正確位置上，每個錯位的棋子至少要移動一次 / 所以有 h1(n)≤h*(n) ? h2(n)=所有棋子到達其目標位置的距離和 —計算水平距離 (曼哈頓距離 ) / 該函數也是可采納的，因為到達其目標位置至少要移動這些距離長度 第 2章 搜索技術 63 啟發(fā)函數精確度對算法性能的影響 ? 刻畫啟發(fā)函數質量的一個度量是有效分支因子b* ? b*是深度為 d的一致搜索樹為了能夠包括 N(生成的總節(jié)點數 )+1個節(jié)點所必需的分支因子 ? N+1=1+b*+(b*)2+……+(b*) d ? 例如： 52個節(jié)點在第 5層找到解，則 b*= ? 有效分支因子可以根據問題實例發(fā)生變化，但是在足夠難的問題中是穩(wěn)定的 / 因此小規(guī)模實驗中測得 b*值可以為啟發(fā)函數的總體有效性提供指導 第 2章 搜索技術 64 八數碼問題啟發(fā)函數的比較 ? 良好設計的啟發(fā)函數使 b*值接近 1，允許對大規(guī)模的問題進行求解 ? 啟發(fā)函數越接近于真實最優(yōu)解的值，則相應的搜索算法效率越高 / 顯然此時有 —如果 h1(n)≤ h2(n)，則 h2(n)優(yōu)于 h1(n) (此時 h2(n)信息量比 h1(n)多 ) ? p85頁給出了八數碼問題的啟發(fā)函數 h1/h2的比較數據 ? “優(yōu)于”的含義 —使用 h2的算法不會比使用 h1的算法擴展更多的節(jié)點 第 2章 搜索技術 65 如何設計啟 發(fā)函數 ? A*搜索的關鍵如何找到是一個合適的啟發(fā)函數 ? 尋找策略： ? 從松弛問題中獲得 —松弛問題的最優(yōu)解的耗散是原問題的一個可采納的啟發(fā)函數 ? 從給定問題子問題的解耗散中獲得 —建立模式數據庫，存儲每個可能子問題實例 ? 從經驗中學習 —使用歸納學習算法，使用相關狀態(tài)特征來預測 第 2章 搜索技術 66 松弛問題最優(yōu)解作為啟發(fā)函數 ? 松弛問題 — 降低了行動限制的問題 ? 松弛問題的最優(yōu)解耗散是原問題的一個可采納的啟發(fā)函數 ? 根據定義，原始問題的最優(yōu)解也是該松弛問題的解，其耗散不低于松弛問題的最優(yōu)解 ? 松弛問題的最優(yōu)解是確切耗散，一定滿足三角不等式，因而是單調的，所以作為啟發(fā)函數一定是可采納的 ? 如果問題定義通過形式化語言描述，則自動地構造其松弛問題是可能的 / 例子 —八數碼問題 第 2章 搜索技術 67 子問題的解耗散作為啟發(fā)函數 ? 子問題的最優(yōu)解耗散是完整問題的耗散下界 ? 建立模式數據庫 — 存儲每個可能子問題實例的精確解耗散 ? 從目標狀態(tài)向后搜索并記錄下每個子問題模式的耗散，存儲于數據庫 ? 搜索中遇到的每個完整狀態(tài)通過在數據庫中查找出相應子問題布局而設計出一個可采納的啟發(fā)函數 ? 對于八數碼問題，這樣的啟發(fā)函數要比曼哈頓距離精確得多 (具體數值見 p87) 第 2章 搜索技術 68 從經驗中學習啟發(fā)函數 ? 從實例中學習 —每個實例包含了解路徑上的各狀態(tài)及其到達解的耗散 ? 每個最優(yōu)解實例提供了可學習 h(n)的實例 ? 收集實際解消耗的統計數據，以此產生可預測其他狀態(tài)解消耗的啟發(fā)函數 h(n) ? 使用歸納學習方法 ? 八數碼問題的討論 (p87) 第 2章 搜索技術 69 A*搜索的例子 (1) ? 積木塊移動游戲 ? 初始狀態(tài)： ? 目標狀態(tài)： ? 移動規(guī)則： (1)積木移到空格 /代價 =1 (2)積木跨越 1個積木移到空格 /代價 =1 (3)積木跨越 2個積木移到空格 /代價 =2 B B B W W W □第 2章 搜索技術 W W W □ BBB70 A*搜索的例子 (2) ? A*搜索： 至少代價 =每個 W左邊 B的個數 (B到W右邊的必須跨越 W的代價 ) ? 令 h(n)=至少代價，則 h(n)≤ h*(n) ? 且滿足單調性 h(ni) ≤ h(ni+1)+g(ni+1)g(ni) (實際是 =) ? g(n)=到達當前狀態(tài)實際付出的代價 ? 搜索過程中括號里的數字分別為 h/g值 第 2章 搜索技術 71 A*搜索的例子 (3) 第 2章 搜索技術 ( 9 , 0 ) ( 9 , 1 ) ( 9 , 1 ) ( 9 , 2 ) ( 7 , 3 ) ( 9 , 2 ) ( 9 , 3 ) ( 7 , 4 ) ( 6 , 5 ) ( 6 , 6 ) ( 5 , 7 ) ( 3 , 1 0 ) ( 5 , 8 ) ( 2 , 1 1 ) ( 1 , 1 3 ) ( 1 , 1 4 ) ( 0 , 1 5 )B B B W W □ W BBBW □ WWB B B W W W □BBB □ W W WBB □ W W B W BBBW □ WW BBB □ W W WBBW □ W B W B □ W B W B W BW □ B W B W□ W B B W B WW □ B B W B WW W B B □ BWW W B B W B □ WWB □ W B B WW □ B W B BW W W □ BBB72 聯機搜索 ? 脫機搜索 —不需感知，只要計算 ? 例子：簡單游戲，通過有限的規(guī)則作用即可推算出目標所在 ? 聯機搜索 —必須通過行動 /觀察與計算交叉進行才能決定下一步搜索 ? 兩種情況：環(huán)境未知 —只有行動才能得知如何正確走向目標 / 環(huán)境空間過大 —雖然理論上已知，但是實際不可計算 (如棋類比賽 ) 第 2章 搜索技術 73 例子：迷宮問題 第 2章 搜索技術 G S 3 2 1 1 2 3 ? 如左圖所示，聯機搜索問題只能通過行動來解決，因為障礙是不能事先預知的 ? 智能體初始位置在 S，其已知信息為： ? ACTION(s)—狀態(tài) S下的行動列表 ? c(s,a,s’)— 通過行動 a從 s狀態(tài)到達 s’狀態(tài) ? GoalTest(s) / G目標位置 ? 智能體可使用曼哈頓距離啟發(fā)式 74 競爭率 (1) ? 代價 —智能體實際走過的路經總耗散 ? 理想耗散 —沒有無用搜索步驟的走過路徑耗散 /也就是應該走過路徑的耗散 ? 競爭率 —代價 247。 理想耗散 ? 該值要盡可能地小 第 2章 搜索技術 75 競爭率 (2) ? 影響競爭率的因素，使其無窮大 ? 行動不可逆 —進入一個不可到達目標的狀態(tài)又不可回溯 ? 沒有算法能夠在所有的狀態(tài)空間中避免死路 (p98圖 ) ? 因此，通常需要假設狀態(tài)空間是可安全探索的 —具有可逆的狀態(tài)空間 / 從每個可達狀態(tài)出發(fā)都有可達的目標狀態(tài) ? 不過，在可逆狀態(tài)空間中，因為對手的存在，也會出現無界競爭率的情況 (p98圖 ) 第 2章 搜索技術 76 聯機搜索智能體 ? 聯機搜索智能體需要行動和感知，然后擴展當前狀態(tài)的環(huán)境地圖 ? 區(qū)別：聯機 —規(guī)劃與行動交叉 / 脫機 —只要規(guī)劃 ? 例子： A*搜索在不同子空間節(jié)點的跳躍式擴展，模擬而非實際行動 / 聯機算法只擴展目前實際占據的節(jié)點 —采用深度優(yōu)先搜索 ? 聯機搜索必須維護一個回溯表 第 2章 搜索技術 77 演講完畢，謝謝觀看！