第二章問題求解基本原理-資料下載頁
2025-09-19 14:01本頁面
【導(dǎo)讀】與或圖搜索有關(guān)概念。與或解圖及其能解標(biāo)記與費用計算。最佳與或解圖的啟發(fā)式搜索算法–AO*算法。問題描述回顧-：。、已知事實等，或是已經(jīng)證明的定理。ifn１thenn２∨n３；ifn４thenn５∨n８；問題及子問題：{n0，n7，n8，n1，n2，……僅由K=1的外向k-連接符構(gòu)成的搜索空間:. 點的祖先節(jié)點，這種與或圖稱為無環(huán)與或圖。選擇n的一個外向k連接符，擴展其后繼節(jié)點。判斷各后繼節(jié)點是否屬于N，若否，則對該k連接符指向的每一個后繼節(jié)點，選擇一個。上述過程周而復(fù)始，直到最底層的外向k連接符的每個后繼。盲目搜索，啟發(fā)式搜索。若n有m個外向k-連接符（k≥1)。算法交替執(zhí)行以下兩個階段的操作：。最好的局部解圖；對該解圖的一個非終葉節(jié)點進行擴展，確定最小花費連接符；如果必要，修改父節(jié)點的花費值；
【正文】 天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 18 AO* 算法： 選擇 最有希望的局部解圖 G’ 及 G’ 中合適的非葉節(jié)點 n：G’:= Find ( G ), n := Select ( G’) 擴展 節(jié)點 n，計算 { mj } 的啟發(fā)式信息： { mi } := Expand( n ), G’ := { mi } ∪ G’ , 對所有 mj: q ( mj ) := h ( mj ) mj 到 N 的估計值 。 如果 mj 屬于 N 則 Mark ( mj， Sovled )。 建立以 n 節(jié)點為初始節(jié)點的祖先節(jié)點集合： A := { n } A = Φ ? Yes No 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 19 m:= Remove ( A ) 針對 m 的 L個 k 連接符，求 m 的最小花費 q (m) ： qi(m):=C (mi) + q(ni1) + q(ni2) + …… + q(nik) ) 1 i L 。 q(m) := min qi(m) （ i = 1, 2, …., L)。 標(biāo)記 m 指向 當(dāng)前花費最小 的 k 連接符。 如果 m 最小花費 ki 連接符連接的所有節(jié)點 nij可解 , 標(biāo)記 節(jié)點 m 可解，即 對（ j = 1,2,….,k) ： ?i ? j Mark (nij, Sovled) Mark (m, Sovled), Mark (m, Sovled) ∨ q(m) ≠ q0(m) 將 m 的父節(jié)點 ma 送集合 A: A := A ∪ { ma } Yes No AO* 算法： 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 20 基于問題空間的與 或圖搜索 ?與或圖搜索 有關(guān)概念 ?與或解圖 及其 能解標(biāo)記 與 費用計算 ? 最佳與或解圖的啟發(fā)式搜索算法 – AO*算法 ? AO*算法應(yīng)用實例
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1