人工智能考試整理

1、 智能定義（知識(shí)閾值理論） 智能就是在巨大的搜索空間中迅速找到一個(gè)滿意解的能力智能的綜合性定義:智能是知識(shí)和智力的總和。其中知識(shí)是智能行為的基礎(chǔ)。智能的特征:1）具有記憶與思維能力存貯有感官得到的外界信息并加以處理（如分析，計(jì)算，聯(lián)想、決策等）2）具有感知能力：通過感官獲取外部信息的能力。3）具有自適應(yīng)能力 通過與外部世界交互學(xué)習(xí)，積累經(jīng)驗(yàn)，增長知識(shí)，以適應(yīng)環(huán)境變化。4）具有表達(dá)能力通過語言、手勢、表情等方式完成信息的輸出。深藍(lán)：能夠模擬人的思維，進(jìn)行博弈的計(jì)算機(jī)。1997年5月12日，一個(gè)名為“深藍(lán)”（deep Blue ）的IBM計(jì)算機(jī)系統(tǒng)戰(zhàn)勝當(dāng)時(shí)的國際象棋冠軍 蓋利.卡斯帕羅夫圖靈測試：

2、兩個(gè)房間，一個(gè)是人，一個(gè)是機(jī)器，測試者通過一系列的提問，如果提問題的人無法分辨是人還是機(jī)器在回答問題，則認(rèn)為該機(jī)器具有智能人工智能（Artifical Intelligence，簡稱AI）又稱機(jī)智能machine intelligence，一般認(rèn)為起源于美國1956年的一次夏季討論（達(dá)特茅斯會(huì)議）在這次會(huì)議上，第一次提出了“Artifical Intelligence”這個(gè)詞。AI的本質(zhì)問題：研究如何制造出人造的智能機(jī)器或系統(tǒng)，來模擬人類的智能活動(dòng)的能力，以延伸人們智能的科學(xué)。產(chǎn)生式系統(tǒng)由三個(gè)部分組成1）綜合數(shù)據(jù)庫（Globe Database） 也稱為：事實(shí)庫，上下文等。 作用:存放問題求解

3、的過程中產(chǎn)生的狀態(tài)描述信息。2）規(guī)則庫（Rule Base）(問題本身知識(shí)、求解知識(shí))也稱為規(guī)則基、規(guī)則集等。作用：存放規(guī)則知識(shí)。產(chǎn)生式規(guī)則的一般表達(dá)形式：IF（前提）THEN(結(jié)論)即 ： 如果 那么.例：1）數(shù)學(xué)定理 2）IF A是一種動(dòng)物 AND A 是哺乳動(dòng)物 AND A 吃肉 THEN A 是高級(jí)動(dòng)物 關(guān)于不精確推理 當(dāng)規(guī)則的前提成立時(shí)，結(jié)論并非完全成立。這種推理稱為不精確推理。通常采用閾值方法來解決此類問題。（3）控制策略（Control Strategy） a 選擇規(guī)則庫中的規(guī)則與綜合數(shù)據(jù)庫的已知事實(shí)進(jìn)行匹配，匹配成功的規(guī)則為可用規(guī)則，否則為不可用規(guī)則。 b 規(guī)則沖突的解決（可用

4、規(guī)則書1）。c將選中的規(guī)則的結(jié)論放入綜合數(shù)據(jù)庫。產(chǎn)生式系統(tǒng)的特點(diǎn)： 1 模式化：所有規(guī)則具有一樣的形式2結(jié)構(gòu)化：規(guī)則見的關(guān)聯(lián)比較簡單，容易維護(hù)。3自燃性：規(guī)則表達(dá)了因果關(guān)系，比較符合人們的思維方式，容易理解。4單一性：智能處理因果關(guān)系問題。5效率低，規(guī)則匹配過程很大。產(chǎn)生式系統(tǒng)的適用圍：1）知識(shí)雜亂、事實(shí)眾多、無統(tǒng)一理論的領(lǐng)域2）該領(lǐng)域的知識(shí)能夠抽象出來3）該領(lǐng)域的知識(shí)可分解為一組獨(dú)立的動(dòng)作，以便用規(guī)則加以表示。概括說的說：問題空間從一個(gè)狀態(tài)到另一個(gè)狀態(tài)的轉(zhuǎn)移序列獨(dú)立的領(lǐng)域可采用產(chǎn)生式系統(tǒng)模擬。產(chǎn)生式系統(tǒng)一般性算法：1 DATA 初始數(shù)據(jù)庫2 until DATA滿足結(jié)束條件條件之前 do：3

5、 Begin 在規(guī)則集中選擇某一可用于DATA的規(guī)則R DATA R應(yīng)用到DATA后得到的結(jié)果END例1 字符轉(zhuǎn)換問題：設(shè)字符轉(zhuǎn)換規(guī)則 ABC ACD BCG BEF DE已知：A,B求：F一、綜合數(shù)據(jù)庫 x ：其中x為字符二、規(guī)則集 IF AB THEN C IF AC THEN D IF BC THEN G IF BE THEN F IF D THEN E三、控制策略 順序排隊(duì)四、初始條件 A,B五、結(jié)束條件：例2 八數(shù)碼游戲問題：一個(gè)33棋盤有八牌1,2，8 與一個(gè)空格，空格周圍的牌可以向空格移動(dòng)。求解：給定一個(gè)初始狀態(tài)s一個(gè)目標(biāo)狀態(tài)G，求S到G的走步序列。產(chǎn)生式系統(tǒng)的基本控制策略概括的

6、講：產(chǎn)生式系統(tǒng)控制策略-搜索1）不可撤回方式2）試探性方式 a 回溯方式（Backtracking） b 圖搜索方式（Graph search）1.不可撤回方式 基本策略：選擇規(guī)則時(shí)只依靠局部知識(shí)（信息），而不考慮是否全局最佳選擇，只能滿足局部優(yōu)化條件，用過的規(guī)則不再撤回。特點(diǎn)： a 方法簡單，容易實(shí)現(xiàn) b 具有一定的局限性，適用圍?。ㄖ豢捎糜趩螛O值情況） c 可能會(huì)造成規(guī)則的多次重復(fù)使用。比如：爬山算法，不可用于解決多極值問題。關(guān)于 局部知識(shí)的利用 ：設(shè)計(jì)局部評(píng)價(jià)函數(shù)W(n),根據(jù)W(n)最大為原則來選擇規(guī)則。例：八數(shù)碼問題設(shè)：- W(n):不在位的數(shù)碼個(gè)數(shù) n：任意狀態(tài)目標(biāo)狀態(tài)：- W(n

7、)=0 （每個(gè)數(shù)碼就位）最不利狀態(tài)- W(n)= -8 （每個(gè)數(shù)碼都不在規(guī)定的位置）2.回溯方式基本策略：試探性的選擇一條規(guī)則，如果發(fā)現(xiàn)此規(guī)則不合適，則退回去另選其他規(guī)則。關(guān)鍵在于回溯條件的設(shè)定。特點(diǎn)： a 實(shí)用性好(相對(duì)不可回撤方式) b 適用圍較大，在一定程度上能避免盲目性 c 可解決局部極值問題設(shè)計(jì)方法： a 確定合適的回溯條件 b 充分利用可用知識(shí)來排列規(guī)則，減少回溯次數(shù)例：八數(shù)碼游戲（主要討論回溯條件）回溯條件： a 新產(chǎn)生的狀態(tài)已經(jīng)在搜索過程中出現(xiàn)； b 應(yīng)用規(guī)則的數(shù)量已經(jīng)超過規(guī)定值(深度限制) c 當(dāng)前狀態(tài)，無可用規(guī)則滿足上述條件之一 則產(chǎn)生回溯，每次回溯一層。3. 圖搜索方式基

8、本策略： 它是一種展開式搜索方法，把問題空間看成一隱含圖，從中搜索出一條解路徑。特點(diǎn)： a 實(shí)用性好 b 能保留完整的搜索樹 c 對(duì)于解空間較大的問題而言，搜索代價(jià)較大。例：八數(shù)碼問題這是一個(gè)典型的寬度優(yōu)先策略，所以搜索代價(jià)比較大?？偨Y(jié)：三種控制策略的特點(diǎn) 1） 不可撤回方式：沿一條路徑單向延伸搜索2)回溯方式：可修正搜索路徑3）圖搜索方式：展開式搜索，可保留完整的搜索樹。產(chǎn)生式系統(tǒng)分類1.一般性產(chǎn)生式系統(tǒng) 根據(jù)規(guī)則的應(yīng)用方式，一般性產(chǎn)生式系統(tǒng)可以分為三種類型： 1）正向系統(tǒng)（數(shù)據(jù)驅(qū)動(dòng)） 采用正向推理方式，即由初始狀態(tài)推理到目標(biāo)狀態(tài)，正向系統(tǒng)里的規(guī)則是正向使用的:規(guī)則的前提成立，那么規(guī)則的結(jié)論

9、成立。 2)反向系統(tǒng)（目標(biāo)驅(qū)動(dòng)系統(tǒng)）采用反向推理方式：即由目標(biāo)狀態(tài)反向推理找到初始狀態(tài)。反向系統(tǒng)的規(guī)則是反向使用的：先假設(shè)規(guī)則的結(jié)論成立，在尋找使其成立的前提條件。 3）雙向系統(tǒng) 由數(shù)據(jù)、目標(biāo)雙向驅(qū)動(dòng)，最后終止在某個(gè)中間狀態(tài)。 例：數(shù)學(xué)證明思路2.可交換產(chǎn)生式系統(tǒng)定義：滿足下列性質(zhì)的產(chǎn)生式系統(tǒng)稱為可交換產(chǎn)生式系統(tǒng) a 給定可以用于數(shù)據(jù)庫D的規(guī)則集R，對(duì)于使用R中的任何規(guī)則后產(chǎn)生的任何數(shù)據(jù)庫，規(guī)則集R仍然可用。(規(guī)則適用性) b 如果目標(biāo)條件被D滿足，則應(yīng)用R中的任何規(guī)則于D上所產(chǎn)生的任何數(shù)據(jù)庫仍可滿足目標(biāo)條件。(數(shù)據(jù)庫可用性) c 應(yīng)用R中一個(gè)規(guī)則序列于D上后，得到的數(shù)據(jù)庫不隨這規(guī)則序列次序變

10、化而變化。（規(guī)則次序無關(guān)性）3.可分解產(chǎn)生式系統(tǒng)定義：任何待求解的數(shù)據(jù)庫都可以分解為若干個(gè)獨(dú)立處理分量的產(chǎn)生式系統(tǒng)稱為可分解產(chǎn)生式系統(tǒng)。求解方法：將初始數(shù)據(jù)庫分解為幾個(gè)可獨(dú)立處理的分量，用規(guī)則分別求解，生成新的數(shù)據(jù)庫，再分解，再求解，知道結(jié)束?？煞纸猱a(chǎn)生式系統(tǒng)的一般性算法：1 DATA 初始數(shù)據(jù)庫2Di DATA， Di庫：獨(dú)立的分量數(shù)據(jù)庫3 until Di 的所有元素都滿足結(jié)束條件之前，do：4 begin 5 從 Di 中選擇一個(gè)不滿足結(jié)束條件的D*6 把D*從Di 中刪除7 從規(guī)則集R中選一條可用于D*的規(guī)則r，設(shè)D是人應(yīng)用于D*的結(jié)果是D的分解式。8 在 Di 添加di9 endAI

11、領(lǐng)域的知識(shí)分類 a 述性知識(shí)：用于描述綜合數(shù)據(jù)庫的狀態(tài)。（如事實(shí)等） b 過程性知識(shí)：用于規(guī)則中表達(dá)問題的知識(shí).（如客觀規(guī)律等） c 控制性知識(shí)：用于構(gòu)成控制策略的知識(shí)（算法、數(shù)據(jù)結(jié)構(gòu)等）AI系統(tǒng)的一個(gè)難題：知識(shí)表達(dá)問題，要能夠客觀的描述現(xiàn)實(shí)，簡化求解過程，有效的提高求解效率，降低求解代價(jià)。產(chǎn)生式系統(tǒng)的搜索策略狀態(tài)空間：由給定問題的所有可能的狀態(tài)組成的空間（相當(dāng)于全集G）搜索空間：按某種策略在狀態(tài)空間中選取的部分空間（G的子集）解路徑（解空間）：求解問題的一條有效路徑。搜索策略的基本思路：搜索空間必須包含解路徑，如果問題有解，且盡量縮小搜索空間。搜索策略的評(píng)價(jià)準(zhǔn)則：總體費(fèi)用最低費(fèi)用的劃分： a

12、 規(guī)則應(yīng)用的費(fèi)用：執(zhí)行規(guī)則時(shí)所花的費(fèi)用 b 控制費(fèi)用：選擇規(guī)則所花的費(fèi)用。1.回溯策略2.圖搜索策略3.啟發(fā)式圖搜索策略1）A算法2）爬山算法3）分支界限算法4）動(dòng)態(tài)規(guī)劃算法5）A*算法6）h函數(shù)與A*的關(guān)系7）關(guān)于單調(diào)性限制8）A*算法示例例 四皇后問題定義綜合數(shù)據(jù)庫：設(shè)：DATA=ij1=i,j=4,其中：ij表示棋子所在行列 如：24表示第二行第四列有一枚棋子因?yàn)槠灞P上 可放入的棋子數(shù)為04個(gè)所以集合中元素?cái)?shù)位0 4個(gè)，即length（DATA）=0 4圖搜索的實(shí)質(zhì)是從問題空間中找出一包含目標(biāo)節(jié)點(diǎn)的子圖。圖搜索的結(jié)果：1，一個(gè)完整的搜索圖G。2一個(gè)解路徑，用指針表示的解路徑。Proced

13、ure GraphSearch1 G=G0(G0=s),open=(s) /s:初始狀態(tài)2 closed=() 3Loop:if open=() then exit(fall)4 nfirst(open) remove(n,open), add(n,closed)5 if goal(n) then exit(success)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn)7 openadd(open，mj) / mj不在open，closed中標(biāo)記mj每個(gè)到n節(jié)點(diǎn)指針確定是否需要修改已在open，closed中的每個(gè)節(jié)點(diǎn)到n的指針確定是否需要修改已在closed中的每個(gè)節(jié)點(diǎn)的后繼節(jié)點(diǎn)原來的

14、指針。8按照某種方式排列open表中的節(jié)點(diǎn)，go loop深度優(yōu)先算法Procedrue depth-First-Search1 G=G0(G0=s),open=(s),closed=() /s:初始狀態(tài)2 Loop:if open=() then exit(fall)3 nfirst(open)4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn)7 openadd(open，mj) / mj不在open，closed中標(biāo)記mj每個(gè)到n節(jié)點(diǎn)指針，按照節(jié)點(diǎn)深度遞減順序排列op

15、en中的節(jié)點(diǎn) 8 go loop討論1：如果問題有解，有深度優(yōu)先搜索算法，是否能夠找到解？不一定.解空間是否有限？討論2：本算法的改進(jìn)之處是open中節(jié)點(diǎn)按照深度優(yōu)先排列，但是沒有對(duì)深度加以控制，可能造成搜索代價(jià)太大寬度優(yōu)先算法：Procedrue breadth-First-Search1 G=G0(G0=s),open=(s),closed=() /s:初始狀態(tài)2 Loop:if open=() then exit(fall)3 nfirst(open)4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expa

16、nd(n), /mj不含n的先輩節(jié)點(diǎn)7 open標(biāo)記每個(gè)到n節(jié)點(diǎn)指針，按照節(jié)點(diǎn)深度遞增順序排列open中的節(jié)點(diǎn) 8 go loop 理論上可以利用寬度優(yōu)先搜索能夠找到解，如果問題有解的話。討論：寬度優(yōu)先算法和深度優(yōu)先算法可能出現(xiàn)組合爆炸。都沒有利用任何啟發(fā)式信息，所以稱為無信息搜索策略penadd(open，mj) / mj不在open，closed中寬度優(yōu)先例題： 由一桌子T、三個(gè)積木A、B、C組成一個(gè)積木世界，初始狀態(tài)是A在B上，B在桌子上，C在桌子上；目標(biāo)狀態(tài)是：A、B、C依次從上到下排列在桌子上。如圖解：1）狀態(tài)描述（P1，P2，P3）表示按A、B、C順序依次分別在P1,P2,P3上其

17、中Pi是積木或者桌子。初始狀態(tài)時(shí)（B、T、T）,目標(biāo)狀態(tài) 可以表示（B、C、T）2）定義操作:move(x,y)表示將積木x移到Y(jié)上 ；約束條件:a X頂部必須是空的 b 如果Y是積木，Y的頂部必須是空 c 同一種狀態(tài)出現(xiàn)不得多于一次。1）解題過程 2）open表和closed表3）節(jié)點(diǎn)樣子畫出整個(gè)圖G 和解路徑4）程序何時(shí)結(jié)束 5）改用深度優(yōu)先如何？啟發(fā)式圖搜索策略：基本概念啟發(fā)式圖搜索的實(shí)質(zhì)是利用啟發(fā)信息有目的地進(jìn)行搜索，減少搜索的盲目性。降低搜索空間 找到最佳解啟發(fā)式信息用于解決open表中節(jié)點(diǎn)的排列次序問題，方法是利用一個(gè)評(píng)價(jià)函數(shù)計(jì)算open表中節(jié)點(diǎn)的評(píng)價(jià)函數(shù)值，按照函數(shù)值從小到大排列

18、所有節(jié)點(diǎn)。評(píng)價(jià)函數(shù)的目的：把最有希望得到最佳解或者解的排列在前面。路徑 ：給定節(jié)點(diǎn)序列（n0，n1，nk）。如果該序列中的任一節(jié)點(diǎn)ni-1都有后繼節(jié)點(diǎn)ni，則該節(jié)點(diǎn)序列為從n0到nk的一條路徑，路徑長度為K路徑耗散值：路徑耗散值等于該路徑上所有相鄰節(jié)點(diǎn)間耗散值的總和。設(shè)：路徑山任兩點(diǎn)間的耗散值為才C(ni,nj),則從ni到nk的路徑耗散值為C(ni,nj)=C(ni,nj)+C(nj,nk)最佳路徑耗散值：最佳路徑上的實(shí)際耗散值，記為：K(ni,nj).K(ni,nj)=g*(n)2)當(dāng)h=0且g(n) =d(n) 時(shí)，f(n)=d(n)既寬度優(yōu)先策略，d(n):節(jié)點(diǎn)深度。3）h(n)稱為啟

19、發(fā)函數(shù)。A算法：1 G=G0(G0=s),open=(s),closed=() ，f(s)=g(s)+ h(s) /s:初始狀態(tài)2 Loop:if open=() then exit(fall)3 nfirst(open)h()4 if goal(n) then exit(success)5remove(n,open), add(n,closed)6mj expand(n), /mj不含n的先輩節(jié)點(diǎn) 計(jì)算f(n,mi)=g(n,mi)+h(mi),(自s經(jīng)過n，mi 到目標(biāo)節(jié)點(diǎn)的耗散值)openadd(open，mj) 標(biāo)記mj到n的指針 (mj不在open，closed中) if f(n,

20、mk)f(mk) then f(mk) f(n, mk)標(biāo)記mk到n的指針(mk在open中)if f(n, mL)f(mL) then f(mL) f(n, mL)標(biāo)記mL到n的指針(mL在closed中) add(mL,open),把mL放回到open中7 Open中的節(jié)點(diǎn)按f值升序排列 8 go loop例 八數(shù)碼問題令：g(n)=d(n) 節(jié)點(diǎn)深度 h(n)=w(n) 不在位的數(shù)碼個(gè)數(shù)(啟發(fā)函數(shù))則 f(n)=d(n)+w(n)如初始節(jié)點(diǎn)s的f值f(0)=d(0)+w(0)=0+4=4有4個(gè)數(shù)碼不在位。對(duì)于f(n)=g(n)+h(n),如果單獨(dú)考慮g(n)或者h(yuǎn)(n),即， 1) f(

21、n)=g(n) 只考慮搜索過的路徑已經(jīng)耗費(fèi)的費(fèi)用；/分支界限算法 2）f(n)=h(n) 只考慮未來的發(fā)展趨勢/爬山算法那么可以得到兩種特殊的算法：爬山算法和分支界限算法。爬山算法：procedure Hill _Climbing1 n=s2 Loop: if goal(n) then exit(success)3mi expangd(n),計(jì)算每個(gè)h(mi) nextn h(mi)最小值的節(jié)點(diǎn)4 if h(n)h(nextn) then exit(fail)5 n nextn6go loop 優(yōu)點(diǎn)，缺點(diǎn)分支界限算法f(n)=g(n)：Procedure Branch_Bound1 queue

22、(s-s),g(s)=0 /queue中保存的是從s出發(fā)的路徑。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH) /取第一條路徑，與該路徑的最后節(jié)點(diǎn)n4 if goal(n) then exit(success)5 mj expand(n), 計(jì)算g(mj)= g(n,mj) remove(s-n,queue),add(s-mj,queue) /刪除原來的路徑，添加長度加一的路徑。6 queue隊(duì)列中分支按g值升序排列7 GO LOOP例 下圖右八城市，城市間的耗散值已經(jīng)給出，利用分支界限算法給出從S到t的最佳路徑。

23、動(dòng)態(tài)規(guī)劃算法：Procedure dynamic_Programming1 queue(s-s),g(s)=0 /queue中保存的是從s出發(fā)的路徑。2 Loop：ifqueue=0 then exit（fail）3 pathFIRST(queue)，n LAST(pATH) /取第一條路徑，與該路徑的最后節(jié)點(diǎn)n4 if goal(n) then exit(success)5 mj expand(n), 計(jì)算g(mj)= g(n,mj) remove(s-n,queue),add(s-mj,queue)/刪除原來的路徑，添加長度加一的路徑。6 僅保留queue中到達(dá)某一公共節(jié)點(diǎn)路徑中耗散值最小

24、的路徑，余者刪除；queue隊(duì)列中分支按g值升序排列7 GO LOOP討論 a 動(dòng)態(tài)規(guī)劃與分支界限差別在于去掉公共路徑的冗余部分，提高效率。 b 如果問題空間是樹結(jié)構(gòu)，動(dòng)態(tài)規(guī)劃與分支界限一樣。因?yàn)閷?duì)于樹結(jié)構(gòu)不存在到達(dá)同一節(jié)點(diǎn)有多重路徑的情況。C動(dòng)態(tài)規(guī)劃 改進(jìn)的代價(jià)。比如上例中，增加一個(gè)城市。A算法總結(jié)：1 初始狀態(tài)，open=（s）2 正常情況下（非成功非失敗），取open中的第一個(gè)節(jié)點(diǎn)n，將n由open 轉(zhuǎn)移到closed。3 擴(kuò)充節(jié)點(diǎn)n ，將新節(jié)點(diǎn)加入到open中4修改某些節(jié)點(diǎn)的路徑5 open中節(jié)點(diǎn)按照升序排列值得重視的一點(diǎn)：A算法失敗的唯一原因是open表為空思考題：圖中：s是起始點(diǎn)

25、t是目標(biāo)節(jié)點(diǎn)；如果存在從s到t的一條最佳路徑。而n是最佳路徑上的一點(diǎn)。1）f*(s) f*(n) f*(t) 的關(guān)系2）如果f*(s)=10 ,g*(n)=4 問h*(n)=?A*算法（最佳圖搜索算法）：A*算法定義： 對(duì)于算法A，如果有h（n） h*（n）,即h（n）以h*（n）為上界，則稱 該算法稱為A*算法。如果令h（n）=0，則滿足h（n） h*（n） 這就是分支界限算法 和動(dòng)態(tài)規(guī)劃算法。再令g(n)=d(n) (d(n)是節(jié)點(diǎn)深度）則f(n)=d(n);A*算法就是寬度優(yōu)先算法。寬度優(yōu)先算法能找到最佳解。 例：第二章中八數(shù)碼問題 令h(n)=w(n)=不在位數(shù)字個(gè)數(shù)。算法可采納性：給

26、定任意圖，設(shè)存在從開始節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑。如果算法能夠結(jié)束在s到t的最佳路徑上，則稱該算法是可采納的。A*是具有可采納性。定理1 對(duì)于有限圖，如果從s到t存在路徑，則A算法一定成功結(jié)束。推論1.1 因?yàn)锳*算法是A算法的一個(gè)特例。所以在有限圖上如果如果從s到t存在路徑，則A*算法一定成功結(jié)束。定理2對(duì)于無限圖，如果存在s到t路徑，則A*算法一定成功結(jié)束。推論2.1： open表中任一滿足f(n) f*(s)的節(jié)點(diǎn)n最終都將被A*選作擴(kuò)展節(jié)點(diǎn)。定理3：如果存在節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t路徑，則A*算法一定能找到最佳解結(jié)束。推論3.1：A*選來擴(kuò)展的節(jié)點(diǎn)都有f(n) f*(s)小結(jié)1如果存在節(jié)點(diǎn)s到

27、目標(biāo)節(jié)點(diǎn)t路徑，則A*算法一定能找到最佳解結(jié)束。2 open表中所有滿足f(n) f*(s)的節(jié)點(diǎn)n最終都將被A*選作擴(kuò)展節(jié)點(diǎn)。3 A*選來擴(kuò)展的節(jié)點(diǎn)都有f(n) f*(s) 4 f*(s)作為A*的一個(gè)衡量上限。h函數(shù)和A*算法的關(guān)系：本節(jié)重點(diǎn)來討論h函數(shù)（即啟發(fā)信息量）對(duì)A*算法搜索效率的影響總結(jié)。定義：給定兩個(gè)A*算法A1 和A2，都有f(n1)=g(n1)+h(n1)，f(n2)=g(n2)+h(n2)如果對(duì)于所有非目標(biāo)節(jié)點(diǎn)n，有h(n1) h(n2)，則算法A2 比算法A1有較多啟發(fā)信息。討論：啟發(fā)信息與h函數(shù)值成正比。極端情況下，完全沒有啟發(fā)信息時(shí)h=0，則此時(shí)A*算法就是寬度優(yōu)先

28、算法。定理：給定兩個(gè)A*算法A1 和A2 如果A2的啟發(fā)式信息比A1多，則在任何存在節(jié)點(diǎn)s到目標(biāo)節(jié)點(diǎn)t的路徑上，搜索結(jié)束時(shí)，由A2擴(kuò)展的每一個(gè)節(jié)點(diǎn)必定被A1擴(kuò)展。(A1擴(kuò)展的節(jié)點(diǎn)多)，注意搜索空間小，不代表能夠找到最佳解。當(dāng)h=0時(shí)，除最下面一層節(jié)點(diǎn)外，所有節(jié)點(diǎn)都進(jìn)入closed表。求解路徑如圖紅線所示。當(dāng)考慮到h時(shí)，被擴(kuò)充的節(jié)點(diǎn)只有s、c、 j，解路徑一樣h函數(shù)單調(diào)性限制單調(diào)性限制的作用是：避免重復(fù)計(jì)算某些節(jié)點(diǎn)的f值（主要對(duì)連通圖而言）以便減少搜索代價(jià)。單調(diào)性定義：給定一個(gè)啟發(fā)函數(shù)h，如果對(duì)于所有節(jié)點(diǎn)ni和nj (nj是ni的子節(jié)點(diǎn))，如果滿足 h(ni)-h(nj) c(ni,nj) h(t)=0,則稱h滿足單調(diào)性限制。上式可以寫成h(ni)- h(nj)+ c(ni,nj)，可以理解為三角不等式。 定理5：如果好h(n)滿足單調(diào)性限制條件，則A*