14啟發(fā)式圖搜索-文庫吧資料
2024-10-05 23:08本頁面
【正文】 從起點(diǎn)到n的代價(jià)值 。這種信息可能與八數(shù)碼魔方問題中的函數(shù) W(n)所用的那種信息相似 。 A算法的引入： g(n)的計(jì)算方法： ? g(n)就是在搜索樹中從 S到 n這段路徑的代價(jià) ， 這一代價(jià)可以由從 n到 S尋找指針時(shí) ， 把所遇到的各段弧線的代價(jià)加起來給出 (這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價(jià)路徑 )。如果說詳細(xì)點(diǎn)， g(n)代表了搜索的寬度優(yōu)先趨勢。 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à)。 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)先算法有時(shí)無法得到最優(yōu)解，因?yàn)樗墓纼r(jià)函數(shù) f的選取時(shí)，忽略了從初始節(jié)點(diǎn)到目前節(jié)點(diǎn)的代價(jià)值。 F(6) G(5) H(3) E(4) A(2) B(0) 1 2 3 4 5 C(3) 6 ? 舉例： 八數(shù)碼魔方（ 8puzzle problem） 1 2 3 8 4 5 6 7 （目標(biāo)狀態(tài)） 1 2 3 8 4 5 6 7 （初始狀態(tài)） 5 7 ① ④ ⑤ ⑥ ③ 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) ② 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1