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