3問題求解及搜索技術(shù)要點-copy 北航6系人工智能課件(文件)
【正文】 21 狀態(tài)空間 搜索 有關(guān)概念 ?狀態(tài) 圖 特點： 多條路徑通向同一節(jié)點。 ? 擴展節(jié)點 n：稱 生成 節(jié)點 n 的所有 后繼節(jié)點 并 計算 生成這些后繼節(jié)點所造成的 花費 的過程（ 即，計算各后繼節(jié)點的優(yōu)劣且將其連接到節(jié)點 n 等操作造成的開銷 ）叫做 擴展節(jié)點 n 。一條路徑的花費等于連接這條路徑各節(jié)點間所有弧線花費值的總和。 { mj }： 第一次生成 的節(jié)點 ， mj ∈ OPEN 且 mj ∈ CLOSED表 ， 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 27 寬度 優(yōu)先搜索算法 open := [S]。 add ( n, closed )； if n = goal then exit ( success )。 exit ( fail )。 remove ( first ( open ) )。 delete ( (?mi)( mi ∈ { mk } ∨ ( mi ∈ { ml } ) )。 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 34 盲目搜索算法應(yīng)用實例 ? 合法走步規(guī)則： 設(shè) (i0、 j0)為空格所在行列數(shù)值， Si0j0 = 0 R1: if j1≥1 then Si0j0:= Si0(j01), Si0(j01):=0 空格左移； R2: if i1≥1 then Si0j0:= S(i01)j0, S(i01)j0:=0 空格上移； R3: if j+1≤3 then Si0j0:= Si0(j0+1), Si0(j0+1):=0 空格右移； R4: if i+1≤3 then Si0j0:= S(i0+1)j0, S(i0+1)j0:=0 空格下移。 ? f *(n) = g* (n) + h* (n)： 從初始節(jié)點 s 出發(fā)，經(jīng)過 最佳路徑 上任意節(jié)點 n，到達目標節(jié)點 t 的 最小 費用。 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 39 啟發(fā)式 圖搜索算法 A 算 法 ? 定義 ： 按照 f (n) = g (n) + h (n) 估價函數(shù)值由小到大地排列待擴展節(jié)點順序的圖搜索算法，稱為 A 算法。 啟發(fā)式圖搜索算法 A算法 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 41 A算法 n 為目標 t ? 取當前節(jié)點 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)目標 t Return ( Fail ) A yes No yes No B Exit ( Success ) 輸出解徑 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 42 擴展 節(jié)點 n：生成 n的后繼節(jié)點；計算后繼節(jié)點的花費。 ? A*算法作用： 問題有解時， A*算法 一定能夠找到 從初始節(jié)點 s 到目標節(jié)點 t 的 最佳 解徑。 ? h: ? 估計當前路徑上節(jié)點到目標節(jié)點 還需要的費用 ，引導搜索向最有希望的路徑前進。 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 48 作業(yè) : 設(shè) h=0。 問題表示： (0, 0) 〉 (2, y) 要求定義合法的裝油規(guī)則，利用盲目搜索策略畫出狀態(tài)圖。 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 49 ? 給定兩個油桶 ,一個可裝 4 公斤油 ,一個可裝 3 公斤油 ,油桶上無任何度量標記。 北京航空航天大學軟件開發(fā)環(huán)境國家重點實驗室 Slide 47 作業(yè) : 利用寬度優(yōu)先法或深度優(yōu)先法，程序?qū)崿F(xiàn) Highway map 問題求解，只考慮節(jié)點的連接和變換 ,不考慮邊的權(quán)值 。 啟發(fā)式最佳 圖搜索算法 A*算法 ? A *算法應(yīng)用驗證 : ? 8數(shù)碼問題 A * 算法搜索實例。 ? 對于 {mk} ∈ {mi}: if f (n, mk) f (mk) then f (mk) := f (n, mk), mk n。 ?A算法應(yīng)用實例 : ? 普通有向圖 A 算法搜索實例 ； ? 8數(shù)碼問題 A 算法搜索實例 。 ? g* (n)： s→ n 最佳路徑 的 分段費用。 ? h (n) ： 迄今為止 從 節(jié)點 n 到目標節(jié)點 t 最佳分段路徑 將要花費 的 未知 估計費用 ， 是對 h* (n) 的一個估計， 可視為 啟發(fā)式分量函數(shù) ，有 h (n) ≥0。 exit ( fail )。
物理相關(guān)推薦
鄂ICP備17016276號-1