【正文】 因此， 有時為了增加算法的啟發(fā)能力， 我們采用較大的啟發(fā)函數(shù)值， 甚至于不滿足 h(n)≦h*(n) ，這樣做犧牲了算法的可采納性， 但可以使算法擴展的節(jié)點個數(shù)大幅度下降，換來了算法的高效率。 人工智能 吉林大學珠海學院計算機科學與技術系 A*算法是可采納的 若存在從初始節(jié)點 s到目標節(jié)點 t的路徑， 則 A*算法必能找到最佳解路徑。 根據(jù)啟發(fā)函數(shù)對尚為探索的節(jié)點進行排序， 把最有希望的節(jié)點排再前面， 在擴展節(jié)點時把最有希望的節(jié)點拿出來考慮。而人工智能中描述問題的有向圖一般說來是無限的， 或者說雖然有限， 但是非常大，我們不可能將其畫出來。 3 if TERM(DATA), return NIL。 2. 傳統(tǒng)方法， 由專家給出公式， 使用者的任務是理解公式， 應用公式。 其中 ****為 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。 8 R ← FIRST(RULES)。 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)。 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 定義： 單調性 啟發(fā)函數(shù)單調的條件是： 1。 人工智能 吉林大學珠海學院計算機科學與技術系 對于一個給定的啟發(fā)函數(shù)， 可以通過對該函數(shù)乘以一個大于 1的正數(shù) w的方法增加它的啟發(fā)能力。 所以，在條件允許的情況下， 我們希望找到費用最低的解路徑，即最佳解路徑。 closed = [s4, B4, D5,E5] 5. 測試 I5, Open = [K5,A6, C6, F6,G6, H7, J7]。 6 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 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é)點加以擴展 , 直至把搜索圖擴展到充分大 , 包含解路徑在內 . 人工智能 吉林大學珠海學院計算機科學與技術系 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是有向弧的集合。 7 RDATA ← R(DATA)。人工智能 吉林大學珠海學院計算機科學與技術系 第 1 章 搜索問題 1. 什么是狀態(tài)空間？ 2. 回溯策略。 6 RULES ← TAIL(RULES)。 13 if PATH = FAIL , go LOOP。 5 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 closed = [s4, B4, D5] 4. 測試 E5, Open = [I5,A6, C6, F6,G6, H7, J7]。 人工智能 吉林大學珠海學院計算機科學與技術系 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)