【正文】 ? A 算法 ： 定義估計函數(shù)： f = g + h； ? A* 算法 ： 定義估計函數(shù)： f = g + h； 滿足 h（ n） ≤ h*（ n）。 ? h* (n)： n → t 最佳路徑 的 分段費用 。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 28 寬度 優(yōu)先搜索算法 S, A, D A, D, B, D D, B, A, E ……… Open 表為 隊 操 作 ： 先進先出！ 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 29 G 節(jié)點 擴展順序 寬度 優(yōu)先搜索算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 30 open := [S]。 ? 后繼節(jié)點 ： 稱將規(guī)則作用于節(jié)點 n 生成 的新節(jié)點為節(jié)點 n 的 后 繼節(jié)點。 ? F: 操作算子集合，用于將問題分解成其若干個子問題的描述規(guī)則 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 12 問題空間法 的有關(guān)概念（ 2） ? 問題空間分解過程 ： 隱含求一個 與或圖 ? 節(jié)點 – 問題， 邊 分解問題的算子。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 7 基于 問題空間 的問題求解方法 ? 問題： 如何將 i 柱子上的 m 個盤子搬到 k 柱子上 ? ? 將 i 柱子上的 m – 1 個盤子搬到 j 柱子上； ? 將 i 柱子上的 第 m 個盤子搬到 k 柱子上； ? 將 j 柱子上的 m – 1 個盤子搬到 k 柱子上。 狀態(tài)描述 大盤在第 i 根柱子上；中號盤在第 j 根柱子上，小號盤在第 k 根柱子上。 ? “與” 節(jié)點： 如果節(jié)點 A 有邊通向一組節(jié)點 { B1， B2，?..Bn } ，問題 A 的解決有待于 A 的子問題組 { B1,B2?..Bn }的 全部解決 ，則稱 A 為“與” 節(jié)點。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 24 ? 路徑 ： 對于一個節(jié)點序列（ n0, n1, …, n l, …, n k），如若每一節(jié)點 ni1都有一個后繼節(jié)點 ni（ i = 1, 2, …, k ），則稱該節(jié)點序列為一條從節(jié)點 n0 到節(jié)點 nk、長度為 k 的路徑；路徑還可表示為與節(jié)點序列對應(yīng)的規(guī)則序列 。 closed := [ ]。 ? g* (n)： s→ n 最佳路徑 的 分段費用。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 47 作業(yè) : 利用寬度優(yōu)先法或深度優(yōu)先法，程序?qū)崿F(xiàn) Highway map 問題求解，只考慮節(jié)點的連接和變換 ,不考慮邊的權(quán)值 。 ? h: ? 估計當前路徑上節(jié)點到目標節(jié)點 還需要的費用 ，引導(dǎo)搜索向最有希望的路徑前進。 ? f *(n) = g* (n) + h* (n)： 從初始節(jié)點 s 出發(fā)，經(jīng)過 最佳路徑 上任意節(jié)點 n，到達目標節(jié)點 t 的 最小 費用。 exit ( fail )。 ? 擴展節(jié)點 n：稱 生成 節(jié)點 n 的所有 后繼節(jié)點 并 計算 生成這些后繼節(jié)點所造成的 花費 的過程（ 即，計算各后繼節(jié)點的優(yōu)劣且將其連接到節(jié)點 n 等操作造成的開銷 ）叫做 擴展節(jié)點 n 。 ? G: 具有 平凡解 的 本原問題 集合。 有 n 個大小全不一樣大的盤子 d1， … ， dn ， 按從小到大 ， 小的在上的次序依次插在第一根柱子上 ，要把這 n 個盤子全部搬到第三根柱子上 ， 每次只許搬一個 ， 任何時候都不允許把大盤子放在小盤子上面 ， 問該 如何搬法 。 問題分解合法規(guī)則： （ 3， 1， 3） 〉（ 2， 1， 2） ? (1， 1， 3） ? （ 2， 2， 3） 。如圖 a 所示。 狀態(tài)空間 搜索有關(guān)概念 ? 路徑花費 ： 設(shè) C（ ni， nj）為節(jié)點 ni 到 nj 這段路徑（或弧線）的花費。 d = 深度限制值 while open ≠ [ ] do { n := first ( open )。 ? s： 初始節(jié)點； n： 當前節(jié)點； t： 目標節(jié)點。求出有向圖的一條解徑 ,給出求解過程（ Open， Closed內(nèi)容）。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 45 8數(shù)碼問題 搜索策略比較： 寬度優(yōu)先 A算法 A*算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點實驗室 Slide 46 小結(jié) ? 啟發(fā)式搜索策略 ? g: ? 考慮當前路徑 已經(jīng)花費的費用 ，及時拋棄已經(jīng)經(jīng)過的花費太大且距目標仍遠的路徑 。 ? g (n) ： 迄今為止搜索到 的從 初始節(jié)點 s 到當前節(jié)