狀態(tài)空間搜索策略課件

第5章狀態(tài)空間搜索策略Searching第5章狀態(tài)空間搜索策略Searching15.1搜索概述在解空間中尋找解的過程與策略搜索問題的產(chǎn)生（1）結(jié)構(gòu)不良或非結(jié)構(gòu)化的問題，無解析解（2）理論上可解的問題，計算復(fù)雜度可能太高基本搜索方式

（1）盲目搜索

按預(yù)定策略進行搜索，不考慮問題本身的特性（2）啟發(fā)式(Heuristic)搜索

利用與問題有關(guān)的啟發(fā)式信息，加快搜索過程5.1搜索概述在解空間中尋找解的過程與策略啟發(fā)式搜索啟發(fā)式信息與評價函數(shù)

反映問題特性，可用于確定搜索方向的信息評價函數(shù)的作用是根據(jù)啟發(fā)式信息，計算對應(yīng)于特定搜索方向的評價值，作為選擇搜索方向的依據(jù)。局部(local)搜索

vs.全局(global)搜索確定搜索方向時考慮局部信息還是全局信息？任一解

vs.最優(yōu)解啟發(fā)式搜索啟發(fā)式信息與評價函數(shù)搜索方法圖搜索方法寬度優(yōu)先法(breadth-first)，深度優(yōu)先法(depth-first)，有界深度優(yōu)先法，啟發(fā)式最優(yōu)圖搜索法(A*，AO*)……..博弈搜索方法極小極大法(MiniMax)，Alpha-Beta剪枝法(pruning)………現(xiàn)代優(yōu)化搜索方法爬山法(hillclimbing)，模擬退火法(simulatedannealing)，遺傳算法(geneticalgorithms)…….搜索方法圖搜索方法搜索策略的評價完備性

如果問題有解，能否保證找到？最優(yōu)性(optimization)

如果問題存在不同的解，能否找到最優(yōu)解？時間復(fù)雜性-找到一個解需要花費多少時間空間復(fù)雜性-在搜索過程中需要占用多少內(nèi)存搜索策略的評價完備性時空復(fù)雜性的量度狀態(tài)空間圖的大小分支因子b目標(biāo)節(jié)點的深度d路徑的最大長度m搜索深度限制l時空復(fù)雜性的量度狀態(tài)空間圖的大小5.2問題及其搜索過程的表示狀態(tài)空間表示法

通過“狀態(tài)”表示問題，通過“操作符”求解問題

狀態(tài)的改變表示了問題求解過程5.2問題及其搜索過程的表示狀態(tài)空間表示法狀態(tài)空間以“狀態(tài)”和“操作符”為基礎(chǔ)

狀態(tài)：問題求解過程中任意時刻的狀況

操作符：使問題從一個狀態(tài)變?yōu)榱硪粋€狀態(tài)的操作問題的全部狀態(tài)(包含初始狀態(tài)和目標(biāo)狀態(tài))及一切可用操作符所構(gòu)成的集合稱為問題的狀態(tài)空間。初始狀態(tài)中間狀態(tài)1中間狀態(tài)2目標(biāo)狀態(tài)狀態(tài)空間以“狀態(tài)”和“操作符”為基礎(chǔ)初始狀態(tài)中間狀態(tài)1中間狀狀態(tài)空間例：二階梵塔問題設(shè)有三根鋼針，它們的編號分別是1號、2號和3號。在初始情況下，l號鋼針上穿有A、B兩個金片，A比B小，A位于B的上面。要求把這兩個金片全部移到另一根鋼針上，而且規(guī)定每次只能移動一個金片，任何時刻都不能使大片位于小片的上面。狀態(tài)空間例：二階梵塔問題設(shè)有三根鋼針，它們的編號分別是1號、用Sk=｛Sk0，Sk1｝表示問題的狀態(tài)，其中，Sk0表示金片A所在的鋼針號，Sk1表示金片B所在的鋼針號。全部可能的問題狀態(tài)共有以下9種：

SO=(1，l)S1=（1，2）S2=（1，3）

S3=(2，1）S4=（2，2）S5=（2，3）

S6=(3，1）S7=（3，2）S8=（3，3）

123BABABA123S0=(1,1)S4=(2,2)S8=(3,3)

二階梵塔問題的初始與目標(biāo)狀態(tài)用Sk=｛Sk0，Sk1｝表示問題的狀態(tài)，其中，Sk0表操作符：A(i,j)表示把金片A從第i號鋼針移到j(luò)號鋼針上；B(i,j)表示把金片B從第i號鋼針移到j(luò)號鋼針上。共有12種操作，分別是：

A(1，3)A(2，1)A(2，3)A(3，1)A(3，2)B(1，3)B(2，1)B(2，3)B(3，1)B(3，2)

(1,1)(2,1)(2,3)(3,3)(1,3)(1,2)(2,2)(3,2)(3,1)A(1,3)B(1,2)A(3,2)

根據(jù)狀態(tài)和操作符，可構(gòu)成二階梵塔問題的狀態(tài)圖最短路徑解操作符：A(i,j)表示把金片A從第i號鋼針移到j(luò)號鋼針上；八數(shù)碼游戲（八數(shù)碼問題）描述為：在3×3組成的九宮格棋盤上，擺有八個將牌，每一個將牌都刻有1-8八個數(shù)碼中的某一個數(shù)碼。棋盤中留有一個空格，允許其周圍的某一個將牌向空格移動，這樣通過移動將牌就可以不斷改變將牌的布局。這種游戲求解的問題是：給定一種初始的將牌布局或結(jié)構(gòu)（稱初始狀態(tài)）和一個目標(biāo)的布局（稱目標(biāo)狀態(tài)），問如何移動將牌，實現(xiàn)從初始狀態(tài)到目標(biāo)狀態(tài)的轉(zhuǎn)變。

八數(shù)碼游戲（八數(shù)碼問題）描述為：在3×3組成的九宮格棋盤上，5.3一般圖搜索算法無論是狀態(tài)空間，還是與或圖的問題表示，問題求解過程都可看作是在“圖”中進行搜索。基本思想

不存儲全部搜索圖，而是逐步展開問題求解所需的搜索子圖具體方法從初始狀態(tài)開始，不斷擴展當(dāng)前節(jié)點，即生成子節(jié)點，直到目標(biāo)狀態(tài)出現(xiàn)在這些子節(jié)點中，或者沒有可供擴展的節(jié)點為止。5.3一般圖搜索算法無論是狀態(tài)空間，還是與或圖的問題表示，數(shù)據(jù)結(jié)構(gòu)Open表（未擴展節(jié)點表）存放未進行過擴展的節(jié)點Closed表（已擴展節(jié)點表）存放已經(jīng)擴展過的節(jié)點

節(jié)點

父節(jié)點

編號

節(jié)點

父節(jié)點Open表：Closed表：數(shù)據(jù)結(jié)構(gòu)Open表（未擴展節(jié)點表）節(jié)點父節(jié)點算法步驟Step1把初始節(jié)點S0放入Open表，建立僅包含S0的圖G；Step2從Open表中取出待擴展節(jié)點，放入Closed表；

（不同搜索策略的區(qū)別主要體現(xiàn)于此）Step3對節(jié)點進行擴展，將擴展得到的、未在G中出現(xiàn)過的子節(jié)點放入Open表；根據(jù)需要修改G中節(jié)點的指針；Step4重復(fù)Step2-3直到

狀態(tài)空間：待擴展節(jié)點為目標(biāo)節(jié)點或Open表為空算法步驟Step1把初始節(jié)點S0放入Open表，建立僅盲目搜索策略廣度（寬度）優(yōu)先搜索

先生成的節(jié)點先擴展深度優(yōu)先搜索

后生成的節(jié)點先擴展有界深度優(yōu)先搜索

在深度優(yōu)先策略中增加深度限制，在廣度優(yōu)先與深度優(yōu)先之間折衷完備最小路徑解效率盲目搜索策略廣度（寬度）優(yōu)先搜索完備最小路徑解效率2834765S012384765Sg盲目搜索例（狀態(tài)空間）:八數(shù)碼難題在3*3的方格棋盤上，分別放置了標(biāo)有數(shù)字1、2、3、4、5、6、7、8的八張牌，初始狀態(tài)S0和目標(biāo)狀態(tài)Sg分別如圖所示?？梢允褂玫牟僮饔校?/p>

空格左移，空格上移，空格右移，空格下移

尋找從初始狀態(tài)到目標(biāo)狀態(tài)的解路徑。

283S0123Sg盲目搜索例（狀態(tài)空間）:八數(shù)碼廣度優(yōu)先搜索算法如下：(1)把初始結(jié)點放入Open表中；(2)如果Open表為空，則問題無解，失敗退出；(3)把Open表的第一個結(jié)點取出，放入Closed表，并記該結(jié)點為n； (4)擴展節(jié)點n，如果沒有后繼節(jié)點，則轉(zhuǎn)向第(2)步；(5)把n的所有后繼結(jié)點放入Open表的末尾，并提供從這些后繼結(jié)點回到父結(jié)點(編號值為n)的指針;(6)如果剛產(chǎn)生的這些后繼結(jié)點中存在一個目標(biāo)結(jié)點，則找到一個解。解可從目標(biāo)結(jié)點開始直到初始結(jié)點的返回指針中得到，算法成功退出。否則轉(zhuǎn)(2)繼續(xù)。廣度優(yōu)先搜索算法如下：SLOMFPQNFFF起始結(jié)點起始把S0放入Open表Open表是否為空失敗把第1個結(jié)點n，從Open表移出并把它放入Closed表中擴展n,把它的后繼結(jié)點放入Open表的末端,提供回到n的指針是否有任何后繼結(jié)點為目標(biāo)結(jié)點？成功否是否是示意圖算法框圖SLOMFPQNFFF起始結(jié)點起始把S0放入Open表Ope2834765S01283

14765223

847653283

47654283

64755832147652837

1465

23

8

476523

8

476528

43765283

4

576283

64

75283

6475678910111213832147652837

14651

23

8

4765234

876528

4

3765283

4

576283

641

75283

67541415218

32147658

13247652223283746

152837

146

52425123847651

2378

4652627Sg解的路徑是：

S0→3→8→16→26(Sg)八數(shù)碼難題的廣度優(yōu)先搜索283S012832233廣度優(yōu)先搜索是一種完備策略，即只要問題有解,它就一定可以找到解。并且廣度優(yōu)先搜索找到的解，還一定是路徑最短的解。深度優(yōu)先搜索深度優(yōu)先搜索是一種后生成的結(jié)點先擴展的策略。其搜索過程是：從初始結(jié)點S0開始，在其子結(jié)點中選擇一個最新生成的結(jié)點進行考察，如果該子結(jié)點不是目標(biāo)結(jié)點且可以擴展，則擴展該子結(jié)點，依此向下搜索，直到某個子結(jié)點既不是目標(biāo)結(jié)點，又不能繼續(xù)擴展時，才選擇其兄弟結(jié)點進行考察。圖示如下：廣度優(yōu)先搜索是一種完備策略，即只要問題有解,它就一定可以找到S0123768459起始結(jié)點起始把S0放入Open表S0是否為目標(biāo)結(jié)點是否Open為空表把Open表中的第一個結(jié)點n移入Closed表結(jié)點n的深度是否等于深度界限擴展結(jié)點n，把其后代放入Open表的前端是否有任何后繼結(jié)點為目標(biāo)結(jié)點成功失敗成功是否是是是否否否示意圖算法框圖S0123768459起始結(jié)點起始把S0放入Open表S0是深度優(yōu)先搜索算法如下：(1)把初始結(jié)點S0放入Open表中；(2)如果Open表空，則問題無解，失敗退出；(3)把Open表的第一個結(jié)點取出放入Close表，并記該結(jié)點為n;(4)考察結(jié)點n是否為目標(biāo)結(jié)點，若是，則得到問題的解，成功退出；(5)

若結(jié)點n不可擴展，則轉(zhuǎn)(2)；(6)擴展結(jié)點n，將其子結(jié)點放入Open表的首部，并為每一個子結(jié)點設(shè)置指向父結(jié)點的指針，然后轉(zhuǎn)(2)。深度優(yōu)先搜索算法如下：2834765S01283

14765318476528314765283164752283164

7528316475328316754428163754283

67545

81637546八數(shù)碼難題的深度優(yōu)先搜索

283S0128332從深度優(yōu)先搜索的算法可以看出,搜索一旦進入某個分支，就將沿這個分支一直進行下去，如果目標(biāo)恰好在這個分支上,則它可以很快找到解.但是,如果目標(biāo)不在這個分支上，且分支是一個無窮分支，則搜索過程就不可能找到解。因此，深度優(yōu)先搜索是一種不完備策略，即使問題有解，它也不一定能夠找到解。從深度優(yōu)先搜索的算法可以看出,搜索一旦進入某個分支，就將沿這解路徑為:

So：l→11→12→13→14：SgSg

八數(shù)碼難題的有界深度優(yōu)先搜索2834765S01283

14765223

8476511283

4765283

6475832147652837

1465

23

8

476523

8

476528

43765283

4

576283

64

75283

64753713832147652837

14651

23

8

4765234

876528

4

3765283

4

576283

641

75283

6754488

32147658

132476556283746

152837

146

5910123847651

2378

4651412深度限制為4解路徑為:

So：l→11→12→13→14：S上面討論的搜索方法都沒有用到問題本身的特性信息，只是按事先設(shè)定的線路進行搜索，具有較大的盲目性。事實上，如果能利用搜索過程所得到的問題自身的一些特性信息來指導(dǎo)搜索過程，則對搜索將是非常有益的。這種利用問題自身的特性來引導(dǎo)搜索過程，提高搜索效率的搜索策略稱為啟發(fā)式搜索或有信息搜索。啟發(fā)式搜索方法所依據(jù)的是問題自身的啟發(fā)性信息，而啟發(fā)性信息又是通過估價函數(shù)而作用于搜索過程的。上面討論的搜索方法都沒有用到問題本身的特性信息，只是按事先設(shè)5.4啟發(fā)式搜索啟發(fā)式算法

利用問題的特殊性，選擇待擴展的節(jié)點，以縮小搜索范圍，提高搜索速度。啟發(fā)信息可指導(dǎo)搜索過程，且與具體問題求解過程有關(guān)的控制性信息。一般有以下三種：

①幫助確定擴展節(jié)點的信息；

②幫助決定哪些后繼節(jié)點應(yīng)被生成的信息；

③在擴展一個節(jié)點時決定哪些節(jié)點應(yīng)被刪除的信息5.4啟發(fā)式搜索啟發(fā)式算法估價函數(shù)f(n)：用于估計節(jié)點代價的函數(shù)

定義為從初始節(jié)點S0出發(fā)，經(jīng)過節(jié)點n約束后，到達目標(biāo)節(jié)點Sg的所有路徑中最優(yōu)路徑的代價估計值。

一般形式為

f(n)=g(n)＋h(n)

g(n)是從初始節(jié)點S0到節(jié)點n的實際代價?？梢詮墓?jié)點n反向跟蹤到初始節(jié)點S0,得到一條當(dāng)前最小代價路徑，把這條路徑上所有有向邊的代價相加，就得到g(n)的值。；

h(n)是從節(jié)點n到目標(biāo)節(jié)點S0的最優(yōu)路徑的估計代價。需要根據(jù)問題自身的特性來確定，體現(xiàn)了問題自身的啟發(fā)性信息，因此也稱為啟發(fā)函數(shù)。估價函數(shù)f(n)：用于估計節(jié)點代價的函數(shù)估價函數(shù)例：f(n)=d(n)+W(n)2834765S0節(jié)點n在搜索樹中的深度n中“不在位”的數(shù)碼個數(shù)f(S0)=?=0+3=312384765Sg估價函數(shù)例：f(n)=d(n)+W(n)283S根據(jù)搜索過程中選擇擴展節(jié)點的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)搜索。

1.全局擇優(yōu)在Open表的所有節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進行擴展

2.局部擇優(yōu)在剛生成的子節(jié)點中選擇一個估價函數(shù)值最小的節(jié)點進行擴展。根據(jù)搜索過程中選擇擴展節(jié)點的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)局部最佳優(yōu)先搜索算法對OPEN表中所有節(jié)點的f(n)進行比較，按從小到大的順序重排OPEN表。其算法效率類似于縱向搜索算法，但使用了與問題特性相關(guān)的估價函數(shù)來確定下一步待擴展的節(jié)點，因此是一種啟發(fā)式搜索方法。局部最佳優(yōu)先搜索算法對OPEN表中所有節(jié)點的f(n)進行比較開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為空表？把OPEN表中的第一個節(jié)點n放入CLOSED表n為目標(biāo)節(jié)點嗎？擴展n，計算所有子節(jié)點的估價函數(shù)值，并提供它們返回節(jié)點n的指針。失敗成功局部最佳優(yōu)先搜索算法框圖是否是否把子節(jié)點送入OPEN表，并對其中的所有節(jié)點按估價函數(shù)值由小到大重排。開始把S放入OPEN表，計算估價函數(shù)f(s)OPEN表為

舉例：八數(shù)碼魔方（8-puzzleproblem）12384567（目標(biāo)狀態(tài)）12384567（初始狀態(tài)）舉例：八數(shù)碼魔方（8-puzzleproblem）12357①④⑤⑥③123845671238456712384567(3)(5)(5)②123845671238456712384567(4)(3)(3)1238456712384567(2)(4)1238456712384567(3)(4)12384567(1)8132456712384567(0)(2)八數(shù)碼魔方的局部最佳優(yōu)先搜索樹123846(4)75⑦搜索得到的路徑如黃線所示57①④⑤⑥③12384567123845671238456本題采用了簡單的估價函數(shù)

f(n)=W(n)其中：W(n)用來計算對應(yīng)于節(jié)點n的數(shù)據(jù)庫中錯放的棋子個數(shù)。因此，初始節(jié)點棋局的f(n)值等于4。12384567本題采用了簡單的估價函數(shù)12384567第②步有三種情況,我們選擇其中f(n)最小的:其它依次類推.最后用了7步得出了結(jié)果.

123845671238456712384567(3)(5)(5)

第②步有三種情況,我們選擇其中f(n)最小的:123845最佳優(yōu)先算法有時無法得到最優(yōu)解，因為它的估價函數(shù)f的選取時，忽略了從初始節(jié)點到目前節(jié)點的代價值。所以，可考慮對估價函數(shù)f(n)進行某些修改或限制。

最佳優(yōu)先算法有時無法得到最優(yōu)解，因為它的估價函數(shù)f的選取時，5.5A*算法對估價函數(shù)加上一些限制，以保證得到最優(yōu)解的啟發(fā)式搜索算法最優(yōu)估價函數(shù)

f*(n)＝g*(n)＋h*(n)初始節(jié)點到節(jié)點n的最小代價節(jié)點n到目標(biāo)節(jié)點的最小代價有關(guān)限制

1.g(n)是對g*(n)的估計，且g(n)＞0；

2.h(n)是h*(n)的下界，即對任意節(jié)點n均有h(n)≤h*(n)

5.5A*算法對估價函數(shù)加上一些限制，以保證得到最優(yōu)解的啟A*算法例1：八數(shù)碼問題解1：h(n)=W(n)。盡管不能確切知道h*(n)

，但當(dāng)采用單位代價時，通過對“不在位”數(shù)碼個數(shù)的估計，可以得出至少要移動W(n)步才能到達目標(biāo)，顯然有W(n)≤h*(n)，滿足A*算法的限制條件。

解2：h(n)=P(n)，P(n)定義為每一個數(shù)碼與其目標(biāo)位置之間距離（不考慮夾在其間的數(shù)碼）的總和，同樣可以斷定至少要移動P(n)步才能到達目標(biāo)，因此有P(n)≤h*(n)，即滿足A*算法的限制條件。A*算法例1：八數(shù)碼問題解1：h(n)=W(n)。盡管28314765h=4,f=4S0231

8476528316475283

1476528314765g=1

2318476523184765g=21

23847651

2378465Sgg=4h=5,f=6h=5,f=6h=3,f=4h=5,f=6h=2,f=4h=3,f=51

2384765g=3h=1,f=4h=0,f=4h=2,f=6八數(shù)碼難題的的A*搜索圖（h(n)=P(n)）283h=4,f=4S02328328A*算法例2：修道士和野人問題設(shè)在河的左岸有三個修道士、三個野人和一條船，修道士想用這條船把所有的人運到河對岸，但受以下條件的約束：

1.修道士和野人都會劃船，但每次船上至多可載兩個人；

2.河的任一岸如果野人數(shù)目超過修道士數(shù)，修道士就會被野人吃掉。

請給出一個確保修道士和野人都能過河，且沒有修道士被野人吃掉的過河規(guī)劃A*算法例2：修道士和野人問題設(shè)在河的左岸有三個修道士、三個問題表示：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。用三元式表示狀態(tài)：

S=(m,c,b)

其中，m表示左岸修道士人數(shù)，c表示左岸野人人數(shù)，b表示左岸船的數(shù)目。解：確定估價函數(shù)。

f(n)=g(n)＋h(n)=d(n)＋m＋c－2b

其中，d(n)為節(jié)點深度。h(n)＜h*(n)，滿足A*算法的限制條件。問題表示：需要考慮兩岸的修道士人數(shù)和野人人數(shù)，船的位置。用三(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=4,f=4f(n)=d(n)+m+c-2bhh=5,f=6h=4,f=5h=4,f=5(3,2,1)h=3,f=5(2,1,0)(3,0,0)h=3,f=6h=3,f=6(2,2,1)(3,1,1)h=2,f=6h=2,f=6h=2,f=7h=2,f=7傳教士和野人問題的A*搜索圖(0,0,0)(0,3,1)h=1,f=7(0,1,0)h=1,f=8(0,2,1)h=0,f=8(0,2,0)(1,1,0)(3,2,0)(3,1,0)(2,2,0)(3,3,1)h=關(guān)于A*算法的一些討論A*算法是到目前為止最快的一種計算最短路徑的算法，但它是一種‘較優(yōu)’算法，即它一般只能找到較優(yōu)解，而非最優(yōu)解，但由于其高效性，使其在實時系統(tǒng)、人工智能等方面應(yīng)用極其廣泛。A*算法結(jié)合了啟發(fā)式方法（這種方法通過充分利用圖給出的信息來動態(tài)地作出決定而使搜索次數(shù)大大降低）和形式化方法（這種方法不利用圖給出的信息，而僅通過數(shù)學(xué)的形式分析，如Dijkstra算法）。它通過一個估價函數(shù)（HeuristicFunction）f(h)來估計圖中的當(dāng)前點p到終點的距離(帶權(quán)值)，并由此決定它的搜索方向，當(dāng)這條路徑失敗時，它會嘗試其它路徑。關(guān)于A*算法的一些討論A*算法是到目前為止最快的一種計算最短我們可以發(fā)現(xiàn)，A*算法成功與否的關(guān)鍵在于估價函數(shù)的正確選擇，從理論上說，一個完全正確的估價函數(shù)是可以非常迅速地得到問題的正確解答，但一般完全正確的估價函數(shù)是得不到的，因而A*算法不能保證它每次都得到正確解答。一個不理想的估價函數(shù)可能會使它工作得很慢，甚至?xí)o出錯誤的解答。為了提高解答的正確性，我們可以適當(dāng)?shù)亟档凸纼r函數(shù)的值，從而使之進行更多的搜索，但這是以降低它的速度為代價的，因而我們可以根據(jù)實際對解答的速度和正確性的要求而設(shè)計出不同的方案，使之更具彈性。我們可以發(fā)現(xiàn)，A*算法成功與否的關(guān)鍵在于估價函數(shù)的正確選擇，A*算法的數(shù)據(jù)結(jié)構(gòu)眾所周知，對圖的表示可以采用數(shù)組或鏈表，而且這些表示法也各有優(yōu)缺點，數(shù)組可以方便地實現(xiàn)對其中某個元素的存取，但插入和刪除操作卻很困難，而鏈表則利于插入和刪除，但對某個特定元素的定位卻需借助于搜索。而A*算法則需要快速插入和刪除所求得的最優(yōu)值以及可以對當(dāng)前結(jié)點以下結(jié)點的操作，因而數(shù)組或鏈表都顯得太通用了，用來實現(xiàn)A*算法會使速度有所降低。要實現(xiàn)這些，可以通過二分樹、跳轉(zhuǎn)表等數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)，實踐中如采用簡單而高效的帶優(yōu)先權(quán)的堆棧，經(jīng)實驗表明，一個1000個結(jié)點的圖，插入而且移動一個排序的鏈表平均需500次比較和2次移動；未排序的鏈表平均需1000次比較和2次移動；而堆僅需10次比較和10次移動。需要指出的是，當(dāng)結(jié)點數(shù)n大于10，000時，堆棧不再是正確的選擇，但這足已滿足我們一般的要求。A*算法的數(shù)據(jù)結(jié)構(gòu)眾所周知，對圖的表示可以采用數(shù)組或鏈表，而估價函數(shù)（HeuristicFunction）估價函數(shù)的正確選取將直接關(guān)系到A*算法的成功與否，而函數(shù)的確定卻與實際情形有著密切的關(guān)系。這里以網(wǎng)格地圖的估價函數(shù)為例，其它情形需要作不同的分析，但至少估價函數(shù)應(yīng)為連續(xù)函數(shù)。a.

ManhattanDistance，這是一種標(biāo)準(zhǔn)的估價函數(shù)，h(A)=10*(abs(A.x-goal.x)+abs(A.y-goal.y))b.

DiagonalDistance，如果在地圖上允許作斜線方向的運動，則MahattanDistance修正為DiagonalDistance：h(A)=max(abs(A.x-goal.x),abs(A.y-goal.y))估價函數(shù)（HeuristicFunction）估價函數(shù)的正估價函數(shù)的判優(yōu)一般情形下，我們只需對估價函數(shù)的值進行比較而取其大者即可，但在幾個結(jié)點的估價函數(shù)值相同的情形下，我們需要采取一定的策略來決定這幾者誰更優(yōu)，從而避免對多個點的搜索。從而如下代碼可實現(xiàn)之：doubledx1=currentX-goalX;doubledy1=currentY-goalY;doubledx2=startX-goalX;doubledy2=startY-goalY;cross=dx1*dy2-dx2*dy1;if(cross<0)cross=-cross;...addcross*0.001totheheuristic...這段代碼計算始點、當(dāng)前點和終點的矢量積，從而可以判斷這三點是否共線（或近似共線），這樣不同點間即使有微小的差別也會被放大，從而更利于判斷。估價函數(shù)的判優(yōu)一般情形下，我們只需對估價函數(shù)的值進行比較而取改進的A*算法a.

BeamSearch。在A*算法中需要保留所有的結(jié)點，這將使得時間和空間的消耗都很大，而BeamSearch方法對結(jié)點數(shù)作出限期，當(dāng)結(jié)點數(shù)過多時，它會將一些不(大)可能為最優(yōu)的點排除，從而降低時間和空間的要求，但需要說明的是，由于在排除結(jié)點后需對結(jié)點排序，當(dāng)排序的工作量大于排除點后所節(jié)省的工作量，則該方法無意義。b.

Iterativedeepening。這是一種在人工智能中常使用的方法，它首先產(chǎn)生一近似值，然后對它進行修正而逐步接近最優(yōu)解。這其實是一種博奕算法的變形。c.

Dynamicweighting。這種算法是基于這樣的考慮，即在搜索初期以速度優(yōu)先，在搜索后期以準(zhǔn)確度優(yōu)先(這可通過對搜索初、后期賦予不同的權(quán)值來實現(xiàn))。即：f(p)=g(p)+w(p)*h(p)改進的A*算法a.

BeamSearch。在Ad.

Bidirectionalsearch。這種算法從起點和終點同時應(yīng)用A*算法，直到有結(jié)點相遇。其缺點在于復(fù)雜度太大，一般僅用于復(fù)雜的圖形。e.

HierarchicalA*。這種算法思想是將搜索過程化，對每個簡單過程求解從而得全局較優(yōu)解。正如當(dāng)我們到另一城市時，可分解為從家里“搜索”一條路徑至車站，再從車站“搜索”一條路徑到另一城市，當(dāng)我們從家里出發(fā)時，需要考慮的是怎樣盡快地到達車站，而不是怎樣盡快地到另一城市。f.

DynamicA*(D*)。這種算法主要用于人工智能和機器人技術(shù)。由于A*算法一開始要求獲得全部信息，而這在實際中有時是不可能的，而D*算法就是在假定信息不完整的前提下應(yīng)用A*算法，但它會隨著得到信息的增多而不斷改進結(jié)果，這就決定了它對空間的要求相當(dāng)高，因為它需要保留以前的所有獲得信息及運算情形。d.

Bidirectionalsearch。這開放實驗：不同搜索策略的算法實現(xiàn)與性能分析——以8數(shù)碼問題求解為例摘要詞匯表第一章、8數(shù)碼問題概述第二章、x算法的一般描述第三章、用x算法分析八數(shù)碼問題（第四章、評價函數(shù)的啟發(fā)能力）第五章、x算法在y開發(fā)環(huán)境下的實現(xiàn)（不限編程語言）（1.類（可參見附錄））

2.數(shù)據(jù)結(jié)構(gòu)

3.程序流程圖與相關(guān)說明第六章、性能比較與分析（如廣度優(yōu)先、深度優(yōu)先