[計(jì)算機(jī)軟件及應(yīng)用]人工智能課件-文庫吧
2025-01-04 17:29 本頁面
【正文】 N表，并更新 f(suc)； ? (3) 跳轉(zhuǎn)到 ” ”. 一般的啟發(fā)式搜索算法 ? 搜索算法的不同，歸根結(jié)底在于，對 OPEN表節(jié)點(diǎn)擴(kuò)展順序的策略不同。 ? OPEN表節(jié)點(diǎn)擴(kuò)展策略一般受制于一下因素： – 稱為 評價(jià)函數(shù) 的 f(n) 。其中， n可以是任意節(jié)點(diǎn)。一般地， f(n) 有實(shí)際意義，如表示 代價(jià) 或 耗散 時(shí)，值越小越好。 – 選擇下一個節(jié)點(diǎn)時(shí)考慮 OPEN表哪些節(jié)點(diǎn)。 ? 一般地，評價(jià)函數(shù)定義為 f(n) = g(n) + h(n) – 搜索算法或許已發(fā)現(xiàn)多條從初始節(jié)點(diǎn) s到 節(jié)點(diǎn) n 的路徑， 它們的最小 代價(jià) 為 g(n) 。 – 雖然 從節(jié)點(diǎn) n到 任一 目標(biāo)節(jié)點(diǎn) g的所有路徑的最小代價(jià)尚不知道，但是可由領(lǐng)域知識對其作出估計(jì)，通過啟發(fā)函數(shù) h(n)實(shí)現(xiàn)。 – 于是， f(n)表示 從初始節(jié)點(diǎn) s經(jīng) 由 節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn) g的最優(yōu)路徑的代價(jià) 估計(jì) 值 。 ? 啟發(fā)式搜索 是 OPEN表是優(yōu)先隊(duì)列的搜索 。 啟發(fā)式搜索算法舉例 ? 八數(shù)碼 ? f(n) = g(n) + h(n)的選取 ?g(n) = “x所在的搜索深度”； ?h(n) = “x與 sg相比，錯位數(shù)字的數(shù)目”。 ? 錯位數(shù) h(n) = 5。顯然， 5 ≤ “實(shí)際需要的最少步數(shù)”，滿足 h(n) ≤ h*(n)。 11 2 8 3 1 5 7 6 4 1 2 3 8 4 7 6 5 目標(biāo)狀態(tài) sg 當(dāng)前狀態(tài) x 貪婪搜索 ? 啟發(fā)式搜索也稱最佳優(yōu)先搜索。 ? 貪婪搜索 或 貪婪最佳優(yōu)先搜索 ： – f(n) = h(n) – 若 n是目標(biāo)節(jié)點(diǎn)，則 h(n)=0。 ? 啟發(fā)函數(shù) h(n)基于 領(lǐng)域知識 ，前瞻（或猜測）從當(dāng)前節(jié)點(diǎn)抵達(dá)任意目標(biāo)節(jié)點(diǎn)的最小代價(jià)。 h(n)越小 ，代表 n越有希望好 。 可納性、單調(diào)性、信息度 A*搜索 ? 若一個啟發(fā)式搜索：對任意節(jié)點(diǎn) n， h(n) ? h*(n)，且對所有目標(biāo)節(jié)點(diǎn) g有 h(g)=0，則稱之為 A*搜索 。 ? 可納
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1