14啟發(fā)式圖搜索(參考版)
2024-10-01 23:08本頁面
【正文】 定義 3 采用 h*(x)的下界 h(x)為啟發(fā)函數(shù)的 A算法，稱為 A*算法。 估價函數(shù) f 定義為： f(n)=g(n)+h(n) —— g是 g*的估計 ， h是 h*的估計 定義 1 在圖搜索過程中，如果重排 OPEN表是依據(jù)f(x)=g(x)+h(x)進行的，則稱該過程為 A算法。 1 2 3 8 4 5 6 7 g (n) h (n) A*（ A*算法） ? 在 A算法中，如果滿足條件： h(n)≤h*(n) 則 A算法稱為 A*算法。 ? 舉例： 八數(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 (1+3=4) (1+5=6) (1+5=6) ② 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (2+4=6) (2+3=5) (2+3=5) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3+2=5) (3+4=7) 1 2 3 8 4 5 6 7 1 2 3 8 4 5 6 7 (3+3=6) (3+4=7) 1 2 3 8 4 5 6 7 (4+1=5) 8 1 3 2 4 5 6 7 1 2 3 8 4 5 6 7 (5+0=5) (5+2=7) 八數(shù)碼魔方的 A算法搜索樹 1 2 3 8 4 6 (0+4=4) ⑦ 搜索得到的路徑如黃線所示 ? 本題采用的估價函數(shù)為： f (n)=g (n)+W (n) 其中： W (n)用來計算對應(yīng)于節(jié)點 n的數(shù)據(jù)庫中錯放的棋子個數(shù)； g (n)為
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1