第二章問題求解基本原理-文庫吧
2025-08-25 14:01 本頁面
【正文】 圖中，如果每一個(gè)后繼節(jié)點(diǎn)不再是該節(jié)點(diǎn)的祖先節(jié)點(diǎn)，這種與或圖稱為 無環(huán)與或圖 。 ? 外向 K連接符 ： 在與或圖中，任一節(jié)點(diǎn)通過 若干個(gè) 外向 k連接符（ k元算子）與其后繼節(jié)點(diǎn)相連接，其中 K = 1 的外向 k連接符： 或 連接符； K 〉 1 的外向 k連接符： 與 連接符。 普通有向圖 由 K ? 1 的外向 k連接符構(gòu)成的搜索空間 : 與或圖 。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 6 ? 問題求解過程分析 ： 與或圖搜索有關(guān)概念 ? 首先 , 自上而下地 生成 與 或圖 。 ? 然后 , 自下而上地 尋找 與或解圖 的 搜索 過程。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 7 ? 與或圖搜索 有關(guān)概念 ? 與或解圖 及其 能解標(biāo)記 與 費(fèi)用計(jì)算 ? 最佳與或解圖的啟發(fā)式搜索算法 – AO*算法 ? AO*算法 應(yīng)用實(shí)例 基于問題空間的 與或圖搜索 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(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 的解圖 G’ 由節(jié)點(diǎn) n、連接符 k 以及{n1,n2,….,n k}中每個(gè)節(jié)點(diǎn) ni 到 N 的解圖組成。 ? 否則， n 到 N 無解圖。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 9 與或解圖及其能解標(biāo)記與費(fèi)用計(jì)算 按 遞歸定義 自上而下地 生成 以 n為根節(jié)點(diǎn)的與或圖一般算法： ? 選擇 n 的一個(gè)外向 k連接符， 擴(kuò)展 其后繼節(jié)點(diǎn)。 ? 判斷各后繼節(jié)點(diǎn)是否屬于 N， ? 若否，則對(duì)該 k 連接符指向的每
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1