【正文】 有向圖 G是一個偶對 (N, E), 其中 N 是節(jié)點集合， E是有向弧的集合。 圖論中研究的有向圖是有限的，我們可以把有向圖全部畫出來。而我們對狀態(tài)空間搜索解的過程是邊產(chǎn)生圖邊求解， 這里所產(chǎn)生的圖是表示狀態(tài)空間的無限圖的顯式部分， 從求解的效率 考慮， 就有把這個無限圖的顯式部分向哪個方向以何種方式擴展的問題。 由 n循指針返回 s, 可以獲得解路徑 . 6. EXPAND(n)→mi, G=ADD(mi, G), 子節(jié)點集 {mi}中不包含 n的父輩節(jié)點 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 7 標記和修改指針 ADD(mj, OPEN), 并標記 mj連接到 n的指針 , mj是未在 OPEN和 CLOSED中出現(xiàn)過的子節(jié)點 . 計算是否需要修改 mk, ml到 n的指針 。 6 6 EXPAND(n)→{mi}, G=ADD(mi, G)。如果應(yīng)用得好，可以明顯地縮小搜索空間， 提高搜索效率 例如， 在九宮游戲中使用啟發(fā)式搜索， 就可以顯著地減少搜索空間 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 MIN MAX 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 在九宮游戲中使用啟發(fā)式搜索： 使用啟發(fā)函數(shù) h(s) = MAX 已投下的子可以占據(jù)的行， 列和對角線數(shù) 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 MIN MAX 5 4 4 3 2 4 3 4 4 4 5 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 啟發(fā)式搜索算法 最佳優(yōu)先搜索。 ? 4 IF 4 IF GOAL(n) THEN EXIT(SUCCESS)。 closed = [] 1. 測試 s4, Open = [B4, A6, C6]。 closed = [s4, B4, D5,E5] 5. 測試 I5, Open = [K5,A6, C6, F6,G6, H7, J7]。 如果在 A算法中使用的啟發(fā)函數(shù)滿足 h(n) ≦ h*(n) 則稱之為 A* 算法。 人工智能 吉林大學(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)所需要的計算就可以省略了。 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)有更高的信息度。 所以，在條件允許的情況下， 我們希望找到費用最低的解路徑，即最佳解路徑。所需要擴展的節(jié)點數(shù)少，說明算法引導(dǎo)搜索集中向目標節(jié)點的方向發(fā)展， 當然有利于較快地找到解。最理想的啟發(fā)函數(shù) h在搜索圖中每一個節(jié)點上的取值都與該節(jié)點到目標節(jié)點的實際費用 h*相同，但這樣的啟發(fā)函數(shù)需要大量的計算，使算法的效率反而下降。 使 w隨搜索樹的節(jié)點深度成反比變化 , 可提高搜索效率 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 演講完畢，謝謝觀看！ 。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 對于一個給定的啟發(fā)函數(shù)， 可以通過對該函數(shù)乘以一個大于 1的正數(shù) w的方法增加它的啟發(fā)能力。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 在構(gòu)造啟發(fā)函數(shù)時， 如果函數(shù)包含的啟發(fā)信息越多， 對算法在 OPEN表中節(jié)點的排序越準確，總能把最有希望獲得解的節(jié)點優(yōu)先選出來擴展。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 解路徑的費用（長度）并不是影響算法的唯一因素。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 8. A*算法的應(yīng)用舉例 . (1) 8 數(shù)碼問題 h(n) = P(n), P(n)為每一方塊與目標位置的距離的總和 . (2) 傳教士與野人問題 h(n)=0 h(n)=M+C h(n)=M+C2B 傳教士與野人渡河問題：有 N 個傳教士帶 N 個野人渡河，河的岸邊有一條船， 每次最多可載 K 人，要求無論在河的哪一邊，或是在船上，野人的數(shù)目不能超過傳教士的數(shù)目，問為安全起見， 應(yīng)如何安排傳教士與野人渡河？ N=5， K=3。 定義： 單調(diào)性 啟發(fā)函數(shù)單調(diào)的條件是： 1。 例如， 在寬度優(yōu)先搜索中， h(n) ≦ 0 ，滿足 h(n) ≦ h*(n) ， 是可采納的。 closed = [s4, B4, D5,E5, I5,K5] 7. L = goal, 成功找到了解 人工智能 吉林大學(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 1 2 3 4 5 Goal node 6 4 4 6 4 6 5 5 6 6 7 5 7 5 5 7 7 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 Closed表中的節(jié)點 open表中的節(jié)點 選擇節(jié)點 D 擴展時的 Open表和 closed 表 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 2. 爬山法 f(n)=h(n) 3. 分支界限法 4. f(n)=g(n) 5. 4. 動態(tài)規(guī)劃法 6. 對分支界限法的改進 , 如果有多條到達某一節(jié)點的路徑 , 只保留費用最小的一條 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A E F t B C 3 2 5 3 4 5 4 4 設(shè)有 7 城市 , 城市之間的距離如圖 , 求從 s到 t的最短通路 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 B g=11 g=13 F 10 9 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 E C g=11 g=12 11 12 10 9 B g=11 g=13 F 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 E C g=11 g=12 B E g=10 g=11 B g=13 F D F B F A C t g=14 g=16 g=15 g=14 g=15 g=15 g=13 11 12 8 10 9 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 動態(tài)規(guī)劃法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 E C B g=11 F g=10 t