【正文】 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 5. 最佳圖搜索算法 A* 在啟發(fā)式搜索中使用評(píng)估函數(shù) f(n) = g(n) + h(n) 其中， g(n) 是從初始狀態(tài)到 n 費(fèi)用； h(n)是從 n 到目標(biāo)的啟發(fā)式估計(jì)費(fèi)用 把使用這種估值函數(shù)的啟發(fā)式程序叫做 A算法。 如果狀態(tài)空間的圖搜索問(wèn)題存在解路徑， 搜索算法 f 一定能找到該問(wèn)題的最優(yōu)解路徑， 則稱(chēng)算法 f 是可采納的。 如果在 A算法中使用的啟發(fā)函數(shù)滿(mǎn)足 h(n) ≦ h*(n) 則稱(chēng)之為 A* 算法。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 A*算法是可采納的 若存在從初始節(jié)點(diǎn) s到目標(biāo)節(jié)點(diǎn) t的路徑， 則 A*算法必能找到最佳解路徑。 例如， 在寬度優(yōu)先搜索中， h(n) ≦ 0 ，滿(mǎn)足 h(n) ≦ h*(n) ， 是可采納的。 和前面舉例的 f(n) = g(n) + h(n)中， h(n)取為偏離目標(biāo)位置的塊數(shù)， 滿(mǎn)足 h(n) ≦ h*(n) ，也是可采納的。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 單調(diào)性 在算法 A 中， g(n)是 g*(n) 的估計(jì)值， 定義為在已經(jīng)產(chǎn)生的節(jié)點(diǎn)中從初始節(jié)點(diǎn)到 n 的最短路徑的費(fèi)用， 在算法進(jìn)行的過(guò)程中， 我們需要不斷地計(jì)算， 比較和調(diào)整這條最短路徑， 這要消耗大量的計(jì)算時(shí)間，因而也影響算法的效率，如果能對(duì)啟發(fā)函數(shù)增加某些限制條件， 使得在這種限制條件下，理論上就可以證明 g(n) 就是 g*(n), 則為獲得 g(n)所需要的計(jì)算就可以省略了。 這個(gè)條件就是單調(diào)性。 定義： 單調(diào)性 啟發(fā)函數(shù)單調(diào)的條件是： 1。 對(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。 h(goal) = 0 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 啟發(fā)函數(shù)的比較 設(shè)有兩個(gè)算法， 分別使用兩個(gè)啟發(fā)函數(shù) 算法 1， f1(n) = g1(n) + h1(n) 算法 2， f2(n) = g2(n) + h2(n) 哪一個(gè)更好一些呢？ 定義 信息度 對(duì)于兩個(gè) A*啟發(fā)式函數(shù) h1(n)和 h2(n)， 如果對(duì)于搜索空間中的所有的節(jié)點(diǎn) n, 都有 h1(n) ≦ h2(n) 則稱(chēng) h2(n) 比 h1(n)有更高的信息度。 如果 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ù)系 8. A*算法的應(yīng)用舉例 . (1) 8 數(shù)碼問(wèn)題 h(n) = P(n), P(n)為每一方塊與目標(biāo)位置的距離的總和 . (2) 傳教士與野人問(wèn)題 h(n)=0 h(n)=M+C h(n)=M+C2B 傳教士與野人渡河問(wèn)題：有 N 個(gè)傳教士帶 N 個(gè)野人渡河，河的岸邊有一條船， 每次最多可載 K 人，要求無(wú)論在河的哪一邊，或是在船上，野人的數(shù)目不能超過(guò)傳教士的數(shù)目，問(wèn)為安全起見(jiàn)， 應(yīng)如何安排傳教士與野人渡河？ N=5， K=3。 人工智能 吉林大學(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ù)系 迷宮問(wèn)題 求從入口到出口通過(guò)迷宮的最短路徑 入口 出口 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 迷宮問(wèn)題 入口 (1,1) 出口 (4,4) 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 問(wèn)題描述 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)用就越大。 所以，在條件允許的情況下， 我們希望找到費(fèi)用最低的解路徑，即最佳解路徑。根據(jù)前面幾節(jié)的介紹， 我們知道如果啟發(fā)函數(shù)滿(mǎn)足 h(n)≦h*(n), 即使用 A*算法， 則只要被搜索的圖有解，算法肯定能找到最佳解路徑。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 解路徑的費(fèi)用（長(zhǎng)度）并不是影響算法的唯一因素。算法在尋找解路徑的過(guò)程中所需要擴(kuò)展的節(jié)點(diǎn)數(shù)也是影響效率的一個(gè)重要因素。所需要擴(kuò)展的節(jié)點(diǎn)數(shù)少，說(shuō)明算法引導(dǎo)搜索集中向目標(biāo)節(jié)點(diǎn)的方向發(fā)展， 當(dāng)然有利于較快地找到解。因此， 有時(shí)為了增加算法的啟發(fā)能力， 我們采用較大的啟發(fā)函數(shù)值， 甚至于不滿(mǎn)足 h(n)≦h*(n) ，這樣做犧牲了算法的可采納性， 但可以使算法擴(kuò)展的節(jié)點(diǎn)個(gè)數(shù)大幅度下降，換來(lái)了算法的高效率。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 在構(gòu)造啟發(fā)函數(shù)時(shí)， 如果函數(shù)包含的啟發(fā)信息越多， 對(duì)算法在 OPEN表中節(jié)點(diǎn)的排序越準(zhǔn)確，總能把最有希望獲得解的節(jié)點(diǎn)優(yōu)先選出來(lái)擴(kuò)展。但這時(shí)啟發(fā)函數(shù)的計(jì)算量也就越大。最理想的啟發(fā)函數(shù) h在搜索圖中每一個(gè)節(jié)點(diǎn)上的取值都與該節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的實(shí)際費(fèi)用 h*相同，但這樣的啟發(fā)函數(shù)需要大量的計(jì)算，使算法的效率反而下降。因此， 在解決實(shí)際問(wèn)題時(shí)，我們需要在啟發(fā)函時(shí)的計(jì)算量和擴(kuò)展節(jié)點(diǎn)的數(shù)量之間作認(rèn)真的權(quán)衡。 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 對(duì)于一個(gè)給定的啟發(fā)函數(shù)， 可以通過(guò)對(duì)該函數(shù)乘以一個(gè)大于 1的正數(shù) w的方法增加它的啟發(fā)能力。這時(shí)評(píng)價(jià)函數(shù)變成 f = g + w*h, 如果 w很大， 相當(dāng)于 g(n)≡0. 有些問(wèn)題只要求我們找出解路徑， 不考慮解路徑的費(fèi)用，對(duì)于這類(lèi)問(wèn)題，我們可以完全不考慮 g 對(duì)求解的影響，采用 f = w*h式的評(píng)價(jià)函數(shù)。 使 w隨搜索樹(shù)的節(jié)點(diǎn)深度成反比變化 , 可提高搜索效率 . 人工智能 吉林大學(xué)珠海學(xué)院計(jì)算機(jī)科學(xué)與技術(shù)系 演講完畢，謝謝觀看！