3問題求解及搜索技術(shù)要點-copy北航6系人工智能課件(已修改)
2025-03-17 01:15 本頁面
【正文】 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 1 人 工 智 能 ( 問題求解 基本原理及 搜索技術(shù) ) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 2 問題求解基本原理 ? 問題求解： 在給定條件下，尋求一個能解決 某類 問題 且能在有限步驟內(nèi)完成的算法。 ? 問題求解特征： ? 傳統(tǒng)軟件 ： ① 求解的問題是能夠用 數(shù)學(xué)精確描述 的 良結(jié)構(gòu)的問題 （如，解方程） ； ② 計算機執(zhí)行的繁雜的統(tǒng)計計算任務(wù)一般不能看成是人工智能活動。 ? AI軟件 ：① 求解的是 不可直接用數(shù)學(xué)模型描述 的所謂 不良結(jié)構(gòu)問題 （如，幾何證明、求不定積分、邏輯演算等） ，通常需要采用 弱方法 進行搜索求解； ② AI程序 中符號的內(nèi)涵不僅局限于數(shù)值計算和數(shù)據(jù)處理中的一般數(shù)據(jù)信息，應(yīng)表現(xiàn)人類進行推理所需要的各種 知識 。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 3 問題求解基本原理 一、問 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 4 問題求解基本原理 ?問題求解方法： ?基于 狀態(tài)空間 的問題求解方法 ?基于 問題空間 的問題求解方法 ?基于 博弈 搜索 的問題求解方法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 5 問題實例 桌上固定了 3 根柱子 ， 按 1， 2， 3 次序排例 。 有 n 個大小全不一樣大的盤子 d1， … ， dn ， 按從小到大 ， 小的在上的次序依次插在第一根柱子上 ，要把這 n 個盤子全部搬到第三根柱子上 ， 每次只許搬一個 ， 任何時候都不允許把大盤子放在小盤子上面 ， 問該 如何搬法 。 設(shè) n = 3， 該 如何搬法 ？ 1 2 3 1 2 3 梵塔問題 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 6 基于 狀態(tài)空間 的問題求解方法 （ 1， 1， 1） → （ 1， 1， 2） （ 1， 1， 1） → （ 1， 1， 3） （ 1， 1， 2） → （ 1， 3， 2） 。 狀態(tài) 合法 變換規(guī)則（滿足約束條件）： 狀態(tài)定義 （ i大 , j中 , k小 ） : 設(shè)向量下標分別表示大盤、中盤、小盤；向量值分別表示盤子所在柱子的編號。 狀態(tài)描述 大盤在第 i 根柱子上；中號盤在第 j 根柱子上，小號盤在第 k 根柱子上。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 7 基于 問題空間 的問題求解方法 ? 問題： 如何將 i 柱子上的 m 個盤子搬到 k 柱子上 ? ? 將 i 柱子上的 m – 1 個盤子搬到 j 柱子上； ? 將 i 柱子上的 第 m 個盤子搬到 k 柱子上； ? 將 j 柱子上的 m – 1 個盤子搬到 k 柱子上。 ? 問題描述： 問題（ a, b, c): 將 b 柱子上的 a 個盤子搬到 c 柱子上。 問題分解合法規(guī)則： （ 3， 1， 3） 〉（ 2， 1， 2） ? (1， 1， 3） ? （ 2， 2， 3） 。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 8 基于 問題空間 的問題求解方法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 9 狀態(tài)空間法 有關(guān)概念 ? 狀態(tài)空間法 : 從問題的 初始狀態(tài) 出發(fā) ， 通過一系列的 狀態(tài)變換 找到 目標狀態(tài) 的問題求解方法 。 ? 狀態(tài) ： 描述問題中事物形狀或狀況的符號或數(shù)據(jù)結(jié)構(gòu)。 ? 狀態(tài)空間 ： 所有狀態(tài)的全體構(gòu)成的集合；用 四元組 （ S, S0, O, G) 表示 : S: 非空狀態(tài)子集， S0 = 初始狀態(tài)（非空）。 G: 非空目標狀態(tài)子集。 O: 操作算子集合，一個狀態(tài) 合法 轉(zhuǎn)換為 另一個狀態(tài)的描述規(guī)則 ? 問題求解過程 ： 隱含 求一個 普通有向圖 ， 節(jié)點 狀態(tài)， 邊 – 算子 ? 搜索空間 ： 問題求解過程中 到達 過的所有狀態(tài)（節(jié)點）的集合 。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 10 狀態(tài)空間法 有關(guān)概念 狀態(tài)空間、搜索空間及解徑的關(guān)系： ? 問題的解（解徑） ： 初始狀態(tài) 到 目標狀態(tài) 通路上的每一條規(guī)則 （或 狀態(tài)）構(gòu)成 序列，稱為 解徑 。 解不唯一。 S0 R1 S2 R2 Sk ?.. Rk G
物理相關(guān)推薦
鄂ICP備17016276號-1