【正文】 必須超過解的長度 . 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索 4。 啟發(fā)式搜索使用關(guān)于領(lǐng)域的信息指導(dǎo)， 使搜索向著有利于獲得解的方向進(jìn)展。 根據(jù)啟發(fā)函數(shù)對尚為探索的節(jié)點進(jìn)行排序， 把最有希望的節(jié)點排再前面， 在擴(kuò)展節(jié)點時把最有希望的節(jié)點拿出來考慮。 通常使用的評價函數(shù)為： f(n)=g(n)+h(n) g*(n) 初始節(jié)點到節(jié)點 n 的距離 . h*(n) 節(jié)點 n 到目標(biāo)節(jié)點 g 的距離 . f*(n)=g*(n)+h*(n), 從初始節(jié)點到目標(biāo)節(jié)點 g 的距離 . f(n),g(n),h(n)分別是 f*(n), g*(n), h*(n)的估計值 . 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 ? A算法 ? Procedure A ? 1 G=s, OPEN=(s), CLOSED = (). ? 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) ? 3 n=FIRST(OPEN)。 ? 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 7 建立和調(diào)整指針 , 計算各節(jié)點的 f 值 . 并按各點的 f值調(diào)整指針 . ? 7 把 OPEN表中的節(jié)點按 f值從小到大排序 . ? 8 GO LOOP 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 4 1+5=6 1+3=4 1+5=6 1 2 3 8 4 7 6 5 目標(biāo)狀態(tài) h 值是偏離目標(biāo)位置的塊數(shù) W(n) 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 4 5 Goal node 6 s4 A6 B4 C6 D5 E5 F6 G6 H7 I5 J7 K5 L5 M7 7 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 初始化 . Open = [s4]。 closed = [s4] 2. 測試 B4, Open = [D5, E5,A6, C6, F6]。 closed = [s4, B4, D5] 4. 測試 E5, Open = [I5,A6, C6, F6,G6, H7, J7]。 closed = [s4, B4, D5,E5, I5] 6. 測試 K5, Open = [L5,A6, C6, F6,G6, H7, J7, M7]。 如果狀態(tài)空間的圖搜索問題存在解路徑， 搜索算法 f 一定能找到該問題的最優(yōu)解路徑， 則稱算法 f 是可采納的。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 A*算法是可采納的 若存在從初始節(jié)點 s到目標(biāo)節(jié)點 t的路徑， 則 A*算法必能找到最佳解路徑。 和前面舉例的 f(n) = g(n) + h(n)中， h(n)取為偏離目標(biāo)位置的塊數(shù)， 滿足 h(n) ≦ h*(n) ，也是可采納的。 這個條件就是單調(diào)性。 對于所有的狀態(tài) ni和 nj， 其中 nj是 ni的后繼 h(ni) h(nj) ≦ cost(ni, nj) cost(ni, nj)是節(jié)點 ni和 nj之間的實際最小費用 2。 如果 h2(n) 比 h1(n)有更高的信息度， 則算法 2所擴(kuò)展的節(jié)點一定會被算法 1所擴(kuò)展， 換句話說， 算法 2所擴(kuò)展的節(jié)點比算法 1擴(kuò)展的節(jié)點少。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 7 8 4 6 5 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 4 5 Goal node 6 G6 H7 I5 P=5 f=5 P=2 f=7 P=6 f=7 P=4 f=5 P=6 f=7 P=5 f=7 P=3 f=5 P=5 f=7 P=2 f=5 P=4 f=7 P=1 f=5 P=0 f=5 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 (5,5,1) (4,4,0) (5,2,0) (5,3,0) (5,4,0) (5,3,1) (5,4,1) (5,0,0) (5,1,0) (3,3,0) (5,1,1) (5,2,1) (4,4,1) (0,3,0) (3,3,1) (2,2,0) h(n)=0 圖雖然簡單 , 但包括許多經(jīng)仔細(xì)考慮后的剪忮 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 迷宮問題 求從入口到出口通過迷宮的最短路徑 入口 出口 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 迷宮問題 入口 (1,1) 出口 (4,4) 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 問題描述 R1: if (x,y) then (x+1,y) R2: if (x,y) then (x,y1) R1: if (x,y) then (x1,y) R1: if (x,y) then (x,y+1) h(n)= |Xgxn|+|Ygyn| 其中 (Xg,Yg)為目標(biāo)點坐標(biāo) , ( xn,yn)為節(jié)點 n的坐標(biāo) , 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 (1,1) (1,2) (1,3) (2,3) (2,2) (2,4) (3,4) (1,4) (2,1) (3,2) (3,1) (3,3) (4,1) (4,2) (4,3) (4,4) 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 (1,1) (2,3) (2,2) (2,4) (1,4) (3,2) (3,4) (3,3) (4,2) (4,3) (4,4) h=3 f=6 h=6 f=6 7 2 1 h=2 f=6 3 h=4 f=8 3 h=3 f=8 h=1 f=6 h=2 f=8 h=1 f=8 h=0 f=8 h=3 f=10 h=2 f=10 4 5 6 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 評價函數(shù)的啟發(fā)能力由以下 3 因素決定 1. 解路徑的費用 . 2. 求解過程中擴(kuò)展節(jié)點的個數(shù) . 3. 計算 h所需要的工作量 . 有時使用 f = g +wh 有時以犧牲可采納性為代價 , 獲得強(qiáng)的啟發(fā)能力 . 顯然解路徑越長， 找到解路徑所需要的計算費用就越大。根據(jù)前面幾節(jié)的介紹， 我們知道如果啟發(fā)函數(shù)滿足 h(n)≦h*(n), 即使用 A*算法， 則只要被搜索的圖有解，算法肯定能找到最佳解路徑。算法在尋找解路徑的過程中所需要擴(kuò)展的節(jié)點數(shù)也是影響效率的一個重要因素。因此， 有時為了增加算法的啟發(fā)能力， 我們采用較大的啟發(fā)函數(shù)值， 甚至于不滿足 h(n)≦h*(n) ，這樣做犧牲了算法的可采納性， 但可以使算法擴(kuò)展的節(jié)點個數(shù)大幅度下降，換來了算法的高效率。但這時啟發(fā)函數(shù)的計算量也就越大。因此， 在解決實際問題時，我們需要在啟發(fā)函時的計算量和擴(kuò)展節(jié)點的數(shù)量之間作認(rèn)真的權(quán)衡。這時評價函數(shù)變成 f = g + w*h, 如果 w很大， 相當(dāng)于 g(n)≡0. 有些問題只要求我們找出解路徑， 不考慮解路徑的費用，對于這類問題，我們可以完全不考慮 g 對求解的影響，采用 f = w*h式的評