1、人工智能原理Principles of Artificial Intelligence信息學院搜索技術（一） 主要內(nèi)容概述狀態(tài)空間的搜索狀態(tài)空間的一般搜索過程盲目搜索啟發(fā)式搜索約束滿足問題博弈概述(1)問題求解AI中每個研究領域都有其各自的特點和規(guī)律,但就求解問題的過程看,都可抽象為一個問題求解過程.問題求解過程實際上是一個搜索,廣義地說,它包含了全部計算機科學1974年，Nilsson歸納出的AI研究的基本問題知識的模型化和表示常識性推理、演繹和問題解決啟發(fā)式搜索人工智能系統(tǒng)和語言本章討論的表示主要包括:狀態(tài)空間表示問題空間表示搜索(2)什么是搜索根據(jù)問題的實際情況不斷尋找可利用的知識,構造

2、出一條代價較少的推理路線,使問題得到圓滿解決的過程稱為搜索 包括兩個方面： - 找到從初始事實到問題最終答案的一條推理路徑 - 找到的這條路徑在時間和空間上復雜度最小搜索分兩大類:盲目搜索:也稱為無信息搜索，即只按預定的控制策略進行搜索,在搜索過程中獲得的中間信息不用來改進控制策略啟發(fā)式搜索: 在搜索中加入了與問題有關的啟發(fā)性信息,用于指導搜索朝著最有希望的方向進行,加速問題的求解過程并找到最優(yōu)解狀態(tài)空間表示法(1)狀態(tài)空間表示法：用來表示問題及其搜索過程的一種方法狀態(tài)狀態(tài)是描述問題求解過程中任一時刻狀況的數(shù)據(jù)結構.23751486A，B，C，D（2, 3,7 ,0 , 5, 2, 4, 8,

3、 6）狀態(tài)空間表示法(2)一般一個搜索問題由四個部分組成：初始狀態(tài)集合：定義了agent所處的環(huán)境；操作符集合：把一個問題從一個狀態(tài)變換為另一個狀態(tài)的動作；目標檢測函數(shù)：agent用來確定一個狀態(tài)是不是目標；路徑費用函數(shù)：對每條路徑賦予一定費用的函數(shù)。初始狀態(tài)集合和操作符集合定義了問題的搜索空間吸塵器問題states? 灰塵和吸塵器的位置 ，共有2228actions? Left, Right, Suckgoal test? 所有位置都沒有灰塵path cost? 每一步消耗為1八數(shù)碼問題states? 數(shù)字的位置 ，共有9！/2=181440actions? 空格的上下左右移動goal te

4、st? 給定的目標狀態(tài)path cost? 每一步消耗為1狀態(tài)空間表示法（3）二階梵塔問題設有三個鋼針,在一號鋼針上穿有A,B兩個金片,A小于B,A位于B的上面.要求把這兩個金片全部移到另一個鋼針上,而且規(guī)定每次只能移動一片,任何時刻都不能使B位于A的上面設用Sk=(Sk0,Sk1)表示問題的狀態(tài),SK0表示金片A所在的鋼針號,SK1表示金片B所在的鋼針號,全部可能的狀態(tài)為:S0=(1,1), S1=(1,2), S2=(1,3)S3=(2,1), S4=(2,2), S5=(2,3)S6=(3,1), S7=(3,2), S8=(3,3)問題初始狀態(tài)集合S=S0,目標狀態(tài)集合G=S4,S8.

5、算符:A( i,j):表示把金片A從第i號針移到第j號針上B(i,j):表示把B從第i號針移到第j號針上共12個算符:A(1,2), A(1,3), A(2,1) ,A(2,3), A(3,1),A(3,2)B(1,2), B(1,3), B(2,1), B(2,3), B(3,1), B(3,2)狀態(tài)空間表示法（4）用狀態(tài)空間表示,首先必須定義狀態(tài)的描述形式,把問題的一切狀態(tài)都表示出來,其次定義算符,完成狀態(tài)的轉換問題的求解過程就是一個把算符不斷地作用于狀態(tài)的過程.如果在使用某個算符后得到的狀態(tài)就是目標狀態(tài),就得到了問題的解.這個解就是從初始狀態(tài)到目標狀態(tài)所用算符構成的序列.算符的一次使用,

6、就使問題由一種狀態(tài)轉變?yōu)榱硪环N狀態(tài).可能有多個算符序列都可使問題從初始狀態(tài)變到目標狀態(tài),這就得到了多個解.對任何一個狀態(tài),可使用的算符可能不止一個,這樣由一個狀態(tài)所生成的后繼狀態(tài)可能有多個.如何選擇下一步的操作,由搜索策略決定.回溯搜索控制策略（1）例：四皇后問題( )( )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)(

7、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) (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)

8、 (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)回溯搜索控制策略（2）對于n皇后問題可用于對搜索算法進行測試對這類問題的形式化描述主要有兩類：增量形式化：包括了增加狀態(tài)描述的算符，從空狀態(tài)開始；這意味著每次行動添加一個皇后到狀態(tài)中去完全狀態(tài)形式化：把8個皇后都放在棋盤上，然后移動它們。現(xiàn)實問題旅行商問題超大規(guī)模集成電路的布局問題機器人導航問題.度量問題求解的性能一般搜索策略可以通過下面四個準則來評價：完備性

9、：如果存在一個解答，該策略是否保證能夠找到？時間復雜性：需要多長時間可以找到解答？空間復雜性：執(zhí)行搜索需要多少存儲空間？最優(yōu)性：如果存在不同的幾個解答，該策略是否可以發(fā)現(xiàn)最高質(zhì)量的解答？搜索策略反映了狀態(tài)空間或問題空間擴展的方法，也決定了狀態(tài)或問題的訪問順序。在AI領域，狀態(tài)空間圖由初始狀態(tài)和算子隱含地表示，經(jīng)常是無限的，它的復雜度根據(jù)下面三個值來表達： 分支因子b：任何節(jié)點的后繼的最大個數(shù)最淺的目標節(jié)點的深度d狀態(tài)空間中任何路徑的最大長度m與/或樹表示法（1）基本概念與/或樹是用于表示問題及其求解過程的又一種形式化方法.復雜問題的簡化方法分解:把一個問題分解到不需再分解或不能再分解為止,然后

10、對每個子問題進行求解,然后把各子問題的解復合起來,就得到原問題的解.等價變換:利用同構或同態(tài)的等價變換,把復雜問題轉換成若干個較為容易求解的新問題.若新問題中有一個可求解,則就得到了原問題的解.與/或樹表示法（2）三階梵塔問題設有A,B,C三個金片以及三個鋼針,三個金片按自上而下從小到大的順序穿在1號鋼針上,要求把它們?nèi)恳频?號鋼針上,而且每次只能移到一個金片,任何時候都不能把大的金片壓在小的金片上面.用與/或樹表示:問題分解(1)為了把三個金片全部移到3號針上,必須先把C移到3號針上(2)為了移到C,必須把A和B移到2號針上(3)當C移到3針后,就可把A和B移到3針上,完成問題求解得到三個

11、子問題(1)把A和B移到2號針的雙金片問題(2)把C移到3號針的單金片問題(3)把A和B移到3號針的雙金片問題狀態(tài)空間搜索過程要點（1）求解一個能夠滿足目標條件的問題可以表達為搜索一個圖以找到一個滿足目標狀態(tài)描述的節(jié)點問題。搜索過程的要點如下:起始節(jié)點:對應于初始狀態(tài)描述后繼節(jié)點:把適用于某個節(jié)點狀態(tài)描述的一些算符用來推算該節(jié)點而得到的新節(jié)點,稱為該節(jié)點的后繼節(jié)點指針:從每個后繼節(jié)點返回指向其父輩節(jié)點檢查各后繼節(jié)點看是否為目標節(jié)點.搜索過程擴展后繼節(jié)點的次序如果搜索是以接近起始節(jié)點的程度(由節(jié)點之間連結弧線的數(shù)目來衡量)依次擴展節(jié)點,稱為廣(寬)度優(yōu)先搜索如果搜索時首先擴展最新產(chǎn)生的節(jié)點,稱為

12、深度優(yōu)先搜索狀態(tài)空間搜索過程要點（2）調(diào)整指針擴展一個節(jié)點生成出該節(jié)點的所有后繼節(jié)點。弧的費用有一條弧連接ni和nj兩個節(jié)點, 用C(ni, nj)表示從ni到nj的費用(耗散值)。 路徑的耗散值一條路徑的耗散值等于連接這條路徑各節(jié)點間所有耗散值的總和。用C(ni, nj)表示從ni到nj的路徑的耗散值。狀態(tài)空間的一般搜索過程（1）主要數(shù)據(jù)結構OPEN表:存放剛生成的節(jié)點,是還未擴展的節(jié)點.一般是端節(jié)點.CLOSED表:存放將要擴展或已擴展的節(jié)點.或者是已被擴展但還沒有在搜索樹中生成后繼節(jié)點的端節(jié)點,或者是非端節(jié)點狀態(tài)空間的一般搜索過程（2）(1)把初始節(jié)點S0放入OPEN表,并建立目前只包含

13、S0的圖,記為G(2)檢查OPEN表是否為空,若為空則問題無解,退出(3)把OPEN表的第一個節(jié)點取出放入CLOSED表,記該節(jié)點為n(4)考察n是否為目標節(jié)點.如是,則問題得解,退出(5)擴展節(jié)點n,生成一組子節(jié)點.把其中不是節(jié)點n先輩的那些節(jié)點記作集合M,并把這些子節(jié)點作為節(jié)點n的子節(jié)點加入G中(6)針對M中子節(jié)點的不同情況,分別進行處理對于那些未曾在G中出現(xiàn)過的M成員設置一個指向父節(jié)點(即n)的指針,并把它們放入OPEN表對于那些先前已在G中出現(xiàn)過的M成員,確定是否需要修改它指向父節(jié)點的指針對于那些先前已在G中出現(xiàn)并且已經(jīng)擴展了的M成員,確定是否需要修改其后繼節(jié)點指向父節(jié)點的指針(7)按

14、某種搜索策略對OPEN表中的節(jié)點進行排序(8)轉第(2)步例子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 2S13451,2,3 S 3,1,2 S OPENCLOSES 4,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1414,10,11,9,7,5,2 S,3,

15、4,6,8,1,12,13 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 14OPEN表中的節(jié)點修改指針2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121

16、313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 2S131,2,3 S 3,1,2 S OPENCLOSES 2454,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的節(jié)點修改指針2S131,2,3 S 3,1,2 S OPENCLOSES 24

17、54,5,1,2 S,3 676,7,5,1,2 S,3,4 898,9,7,5,1,2 S,3,4,6 10,11,9,7,5,1,2 S,3,4,6,8 1011121313,10,11,9,7,5,2 S,3,4,6,8,1,12 1413,10,11,9,7,5 S,3,4,6,8,1,12,2 CLOSE表中的節(jié)點(8)的后裔(10)修改指針狀態(tài)空間的一般搜索過程(3)這是一個通用的搜索過程,后面討論的狀態(tài)空間各種搜索策略都是其特例.各種搜索策略的主要區(qū)別就是對OPEN表中節(jié)點排序準則不同算法結束后，將生成一個圖G，稱為搜索圖。同時由于每個節(jié)點都有一個指針指向父節(jié)點，這些指針指向的節(jié)

18、點構成G的一個支撐樹，稱為搜索樹。 從目標節(jié)點開始，將指針指向的狀態(tài)回串起來，即找到一條解路徑.盲目搜索盲目 搜索策略只使用問題定義中的信息寬度優(yōu)先搜索代價一致搜索深度優(yōu)先搜索深度有限搜索迭代加深搜索廣度優(yōu)先搜索（1）搜索過程如下:(1)把初始節(jié)點S0放入OPEN表(2)如果OPEN表為空,則問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)考查節(jié)點n是否為目標節(jié)點.若是,則求得了問題的解,退出(5)若節(jié)點n不可擴展,則轉第(2)步(6)擴展節(jié)點n,將其子節(jié)點放入OPEN表的尾部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉第(2)步擴展最淺的未擴展的節(jié)點實

19、現(xiàn):FIFO隊列2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 51256731 2 3 8 47 6 5目標82 3 41 8 7 6 54廣度優(yōu)先搜索（2）Complete? Yes (如果 b 是有限的)Time? 1+b+b2+b3+ +

20、bd + b(bd-1) = O(bd+1)Space? O(bd+1)Optimal? Yes (如果每步代價為1)空間是大問題(和時間相比)特點缺點當目標節(jié)點距離初始節(jié)點較遠時會產(chǎn)生許多無用的節(jié)點,搜索效率低優(yōu)點只要問題有解,則總可以得到解,而且是最短路徑的解深度優(yōu)先搜索（1）搜索過程如下:(1)把初始節(jié)點S0放入OPEN表(2)如果OPEN表為空,則問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)考查節(jié)點n是否為目標節(jié)點.若是,則求得了問題的解,退出(5)若節(jié)點n不可擴展,則轉第(2)步(6)擴展節(jié)點n,將其子節(jié)點放入OPEN表的首部,并為每一個子

21、節(jié)點都配置指向父節(jié)點的指針,轉第(2)步擴展最深的未擴展節(jié)點實現(xiàn): LIFO隊列2 31 8 47 6 5 2 31 8 47 6 52 8 31 47 6 52 31 8 47 6 52 8 31 47 6 52 8 31 6 47 52 8 3 1 47 6 52 8 31 6 47 52 8 31 6 4 7 52 8 37 1 4 6 5 8 32 1 47 6 52 81 4 37 6 52 8 31 4 57 6 1 2 37 8 4 6 51 2 38 47 6 52 8 3 6 41 7 52 8 31 67 5 48 32 1 47 6 52 8 37 1 46 52 81

22、4 37 6 52 8 31 4 57 623456789abcd1 2 3 8 47 6 5目標深度優(yōu)先搜索（2）Complete? No: 當空間為無限深度時Time? O(bm): 如果 m 比d大很多則比較嚴重Space? O(bm), 線性空間Optimal? No特點缺點如果目標節(jié)點不在搜索所進入的分支上,而該分支又是一個無窮分支,則就得不到解.因此該算法是不完備的優(yōu)點如果目標節(jié)點不在搜索所進入的分支上,則可以較快地得到解有界深度優(yōu)先搜索定義搜索深度的界限dm,當搜索深度達到了深度界限,而尚未出現(xiàn)目標節(jié)點時,就換一個分支進行搜索搜索過程如下:(1)把初始節(jié)點S0放入OPEN表,置S

23、0的深度d(S0)=0(2)如果OPEN表為空,則問題無解,退出(3)把OPEN表的第一個節(jié)點(記為節(jié)點n)取出,放入CLOSED表(4)考查節(jié)點n是否為目標節(jié)點.若是,則求得了問題的解,退出(5)如果節(jié)點n的深度d(節(jié)點n)=dm,則轉第(2)步(6)若節(jié)點n不可擴展,則轉第(2)步(7)擴展節(jié)點n,將其子節(jié)點放入OPEN表的首部,并為每一個子節(jié)點都配置指向父節(jié)點的指針,轉第(2)步迭代加深搜索（1）對于有界深度搜索策略，有下面幾點需要說明： 1）在有界深度搜索算法中，深度限制dm是一個很重要的參數(shù)。 2）深度限制dm不能太大。 3）有界深度搜索的主要問題是深度限制值dm的選取。 問題：但是

24、對很多問題，我們并不知道該值到底為多少，直到該問題求解完成了，才可以確定出深度限制dm。迭代加深搜索（2）改進方法-迭代加深搜索算法 ：先任意給定一個較小的數(shù)作為dm，然后按有界深度算法搜索，若在此深度限制內(nèi)找到了解，則算法結束；如在此限度內(nèi)沒有找到問題的解，則增大深度限制dm，繼續(xù)搜索。 迭代加深搜索是一種回避選擇最優(yōu)深度限制問題的策略，它是試圖嘗試所有可能的深度限制：首先深度為0，然后深度為1，然后為2，等等，一直進行下去。 問題：迭代加深搜索看起來會很浪費，因為很多節(jié)點都要擴展多次。 迭代加深搜索（3）迭代加深搜索（4）迭代加深搜索（5）迭代加深搜索（6）迭代加深搜索（6）深度為d，分支

25、因子為b的深度優(yōu)先搜索生成的節(jié)點數(shù)為：NDLS = b0 + b1 + b2 + + bd-2 + bd-1 + bd 深度為d，分支因子為b的迭代加深搜索生成的節(jié)點數(shù)為NIDS = (d+1)b0 + d b1 + (d-1)b2 + + 3bd-2 +2bd-1 + 1bd 對于 b = 10, d = 5,NDLS = 1 + 10 + 100 + 1,000 + 10,000 + 100,000 = 111,111NIDS = 6 + 50 + 400 + 3,000 + 20,000 + 100,000 = 123,456增加 = (123,456 - 111,111)/111,11

26、1 = 11%迭代加深搜索（7）Complete? YesTime? (d+1)b0 + d b1 + (d-1)b2 + + bd = O(bd)Space? O(bd)Optimal? Yes, 如果每步代價為1其他問題避免重復狀態(tài)：由于擴展已經(jīng)遇到并擴展過的狀態(tài)可能造成時間的浪費利用CLOSED表，如果當前節(jié)點與其中的某個節(jié)點相匹配的話，那么它可以被放棄而不去擴展，或者需要比較耗散值如果單步耗散為常數(shù)時，代價廣度優(yōu)先搜索找到的總是最優(yōu)路徑使用不完全信息的搜索：無傳感問題：Agent了解它的每個行動的結果，但是沒有傳感器。從Agent可能到達的狀態(tài)中搜索，而不是實際狀態(tài)空間中搜索偶發(fā)性問題

27、：環(huán)境是部分可觀察的，或者行動是不確定的。在每個行動后Agent能從感知器中得到新的信息。其解答往往表現(xiàn)為樹的形式，對樹的分支的選擇取決于樹上結點接收到的感知信息主要內(nèi)容概述狀態(tài)空間的搜索狀態(tài)空間的一般搜索過程盲目搜索啟發(fā)式搜索約束滿足問題博弈啟發(fā)式搜索（1）前面討論的方法都是盲目的搜索方法,即都沒有利用問題本身的特性信息,在決定要被擴展的節(jié)點時,都沒有考慮該節(jié)點在解的路徑上的可能性有多大,它是否有利于問題求解以及求出的解是否為最優(yōu)啟發(fā)式搜索要用到問題自身的某些特性信息,以指導搜索朝著最有希望的方向前進啟發(fā)信息的強度強：降低搜索工作量，但可能導致找不到最優(yōu)解弱：一般導致工作量加大，極限情況下變

28、為盲目搜索，但可能可以找到最優(yōu)解啟發(fā)式搜索（2）啟發(fā)性信息和估價函數(shù)用于指導搜索過程,且與具體問題有關的控制性信息稱為為啟發(fā)性信息用于評價節(jié)點重要性的函數(shù)稱為估價函數(shù).記為 f(x) = g(x) + h(x)g(x)為從初始節(jié)點S0到節(jié)點x已經(jīng)實際付出的代價h(x)是從節(jié)點x到目標節(jié)點Sg的最優(yōu)路徑的估價代價,體現(xiàn)了問題的啟發(fā)性信息,稱為啟發(fā)函數(shù)f(x)表示從初始節(jié)點經(jīng)過節(jié)點x到達目標節(jié)點的最優(yōu)路徑的代價估價值,其作用是用來評估OPEN表中各節(jié)點的重要性,決定其次序啟發(fā)式搜索（3）啟發(fā)式就是要猜測：從節(jié)點n開始，找到最優(yōu)解的可能性有多大？ 從起始節(jié)點開始，經(jīng)過節(jié)點n，到達目標節(jié)點的最佳路徑的

29、費用是多少？(存在一個約束) gh最佳優(yōu)先搜索（1）思想:對每個節(jié)點使用估價函數(shù),估計希望: 擴展最有希望未擴展的節(jié)點主要包括: - 貪婪最佳優(yōu)先搜索 - A*算法最佳優(yōu)先搜索（2）貪婪最佳優(yōu)先搜索(1)啟發(fā)失函數(shù) f(n)=h(n) :從n到最近的目標節(jié)點代價的估計這里采用hSLD(n): 從n到Bucharest的直線距離貪婪算法擴展看來與目標最近的節(jié)點貪婪最佳優(yōu)先搜索(2)貪婪最佳優(yōu)先搜索(3)貪婪最佳優(yōu)先搜索(4)貪婪最佳優(yōu)先搜索(5)特性完備性 : NO時間: O(bm) ,但是一個好的啟發(fā)式可以得到很大的改進空間: O(bm) ,保存所有的節(jié)點在內(nèi)存中最優(yōu): NOA*算法(1)思想

30、: 避免對已經(jīng)擴展的路徑進行再擴展評價函數(shù)為: f(x) = g(x) + h(x) 把OPEN表中的節(jié)點按此函數(shù)的值從小到大進行排序g(x)是對g*(x)的估價,g(x)0h(x)是h*(x)的下界,即對所有的x, h(x)=h*(x)其中: g*(x)是從初始節(jié)點S0到節(jié)點x的最小代價 h*(x)是從節(jié)點x到目標節(jié)點的最小代價,若有多個目標節(jié)點,則為 其中最小的一個nSg*(n)h*(n) gA*算法（2）f*(S)f*(S) = g*(S)+h*(S) = h*(S)從S無約束地到達目標的最佳路經(jīng)上的耗散值;g(n)一般取實際走過的路徑的費用和.g(n) g*(n)隨著算法的執(zhí)行，由于指

31、針的變動，g(n)會下降. h0沒有啟發(fā)式信息;A*算法（3）8數(shù)碼問題h(n) = “不在位”的將牌數(shù)h(n) = 將牌“不在位”的距離和2 8 31 6 47 51 2 3457 6 8將牌1：1將牌2：1將牌6：1將牌8：2A*算法（4）A*算法（5）寬度優(yōu)先: 當問題為單位耗散值，且問題有解時，一定能找到最優(yōu)解;f(n) = g(n) + h(n)g(n)h(n) = 0 h*(n)A*算法例子(1)A*算法例子(2)A*算法例子(3)A*算法例子(4)A*算法例子(5)A*算法可納性對于可解狀態(tài)圖(即從初始節(jié)點到目標節(jié)點有路徑存在)所說,如果一個搜索算法能在有限步內(nèi)終止,并且能找到最

32、優(yōu)解,則稱該搜索算法是可納的. 定理:A*算法是可納的,即在有限步內(nèi)終止,并且找到最優(yōu)解證明思路對于有限圖,A*算法一定會在有限步內(nèi)終止對應無限圖,只要從初始節(jié)點到目標節(jié)點有路徑存在,A*算法也必然終止A*算法一定終止在最優(yōu)路徑上A*算法的最優(yōu)性和單調(diào)性最優(yōu)性A*算法的搜索效率在很大程度上取決于h(x),在滿足h(x)=h*(x)的前提下,h(x)的值越大越好.H(x)所攜帶的啟發(fā)性信息越多,搜索時所擴展的節(jié)點數(shù)越少,搜索效率就越高單調(diào)性限制單調(diào)性限制是指h(x)滿足如下兩個條件h(Sg)=0設xj是節(jié)點xi 的任意子節(jié)點,則有 h(xi)-h(xj)=c(xi,xj) 其中:Sg是目標節(jié)點,

33、c(xi,xj)是節(jié)點xi到子節(jié)點xj的邊代價A*算法的h(x)滿足單調(diào)性限制時,可有下面的結論若A*算法選擇節(jié)點xn進行擴展,則g(xn)=g*(x)由A*算法所擴展的節(jié)點序列其f值是非遞減的啟發(fā)式對性能的影響(1)8數(shù)碼問題,兩個啟發(fā)式函數(shù):h1(n):不在目標位的棋子數(shù)目h2(n):所有棋子到其目標位置的距離和(Manhattan距離)h1(S)=6h2(s)=4+0+3+3+1+0+2+1=14啟發(fā)式對性能的影響(2)典型情況下的搜索代價:d=14 IDS=3,473,941節(jié)點 A*(h1)=539節(jié)點 A*(h2)=113節(jié)點d=24 IDS 54,000,000,000節(jié)點 A*

34、(h1)=39,135節(jié)點 A*(h2)=1,641節(jié)點A*算法特性（1）完備性 : Yes,除非有無限多的節(jié)點具有f =f(G)時間: 指數(shù)空間: 保存所有的節(jié)點在內(nèi)存中最優(yōu): YESA*擴展所有的f(n)C*的節(jié)點A*算法特性（2）但是對大多數(shù)搜索問題，搜索目標時的搜索空間的節(jié)點數(shù)仍然是答案深度的指數(shù)。在A*算法中計算時間不是主要的問題。由于A*算法把所有生成的節(jié)點保存在內(nèi)存中，所以A*算法在耗盡計算時間之前一般早已經(jīng)把空間耗盡了。為了克服空間問題，開發(fā)了一些新的算法，如迭代加深A*算法IDA*。啟發(fā)式函數(shù)用做深度的限制，而不是選擇擴展節(jié)點時的排序。IDA*算法和A*算法相比，主要優(yōu)點是對于內(nèi)存的需求。A*算法需要指數(shù)級數(shù)量的存貯空間，因為沒有深度方面的限制。而IDA*算法只有當節(jié)點n的所有子節(jié)點n的f(n