[計(jì)算機(jī)軟件及應(yīng)用]人工智能課件-wenkub.com
2025-01-16 17:29 本頁(yè)面
【正文】 ?顯然，兩個(gè)模式對(duì)應(yīng)的轉(zhuǎn)換步數(shù)，是原問(wèn)題的下界。 ? 注意：將松弛問(wèn)題作為啟發(fā)函數(shù)時(shí)，應(yīng)保證容易求解。 ? 以八數(shù)碼為例。 20 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 思 考 題 尋找從城市 A到城市 G的最短路徑 21 啟發(fā)函數(shù) h(n) 城市 到 G的直線距離 A 300 B 210 C 150 D 165 E 80 F 120 G 0 尋找從城市 A到城市 G的最短路徑 22 啟發(fā)函數(shù) h(n) 城市 到 G的直線距離 A 300 B 210 C 150 D 165 E 80 F 120 G 0 A*搜索搜索最短路徑的過(guò)程 23 g(A)=0 h(A)=300 f(A)=300 270+210 =480 A B C D A 245+150 =395 265+165 =430 (a) 初始狀態(tài) (b) 擴(kuò)展 A之后 考慮將 A*搜索用于樹搜索。 ? (2) ?suc? T, suc在 OPEN表，則更新 f(suc)；若 suc在CLOSED表，則不做任何操作；否則，將 f(suc)賦予suc并放入 OPEN表； ? (3) OPEN?OPEN?T, CLOSED?CLOSED?{node} 。 具有單調(diào)性的啟發(fā)函數(shù)的 A* 啟發(fā)函數(shù)具有 單調(diào)性 的 A*搜索算法的執(zhí)行過(guò)程描述： ? ： ? OPEN={初始狀態(tài) s}， CLOSED=? 。 h(n)滿足以下條件就是一致的：對(duì)于每個(gè)結(jié)點(diǎn) n，通過(guò)任何行動(dòng) a生成的 n的每個(gè)后繼結(jié)點(diǎn) n‘，滿足下列三角不等式： h(n) ≤ cost(n, a, n‘) + h(n‘)。 G‘是解，故h(G’)=0， f(G‘)=g(G’)+h(G‘)=g(G’) C* 。 ? 根據(jù) A*定義， 所有 A*搜索都是可納的 。 h(n)越小 ，代表 n越有希望好 。顯然， 5 ≤ “實(shí)際需要的最少步數(shù)”，滿
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1