第二章問題求解基本原理(編輯修改稿)
2024-11-03 14:01 本頁面
【文章內(nèi)容簡介】 一個后繼節(jié)點，選擇一個外向 k連接符的后繼節(jié)點繼續(xù)進行擴展； ? 上述過程周而復(fù)始，直到 最底層的 外向 k連接符的每個后繼節(jié)點均屬于 N 為止。 針對任意節(jié)點的 外向 K連接符 的 選擇 順序不同 , 對應(yīng)的搜索策略可不同 : 盲目搜索，啟發(fā)式搜索。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 10 ? 標記 能解節(jié)點 （ Solved)： ? 終葉節(jié)點是能解節(jié)點； ? 對于非終葉節(jié)點： ?如果 n 有多個用 k=1 的連接符連接的 或子節(jié)點 ， iff 這些或子節(jié)點中至少有一個能解，節(jié)點 n 是能解節(jié)點； 與或解圖及其 能解標記 與費用計算 ? 如果 n 有用 k1 的連接符連接的 與子節(jié)點 。 Iff 這些與子節(jié)點全部能解，節(jié)點 n 是能解節(jié)點。 定義 : 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 11 與或解圖及其 能解標記 與費用計算 ? 標記 不能解節(jié)點 （ Unsolved) 沒有后裔的非終節(jié)點是不能解節(jié)點 ； ? 對于有后裔的非終節(jié)點 n： ? 如果 n 有多個用 k=1 連接符連接的 或子節(jié)點 ， iff 所有 這些或子節(jié)點均不能解，節(jié)點 n 是不能解節(jié)點； ? 如果 n 有用 k1 連接符連接的 與子節(jié)點 。 Iff 這些與子節(jié)點中有一節(jié)點不能解，節(jié)點 n 是不能解節(jié)點。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 12 與或解圖及其 能解標記 與費用計算 標記 能解節(jié)點 ，求以 n為根節(jié)點的與或解圖： n８ n８ n８ 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 13 與或解圖及其能解標記與 費用計算 ? 解圖費用 定義： 設(shè) k連接符的花費 C(k)= k, 以 n 為根節(jié)點的局部解圖的費用 C(n,N) 可 遞歸計算 如下： ? 若 n 屬于 N, 則 C(n,N) = 0； ? 若 n 有 m 個 外向 k連接符（ k ≥ 1) 。設(shè)其中第 i 個外向 k連接符的費用為 Cni，其連接的后
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1