第二章問(wèn)題求解基本原理(參考版)
2024-10-02 14:01本頁(yè)面
【正文】 如果 m 最小花費(fèi) ki 連接符連接的所有節(jié)點(diǎn) nij可解 , 標(biāo)記 節(jié)點(diǎn) m 可解，即 對(duì)（ j = 1,2,….,k) ： ?i ? j Mark (nij, Sovled) Mark (m, Sovled), Mark (m, Sovled) ∨ q(m) ≠ q0(m) 將 m 的父節(jié)點(diǎn) ma 送集合 A: A := A ∪ { ma } Yes No AO* 算法： 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 20 基于問(wèn)題空間的與 或圖搜索 ?與或圖搜索 有關(guān)概念 ?與或解圖 及其 能解標(biāo)記 與 費(fèi)用計(jì)算 ? 最佳與或解圖的啟發(fā)式搜索算法 – AO*算法 ? AO*算法應(yīng)用實(shí)例 。 q(m) := min qi(m) （ i = 1, 2, …., L)。 如果 mj 屬于 N 則 Mark ( mj， Sovled )。 G： 以 s 為根節(jié)點(diǎn)產(chǎn)生的與或圖； G’： 當(dāng)前選擇的局部與或解圖 ； h(m)： 任意 節(jié)點(diǎn) m 到 N 的啟發(fā)式費(fèi)用估計(jì)值； q (n)： 目前得到的以節(jié)點(diǎn) n 為根的解圖的最小費(fèi)用； q0 (n)： 上一次獲得的以節(jié)點(diǎn) n為根的解圖的最小費(fèi)用 。此過(guò)程不斷進(jìn)行直到到達(dá)局部解圖的根節(jié)點(diǎn)為止。設(shè)其中第 i 個(gè)外向 k連接符的費(fèi)用為 Cni，其連接的后繼節(jié)點(diǎn) 為 {ni1,ni2,….,n ik}，則節(jié)點(diǎn) n 通過(guò)此連接符到 N 的一個(gè)解圖的費(fèi)用為： C(n， N)i = Cni + C(ni1， N) + … . + C(nik， N) m ?最佳解圖花費(fèi) 計(jì)算： C(n， N) = min ( C(n， N)i ) i = 1 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 14 與或解圖及其能解標(biāo)記與 費(fèi)用計(jì)算 求解圖的花費(fèi)： (設(shè)每條邊為 單位花費(fèi) ) n８ n８ n８ 北京航空航天大學(xué)軟件開(kāi)發(fā)
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1