【正文】 (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ī)科學(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ī)科學(xué)與技術(shù)系 評價函數(shù)的啟發(fā)能力由以下 3 因素決定 1. 解路徑的費用 . 2. 求解過程中擴(kuò)展節(jié)點的個數(shù) . 3. 計算 h所需要的工作量 . 有時使用 f = g +wh 有時以犧牲可采納性為代價 , 獲得強(qiáng)的啟發(fā)能力 . 顯然解路徑越長， 找到解路徑所需要的計算費用就越大。這時評價函數(shù)變成 f = g + w*h, 如果 w很大， 相當(dāng)于 g(n)≡0. 有些問題只要求我們找出解路徑， 不考慮解路徑的費用，對于這類問題，我們可以完全不考慮 g 對求解的影響，采用 f = w*h式的評價函數(shù)。 對于所有的狀態(tài) ni和 nj， 其中 nj是 ni的后繼 h(ni) h(nj) ≦ cost(ni, nj) cost(ni, nj)是節(jié)點 ni和 nj之間的實際最小費用 2。 建立和調(diào)整指針 , 計算各節(jié)點的 f 值 . 并按各點的 f值調(diào)整指針 . 7 把 OPEN表中的節(jié)點按 f值從小到大排序 . 8 GO LOOP 人工智能 吉林大學(xué)珠海學(xué)院計算機(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 4 1+5=6 1+3=4 1+5=6 1 2 3 8 4 7 6 5 目標(biāo)狀態(tài) h 值是偏離目標(biāo)位置的塊數(shù) W(n) 人工智能 吉林大學(xué)珠海學(xué)院計算機(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 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ī)科學(xué)與技術(shù)系 初始化 . Open = [s4]。 稱n為當(dāng)前節(jié)點 . 5. IF GOAL(n) THEN EXIT(SUCCESS)。 9 RULES ← TAIL(RULES)。 2 if DEADEND(DATA), return FAIL。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 狀態(tài)空間 1. 計算機(jī)對傳統(tǒng)的問題求解方法帶來了根本性的改變。 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL。 圖論中研究的有向圖是有限的，我們可以把有向圖全部畫出來。如果應(yīng)用得好，可以明顯地縮小搜索空間， 提高搜索效率 例如， 在九宮游戲中使用啟發(fā)式搜索， 就可以顯著地減少搜索空間 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 MIN MAX 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 在九宮游戲中使用啟發(fā)式搜索： 使用啟發(fā)函數(shù) h(s) = MAX 已投下的子可以占據(jù)的行， 列和對角線數(shù) 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 MIN MAX 5 4 4 3 2 4 3 4 4 4 5 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索算法 最佳優(yōu)先搜索。 如果在 A算法中使用的啟發(fā)函數(shù)滿足 h(n) ≦ h*(n) 則稱之為 A* 算法。所需要擴(kuò)展的節(jié)點數(shù)少，說明算法引導(dǎo)搜索集中向目標(biāo)節(jié)點的方向發(fā)展， 當(dāng)然有利于較快地找到解。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 在構(gòu)造啟發(fā)函數(shù)時， 如果函數(shù)包含的啟發(fā)信息越多， 對算法在 OPEN表中節(jié)點的排序越準(zhǔn)確，總能把最有希望獲得解的節(jié)點優(yōu)先選出來擴(kuò)展。 例如， 在寬度優(yōu)先搜索中， h(n) ≦ 0 ，滿足 h(n) ≦ h*(n) ， 是可采納的。 最佳優(yōu)先搜索算法 function bestfirstsearch 算法保存 2 個表， 一個是 open表， 記錄已經(jīng)產(chǎn)生但尚未探索的節(jié)點， 另一個是 closed 表， 記錄已經(jīng)探索過的節(jié)點， 算法把新產(chǎn)生的節(jié)點加入到 open 表中， 然后按啟發(fā)函數(shù)值將它們排序， 把最有希望的節(jié)點排在前面， 選出來加以測試和擴(kuò)展 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索算法 A 評價函數(shù) 依據(jù)領(lǐng)域知識， 對狀態(tài)空間的狀態(tài)的好壞程度的度量。 2。 4 if DEADEND(DATA), return FAIL。 有些問題用傳統(tǒng)方法描述很困難 , 例如本節(jié)的幾個例子 公式的推導(dǎo)需要很高的水平， 與實際問題相差較遠(yuǎn)，對應(yīng)用者要求很高。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 1 4 3 7 6 5 8 2 1 3 7 4 6 5 8 2 1 4 3 7 6 5 8 2 1 2 3 7 8 6 5 2 1 2 3 7 6 5 8 2 1 3 7 4 6 5 8 2 1 3 7 4 6 5 8 2 1 4 3 1 7 6 5 8 2 1 4 3 5 7 6 8 2 1 4 3 7 8 6 5 2 1 4 3 7 8 6 5 2 1 4 3 7 6 3 5 8 2 1 4 3 7 6 2 5 8 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 例 旅行推銷員問題 A B D C E 75 100 125 125 50 100 50 75 125 100 125 問題表示 , 形式為 (A****)的字符串和 (A****A)的字符串。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 7 LOOP: if NULL(RULES), return FAIL。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 graphsearch strategies ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB4 R2 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 DB1 DB2 DB4 R1 R2 DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 問題的狀態(tài)和它們之間的關(guān)系可以用一個圖隱含地加以描述 . 狀態(tài)用圖的節(jié)點表示 , 狀態(tài)之間的關(guān)系用圖中的弧表示 . the states and their relations are defined by a graph implicitly: s