第二章問題求解基本原理-文庫吧資料
2024-10-06 14:01本頁面
【正文】 環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 15 基于問題空間的與 或圖搜索 ? 與或圖搜索 有關(guān)概念 ?與或解圖 及其 能解標(biāo)記 與 費(fèi)用計(jì)算 ? 最佳與或解圖啟發(fā)式搜索算法 – AO*算法 ? AO*算法 應(yīng)用實(shí)例 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 16 最佳與或圖啟發(fā)式搜索 AO* 算法概述 ?算法 交替執(zhí)行 以下兩個(gè)階段的操作： ? 第一階段 ： 自頂向下 地 生成 局部 與或圖 選擇 迄今為止最好的局部解圖 ；對(duì)該解圖的一個(gè)非終葉節(jié)點(diǎn)進(jìn)行 擴(kuò)展 ，計(jì)算該 節(jié)點(diǎn)各個(gè) K連接符連接的后繼節(jié)點(diǎn)解圖的花費(fèi)計(jì)值；如果可能，標(biāo)記后繼節(jié)點(diǎn)為能解節(jié)點(diǎn)。 Iff 這些與子節(jié)點(diǎn)中有一節(jié)點(diǎn)不能解，節(jié)點(diǎn) n 是不能解節(jié)點(diǎn)。 Iff 這些與子節(jié)點(diǎn)全部能解，節(jié)點(diǎn) n 是能解節(jié)點(diǎn)。 針對(duì)任意節(jié)點(diǎn)的 外向 K連接符 的 選擇 順序不同 , 對(duì)應(yīng)的搜索策略可不同 : 盲目搜索，啟發(fā)式搜索。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 9 與或解圖及其能解標(biāo)記與費(fèi)用計(jì)算 按 遞歸定義 自上而下地 生成 以 n為根節(jié)點(diǎn)的與或圖一般算法： ? 選擇 n 的一個(gè)外向 k連接符， 擴(kuò)展 其后繼節(jié)點(diǎn)。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 7 ? 與或圖搜索 有關(guān)概念 ? 與或解圖 及其 能解標(biāo)記 與 費(fèi)用計(jì)算 ? 最佳與或解圖的啟發(fā)式搜索算法 – AO*算法 ? AO*算法 應(yīng)用實(shí)例 基于問題空間的 與或圖搜索 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 8 與或解圖 及其能解標(biāo)記與費(fèi)用計(jì)算 ? 定義 : 與或圖 G 中，從任一節(jié)點(diǎn) n 到葉節(jié)點(diǎn) (本原問題 )集合 N 的一個(gè)局部解圖 G’ 遞歸定義 如下： ? 若 n 屬于 N,則此解圖 G’ 由單一節(jié)點(diǎn) {n}組成； ? 若 n 有一個(gè)指向節(jié)點(diǎn) {n1,n2,….,n k}的 外向 k連接符（ k ≥ 1), 而且從每一個(gè) ni(i=1,2,….k) 到 N 都有一個(gè)解圖，則 n 到 N
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1