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

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

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

4、st? 給定的目標狀態path cost? 每一步消耗為1狀態空間表示法（3）二階梵塔問題設有三個鋼針,在一號鋼針上穿有A,B兩個金片,A小于B,A位于B的上面.要求把這兩個金片全部移到另一個鋼針上,而且規定每次只能移動一片,任何時刻都不能使B位于A的上面設用Sk=(Sk0,Sk1)表示問題的狀態,SK0表示金片A所在的鋼針號,SK1表示金片B所在的鋼針號,全部可能的狀態為: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)問題初始狀態集合S=S0,目標狀態集合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)狀態空間表示法（4）用狀態空間表示,首先必須定義狀態的描述形式,把問題的一切狀態都表示出來,其次定義算符,完成狀態的轉換問題的求解過程就是一個把算符不斷地作用于狀態的過程.如果在使用某個算符后得到的狀態就是目標狀態,就得到了問題的解.這個解就是從初始狀態到目標狀態所用算符構成的序列.算符的一次使用,

6、就使問題由一種狀態轉變為另一種狀態.可能有多個算符序列都可使問題從初始狀態變到目標狀態,這就得到了多個解.對任何一個狀態,可使用的算符可能不止一個,這樣由一個狀態所生成的后繼狀態可能有多個.如何選擇下一步的操作,由搜索策略決定.回溯搜索控制策略（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皇后問題可用于對搜索算法進行測試對這類問題的形式化描述主要有兩類：增量形式化：包括了增加狀態描述的算符，從空狀態開始；這意味著每次行動添加一個皇后到狀態中去完全狀態形式化：把8個皇后都放在棋盤上，然后移動它們。現實問題旅行商問題超大規模集成電路的布局問題機器人導航問題.度量問題求解的性能一般搜索策略可以通過下面四個準則來評價：完備性

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

10、對每個子問題進行求解,然后把各子問題的解復合起來,就得到原問題的解.等價變換:利用同構或同態的等價變換,把復雜問題轉換成若干個較為容易求解的新問題.若新問題中有一個可求解,則就得到了原問題的解.與/或樹表示法（2）三階梵塔問題設有A,B,C三個金片以及三個鋼針,三個金片按自上而下從小到大的順序穿在1號鋼針上,要求把它們全部移到3號鋼針上,而且每次只能移到一個金片,任何時候都不能把大的金片壓在小的金片上面.用與/或樹表示:問題分解(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號針的雙金片問題狀態空間搜索過程要點（1）求解一個能夠滿足目標條件的問題可以表達為搜索一個圖以找到一個滿足目標狀態描述的節點問題。搜索過程的要點如下:起始節點:對應于初始狀態描述后繼節點:把適用于某個節點狀態描述的一些算符用來推算該節點而得到的新節點,稱為該節點的后繼節點指針:從每個后繼節點返回指向其父輩節點檢查各后繼節點看是否為目標節點.搜索過程擴展后繼節點的次序如果搜索是以接近起始節點的程度(由節點之間連結弧線的數目來衡量)依次擴展節點,稱為廣(寬)度優先搜索如果搜索時首先擴展最新產生的節點,稱為

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

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

14、某種搜索策略對OPEN表中的節點進行排序(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表中的節點修改指針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表中的節點修改指針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表中的節點(8)的后裔(10)修改指針狀態空間的一般搜索過程(3)這是一個通用的搜索過程,后面討論的狀態空間各種搜索策略都是其特例.各種搜索策略的主要區別就是對OPEN表中節點排序準則不同算法結束后，將生成一個圖G，稱為搜索圖。同時由于每個節點都有一個指針指向父節點，這些指針指向的節

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

19、現: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廣度優先搜索（2）Complete? Yes (如果 b 是有限的)Time? 1+b+b2+b3+ +

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

21、節點都配置指向父節點的指針,轉第(2)步擴展最深的未擴展節點實現: 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目標深度優先搜索（2）Complete? No: 當空間為無限深度時Time? O(bm): 如果 m 比d大很多則比較嚴重Space? O(bm), 線性空間Optimal? No特點缺點如果目標節點不在搜索所進入的分支上,而該分支又是一個無窮分支,則就得不到解.因此該算法是不完備的優點如果目標節點不在搜索所進入的分支上,則可以較快地得到解有界深度優先搜索定義搜索深度的界限dm,當搜索深度達到了深度界限,而尚未出現目標節點時,就換一個分支進行搜索搜索過程如下:(1)把初始節點S0放入OPEN表,置S

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

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

25、因子為b的深度優先搜索生成的節點數為：NDLS = b0 + b1 + b2 + + bd-2 + bd-1 + bd 深度為d，分支因子為b的迭代加深搜索生成的節點數為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其他問題避免重復狀態：由于擴展已經遇到并擴展過的狀態可能造成時間的浪費利用CLOSED表，如果當前節點與其中的某個節點相匹配的話，那么它可以被放棄而不去擴展，或者需要比較耗散值如果單步耗散為常數時，代價廣度優先搜索找到的總是最優路徑使用不完全信息的搜索：無傳感問題：Agent了解它的每個行動的結果，但是沒有傳感器。從Agent可能到達的狀態中搜索，而不是實際狀態空間中搜索偶發性問題

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

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

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

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

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

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

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

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