3問(wèn)題求解及搜索技術(shù)要點(diǎn)-copy北航6系人工智能課件-閱讀頁(yè)
2025-03-19 01:15本頁(yè)面
【正文】 Slide 35 寬度優(yōu)先策略 求解 8數(shù)碼問(wèn)題 ： 目標(biāo) R1 R2 R3 R2 R1 R2 R3 R2 R2 R3 R2 R4 R1 R3 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 36 深度優(yōu)先策略 求解 8數(shù)碼問(wèn)題： ? 說(shuō)明： ? 設(shè)規(guī)則固定使用順序： R1 左移、 R2上移、R3 右移、 R4下移； ? 設(shè)節(jié)點(diǎn)深度限制值： 6 ； 合法的走步規(guī)則 重復(fù)節(jié)點(diǎn) –造成循環(huán) 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 37 問(wèn)題求解基本原理 基于 狀態(tài)空間 的 啟發(fā)式 搜索算法 : A 算法； A* 算法 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 38 啟發(fā)式 圖搜索算法 ? 假設(shè)： ? f (n) = g (n) + h (n) – 任意節(jié)點(diǎn) n 的 評(píng)價(jià)函數(shù) ： 指 迄今為止 已 找到 的從初始節(jié)點(diǎn) s ，到達(dá)節(jié)點(diǎn) n，再?gòu)墓?jié)點(diǎn) n 到達(dá)目標(biāo)節(jié)點(diǎn) t 的路徑全程的最小費(fèi)用， 是對(duì) f *(n ) 的一個(gè)估計(jì)。 ? g (n) ： 迄今為止搜索到 的從 初始節(jié)點(diǎn) s 到當(dāng)前節(jié)點(diǎn) n 最佳路徑分段的已知費(fèi)用 ， 是對(duì) g* (n) 的一個(gè)估計(jì)。 ? h* (n)： n → t 最佳路徑 的 分段費(fèi)用 。 ? s： 初始節(jié)點(diǎn)； n： 當(dāng)前節(jié)點(diǎn)； t： 目標(biāo)節(jié)點(diǎn)。 ? A 算法流程 。 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 40 ? 算法中符號(hào)： s：初始節(jié)點(diǎn)； G：搜索圖的節(jié)點(diǎn)集合； OPEN表： 已生成但尚未被擴(kuò)展的節(jié)點(diǎn)序列表； CLOSED表： 已生成且已被擴(kuò)展的節(jié)點(diǎn)序列表； n： 待擴(kuò)展的當(dāng)前節(jié)點(diǎn)； {mi} = {mj} ∪ {mk}∪ {ml} ：擴(kuò)展 n 后生成的后繼節(jié)點(diǎn) 其中， mj：第一次生成的節(jié)點(diǎn)， mj ∈ OPEN 且 mj ∈ CLOSED 表， mk：在 OPEN表中出現(xiàn)過(guò)的待擴(kuò)展節(jié)點(diǎn)， ml：在 CLOSED表中出現(xiàn)過(guò)的已擴(kuò)展節(jié)點(diǎn)。 {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ì)于 {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é)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(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， 都滿(mǎn)足h（ n） ≤ h*（ n） ， 則稱(chēng)此時(shí)的 A 算法為 A* 算法 。 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(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一樣多。 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 45 8數(shù)碼問(wèn)題 搜索策略比較： 寬度優(yōu)先 A算法 A*算法 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 46 小結(jié) ? 啟發(fā)式搜索策略 ? g: ? 考慮當(dāng)前路徑 已經(jīng)花費(fèi)的費(fèi)用 ，及時(shí)拋棄已經(jīng)經(jīng)過(guò)的花費(fèi)太大且距目標(biāo)仍遠(yuǎn)的路徑 。 ? A 算法 ： 定義估計(jì)函數(shù)： f = g + h； ? A* 算法 ： 定義估計(jì)函數(shù)： f = g + h； 滿(mǎn)足 h（ n） ≤ h*（ n）。求出有向圖的一條解徑 ,給出求解過(guò)程（ Open， Closed內(nèi)容）。 f=g=邊的標(biāo)記值， 程序求解 Highway map 問(wèn)題，求出最短解徑，給出求解過(guò)程（ Open， Closed內(nèi)容）。問(wèn)：怎樣才能使 4 公斤油桶里恰好只裝 2 公斤油？ 設(shè)狀態(tài)定義 ： (x,y)，其中， x： 4 公斤油桶中實(shí)際裝油公斤數(shù)； y： 3 公斤油桶中實(shí)際裝油公斤數(shù)。 作業(yè) : 北京航空航天大學(xué)軟件開(kāi)發(fā)環(huán)境國(guó)家重點(diǎn)實(shí)驗(yàn)室 Slide 50 演講完畢，謝謝觀看！
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1