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