【正文】 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 人工智能 吉林大學珠海學院計算機科學與技術系 初始化 . Open = [s4]。 如果狀態(tài)空間的圖搜索問題存在解路徑， 搜索算法 f 一定能找到該問題的最優(yōu)解路徑， 則稱算法 f 是可采納的。 對于所有的狀態(tài) ni和 nj， 其中 nj是 ni的后繼 h(ni) h(nj) ≦ cost(ni, nj) cost(ni, nj)是節(jié)點 ni和 nj之間的實際最小費用 2。算法在尋找解路徑的過程中所需要擴展的節(jié)點數(shù)也是影響效率的一個重要因素。這時評價函數(shù)變成 f = g + w*h, 如果 w很大， 相當于 g(n)≡0. 有些問題只要求我們找出解路徑， 不考慮解路徑的費用，對于這類問題，我們可以完全不考慮 g 對求解的影響，采用 f = w*h式的評價函數(shù)。但這時啟發(fā)函數(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 人工智能 吉林大學珠海學院計算機科學與技術系 (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)仔細考慮后的剪忮 人工智能 吉林大學珠海學院計算機科學與技術系 迷宮問題 求從入口到出口通過迷宮的最短路徑 入口 出口 人工智能 吉林大學珠海學院計算機科學與技術系 迷宮問題 入口 (1,1) 出口 (4,4) 人工智能 吉林大學珠海學院計算機科學與技術系 問題描述 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)為目標點坐標 , ( xn,yn)為節(jié)點 n的坐標 , 人工智能 吉林大學珠海學院計算機科學與技術系 (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) 人工智能 吉林大學珠海學院計算機科學與技術系 (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 人工智能 吉林大學珠海學院計算機科學與技術系 評價函數(shù)的啟發(fā)能力由以下 3 因素決定 1. 解路徑的費用 . 2. 求解過程中擴展節(jié)點的個數(shù) . 3. 計算 h所需要的工作量 . 有時使用 f = g +wh 有時以犧牲可采納性為代價 , 獲得強的啟發(fā)能力 . 顯然解路徑越長， 找到解路徑所需要的計算費用就越大。 和前面舉例的 f(n) = g(n) + h(n)中， h(n)取為偏離目標位置的塊數(shù)， 滿足 h(n) ≦ h*(n) ，也是可采納的。 closed = [s4, B4, D5] 4. 測試 E5, Open = [I5,A6, C6, F6,G6, H7, J7]。 通常使用的評價函數(shù)為： f(n)=g(n)+h(n) g*(n) 初始節(jié)點到節(jié)點 n 的距離 . h*(n) 節(jié)點 n 到目標節(jié)點 g 的距離 . f*(n)=g*(n)+h*(n), 從初始節(jié)點到目標節(jié)點 g 的距離 . f(n),g(n),h(n)分別是 f*(n), g*(n), h*(n)的估計值 . 人工智能 吉林大學珠海學院計算機科學與技術系 ? A算法 ? Procedure A ? 1 G=s, OPEN=(s), CLOSED = (). ? 2 LOOP: IF OPEN=(), THEN EXIT(FAIL) ? 3 n=FIRST(OPEN)。 5 5 REMOVE(n, OPEN), ADD(n, CLOSED)。圖論中的問題求解是在對圖完全了解的情況下進行。 13 if PATH = FAIL , go LOOP。 5 if LENGTH(DATALIST) BOUND, return FAIL。 6 RULES ← TAIL(RULES)。 5. 2. 計算機利用自己強大的計算能力和存儲能力 , 采用”猜”的方式 , 試探法 . 能解決問題的領域更廣 , 更結合實際 . 人工智能 吉林大學珠海學院計算機科學與技術系 例 智力游戲問題：傳教士與野人渡河問題 傳教士與野人渡河問題：有 3 個傳教士帶 3 個野人渡河，河的岸邊有一條船， 每次最多可載 2 人，要求無論在河的哪一邊，野人的數(shù)目不能超過傳教士的數(shù)目，問為安全起見， 應如何安排傳教士與野人渡河？ 一種較為簡單的表示方式 3 元向量（ x, y, z） x: 河此岸的傳教士數(shù)， y: 河此岸的野人數(shù)。人工智能 吉林大學珠海學院計算機科學與技術系 第 1 章 搜索問題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 x,y 取值范圍 {0， 1， 2， 3} z: 船在此岸， z取值范圍 {0， 1} 人工智能 吉林大學珠海學院計算機科學與技術系 初始狀態(tài) ： （ 3， 3， 1） 目標狀態(tài)： （ 0， 0， 0） 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 初始狀態(tài) Initial 目標狀態(tài) Goal 例 設有 8 數(shù)碼難題如下 :在 3 3 的框架中有 8 個標有數(shù)字的硬紙片， 這些硬紙片上標的數(shù)字分別是 1， 2， ?, 8 ， 每個紙片都可以移進相鄰的空格， 8 數(shù)碼難題的初始狀態(tài)和目標狀態(tài)分別列出如下，問如何把這個問題由初始狀態(tài)移向目標狀態(tài)？ 人工智能 吉林大學珠海學院計算機科學與技術系 2 8 3 1 6 4 7 5 1 2 3 8 6 4 7 5 Initial Goal 8 數(shù)碼難題（ 8puzzle）的矩陣描述 對于 8 數(shù)碼難題， 我們選用直接的矩陣描述，解題過程中的任何一個中間情況都對應一個 3*3的矩陣， 用 0,1，2， ?, 8 這 9個數(shù)的一個排列依次去充填這個矩陣的各個單元 ,就是求解問題的一個可能的情況 , 共有 9!種。 7 RDAT