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