14啟發(fā)式圖搜索(編輯修改稿)
2024-11-02 23:08 本頁面
【文章內(nèi)容簡介】 5 6 7 1 2 3 8 4 5 6 7 (2) (4) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (4) 1 2 3 8 4 5 6 7 (1) 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 (0) (2) 八數(shù)碼魔方的最佳優(yōu)先搜索樹 1 2 3 8 4 6 (4) ⑦ 搜索得到的路徑如黃線所示 ? 本題采用了簡單的估價(jià)函數(shù) f(n)=W(n) 其中： W(n)用來計(jì)算對應(yīng)于節(jié)點(diǎn) n的數(shù)據(jù)庫中錯放的棋子個數(shù) 。 因此 ， 初始節(jié)點(diǎn)棋局 的 f(n)值等于 4。 1 2 3 8 4 5 6 7 ? 第 ② 步有三種情況 ,我們選擇其中f(n)最小的 : ? 其它依次類推 .最后用了 7步得出了結(jié)果 . 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3) (5) (5) ? 3. A算法 ? 最佳優(yōu)先算法有時無法得到最優(yōu)解，因?yàn)樗墓纼r(jià)函數(shù) f的選取時，忽略了從初始節(jié)點(diǎn)到目前節(jié)點(diǎn)的代價(jià)值。所以，可考慮每個節(jié)點(diǎn) n的估價(jià)函數(shù) f(n)分為兩個分量：從起始節(jié)點(diǎn)到節(jié)點(diǎn) n的代價(jià) g(n)以及從節(jié)點(diǎn) n到達(dá)目標(biāo)節(jié)點(diǎn)代價(jià)的估算值 h(n)。 f(n)=g(n)+h(n) ? f(n)——節(jié)點(diǎn) n的估價(jià)函數(shù)； g(n)——評價(jià)函數(shù)， 從初始節(jié)點(diǎn) S到 n節(jié)點(diǎn)的實(shí)際代價(jià)； h(n)——啟發(fā)函數(shù)， 從 n到目標(biāo)節(jié)點(diǎn) Sg最佳路徑的估計(jì) 代價(jià)。 ? 這里 h(n)體現(xiàn)了搜索的啟發(fā)信息，因?yàn)?g(n)是已知的。如果說詳細(xì)點(diǎn)， g(n)代表了搜索的寬度優(yōu)先趨勢。但是當(dāng) h(n)??g(n) 時，可以省略 g(n),而提高效率。 A算法的引入： g(n)的計(jì)算方法： ? g(n)就是在搜索樹中從 S到 n
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1