【正文】 A ← R(DATA)。 6 RULES ← APPRULES(DATA)。 14 return CONS( R, PATH) 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 圖搜索策略 graphsearch strategies 回溯算法只包含一條探索路徑 , 如果發(fā)現(xiàn)deadend節(jié)點或無規(guī)則可用時要退回來 , 因此可能產(chǎn)生把探索過的節(jié)點擦掉后又重新產(chǎn)生的現(xiàn)象 . 在圖搜索算法中 .將所有搜索過的狀態(tài)用一個圖 (搜索圖 )記錄下來 , 圖的弧反映狀態(tài)之間的關(guān)系 .在圖中選擇節(jié)點加以擴展 , 直至把搜索圖擴展到充分大 , 包含解路徑在內(nèi) . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 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. 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 圖論與狀態(tài)空間表示 有向圖 G是一個偶對 (N, E), 其中 N 是節(jié)點集合， E是有向弧的集合。而我們對狀態(tài)空間搜索解的過程是邊產(chǎn)生圖邊求解， 這里所產(chǎn)生的圖是表示狀態(tài)空間的無限圖的顯式部分， 從求解的效率 考慮， 就有把這個無限圖的顯式部分向哪個方向以何種方式擴展的問題。 6 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 ? 4 IF 4 IF GOAL(n) THEN EXIT(SUCCESS)。 closed = [s4, B4, D5,E5] 5. 測試 I5, Open = [K5,A6, C6, F6,G6, H7, J7]。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 單調(diào)性 在算法 A 中， g(n)是 g*(n) 的估計值， 定義為在已經(jīng)產(chǎn)生的節(jié)點中從初始節(jié)點到 n 的最短路徑的費用， 在算法進行的過程中， 我們需要不斷地計算， 比較和調(diào)整這條最短路徑， 這要消耗大量的計算時間，因而也影響算法的效率，如果能對啟發(fā)函數(shù)增加某些限制條件， 使得在這種限制條件下，理論上就可以證明 g(n) 就是 g*(n), 則為獲得 g(n)所需要的計算就可以省略了。 所以，在條件允許的情況下， 我們希望找到費用最低的解路徑，即最佳解路徑。最理想的啟發(fā)函數(shù) h在搜索圖中每一個節(jié)點上的取值都與該節(jié)點到目標節(jié)點的實際費用 h*相同，但這樣的啟發(fā)函數(shù)需要大量的計算，使算法的效率反而下降。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 對于一個給定的啟發(fā)函數(shù)， 可以通過對該函數(shù)乘以一個大于 1的正數(shù) w的方法增加它的啟發(fā)能力。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 解路徑的費用（長度）并不是影響算法的唯一因素。 定義： 單調(diào)性 啟發(fā)函數(shù)單調(diào)的條件是： 1。 closed = [s4, B4, D5,E5, I5,K5] 7. L = goal, 成功找到了解 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(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 4 4 6 4 6 5 5 6 6 7 5 7 5 5 7 7 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 Closed表中的節(jié)點 open表中的節(jié)點 選擇節(jié)點 D 擴展時的 Open表和 closed 表 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 2. 爬山法 f(n)=h(n) 3. 分支界限法 4. f(n)=g(n) 5. 4. 動態(tài)規(guī)劃法 6. 對分支界限法的改進 , 如果有多條到達某一節(jié)點的路徑 , 只保留費用最小的一條 . 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A E F t B C 3 2 5 3 4 5 4 4 設(shè)有 7 城市 , 城市之間的距離如圖 , 求從 s到 t的最短通路 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 B g=11 g=13 F 10 9 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 E C g=11 g=12 11 12 10 9 B g=11 g=13 F 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 分支界限法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 E C g=11 g=12 B E g=10 g=11 B g=13 F D F B F A C t g=14 g=16 g=15 g=14 g=15 g=15 g=13 11 12 8 10 9 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 動態(tài)規(guī)劃法 s D A 1 g=0 2 g=3 3 g=4 D B 5 g=7 6 g=8 E A 7 g=9 4 g=6 E C B g=11 F g=10 t g=14 g=13 11 12 10 9 ╳ ╳ ╳ ╳ 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 5. 最佳圖搜索算法 A* 在啟發(fā)式搜索中使用評估函數(shù) f(n) = g(n) + h(n) 其中， g(n) 是從初始狀態(tài)到 n 費用； h(n)是從 n 到目標的啟發(fā)式估計費用 把使用這種估值函數(shù)的啟發(fā)式程序叫做 A算法。 6 EXPAND(n)→{mi}, G=ADD(mi, G)。 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)先都不使用領(lǐng)域知識， 效率很低。 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)。 人工智能 吉林大學(xué)珠海學(xué)院計算機科學(xué)與技術(shù)系 用有向圖表示問題的狀態(tài)空間是一種很自然的方式， 節(jié)