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