【正文】 12 10 9 ╳ ╳ ╳ ╳ 人工智能 吉林大學珠海學院計算機科學與技術系 5. 最佳圖搜索算法 A* 在啟發(fā)式搜索中使用評估函數(shù) f(n) = g(n) + h(n) 其中， g(n) 是從初始狀態(tài)到 n 費用； h(n)是從 n 到目標的啟發(fā)式估計費用 把使用這種估值函數(shù)的啟發(fā)式程序叫做 A算法。 closed = [s4, B4] 3. 測試 D5, Open = [E5,A6, C6, F6,G6, H7]。 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 最佳優(yōu)先搜索算法 function bestfirstsearch 算法保存 2 個表， 一個是 open表， 記錄已經(jīng)產(chǎn)生但尚未探索的節(jié)點， 另一個是 closed 表， 記錄已經(jīng)探索過的節(jié)點， 算法把新產(chǎn)生的節(jié)點加入到 open 表中， 然后按啟發(fā)函數(shù)值將它們排序， 把最有希望的節(jié)點排在前面， 選出來加以測試和擴展 人工智能 吉林大學珠海學院計算機科學與技術系 啟發(fā)式搜索算法 A 評價函數(shù) 依據(jù)領域知識， 對狀態(tài)空間的狀態(tài)的好壞程度的度量。 0 簡介 heuristic Of or relating to a usually speculative formulation serving as a guide in the investigation or solution of a problem: 探索的 ,做為調(diào)查或解決問題的向?qū)У囊环N通常為推測性系統(tǒng)闡述 回溯式搜索， 深度優(yōu)先和寬度優(yōu)先都不使用領域知識， 效率很低。 4 IF GOAL(n) THEN EXIT(SUCCESS)。 G為搜索圖 , 初始化為問題的初始狀態(tài) s, 建立 OPEN表 ,初始化為只含初始狀態(tài) s. 2. CLOSED = (),建立 CLOSED表 ,初始化為空表 . 3. LOOP: IF OPEN=(), THEN EXIT(FAIL) 4. n=FIRST(OPEN), REMOVE(n, OPEN), ADD(n, CLOSED)。 2。 人工智能 吉林大學珠海學院計算機科學與技術系 用有向圖表示問題的狀態(tài)空間是一種很自然的方式， 節(jié)點代表狀態(tài)描述， 弧代表狀態(tài)之間的轉(zhuǎn)移。 12 PATH ←BACKTRACK( RDATALIST)。 8 R ← FIRST(RULES)。 4 if DEADEND(DATA), return FAIL。 9 if PATH = FAIL , go LOOP。 5 R ← FIRST(RULES)。 其中 ****為 B,C, D, E 的排列 . 問題的節(jié)，形式為 (A****A)的字符串 , 其中 ****為 B,C, D, E 的排列 . 人工智能 吉林大學珠海學院計算機科學與技術系 旅行推銷員問題的搜索空間 E A D C B C D E A E D A D C E A E 100 125 100 75 150 175 425 225 325 275 375 300 250 人工智能 吉林大學珠海學院計算機科學與技術系 回溯策略 回溯策略的主要思想 : 只保留從初始狀態(tài)到當前狀態(tài)的一條解路徑 , 給變換狀態(tài)的規(guī)則給出一個排序方法 , 對當前狀態(tài)使用規(guī)則產(chǎn)生新的狀態(tài) , 不斷地向前延伸解路徑 . 當沒有規(guī)則可用 , 或向前延伸的狀態(tài)都是無解狀態(tài) (稱為死點 ,deadend)時 , 沿解路徑后退到前一個狀態(tài) (回溯 ), 重新開始搜索 , 直至找到解或宣布失敗 . 回溯策略是一種窮盡的搜索方法 . 人工智能 吉林大學珠海學院計算機科學與技術系 回溯算法 Backtracking Strategies 遞歸過程 A simple recursive procedure 輸入 : 問題的初始狀態(tài) . . The input: the initial state. 輸出 :一個規(guī)則表 . 應用這個規(guī)則表可以把初始狀態(tài)變?yōu)槟繕藸顟B(tài) . 否則回答 FAIL. The output of the procedure, a list of rules, using it we can get the goal from the initial state. If the procedure can not find the solution, it return FAIL. Recursive procedure BACKTRCK(DATA) 1 if TERM(DATA), return NIL。 有些問題用傳統(tǒng)方法描述很困難 , 例如本節(jié)的幾個例子 公式的推導需要很高的水平， 與實際問題相差較遠，對應用者要求很高。 7. A*算法的性質(zhì)。 3. 圖搜索策略 4. 無信息的圖搜索策略 5. 啟發(fā)式圖搜索策略 6. A*算法。 傳統(tǒng)方法， 由專家給出公式， 使用者的任務是理解公式， 應用公式。 人工智能 吉林大學珠海學院計算機科學與技術系 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 人工智能 吉林大學珠海學院計算機科學與技術系 例 旅行推銷員問題 A B D C E 75 100 125 125 50 100 50 75 125 100 125 問題表示 , 形式為 (A****)的字符串和 (A****A)的字符串。 人工智能 吉林大學珠海學院計算機科學與技術系 4 LOOP: if NULL(RULES), return FAIL。 8 PATH ←BACKTRACK( RDATA)。 3 if TERM(DATA), return NIL。 人工智能 吉林大學珠海學院計算機科學與技術系 7 LOOP: if NULL(RULES), return FAIL。 11 RDATALIST ←CONS( RDATA, DATALIST)。 D E C B A 有向圖中的有關概念，父親節(jié)點， 兒子節(jié)點， 葉節(jié)點，路徑， 回路， 有向樹。而人工智能中描述問題的有向圖一般說來是無限的， 或者說雖然有限， 但是非常大，我們不可能將其畫出來。 人工智能 吉林大學珠海學院計算機科學與技術系 ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學珠海學院計算機科學與技術系 graphsearch strategies ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB4 R2 人工智能 吉林大學珠海學院計算機科學與技術系 DB1 DB2 DB4 R1 R2 DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學珠海學院計算機科學與技術系 問題的狀態(tài)和它們之間的關系可以用一個圖隱含地加以描述 . 狀態(tài)用圖的節(jié)點表示 , 狀態(tài)之間的關系用圖中的弧表示 . the states and their relations are defined by a graph implicitly: states ———————— nodes rule applications —————— arcs 但是 , 我們也應該注意到它們之間的區(qū)別 : However, generally the graph is endless , We can not draw the graphsin ordinary way. 人工智能 吉林大學珠海學院計算機科學與技術系 Starti