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