3問題求解及搜索技術(shù)要點(diǎn)-copy北航6系人工智能課件(編輯修改稿)
2025-03-27 01:15 本頁面
【文章內(nèi)容簡介】 狀態(tài)空間 的 搜索技術(shù)： 有關(guān)搜索概念 盲目搜索策略 啟發(fā)式 搜索策略 問題求解基本原理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 21 狀態(tài)空間 搜索 有關(guān)概念 ?狀態(tài) 圖 特點(diǎn)： 多條路徑通向同一節(jié)點(diǎn)。例： E 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 22 狀態(tài)空間 搜索 有關(guān)概念 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 23 狀態(tài)空間 搜索有關(guān)概念 ? 節(jié)點(diǎn)深度 ： 根節(jié)點(diǎn) 的 深度 為 0， 其它節(jié)點(diǎn) 的 深度 規(guī)定為其父節(jié) 點(diǎn)的深度加 1，即 dn+1 = dn + 1 。 ? 標(biāo)記節(jié)點(diǎn) n： 用 指針 將后繼節(jié)點(diǎn) 連接 到父節(jié)點(diǎn) n 的操作 。 ? 節(jié)點(diǎn) ： 對應(yīng)狀態(tài)圖中有關(guān) 狀態(tài) 的描述。 ? 擴(kuò)展節(jié)點(diǎn) n：稱 生成 節(jié)點(diǎn) n 的所有 后繼節(jié)點(diǎn) 并 計(jì)算 生成這些后繼節(jié)點(diǎn)所造成的 花費(fèi) 的過程（ 即，計(jì)算各后繼節(jié)點(diǎn)的優(yōu)劣且將其連接到節(jié)點(diǎn) n 等操作造成的開銷 ）叫做 擴(kuò)展節(jié)點(diǎn) n 。 ? 后繼節(jié)點(diǎn) ： 稱將規(guī)則作用于節(jié)點(diǎn) n 生成 的新節(jié)點(diǎn)為節(jié)點(diǎn) n 的 后 繼節(jié)點(diǎn)。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 24 ? 路徑 ： 對于一個(gè)節(jié)點(diǎn)序列（ n0, n1, …, n l, …, n k），如若每一節(jié)點(diǎn) ni1都有一個(gè)后繼節(jié)點(diǎn) ni（ i = 1, 2, …, k ），則稱該節(jié)點(diǎn)序列為一條從節(jié)點(diǎn) n0 到節(jié)點(diǎn) nk、長度為 k 的路徑；路徑還可表示為與節(jié)點(diǎn)序列對應(yīng)的規(guī)則序列 。 狀態(tài)空間 搜索有關(guān)概念 ? 路徑花費(fèi) ： 設(shè) C（ ni， nj）為節(jié)點(diǎn) ni 到 nj 這段路徑（或弧線）的花費(fèi)。一條路徑的花費(fèi)等于連接這條路徑各節(jié)點(diǎn)間所有弧線花費(fèi)值的總和。路徑 ni → n j → t 的花費(fèi)值 C（ ni， t）可遞歸計(jì)算如下 : C（ ni， t） = C (ni， nj) + C（ nj， t )。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 25 基于 狀態(tài)空間 的 盲目 搜索算法 : 寬 度優(yōu)先搜索策略 深 度優(yōu)先搜索策略 問題求解基本原理 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 26 盲目搜索 算法的 符號 及 數(shù)據(jù)結(jié)構(gòu) s： 初始節(jié)點(diǎn)； n： 當(dāng)前節(jié)點(diǎn) 。 open： 已被生成 但 未被擴(kuò)展 的節(jié)點(diǎn)序列表； closed： 已被生成 且 已被擴(kuò)展 的節(jié)點(diǎn)序列表； {mi} = {mj} ∪ {mk}∪ {ml} ： 擴(kuò)展 n 后所得的 n 的 后繼節(jié)點(diǎn) 其中， { mk }： 在 OPEN表中出現(xiàn)過的 待擴(kuò)展節(jié)點(diǎn) ， { ml }： 在 CLOSED表中出現(xiàn)過的 已擴(kuò)展節(jié)點(diǎn) 。 { mj }： 第一次生成 的節(jié)點(diǎn) ， mj ∈ OPEN 且 mj ∈ CLOSED表 ， 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 27 寬度 優(yōu)先搜索算法 open := [S]。 closed := [ ]。 while open ≠ [ ] do { n := first ( open )。 remove ( first ( open ) )。 add ( n, closed )； if n = goal then exit ( success )。 expand ( n ) { mi }。 delete ( (?mi)( mi ∈ { mk } ∨ ( mi ∈ { ml } ) )。 add ( open, mj) }。 exit ( fail )。 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 28 寬度 優(yōu)先搜索算法 S, A, D A, D, B, D D, B, A, E ……… Open 表為 隊(duì) 操 作 ： 先進(jìn)先出！ 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 29 G 節(jié)點(diǎn) 擴(kuò)展順序 寬度 優(yōu)先搜索算法 北京航空航天大學(xué)軟件開發(fā)環(huán)境國家重點(diǎn)實(shí)驗(yàn)室 Slide 30 open := [S]。 closed := [ ]。 d = 深度限制值 while open ≠ [ ] do { n := first ( open )。 remove ( first ( open ) )。 add ( n, closed )； if n = goal then exit ( success )。 if depth ( n ) d th
物理相關(guān)推薦
鄂ICP備17016276號-1