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