【正文】 h(s) = MAX 已投下的子可以占據(jù)的行， 列和對角線數(shù) 人工智能 吉林大學珠海學院計算機科學與技術系 MIN MAX 5 4 4 3 2 4 3 4 4 4 5 人工智能 吉林大學珠海學院計算機科學與技術系 啟發(fā)式搜索算法 最佳優(yōu)先搜索。 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)先都不使用領域知識， 效率很低。 6 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 4 4 IF GOAL(n) THEN EXIT(SUCCESS)。 由 n循指針返回 s, 可以獲得解路徑 . 6. EXPAND(n)→mi, G=ADD(mi, G), 子節(jié)點集 {mi}中不包含 n的父輩節(jié)點 . 人工智能 吉林大學珠海學院計算機科學與技術系 7 標記和修改指針 ADD(mj, OPEN), 并標記 mj連接到 n的指針 , mj是未在 OPEN和 CLOSED中出現(xiàn)過的子節(jié)點 . 計算是否需要修改 mk, ml到 n的指針 。 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)。而我們對狀態(tài)空間搜索解的過程是邊產(chǎn)生圖邊求解， 這里所產(chǎn)生的圖是表示狀態(tài)空間的無限圖的顯式部分， 從求解的效率 考慮， 就有把這個無限圖的顯式部分向哪個方向以何種方式擴展的問題。 2。 圖論中研究的有向圖是有限的，我們可以把有向圖全部畫出來。 人工智能 吉林大學珠海學院計算機科學與技術系 用有向圖表示問題的狀態(tài)空間是一種很自然的方式， 節(jié)點代表狀態(tài)描述， 弧代表狀態(tài)之間的轉(zhuǎn)移。 14 return CONS( R, PATH) 人工智能 吉林大學珠海學院計算機科學與技術系 圖搜索策略 graphsearch strategies 回溯算法只包含一條探索路徑 , 如果發(fā)現(xiàn)deadend節(jié)點或無規(guī)則可用時要退回來 , 因此可能產(chǎn)生把探索過的節(jié)點擦掉后又重新產(chǎn)生的現(xiàn)象 . 在圖搜索算法中 .將所有搜索過的狀態(tài)用一個圖 (搜索圖 )記錄下來 , 圖的弧反映狀態(tài)之間的關系 .在圖中選擇節(jié)點加以擴展 , 直至把搜索圖擴展到充分大 , 包含解路徑在內(nèi) . 人工智能 吉林大學珠海學院計算機科學與技術系 The main idea of graph search In the backtracking procedure, we preserve only a path from the initial state to the current state, so sometimes we need to product some states again after the states were removed. However, in graph search method, We preserve a graph in the memory, the graph include all the states we passed through and the relation of their sequences. When we find some node(state) in the graph is suited to expand for search, we expand it, continue our searching, until a solution is finded. 人工智能 吉林大學珠海學院計算機科學與技術系 圖論與狀態(tài)空間表示 有向圖 G是一個偶對 (N, E), 其中 N 是節(jié)點集合， E是有向弧的集合。 12 PATH ←BACKTRACK( RDATALIST)。 10 RDATA ← R(DATA)。 8 R ← FIRST(RULES)。 6 RULES ← APPRULES(DATA)。 4 if DEADEND(DATA), return FAIL。 2 if MEMBER(DATA, TAIL(DATALIST)), return FAIL。 9 if PATH = FAIL , go LOOP。 7 RDATA ← R(DATA)。 5 R ← FIRST(RULES)。 3 RULES ← APPRULES(DATA)。 其中 ****為 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。 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!種。 3. 有些問題用傳統(tǒng)方法描述很困難 , 例如本節(jié)的幾個例子 4. 公式的推導需要很高的水平， 與實際問題相差較遠，對應用者要求很高。 人工智能 吉林大學珠海學院計算機科學與技術系 狀態(tài)空間 1. 計算機對傳統(tǒng)的問題求解方法帶來了根本性的改變。 7. A*算法的性質(zhì)。人工智能 吉林大學珠海學院計算機科學與技術系 第 1 章 搜索問題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 3. 圖搜索策略 4. 無信息的圖搜索策略 5. 啟發(fā)式圖搜索策略 6. A*算法。 8. 搜索算法的討論。 2. 傳統(tǒng)方法， 由專家給出公式， 使用者的任務是理解公式， 應用公式。 5. 2. 計算機利用自己強大的計算能力和存儲能力 , 采用”猜”的方