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