【正文】 f (n)的啟發(fā)式分量函數(shù) h（ n） 的值限制在 h*（ n） 的下界范圍內(nèi) ， 亦即對所有節(jié)點(diǎn) n， 都滿足h（ n） ≤ h*（ n） ， 則稱此時的 A 算法為 A* 算法 。 ? s： 初始節(jié)點(diǎn)； n： 當(dāng)前節(jié)點(diǎn)； t： 目標(biāo)節(jié)點(diǎn)。 深度 優(yōu)先搜索算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 31 深度 優(yōu)先搜索算法 S A, D B, D, D ……… Open表為 棧 操 作 ： 后進(jìn)先出！ C, E, D 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 32 節(jié)點(diǎn) 擴(kuò)展順序 深度 優(yōu)先搜索算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 33 盲目 搜索 算法應(yīng)用實(shí)例 8數(shù)碼問題 描述 狀態(tài) ： 矩陣 (Sij)，其中 1≤i,j≤3， Sij∈ {0,1,… ,8}。 d = 深度限制值 while open ≠ [ ] do { n := first ( open )。 remove ( first ( open ) )。 狀態(tài)空間 搜索有關(guān)概念 ? 路徑花費(fèi) ： 設(shè) C（ ni， nj）為節(jié)點(diǎn) ni 到 nj 這段路徑（或弧線）的花費(fèi)。 ? 啟發(fā)式搜索策略 : ? 考慮給定問題領(lǐng)域具有的特定知識（ 啟發(fā)式信息 ），系統(tǒng)動態(tài)地規(guī)定 規(guī)則調(diào)用順序， 優(yōu)先使用“較”合適 的規(guī)則。如圖 a 所示。 解不唯一。 問題分解合法規(guī)則： （ 3， 1， 3） 〉（ 2， 1， 2） ? (1， 1， 3） ? （ 2， 2， 3） 。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 3 問題求解基本原理 一、問 題 求 解 的 基 本 方 法 二、搜 索 技 術(shù) 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 4 問題求解基本原理 ?問題求解方法： ?基于 狀態(tài)空間 的問題求解方法 ?基于 問題空間 的問題求解方法 ?基于 博弈 搜索 的問題求解方法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 5 問題實(shí)例 桌上固定了 3 根柱子 ， 按 1， 2， 3 次序排例 。 有 n 個大小全不一樣大的盤子 d1， … ， dn ， 按從小到大 ， 小的在上的次序依次插在第一根柱子上 ，要把這 n 個盤子全部搬到第三根柱子上 ， 每次只許搬一個 ， 任何時候都不允許把大盤子放在小盤子上面 ， 問該 如何搬法 。 G: 非空目標(biāo)狀態(tài)子集。 ? G: 具有 平凡解 的 本原問題 集合。 ? 常用的 盲目 搜索算法 : 深度優(yōu)先搜索策略； 寬度優(yōu)先搜索策略 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 18 搜索策略預(yù)備 ?啟發(fā)式信息 ： ?與問題求解有關(guān)的信息和知識。 ? 擴(kuò)展節(jié)點(diǎn) n：稱 生成 節(jié)點(diǎn) n 的所有 后繼節(jié)點(diǎn) 并 計算 生成這些后繼節(jié)點(diǎn)所造成的 花費(fèi) 的過程（ 即，計算各后繼節(jié)點(diǎn)的優(yōu)劣且將其連接到節(jié)點(diǎn) n 等操作造成的開銷 ）叫做 擴(kuò)展節(jié)點(diǎn) n 。 { mj }： 第一次生成 的節(jié)點(diǎn) ， mj ∈ OPEN 且 mj ∈ CLOSED表 ， 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 27 寬度 優(yōu)先搜索算法 open := [S]。 exit ( fail )。 delete ( (?mi)( mi ∈ { mk } ∨ ( mi ∈ { ml } ) )。 ? f *(n) = g* (n) + h* (n)： 從初始節(jié)點(diǎn) s 出發(fā)，經(jīng)過 最佳路徑 上任意節(jié)點(diǎn) n，到達(dá)目標(biāo)節(jié)點(diǎn) t 的 最小 費(fèi)用。 啟發(fā)式圖搜索算法 A算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 41 A算法 n 為目標(biāo) t ? 取當(dāng)前節(jié)點(diǎn) n n := first ( OPEN ), 從 OPEN中刪除 n, CLOSED:= CLOSED∪ {n} 初 始 化 G:=G0∪ S, OPEN:=(S) CLOSED := ( ), f (S) := g(S) + h(S) OPEN=Φ ^ 未發(fā)現(xiàn)目標(biāo) t Return ( Fail ) A yes No yes No B Exit ( Success ) 輸出解徑 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 42 擴(kuò)展 節(jié)點(diǎn) n：生成 n的后繼節(jié)點(diǎn)；計算后繼節(jié)點(diǎn)的花費(fèi)。 ? h: ? 估計當(dāng)前路徑上節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn) 還需要的費(fèi)用 ，引導(dǎo)搜索向最有希望的路徑