人工智能 第三章 基本的問題求解方法

1、第三章第三章 基本的問題求解方法基本的問題求解方法問題求解的過程：問題求解的過程：1 1）知識表示；）知識表示；2 2）針對問）針對問題，分析特征，選擇合適的方法來求解（包題，分析特征，選擇合適的方法來求解（包括搜索和推理）括搜索和推理）方法：方法：1 1）基于狀態(tài)圖方法）基于狀態(tài)圖方法- -搜索；搜索；2 2）基于謂詞邏輯方法）基于謂詞邏輯方法- -推理；推理；3 3）基于結構化的知識表示方法來求解問題；）基于結構化的知識表示方法來求解問題；本章介紹本章介紹搜索技術搜索技術搜索技術是人工智能的基本技術之一, 在人工智能各應用領域中被廣泛地使用。早期的人工智能程序與搜索技術聯(lián)系就更為緊密，幾乎

2、所有的早期的人工智能程序都是以搜索為基礎的。uA.Newell和HASimon-LT程序uANewell和HASimon-GPS(General Problem Solver)uR.Fikes和N.Nilsson-STRIPS(Stanford Research Institute Problem Solver)現(xiàn)在, 搜索技術滲透在各種人工智能系統(tǒng)中, 在專家系統(tǒng)、自然語言理解、自動程序設計、模式識別、機器人學、信息檢索和博奕都廣泛使用。 搜索(search)路徑l狀態(tài)序列搜索l尋找從初始狀態(tài)到目標狀態(tài)的路徑;S0Sg搜索的必要性lAI為什么要研究search?l問題沒有直接的解法;解方程組

3、;定理證明;l需要探索地求解;搜索與檢索的區(qū)別l狀態(tài)是否動態(tài)生成;l檢索: 靜態(tài);在數(shù)據(jù)庫中檢索某人的紀錄;l搜索: 動態(tài)生成;下棋幾個問題l 目標狀態(tài)是否確定?l確定: 定理證明, eight-puzzlel不確定: 求積分, 下棋;確定目標的性質;l 問題的解: 路徑(解路徑)/目標狀態(tài);需要路徑:下棋 不需要路徑:電路設計 需要/不需要: 診病l 約束條件l目標狀態(tài)不確定時, 用來約束目標狀態(tài)的性質; lX+Y=4: 非整數(shù)解/整數(shù)解幾個問題(續(xù)1)多解性;lX+Y=4:整數(shù)解最優(yōu)解l評價標準/判斷準則;lmin(x*y)l北京-上海: 時間最短/費用最少最優(yōu)解是否唯一?l下棋搜索問題狀

4、態(tài)空間2375148612384765搜索不是檢索2375148612384765難點2375148612384765啟發(fā)式方法2375148612384765搜索方法的評價標準 搜索問題是AI核心理論問題之一。一般一個問題可以用好幾種搜索技術解決, 選擇一種好的搜索技術對解決問題的效率很有關系, 甚至關系到求解問題有沒有解。 搜索方法好的標準, 一般認為有兩個： (1)搜索空間小; (2)解最佳。 搜索分類搜索從問題性質上來看, 可分為一般搜索和博奕搜索, 從處理方法上來看, 可分為盲目搜索和啟發(fā)式搜索。還可以分得更細。到目前為止, AI領域中已提出許多具體的搜索方法, 概括起來有： (1)

5、求任一解路的搜索策略回溯法；爬山法(Hill Climbing)；寬度優(yōu)先法(Breadth-first)；深度優(yōu)先法(Depth-first) (2)求最佳解路的搜索策略大英博物館法(British Museum)；最佳圖搜索法(A*) (3)求與或關系解圖的搜索法一般與或圖搜索法(AO*)；極小極大法(Minimax)剪枝法(Alpha-beta Pruning)；啟發(fā)式剪枝法(Heuristic Pruning) TOPICS回溯策略（ Backtracking ）圖搜索（GRAPHSEARCH）無信息搜索啟發(fā)式搜索TOPIC1 BacktrackingN1N0N2 N3 N4 N5 回

6、溯策略例：四皇后問題QQQQ()()Q(1,1)()QQ(1,1)(1,1)(2,3)()Q(1,1)(1,1)(2,3)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)Q(1,1)(2,4)(3.2)()QQ(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()Q(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4

7、)(3.2)Q(1,2)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)Q(1,2)Q(1,2)(2,4)Q(1,2)(2,4)(3,1)QQQQ()(1,1)(1,1)(2,3)(1,1)(2,4)(1,1)(2,4)(3.2)(1,2)(1,2)(2,4)(1,2)(2,4)(3,1)(1,2)(2,4)(3,1)(4,3)存在問題及解決辦法問題和解決方法：l深度問題對搜索深度加以限制l死循環(huán)問題狀態(tài)重復: AB，BC, CA 記錄從初始

8、狀態(tài)到當前狀態(tài)的路徑TOPIC2 GRAPH SEARCH圖搜索策略問題的引出l回溯搜索：只保留從初始狀態(tài)到當前狀態(tài)的一條路徑。l圖搜索：保留所有已經搜索過的路徑。N5 N1N0N2 N3 N4 一些基本概念圖：一個節(jié)點的集合。節(jié)點由弧連接起來。 有向圖：弧是一個節(jié)點指向另一個節(jié)點的圖，稱為有向圖。 后繼/父親：如果有一條弧從ni指向nj，則nj稱為n i的后繼，ni稱為nj的父輩（父親）； 一些基本概念(續(xù)1)路徑：如果存在一個節(jié)點序列（ni0，ni1，nik），nij是nij-1是的后繼，j=1，k，則稱這個序列是從節(jié)點ni0到節(jié)點nik的一條路徑，長度為k。祖先/后裔：如果存在一條從ni

9、到nj的路徑，則稱nj是ni的后裔，ni稱為nj的祖先。樹：每個節(jié)點最多只有一個父輩。沒有父輩的節(jié)點稱為根節(jié)點。沒有后繼的節(jié)點稱為葉節(jié)點。 一些基本概念(續(xù)2)節(jié)點深度：根節(jié)點深度=0其它節(jié)點深度=父節(jié)點深度+10123一些基本概念（續(xù)3）擴展一個節(jié)點l生成出該節(jié)點的所有后繼節(jié)點?；〉馁M用l有一條弧連接ni和nj兩個節(jié)點, 用C(ni, nj)表示使用規(guī)則從ni到nj的費用(耗散值)。 玉泉路-天安門路徑的耗散值l一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。GRAPHSEARCH的思路OPEN表l已經生成但未擴展節(jié)點CLOSED

10、表l已擴展節(jié)點擴展節(jié)點i生成節(jié)點j 指針 調整指針圖搜索（圖搜索（Graph Search）的一般過程的一般過程 1 1、建立一個只有起始節(jié)點、建立一個只有起始節(jié)點S S的搜索圖的搜索圖G G，把，把S S放入一個叫放入一個叫openopen的的未擴展節(jié)點表；未擴展節(jié)點表；2 2、 建立已擴展節(jié)點表建立已擴展節(jié)點表closedclosed，初始為空；初始為空；3 3、 LOOPLOOP；若；若openopen為空，則失敗退出；為空，則失敗退出；4 4、 選選openopen表中的第一個節(jié)點，設為表中的第一個節(jié)點，設為n n，移入移入closedclosed表；表；5 5、若、若n n為目標節(jié)點

11、，則成功退出，該問題的解即是為目標節(jié)點，則成功退出，該問題的解即是G G中沿中沿S S指向指向n n的路徑；的路徑；6 6、若不是目標節(jié)點，則擴展、若不是目標節(jié)點，則擴展n n，生成不是生成不是n n的祖先的那些后繼的祖先的那些后繼節(jié)點的集合節(jié)點的集合m m，把，把m m的成員作為的成員作為n n的后繼加入的后繼加入G G中；中；7 7、對未曾在、對未曾在G G中出現(xiàn)過的中出現(xiàn)過的m m成員，設一通向成員，設一通向n n的指針，把它們加的指針，把它們加入入openopen表。對已在表。對已在closedclosed或或openopen表上的表上的m m成員，確定是否要更成員，確定是否要更改到改

12、到n n的指針方向，對已在的指針方向，對已在closedclosed上的上的m m成員，確定是否要更改成員，確定是否要更改G G中通向每個后裔節(jié)點的指針方向。中通向每個后裔節(jié)點的指針方向。8 8、按某一方式（深度優(yōu)先、寬度優(yōu)先、按某一方式（深度優(yōu)先、寬度優(yōu)先、A A* *算法）重排算法）重排openopen表表9 9、GO LOOP GO LOOP 例子SOPENCLOSES 123 S 1,2,3 S 2,1,3 S 451,3 S,2 1,3,4,5 S,2 3,1,4,5 S,2 1,4,5 S,2,3 61,4,5,6 S,2,3 例：右圖中黑節(jié)點表示例：右圖中黑節(jié)點表示已擴展，白節(jié)點

13、表示未已擴展，白節(jié)點表示未擴展，問題：先擴展擴展，問題：先擴展6 6號號節(jié)點生成節(jié)點生成m1=4m1=4，77，然，然后擴展節(jié)點后擴展節(jié)點1 1，生成，生成m2=2m2=2，按算法第七步按算法第七步重新修改原圖。重新修改原圖。612453難點！算法中第七步7擴展節(jié)點6生成m1=4，7的調整61245371235467再擴展節(jié)點1生成m2=2的調整12354671235467最終結果61245371235467圖搜索與回溯算法的區(qū)別 擴展節(jié)點:l回溯算法:生成一個兒子節(jié)點. l圖搜索:擴展節(jié)點, 生成所有兒子節(jié)點. 候選節(jié)點:l回溯算法:一個. l圖搜索:多個. 回溯:l回溯算法:返回父親節(jié)點.

14、 l圖搜索:不一定返回父親節(jié)點.TOPIC3 無信息搜索如果在GRAPHSEARCH中，對節(jié)點的排序不使用與問題相關的信息，則稱為無信息圖搜索（盲目搜索）寬度優(yōu)先和深度優(yōu)先1 1、breadth-first searchbreadth-first searchp寬度優(yōu)先搜索：如果搜索是以接近起始節(jié)點寬度優(yōu)先搜索：如果搜索是以接近起始節(jié)點的程度依次擴展節(jié)點的的程度依次擴展節(jié)點的 。 p搜索逐層進行；在對下一層的任一節(jié)點進行搜索逐層進行；在對下一層的任一節(jié)點進行搜索之前，必須搜索完本層的所有節(jié)點。搜索之前，必須搜索完本層的所有節(jié)點。(1) (1) 把起始節(jié)點放到把起始節(jié)點放到OPENOPEN表中表

15、中( (如果該起始節(jié)點為如果該起始節(jié)點為一目標節(jié)點，則求得一個解答一目標節(jié)點，則求得一個解答) )。(2) (2) 如果如果OPENOPEN是個空表，則沒有解，失敗退出；是個空表，則沒有解，失敗退出；否則繼續(xù)。否則繼續(xù)。(3) (3) 把第一個節(jié)點把第一個節(jié)點( (節(jié)點節(jié)點n)n)從從OPENOPEN表移出，并把它表移出，并把它放入放入CLOSEDCLOSED的擴展節(jié)點表中。的擴展節(jié)點表中。(4) (4) 擴展節(jié)點擴展節(jié)點n n。如果沒有后繼節(jié)點，則轉向上述。如果沒有后繼節(jié)點，則轉向上述第第(2)(2)步。步。(5) (5) 把把n n的所有后繼節(jié)點放到的所有后繼節(jié)點放到OPENOPEN表的末

16、端，并提表的末端，并提供從這些后繼節(jié)點回到供從這些后繼節(jié)點回到n n的指針。的指針。(6) (6) 如果如果n n的任一個后繼節(jié)點是個目標節(jié)點，則找的任一個后繼節(jié)點是個目標節(jié)點，則找到一個解答，成功退出；否則轉向第到一個解答，成功退出；否則轉向第(2)(2)步。步。算法1234567891011121314151617 1819 2122 23 24 2627 282930311234567891011121314151617 1819 2 34 5 678 9 10 11 12 13 14 15 16 17 18 1912345678910123456789搜索演示已擴展節(jié)點正在擴展節(jié)點擴展

17、的子節(jié)點未擴展節(jié)點目標寬度優(yōu)先法應用示例寬度優(yōu)先法應用示例寬度優(yōu)先法求九宮重排問題寬度優(yōu)先法求九宮重排問題231847651238476523184765231847652831476523184765283147652831647528314765283164752831647528371465832147652814376528314576123784651238476512567312384765目標8234187654p寬度優(yōu)先搜索是圖搜索一般過程的特殊情寬度優(yōu)先搜索是圖搜索一般過程的特殊情況，將圖搜索一般過程中的第況，將圖搜索一般過程中的第8 8步具體化為本步具體化為本算法中的第算法

18、中的第6 6步，這實際是將步，這實際是將OPENOPEN表作為表作為“先先進先出進先出”的隊列進行操作。的隊列進行操作。p一定能找到解一定能找到解p找到的解一定是最佳解找到的解一定是最佳解u(在每個路徑消耗是同樣的意義上在每個路徑消耗是同樣的意義上)p搜索的空間大、慢。搜索的空間大、慢。 分析分析p深度優(yōu)先搜索：首先擴展最新產生的深度優(yōu)先搜索：首先擴展最新產生的( (即最即最深的深的) )節(jié)點。深度相等的節(jié)點可以任意排列。節(jié)點。深度相等的節(jié)點可以任意排列。p特點：擴展最深的節(jié)點特點：擴展最深的節(jié)點, ,使得搜索沿著狀態(tài)使得搜索沿著狀態(tài)空間某條單一的路徑從起始節(jié)點向下進行下空間某條單一的路徑從起

19、始節(jié)點向下進行下去；只有當搜索到達一個沒有后裔的狀態(tài)時，去；只有當搜索到達一個沒有后裔的狀態(tài)時，它才考慮另一條替代的路徑。它才考慮另一條替代的路徑。p算法：與寬度優(yōu)先相似，不同在于：算法：與寬度優(yōu)先相似，不同在于：(5) (5) 把把n n的所有后繼節(jié)點放到的所有后繼節(jié)點放到OPENOPEN表的前端表的前端2 2、depth-first searchdepth-first search34567891011121314151617 1819 20 21 23 24 2627 2829303112活結點表活結點表1 1211242248448168816168178817178 84944918

20、991818919919194 425225105510209 9 91010202010211010212110105115511演示例 九宮重排問題九宮重排問題28 3 16 427 5初始狀態(tài)初始狀態(tài)1 2 3 8 47 6 5目標狀態(tài)目標狀態(tài)應用示例應用示例2 32 31 8 41 8 47 6 57 6 5 2 32 31 8 41 8 47 6 57 6 52 8 32 8 31 41 47 6 57 6 52 32 31 8 41 8 47 6 57 6 52 8 32 8 31 41 47 6 57 6 52 8 32 8 31 6 41 6 47 57 52 8 32 8 3

21、 1 4 1 47 6 57 6 52 8 32 8 31 6 41 6 47 57 52 8 32 8 31 6 41 6 4 7 5 7 52 8 32 8 37 1 47 1 4 6 5 6 5 8 38 32 1 42 1 47 6 57 6 52 82 81 4 31 4 37 6 57 6 52 8 32 8 31 4 51 4 57 6 7 6 1 2 31 2 37 8 47 8 4 6 5 6 51 2 31 2 38 48 47 6 57 6 52 8 32 8 3 6 4 6 41 7 51 7 52 8 32 8 31 61 67 5 47 5 48 38 32 1 4

22、2 1 47 6 57 6 52 8 32 8 37 1 47 1 46 56 52 82 81 4 31 4 37 6 57 6 52 8 32 8 31 4 51 4 57 67 612 23 34 45 56 67 78 89 9a ab bd d1 2 31 2 3 8 4 8 47 6 57 6 5目標目標分析不一定能找到解。解不一定是最佳解。 3 3、其他方法、其他方法p含有深度界限的深度優(yōu)先搜索算法：含有深度界限的深度優(yōu)先搜索算法：p基于代價樹的搜索算法：基于代價樹的搜索算法：TOPIC4 TOPIC4 heuristic searchp盲目搜索效率低，耗費過多的計算空間與時盲目

23、搜索效率低，耗費過多的計算空間與時間，這是組合爆炸的一種表現(xiàn)形式。間，這是組合爆炸的一種表現(xiàn)形式。 p利用知識來引導搜索，達到減少搜索范圍，利用知識來引導搜索，達到減少搜索范圍，降低問題復雜度的目的。降低問題復雜度的目的。p啟發(fā)式方法啟發(fā)式方法的本質是部分地放棄算法的本質是部分地放棄算法一般一般化化, 通用化通用化的概念的概念, 把所要解的問題的具體領把所要解的問題的具體領域域 的知識加進算法中去的知識加進算法中去, 以提高算法的效率。以提高算法的效率。 啟發(fā)式搜索啟發(fā)式搜索：就是利用與問題有關的啟發(fā)信：就是利用與問題有關的啟發(fā)信息進行搜索息進行搜索啟發(fā)信息：與具體問題有關的特性信息啟發(fā)信息：

24、與具體問題有關的特性信息啟發(fā)信息的強度啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到強：降低搜索工作量，但可能導致找不到最優(yōu)解最優(yōu)解弱：一般導致工作量加大，極限情況下變弱：一般導致工作量加大，極限情況下變?yōu)槊つ克阉?，但可能可以找到最?yōu)解為盲目搜索，但可能可以找到最優(yōu)解難點：難點：獲?。猾@取；強度的確定；強度的確定；啟發(fā)信息的用途a a、用于決定要擴展的下一節(jié)點（避免盲目、用于決定要擴展的下一節(jié)點（避免盲目擴展）擴展）b b、在擴展過程中，用于決定生成哪一個或、在擴展過程中，用于決定生成哪一個或哪幾個后繼（以免太多無用節(jié)點）哪幾個后繼（以免太多無用節(jié)點）C C、用于決定被拋棄、用于決定被拋棄

25、oror被修剪的節(jié)點（博羿被修剪的節(jié)點（博羿中常用，其它不常見）中常用，其它不常見）?；舅枷雴l(fā)式搜索過程中, 要對OPEN表進行排序, 這就需要有一種方法來計算待擴展節(jié)點有希望通向目標節(jié)點的不同程度, 我們總是希望能找到最有希望通向目標節(jié)點的待擴展節(jié)點優(yōu)先擴展。 希望的量度就是通過估價函數(shù)f（n）來描述的p估價函數(shù)：定義為從初始節(jié)點經過估價函數(shù)：定義為從初始節(jié)點經過n n節(jié)點到達節(jié)點到達目的節(jié)點的路徑的最小代價的估計值，目的節(jié)點的路徑的最小代價的估計值，XWZg(X)h(X)估價函數(shù)的形式為估價函數(shù)的形式為f(n)=g(n)+h(n)g g（n n）是是到目前為止到目前為止, , 從從s

26、s到到n n的最小路徑的最小路徑 （實（實際值）際值）h h（n n） n n節(jié)點到目標節(jié)點到目標節(jié)點最佳路徑的估計值，節(jié)點最佳路徑的估計值，體現(xiàn)了啟發(fā)信息體現(xiàn)了啟發(fā)信息通常通常f f（n n）由經驗和直）由經驗和直覺得到的，有很多種取法，覺得到的，有很多種取法，關鍵在于關鍵在于h h（n n）。）。e eg g八數(shù)碼難題的估價函數(shù)八數(shù)碼難題的估價函數(shù)f f（n n）=g=g（n n）+h+h（n n）d d（n n）：）：節(jié)點節(jié)點n n的深度的深度w w（n n）：）：不在位的數(shù)字個數(shù)不在位的數(shù)字個數(shù)p p（n n）：）：不在位的數(shù)字離目標的距離之和不在位的數(shù)字離目標的距離之和例：右圖（例：

27、右圖（a a）中中2 2、8 8、1 1、6 6不在位，不在位，w w（n n）=4 =4 ，p p（n n）=1+2+1+1=5=1+2+1+1=5；（b b）6 6、8 8、2 2、1 1不不在位，在位，w w（n n）=4 =4 ，p p（n n）=3+2+2+2=9 =3+2+2+2=9 2831647568321475abc81263754s（n）：沿著周圍那些非中心方格上依順時針方向檢查n格局中每一將牌，如果其后緊跟的將牌正好是目標格局中該將牌的后續(xù)者，則該將牌得0分，否則得2分；在中中方格上有將牌得1分，無得0分；將所有將牌得分之和即為s（n）。圖（c）中s（a）=6。 2831

28、647568321475abc81263754例子: eight-puzzlen評價函數(shù)nf(n) = d(n) + W(n)nd(n): 節(jié)點n的深度;nW(n):與目標相比, 錯位的數(shù)字數(shù)目，即不在位的數(shù)字個數(shù);1238476528316475初始狀態(tài)目標狀態(tài) 2831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7

29、)目標123456由前例看出, 與深度優(yōu)先搜索和寬度優(yōu)先搜索相比較, 啟發(fā)式搜索大大減少了搜索范圍, 大大減少了擴展的節(jié)點, 大大減少了生成的節(jié)點, 從而達到降低問題復雜度, 提高算法的效率的目的。 估價函數(shù)的進一步說明nSg*(n)h*(n) gf*(n)=g*(n)+h*(n)：從s經過n到g的最短路徑lg*(n)：從s到n的最短路徑lh*(n)：從n到g的最短路徑f（n）=g（n）+h（n）：從s經過n到g的最短路徑的估計值lg(n)、h(n) 分別是g*(n)、h*(n) 的估計值g(n)l一般取實際走過的路徑的費用和.lg(n) g*(n)l隨著算法的執(zhí)行，由于指針的變動，g(n)會

30、下降. h0l沒有啟發(fā)式信息;啟發(fā)式搜索算法A算法A*算法A算法在Graphsearch過程中，如果第8步的重排open表是依據(jù)f（n）=g（n）+h（n）進行的，則稱該過程為A算法。lg(n)取實際走過的路徑的費用和;l節(jié)點排序是按照f(n)從小到大排;l如前例-九宮重排問題算法A*在A算法中，如果滿足條件： 0h(n)h*(n)則A算法稱為A*算法。l稱h（x）為h*（x）的下界，它表示某種偏于保守的估計。啟發(fā)式搜索算法A*又稱為最佳圖搜索算法(Optimal Search)。 5 5、經典例題（八數(shù)碼難題）：、經典例題（八數(shù)碼難題）：設有八數(shù)碼難題，起始狀態(tài)如右圖，設有八數(shù)碼難題，起始狀

31、態(tài)如右圖，要求找出九宮重排的最終解路徑，要求找出九宮重排的最終解路徑，并畫框圖。并畫框圖。28316475解法一：解法一：第一步：取估價函數(shù)為第一步：取估價函數(shù)為f f（n n）=d=d（n n）+w+w（n n），），則顯然按照定義則顯然按照定義1 1它是它是A A算法；算法；第二步：因為第二步：因為w w（n n）指的是不在位的個數(shù)，所以指的是不在位的個數(shù)，所以w w（n n）=4=4，即估計只需要走，即估計只需要走4 4步即可到達目標狀步即可到達目標狀態(tài)，而實際上要到達目標狀態(tài)肯定要大于態(tài)，而實際上要到達目標狀態(tài)肯定要大于3 3步，步，即即w w（x x）w w* *（x x），），滿足

32、定義，所以是滿足定義，所以是A A* *算法；算法；第三步：畫圖，并計算各個狀態(tài)第三步：畫圖，并計算各個狀態(tài)f f（n n）的值，取的值，取f f（n n）值最小的節(jié)點進行擴充。值最小的節(jié)點進行擴充。( (圖見前圖見前) )解法二：取估價函數(shù)為f（n）=d（n）+P（n），同理也是A*算法；如圖Tips A算法與A*算法區(qū)別區(qū)別在于在A*算法中， 0h(n)h*(n)示例：八數(shù)碼難題中h(n)的三種定義h(n)=w(n), h(n)=p(n)-A*算法h(n)=p(n)+3s(n)-A算法A*算法具有可采納性 一般地說對任意一個圖, 當s到目標節(jié)點有一條路徑存在時, 如果搜索算法總是在找到一條

33、從s到目標節(jié)點的最佳路徑上結束, 則稱該搜索算法是可采納的(Admissibility)。lA*就具有可采納性即當問題有解時, A*一定能找到一條到達目標節(jié)點的最佳路徑。（why？）證明見參考資料-A*算法具有可采納性考慮h(n)0的情況！A*算法的理論意義 A*算法的理論意義在于給出了求解最佳解的條件h(n) h*(n) 對給定的問題,函數(shù)h*(n)在問題有解的條件下客觀上是存在的。但在問題求解過程中不可能都明確知道。因此, 對實際問題, 能不能使所定義的啟發(fā)函數(shù)滿足下界范圍條件? 這是個問題。如果困難很大, 那未A*算法的實際應用就會受到限制。 以前面-八數(shù)碼難題為例定義h(n)為任意節(jié)點與目標之間的差異若取= w(n)(將牌不在位個數(shù)), 那未很容易看出, 盡管我們對具體的h*(n)是多少很難確切知道, 但根據(jù)“不在位”將牌個數(shù)這個估計, 就能得出至少要移動W(n)步才能到達目標, 顯然有h(n) = W(n) h*(n)。進一步考慮任意節(jié)點與目標之間距離的信息, 即取h(n) = p(n), p(n)定義為每一個將牌與其目標位置之間距離(不考慮夾在其間的將牌)的總和,那未同樣能斷定至少也要移動p(n)步才能達到目