3問(wèn)題求解及搜索技術(shù)要點(diǎn)-copy北航6系人工智能課件-wenkub
2023-03-28 01:15:48 本頁(yè)面
【正文】 邊 狀態(tài)變換規(guī)則（算子） 問(wèn)題分解規(guī)則（算子） 求解 解徑 解圖 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 15 問(wèn)題求解基本原理 一、問(wèn) 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) （一） 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 16 ? 搜索技術(shù)預(yù)備 ? 狀態(tài)空間搜索 ? 有關(guān)概念 ? 盲目搜索策略 ? 啟發(fā)式搜索策略 問(wèn)題求解基本原理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 17 搜索策略預(yù)備 ?盲目搜索： ?不考慮給定問(wèn)題所具有的特定知識(shí)，系統(tǒng)按照事先確定好的某種 固定順序 調(diào)用規(guī)則，或是 隨機(jī)地調(diào)用規(guī)則。如圖 a 所示。 ? 問(wèn)題空間 ： 初始問(wèn)題以及其所有子問(wèn)題的全體構(gòu)成的集合，用 四元組 （ S, S0, F, G) 表示 : ? S: 問(wèn)題和子問(wèn)題； S0 : 初始問(wèn)題。 解不唯一。 ? 狀態(tài)空間 ： 所有狀態(tài)的全體構(gòu)成的集合；用 四元組 （ S, S0, O, G) 表示 : S: 非空狀態(tài)子集， S0 = 初始狀態(tài)（非空）。 問(wèn)題分解合法規(guī)則： （ 3， 1， 3） 〉（ 2， 1， 2） ? (1， 1， 3） ? （ 2， 2， 3） 。 狀態(tài) 合法 變換規(guī)則（滿足約束條件）： 狀態(tài)定義 （ i大 , j中 , k小 ） : 設(shè)向量下標(biāo)分別表示大盤、中盤、小盤；向量值分別表示盤子所在柱子的編號(hào)。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 3 問(wèn)題求解基本原理 一、問(wèn) 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 4 問(wèn)題求解基本原理 ?問(wèn)題求解方法： ?基于 狀態(tài)空間 的問(wèn)題求解方法 ?基于 問(wèn)題空間 的問(wèn)題求解方法 ?基于 博弈 搜索 的問(wèn)題求解方法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 5 問(wèn)題實(shí)例 桌上固定了 3 根柱子 ， 按 1， 2， 3 次序排例 。北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 1 人 工 智 能 ( 問(wèn)題求解 基本原理及 搜索技術(shù) ) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 2 問(wèn)題求解基本原理 ? 問(wèn)題求解： 在給定條件下，尋求一個(gè)能解決 某類 問(wèn)題 且能在有限步驟內(nèi)完成的算法。 有 n 個(gè)大小全不一樣大的盤子 d1， … ， dn ， 按從小到大 ， 小的在上的次序依次插在第一根柱子上 ，要把這 n 個(gè)盤子全部搬到第三根柱子上 ， 每次只許搬一個(gè) ， 任何時(shí)候都不允許把大盤子放在小盤子上面 ， 問(wèn)該 如何搬法 。 ? 問(wèn)題描述： 問(wèn)題（ a, b, c): 將 b 柱子上的 a 個(gè)盤子搬到 c 柱子上。 G: 非空目標(biāo)狀態(tài)子集。 S0 R1 S2 R2 Sk ?.. Rk G ? 問(wèn)題有解 ： 從代表 初始狀態(tài) s 節(jié)點(diǎn)出發(fā)， 存在一條通向 目標(biāo)節(jié)點(diǎn) 的路徑。 ? G: 具有 平凡解 的 本原問(wèn)題 集合。 ? “或” 節(jié)點(diǎn)： 若 節(jié)點(diǎn)Ａ有邊通向一組節(jié)點(diǎn) {{Ｂ １ },{Ｂ 2}， ?{Ｂ n}}，問(wèn)題Ａ的解決有待于子問(wèn)題Ｂ １ 或Ｂ 2或 ? 或Ｂ n中 某一個(gè)子問(wèn)題的解決 ， 則稱 A 為“或” 節(jié)點(diǎn)。 ? 常用的 盲目 搜索算法 : 深度優(yōu)先搜索策略； 寬度優(yōu)先搜索策略 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 18 搜索策略預(yù)備 ?啟發(fā)式信息 ： ?與問(wèn)題求解有關(guān)的信息和知識(shí)。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(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)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 20 基于 狀態(tài)空間 的 搜索技術(shù)： 有關(guān)搜索概念 盲目搜索策略 啟發(fā)式 搜索策略 問(wèn)題求解基本原理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1