3問題求解及搜索技術(shù)要點-copy北航6系人工智能課件-文庫吧在線文庫
【正文】 2 問題求解基本原理 ? 問題求解： 在給定條件下，尋求一個能解決 某類 問題 且能在有限步驟內(nèi)完成的算法。 狀態(tài) 合法 變換規(guī)則（滿足約束條件）： 狀態(tài)定義 （ i大 , j中 , k小 ） : 設(shè)向量下標(biāo)分別表示大盤、中盤、小盤；向量值分別表示盤子所在柱子的編號。 ? 狀態(tài)空間 ： 所有狀態(tài)的全體構(gòu)成的集合；用 四元組 （ S, S0, O, G) 表示 : S: 非空狀態(tài)子集， S0 = 初始狀態(tài)（非空）。 ? 問題空間 ： 初始問題以及其所有子問題的全體構(gòu)成的集合，用 四元組 （ S, S0, F, G) 表示 : ? S: 問題和子問題； S0 : 初始問題。 例： （ C,B,Z) 〉（ M,…M) 重寫規(guī)則 : R1: C ? ( D, L ) R2: C ? ( B, M ) R3: B ? ( M, M) R4: Z ? ( B, B,M ) 解圖 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 14 小結(jié) – 問題求解方法比較 狀態(tài)空間法 問題空間法 問題求解 狀態(tài)變換 問題分解 搜索過程 隱含構(gòu)建 普通有向圖 隱含構(gòu)建 與或圖 節(jié)點 狀態(tài) 問題 邊 狀態(tài)變換規(guī)則（算子） 問題分解規(guī)則（算子） 求解 解徑 解圖 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 15 問題求解基本原理 一、問 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) （一） 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 16 ? 搜索技術(shù)預(yù)備 ? 狀態(tài)空間搜索 ? 有關(guān)概念 ? 盲目搜索策略 ? 啟發(fā)式搜索策略 問題求解基本原理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 17 搜索策略預(yù)備 ?盲目搜索： ?不考慮給定問題所具有的特定知識，系統(tǒng)按照事先確定好的某種 固定順序 調(diào)用規(guī)則，或是 隨機地調(diào)用規(guī)則。 ? 節(jié)點 ： 對應(yīng)狀態(tài)圖中有關(guān) 狀態(tài) 的描述。 open： 已被生成 但 未被擴展 的節(jié)點序列表； closed： 已被生成 且 已被擴展 的節(jié)點序列表； {mi} = {mj} ∪ {mk}∪ {ml} ： 擴展 n 后所得的 n 的 后繼節(jié)點 其中， { mk }： 在 OPEN表中出現(xiàn)過的 待擴展節(jié)點 ， { ml }： 在 CLOSED表中出現(xiàn)過的 已擴展節(jié)點 。 add ( open, mj) }。 expand ( n ) { mi }。 ? g (n) ： 迄今為止搜索到 的從 初始節(jié)點 s 到當(dāng)前節(jié)點 n 最佳路徑分段的已知費用 ， 是對 g* (n) 的一個估計。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 40 ? 算法中符號： s：初始節(jié)點； G：搜索圖的節(jié)點集合； OPEN表： 已生成但尚未被擴展的節(jié)點序列表； CLOSED表： 已生成且已被擴展的節(jié)點序列表； n： 待擴展的當(dāng)前節(jié)點； {mi} = {mj} ∪ {mk}∪ {ml} ：擴展 n 后生成的后繼節(jié)點 其中， mj：第一次生成的節(jié)點， mj ∈ OPEN 且 mj ∈ CLOSED 表， mk：在 OPEN表中出現(xiàn)過的待擴展節(jié)點， ml：在 CLOSED表中出現(xiàn)過的已擴展節(jié)點。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 45 8數(shù)碼問題 搜索策略比較： 寬度優(yōu)先 A算法 A*算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 46 小結(jié) ? 啟發(fā)式搜索策略 ? g: ? 考慮當(dāng)前路徑 已經(jīng)花費的費用 ，及時拋棄已經(jīng)經(jīng)過的花費太大且距目標(biāo)仍遠的路徑 。問：怎樣才能使 4 公斤油桶里恰好只裝 2 公斤油？ 設(shè)狀態(tài)定義 ： (x,y)，其中， x： 4 公斤油桶中實際裝油公斤數(shù)； y： 3 公斤油桶中實際裝油公斤數(shù)。求出有向圖的一條解徑 ,給出求解過程（ Open， Closed內(nèi)容）。 ? 對于 {ml} ∈ {mi}: if f (n, ml) f (ml) then f (ml) := f (n, ml), ml n, OPEN:= OPEN ∪ {ml} 將 OPEN表中節(jié)點按 f 值 從小到大重新排序 A B 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 43 啟發(fā)式最佳 圖搜索算法 A*算法 ? A*算法定義： 若將 A算法中評價函數(shù)
物理相關(guān)推薦
鄂ICP備17016276號-1