【文章內(nèi)容簡(jiǎn)介】 第 2章 搜索技術(shù) 34 疊代深入深度優(yōu)先搜索 ? 如果每次改變限制深度，多次調(diào)用深度有限搜索算法，就得到了疊代深入深度優(yōu)先搜索算法 ? 其深度限制依次為 0/1/2… 這樣，當(dāng)搜索到達(dá)最淺的目標(biāo)節(jié)點(diǎn)深度時(shí)就可以發(fā)現(xiàn)目標(biāo)節(jié)點(diǎn) ? 這種搜索結(jié)合了廣度優(yōu)先和深度優(yōu)先兩種算法的優(yōu)點(diǎn) (算法見(jiàn) p63) ? 分支因子有限時(shí)是完備的 / 路徑耗散是節(jié)點(diǎn)深度的非遞增函數(shù)時(shí)是最優(yōu)的 ? 空間需求為 O(bd) / 時(shí)間復(fù)雜性為 O(bd) 第 2章 搜索技術(shù) 35 狀態(tài)的生成 ? 疊代深入搜索中因?yàn)槎啻沃貜?fù)搜索，因此部分狀態(tài)被多次生成，看起來(lái)很浪費(fèi) ? 但是因?yàn)樵诜种б蜃颖容^平衡的搜索樹(shù)中，多數(shù)節(jié)點(diǎn)都在最底層 (即葉子節(jié)點(diǎn) )，所以上層節(jié)點(diǎn)的多次生成影響不是很大 / 與廣度優(yōu)先搜索相比，效率還是更高 ? 一般來(lái)講，當(dāng)搜索空間很大而解的深度未知時(shí)，疊代深入搜索是一個(gè)首選的無(wú)信息搜索方法 第 2章 搜索技術(shù) 36 無(wú)信息搜索策略比較 第 2章 搜索技術(shù) 評(píng)價(jià)標(biāo)準(zhǔn) 廣度優(yōu)先 代價(jià)一致 深度優(yōu)先 深度有限 疊代深入 雙向搜索 是否完備 時(shí)間 空間 是否最優(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的解釋?zhuān)?A—如果 b有限則是完備的 / B—單步耗散 ≥e則是完備的 / C—如果單步耗散都是相同的則是最優(yōu)的 / D—兩個(gè)方向上都使用廣度優(yōu)先搜索 37 圖搜索算法 ? 已經(jīng)看到搜索過(guò)程中會(huì)出現(xiàn)重復(fù)的狀態(tài)擴(kuò)展，應(yīng)該避免 / 如果算法不檢測(cè)重復(fù)狀態(tài)的話(huà)，有可能使一個(gè)本來(lái)可解的問(wèn)題變?yōu)椴豢山? ? 檢測(cè)就是把要擴(kuò)展的節(jié)點(diǎn)與已擴(kuò)展的節(jié)點(diǎn)進(jìn)行比較，把遇到的相同狀態(tài)去掉 ? 所以要記錄已經(jīng)擴(kuò)展的節(jié)點(diǎn) —引入兩個(gè)表 —存儲(chǔ)已擴(kuò)展的節(jié)點(diǎn) closed表和未擴(kuò)展的節(jié)點(diǎn) open表 (即前述 fringe) ? 新算法稱(chēng)為圖搜索算法 第 2章 搜索技術(shù) 38 圖搜索算法 第 2章 搜索技術(shù) function GraphSearch(problem,fringe) return solution or failure closed← empty set fringe← Insert(MakeNode(InitialState[problem]),fringe) do while(1) if fringe=Empty then return failure node← RemoveFirst(fringe) if State[node]=Goal then return Solution(node) if State[node] !?CLOSED then add State[node] to closed fringe← InsertAll(Expend(node,problem),fringe) 39 圖搜索算法的性能 ? 由樹(shù)到圖：存在不同分支節(jié)點(diǎn)的合并 ? 圖搜索算法與樹(shù)搜索算法比較：只是增加了對(duì)展開(kāi)節(jié)點(diǎn)的判斷，因此由不同的待擴(kuò)展節(jié)點(diǎn)排列方式而形成的搜索策略(如廣度優(yōu)先和深度優(yōu)先 )的性能仍然同樹(shù)搜索算法 ? 對(duì)于含很多重復(fù)狀態(tài)的問(wèn)題，其搜索效率比樹(shù)搜索算法有效很多 ? 討論參見(jiàn) p67 第 2章 搜索技術(shù) 40 例子：“農(nóng)夫過(guò)河 ” 問(wèn)題搜索 ? 農(nóng)夫過(guò)河問(wèn)題 ? 用向量 人 ,狼 ,羊 ,白菜 表示在河岸兩邊的情況 ? 0表示此岸 / 1表示彼岸 ? 過(guò)河規(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ù) 41 “農(nóng)夫過(guò)河 ” — 廣度優(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 1 0 1 1 0 0 0 1 closed表 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 1 0 1 1 0 1 0 0 0 0 0 1 1 1 0 1 所用規(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 42 “農(nóng)夫過(guò)河 ” — 深度優(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表 0 0 0 0 1 0 1 0 0 0 1 0 1 1 1 0 0 1 0 0 1 1 0 1 所用規(guī)則序列 3/5/2/7/4 所用規(guī)則序列 3/5/2/7/4/5/3 只使用一個(gè)搜索分支 / 所擴(kuò)展的第一個(gè)節(jié)點(diǎn)是最新節(jié)點(diǎn) 43 啟發(fā)式搜索策略 貪婪最佳優(yōu)先搜索 A*搜索 啟發(fā)函數(shù) 聯(lián)機(jī)搜索 第 2章 搜索技術(shù) 44 啟發(fā)式搜索通用算法 ? 啟發(fā)式搜索也稱(chēng)有信息搜索，其通用算法稱(chēng)為最佳優(yōu)先搜索 (BestFirstSearch) ? 最佳優(yōu)先搜索基于評(píng)價(jià)函數(shù)擴(kuò) 展節(jié)點(diǎn) — 按照距離目標(biāo)最短的評(píng)價(jià)值來(lái)擴(kuò)展 ? 并不是真正的最佳 — 只是表現(xiàn)得最佳 /近似最佳 ? 算法的關(guān)鍵因素是啟發(fā)函數(shù) (Heuristic function)，記為 f(n) / f(n)=從節(jié)點(diǎn) n到目標(biāo)節(jié)點(diǎn)的最低耗散路徑的耗散估計(jì)值 ? 啟發(fā)函數(shù)引導(dǎo)搜索兩種方式 —貪婪最佳優(yōu)先搜索 / A*搜索 (A*算法 ) 第 2章 搜索技術(shù) 45 貪婪最佳優(yōu)先搜索 ? 貪婪最佳優(yōu)先搜索的 評(píng)價(jià)函數(shù) f(n)=h(n) ? 在貪婪最佳優(yōu)先搜索中總是選擇當(dāng)前離目標(biāo)最近 (最小代價(jià) )的節(jié)點(diǎn)進(jìn)行擴(kuò)展 (搜索 ) ? 局部最佳未必全局最佳 —不是最優(yōu)的 (下例 ) ? 使用 貪婪最佳優(yōu)先搜索算法搜索 從 Arad到首都的行車(chē)最短路線(xiàn) ? Arad的下一站有 3個(gè)城市 S(253)/T(329)/ Z(374) → 擴(kuò)展 Sibiu有 3個(gè)城市 F(176)/O(380) /R(193) → 擴(kuò)展Fagaras直接可到目的地 ? 然而實(shí)際不是最優(yōu)的： S→ F→ B實(shí)際全長(zhǎng) 310 / S→ RV→ P→ B實(shí)際全長(zhǎng) 278，多了 32km 第 2章 搜索技術(shù) 46 問(wèn)題實(shí)例 — Romania公路圖 第 2章 搜索技術(shù) 47 問(wèn)題實(shí)例 (1) 第 2章 搜索技術(shù) ? 尋找從 Arad到首都的行車(chē)最短路線(xiàn) ? 評(píng)價(jià)函數(shù) f(n)=h(n) ? 直線(xiàn)距離啟發(fā)式 hSLD 與實(shí)際距離相關(guān)但需另外給出，見(jiàn)下表 Arad 366 Mehadia 241 Bucharest 0 Neamt 234 Craiova 160 Oradea 380 Dobreta 242 Pitesti 100 Eforie 161 Rimnicu Vilcea 193 Fagaras 176 Sibiu 253