3問題求解及搜索技術(shù)要點(diǎn)-copy-北航6系人工智能課件-資料下載頁
2025-07-24 06:41本頁面
【正文】 ∈ OPEN 且 mj ∈ CLOSED 表， mk：在 OPEN表中出現(xiàn)過的待擴(kuò)展節(jié)點(diǎn)， ml：在 CLOSED表中出現(xiàn)過的已擴(kuò)展節(jié)點(diǎn)。 啟發(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)；計(jì)算后繼節(jié)點(diǎn)的花費(fèi)。 {mi} := Expand(n), 計(jì)算 : f (n, mi) := g(n,mi) + h(mi) 比較花費(fèi)，修改 連接標(biāo)記 ? 對(duì)于 {mj} ∈ {mi}: OPEN:= OPEN ∪ {mj} , mj n。 ? 對(duì)于 {mk} ∈ {mi}: if f (n, mk) f (mk) then f (mk) := f (n, mk), mk n。 ? 對(duì)于 {ml} ∈ {mi}: if f (n, ml) f (ml) then f (ml) := f (n, ml), ml n, OPEN:= OPEN ∪ {ml} 將 OPEN表中節(jié)點(diǎn)按 f 值 從小到大重新排序 A B 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 43 啟發(fā)式最佳 圖搜索算法 A*算法 ? A*算法定義： 若將 A算法中評(píng)價(jià)函數(shù) f (n)的啟發(fā)式分量函數(shù) h（ n） 的值限制在 h*（ n） 的下界范圍內(nèi) ， 亦即對(duì)所有節(jié)點(diǎn) n， 都滿足h（ n） ≤ h*（ n） ， 則稱此時(shí)的 A 算法為 A* 算法 。 ? A*算法作用： 問題有解時(shí)， A*算法 一定能夠找到 從初始節(jié)點(diǎn) s 到目標(biāo)節(jié)點(diǎn) t 的 最佳 解徑。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 44 ? 信息度 定理： 有兩個(gè) A*算法 A1和 A2, 若 A2比 A1有較多的啟發(fā)式信息（即對(duì)所有非目標(biāo)節(jié)點(diǎn)均有： h1（ n） ≤ h2（ n） ≤ h*（ n）），則在具有一條從 s 到 t 的隱含狀態(tài)圖上，搜索結(jié)束時(shí)，由 A2擴(kuò)展的每一個(gè)節(jié)點(diǎn)，也必定由 A1所擴(kuò)展，即 A1擴(kuò)展的節(jié)點(diǎn)數(shù)至少和 A2一樣多。 啟發(fā)式最佳 圖搜索算法 A*算法 ? A *算法應(yīng)用驗(yàn)證 : ? 8數(shù)碼問題 A * 算法搜索實(shí)例。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 45 8數(shù)碼問題 搜索策略比較： 寬度優(yōu)先 A算法 A*算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 46 小結(jié) ? 啟發(fā)式搜索策略 ? g: ? 考慮當(dāng)前路徑 已經(jīng)花費(fèi)的費(fèi)用 ，及時(shí)拋棄已經(jīng)經(jīng)過的花費(fèi)太大且距目標(biāo)仍遠(yuǎn)的路徑 。 ? h: ? 估計(jì)當(dāng)前路徑上節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn) 還需要的費(fèi)用 ，引導(dǎo)搜索向最有希望的路徑前進(jìn)。 ? A 算法 ： 定義估計(jì)函數(shù)： f = g + h； ? A* 算法 ： 定義估計(jì)函數(shù)： f = g + h； 滿足 h（ n） ≤ h*（ n）。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 47 作業(yè) : 利用寬度優(yōu)先法或深度優(yōu)先法，程序?qū)崿F(xiàn) Highway map 問題求解，只考慮節(jié)點(diǎn)的連接和變換 ,不考慮邊的權(quán)值 。求出有向圖的一條解徑 ,給出求解過程（ Open， Closed內(nèi)容）。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 48 作業(yè) : 設(shè) h=0。 f=g=邊的標(biāo)記值， 程序求解 Highway map 問題，求出最短解徑，給出求解過程（ Open， Closed內(nèi)容）。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 49 ? 給定兩個(gè)油桶 ,一個(gè)可裝 4 公斤油 ,一個(gè)可裝 3 公斤油 ,油桶上無任何度量標(biāo)記。問：怎樣才能使 4 公斤油桶里恰好只裝 2 公斤油？ 設(shè)狀態(tài)定義 ： (x,y)，其中， x： 4 公斤油桶中實(shí)際裝油公斤數(shù)； y： 3 公斤油桶中實(shí)際裝油公斤數(shù)。 問題表示： (0, 0) 〉 (2, y) 要求定義合法的裝油規(guī)則，利用盲目搜索策略畫出狀態(tài)圖。 作業(yè)
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1