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