3問題求解及搜索技術(shù)要點(diǎn)-copy 北航6系人工智能課件-文庫吧
2025-02-27 01:15 本頁面
【正文】 ? 問題有解 ： 從代表 初始狀態(tài) s 節(jié)點(diǎn)出發(fā)， 存在一條通向 目標(biāo)節(jié)點(diǎn) 的路徑。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 11 問題空間法 有關(guān)概念 ? 問題空間法 ： 首先產(chǎn)生待證問題的 所有 子問題 ， 而后通過解決所有子問題達(dá)到問題求解目的的方法 。 ? 問題 ： 描述問題及其子問題的符號(hào)或數(shù)據(jù)結(jié)構(gòu) 。 ? 問題空間 ： 初始問題以及其所有子問題的全體構(gòu)成的集合，用 四元組 （ S, S0, F, G) 表示 : ? S: 問題和子問題； S0 : 初始問題。 ? G: 具有 平凡解 的 本原問題 集合。 ? F: 操作算子集合，用于將問題分解成其若干個(gè)子問題的描述規(guī)則 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 12 問題空間法 的有關(guān)概念（ 2） ? 問題空間分解過程 ： 隱含求一個(gè) 與或圖 ? 節(jié)點(diǎn) – 問題， 邊 分解問題的算子。 ? “與” 節(jié)點(diǎn)： 如果節(jié)點(diǎn) A 有邊通向一組節(jié)點(diǎn) { B1， B2，?..Bn } ，問題 A 的解決有待于 A 的子問題組 { B1,B2?..Bn }的 全部解決 ，則稱 A 為“與” 節(jié)點(diǎn)。如圖 a 所示。 ? “或” 節(jié)點(diǎn)： 若 節(jié)點(diǎn)Ａ有邊通向一組節(jié)點(diǎn) {{Ｂ １ },{Ｂ 2}， ?{Ｂ n}}，問題Ａ的解決有待于子問題Ｂ １ 或Ｂ 2或 ? 或Ｂ n中 某一個(gè)子問題的解決 ， 則稱 A 為“或” 節(jié)點(diǎn)。 如圖 b 所示 。 …... a : A B1 B2 Bn …... b : A B1 B2 Bn 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 13 問題空間法 有關(guān)概念（ 2） ? 問題的解（解圖） ： 從代表 初始問題 的節(jié)點(diǎn)出發(fā)，搜索到一個(gè)完整的 ‘與或’ 子圖 ，圖中所有葉節(jié)點(diǎn)均滿足問題求解的結(jié)束條件。 例： （ 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)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 14 小結(jié) – 問題求解方法比較 狀態(tài)空間法 問題空間法 問題求解 狀態(tài)變換 問題分解 搜索過程 隱含構(gòu)建 普通有向圖 隱含構(gòu)建 與或圖 節(jié)點(diǎn) 狀態(tài) 問題 邊 狀態(tài)變換規(guī)則（算子） 問題分解規(guī)則（算子） 求解 解徑 解圖 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 15 問題求解基本原理 一、問 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) （一） 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 16 ? 搜索技術(shù)預(yù)備 ? 狀態(tài)空間搜索 ? 有關(guān)概念 ? 盲目搜索策略 ? 啟發(fā)式搜索策略 問題求解基本原理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 17 搜索策略預(yù)備 ?盲目搜索： ?不考慮給定問題所具有的特定知識(shí)，系統(tǒng)按照事先確定好的某種 固定順序 調(diào)用規(guī)則，或是 隨機(jī)地調(diào)用規(guī)則。 ? 常用的 盲目 搜索算法 : 深度優(yōu)先搜索策略； 寬度優(yōu)先搜索策略 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 18 搜索策略預(yù)備 ?啟發(fā)式信息 ： ?與問題求解有關(guān)的信息和知識(shí)。 ?由于 信息的 片面性 和 不準(zhǔn)確性 ，應(yīng)用啟發(fā)式信息 不能百分之百地保證 找到問題的解，但能提高問題求解的可能性。 ? 啟發(fā)式信息 在問題求解過程中的 作用 ： ?有助于 加速求解過程； ?有助于 找到“較優(yōu)”解。 ? 啟發(fā)式搜索策略 : ? 考慮給定問題領(lǐng)域具有的特定知識(shí)（ 啟發(fā)式信息 ），系統(tǒng)動(dòng)態(tài)地規(guī)定 規(guī)則調(diào)用順序， 優(yōu)先使用“較”合適 的規(guī)則。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 19 搜索策略預(yù)備 ? 常用的基于 狀態(tài)圖 的 啟發(fā)式 搜索策略 : ? 爬山搜索策略 (Hill Climbing) ? 大英博物館搜索策略 (British Museum) ? 啟發(fā)式圖搜索策略 ( A ) ? 最佳 啟發(fā)式 圖搜索策略 ( A* ) ? 常用的基于 與或圖及博弈 的 啟發(fā)式 搜索策略 ： ? 最佳 啟發(fā)式 與或圖搜索策略 ( AO* ) ? 極大極小搜索策略 (Minimax) ? α － β 剪枝搜索策略 (AlphaBeta Pruning) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 20 基于
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1