【正文】 因此， 在解決實(shí)際問題時，我們需要在啟發(fā)函時的計算量和擴(kuò)展節(jié)點(diǎn)的數(shù)量之間作認(rèn)真的權(quán)衡。根據(jù)前面幾節(jié)的介紹， 我們知道如果啟發(fā)函數(shù)滿足 h(n)≦h*(n), 即使用 A*算法， 則只要被搜索的圖有解，算法肯定能找到最佳解路徑。 這個條件就是單調(diào)性。 closed = [s4, B4, D5,E5, I5] 6. 測試 K5, Open = [L5,A6, C6, F6,G6, H7, J7, M7]。 ? 5 REMOVE(n, OPEN), ADD(n, CLOSED)。 7 ADD(mi, OPEN), 并標(biāo)記 mi到 n的指針 , 把不在 OPEN和 8 CLOSED 中的節(jié)點(diǎn)放在最前面 , 使深度大的節(jié)點(diǎn)可以優(yōu)先擴(kuò)展 . 9 8 GO LOOP 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 使用 DEPTHFIRSTSEARCH搜索的例 D6 C4 B4 A5 H3 G4 F5 E5 O2 J I K P3 T S K K L M N goal 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 為保證深度優(yōu)先算法在問題有解的情況下總能找到解 , 需要增加深度限制 , 而且深度限制必須超過解的長度 . 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索 4。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 graphsearch strategies ? Motivation: the limitation of backtracking procedure ? Sometimes, after analyzing we need to reproduce some states again. DB1 DB4 R2 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 DB1 DB2 DB4 R1 R2 DB1 DB2 DB3 DB4 R1 R2 R3 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 問題的狀態(tài)和它們之間的關(guān)系可以用一個圖隱含地加以描述 . 狀態(tài)用圖的節(jié)點(diǎn)表示 , 狀態(tài)之間的關(guān)系用圖中的弧表示 . the states and their relations are defined by a graph implicitly: states ———————— nodes rule applications —————— arcs 但是 , 我們也應(yīng)該注意到它們之間的區(qū)別 : However, generally the graph is endless , We can not draw the graphsin ordinary way. 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 Starting from the initial state, we generate an subgraph(an explicit part of the graph implicitly defined by production system), then we select the node in the subgraph to expand it, if the subgraph does not contain the goal node, we continue to expand it, until the subgraph is large enough to include the goal node , and we find the solution path from the initial node to the goal node. The procedure GRAPHSEARCH input : the production system(the initial nose, production rule, goal node) output: the solution path from the initial node to a goal node 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 Procedure GRAPHSEARCH 1 G=s, OPEN=(s)。 D E C B A 有向圖中的有關(guān)概念，父親節(jié)點(diǎn)， 兒子節(jié)點(diǎn)， 葉節(jié)點(diǎn)，路徑， 回路， 有向樹。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 7 LOOP: if NULL(RULES), return FAIL。 8 PATH ←BACKTRACK( RDATA)。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 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 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 例 旅行推銷員問題 A B D C E 75 100 125 125 50 100 50 75 125 100 125 問題表示 , 形式為 (A****)的字符串和 (A****A)的字符串。 3. 圖搜索策略 4. 無信息的圖搜索策略 5. 啟發(fā)式圖搜索策略 6. A*算法。 3. 有些問題用傳統(tǒng)方法描述很困難 , 例如本節(jié)的幾個例子 4. 公式的推導(dǎo)需要很高的水平， 與實(shí)際問題相差較遠(yuǎn)，對應(yīng)用者要求很高。 5 R ← FIRST(RULES)。 4 if DEADEND(DATA), return FAIL。 12 PATH ←BACKTRACK( RDATALIST)。 2。 4 4 IF GOAL(n) THEN EXIT(SUCCESS)。 最佳優(yōu)先搜索算法 function bestfirstsearch 算法保存 2 個表， 一個是 open表， 記錄已經(jīng)產(chǎn)生但尚未探索的節(jié)點(diǎn)， 另一個是 closed 表， 記錄已經(jīng)探索過的節(jié)點(diǎn)， 算法把新產(chǎn)生的節(jié)點(diǎn)加入到 open 表中， 然后按啟發(fā)函數(shù)值將它們排序， 把最有希望的節(jié)點(diǎn)排在前面， 選出來加以測試和擴(kuò)展 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 啟發(fā)式搜索算法 A 評價函數(shù) 依據(jù)領(lǐng)域知識， 對狀態(tài)空間的狀態(tài)的好壞程度的度量。 closed = [s4, B4] 3. 測試 D5, Open = [E5,A6, C6, F6,G6, H7]。 例如， 在寬度優(yōu)先搜索中， h(n) ≦ 0 ，滿足 h(n) ≦ h*(n) ， 是可采納的。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 8. A*算法的應(yīng)用舉例 . (1) 8 數(shù)碼問題 h(n) = P(n), P(n)為每一方塊與目標(biāo)位置的距離的總和 . (2) 傳教士與野人問題 h(n)=0 h(n)=M+C h(n)=M+C2B 傳教士與野人渡河問題：有 N 個傳教士帶 N 個野人渡河，河的岸邊有一條船， 每次最多可載 K 人，要求無論在河的哪一邊，或是在船上，野人的數(shù)目不能超過傳教士的數(shù)目，問為安全起見， 應(yīng)如何安排傳教士與野人渡河？ N=5， K=3。 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 在構(gòu)造啟發(fā)函數(shù)時， 如果函數(shù)包含的啟發(fā)信息越多， 對算法在 OPEN表中節(jié)點(diǎn)的排序越準(zhǔn)確，總能把最有希望獲得解的節(jié)點(diǎn)優(yōu)先選出來擴(kuò)展。 使 w隨搜索樹的節(jié)點(diǎn)深度成反比變化 , 可提高搜索效率 . 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 演講完畢，謝謝觀看！ 。所需要擴(kuò)展的節(jié)點(diǎn)數(shù)少，說明算法引導(dǎo)搜索集中向目標(biāo)節(jié)點(diǎn)的方向發(fā)展， 當(dāng)然有利于較快地找到解。 h(goal) = 0 人工智能 吉林大學(xué)珠海學(xué)院計算機(jī)科學(xué)與技術(shù)系 啟發(fā)函數(shù)的比較 設(shè)有兩個算法， 分別使用兩個啟發(fā)函數(shù)