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

（1）盲目搜索

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

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

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

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

vs.最優(yōu)解啟發(fā)式搜索啟發(fā)式信息與評(píng)價(jià)函數(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)…….搜索方法圖搜索方法搜索策略的評(píng)價(jià)完備性

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

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

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

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

狀態(tài)：?jiǎn)栴}求解過(guò)程中任意時(shí)刻的狀況

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

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

八數(shù)碼游戲（八數(shù)碼問(wèn)題）描述為：在3×3組成的九宮格棋盤(pán)上，5.3一般圖搜索算法無(wú)論是狀態(tài)空間，還是與或圖的問(wèn)題表示，問(wèn)題求解過(guò)程都可看作是在“圖”中進(jìn)行搜索?；舅枷?/p>

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

節(jié)點(diǎn)

父節(jié)點(diǎn)

編號(hào)

節(jié)點(diǎn)

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

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

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

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

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

在深度優(yōu)先策略中增加深度限制，在廣度優(yōu)先與深度優(yōu)先之間折衷完備最小路徑解效率盲目搜索策略廣度（寬度）優(yōu)先搜索完備最小路徑解效率2834765S012384765Sg盲目搜索例（狀態(tài)空間）:八數(shù)碼難題在3*3的方格棋盤(pán)上，分別放置了標(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é)點(diǎn)放入Open表中；(2)如果Open表為空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)結(jié)點(diǎn)取出，放入Closed表，并記該結(jié)點(diǎn)為n； (4)擴(kuò)展節(jié)點(diǎn)n，如果沒(méi)有后繼節(jié)點(diǎn)，則轉(zhuǎn)向第(2)步；(5)把n的所有后繼結(jié)點(diǎn)放入Open表的末尾，并提供從這些后繼結(jié)點(diǎn)回到父結(jié)點(diǎn)(編號(hào)值為n)的指針;(6)如果剛產(chǎn)生的這些后繼結(jié)點(diǎn)中存在一個(gè)目標(biāo)結(jié)點(diǎn)，則找到一個(gè)解。解可從目標(biāo)結(jié)點(diǎn)開(kāi)始直到初始結(jié)點(diǎn)的返回指針中得到，算法成功退出。否則轉(zhuǎn)(2)繼續(xù)。廣度優(yōu)先搜索算法如下：SLOMFPQNFFF起始結(jié)點(diǎn)起始把S0放入Open表Open表是否為空失敗把第1個(gè)結(jié)點(diǎn)n，從Open表移出并把它放入Closed表中擴(kuò)展n,把它的后繼結(jié)點(diǎn)放入Open表的末端,提供回到n的指針是否有任何后繼結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)？成功否是否是示意圖算法框圖SLOMFPQNFFF起始結(jié)點(diǎn)起始把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)先搜索是一種完備策略，即只要問(wèn)題有解,它就一定可以找到解。并且廣度優(yōu)先搜索找到的解，還一定是路徑最短的解。深度優(yōu)先搜索深度優(yōu)先搜索是一種后生成的結(jié)點(diǎn)先擴(kuò)展的策略。其搜索過(guò)程是：從初始結(jié)點(diǎn)S0開(kāi)始，在其子結(jié)點(diǎn)中選擇一個(gè)最新生成的結(jié)點(diǎn)進(jìn)行考察，如果該子結(jié)點(diǎn)不是目標(biāo)結(jié)點(diǎn)且可以擴(kuò)展，則擴(kuò)展該子結(jié)點(diǎn)，依此向下搜索，直到某個(gè)子結(jié)點(diǎn)既不是目標(biāo)結(jié)點(diǎn)，又不能繼續(xù)擴(kuò)展時(shí)，才選擇其兄弟結(jié)點(diǎn)進(jìn)行考察。圖示如下：廣度優(yōu)先搜索是一種完備策略，即只要問(wèn)題有解,它就一定可以找到S0123768459起始結(jié)點(diǎn)起始把S0放入Open表S0是否為目標(biāo)結(jié)點(diǎn)是否Open為空表把Open表中的第一個(gè)結(jié)點(diǎn)n移入Closed表結(jié)點(diǎn)n的深度是否等于深度界限擴(kuò)展結(jié)點(diǎn)n，把其后代放入Open表的前端是否有任何后繼結(jié)點(diǎn)為目標(biāo)結(jié)點(diǎn)成功失敗成功是否是是是否否否示意圖算法框圖S0123768459起始結(jié)點(diǎn)起始把S0放入Open表S0是深度優(yōu)先搜索算法如下：(1)把初始結(jié)點(diǎn)S0放入Open表中；(2)如果Open表空，則問(wèn)題無(wú)解，失敗退出；(3)把Open表的第一個(gè)結(jié)點(diǎn)取出放入Close表，并記該結(jié)點(diǎn)為n;(4)考察結(jié)點(diǎn)n是否為目標(biāo)結(jié)點(diǎn)，若是，則得到問(wèn)題的解，成功退出；(5)

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

14765318476528314765283164752283164

7528316475328316754428163754283

67545

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

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

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上面討論的搜索方法都沒(méi)有用到問(wèn)題本身的特性信息，只是按事先設(shè)定的線路進(jìn)行搜索，具有較大的盲目性。事實(shí)上，如果能利用搜索過(guò)程所得到的問(wèn)題自身的一些特性信息來(lái)指導(dǎo)搜索過(guò)程，則對(duì)搜索將是非常有益的。這種利用問(wèn)題自身的特性來(lái)引導(dǎo)搜索過(guò)程，提高搜索效率的搜索策略稱為啟發(fā)式搜索或有信息搜索。啟發(fā)式搜索方法所依據(jù)的是問(wèn)題自身的啟發(fā)性信息，而啟發(fā)性信息又是通過(guò)估價(jià)函數(shù)而作用于搜索過(guò)程的。上面討論的搜索方法都沒(méi)有用到問(wèn)題本身的特性信息，只是按事先設(shè)5.4啟發(fā)式搜索啟發(fā)式算法

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

①幫助確定擴(kuò)展節(jié)點(diǎn)的信息；

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

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

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

一般形式為

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

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

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

1.全局擇優(yōu)在Open表的所有節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展

2.局部擇優(yōu)在剛生成的子節(jié)點(diǎn)中選擇一個(gè)估價(jià)函數(shù)值最小的節(jié)點(diǎn)進(jìn)行擴(kuò)展。根據(jù)搜索過(guò)程中選擇擴(kuò)展節(jié)點(diǎn)的范圍，分為全局擇優(yōu)搜索和局部擇優(yōu)局部最佳優(yōu)先搜索算法對(duì)OPEN表中所有節(jié)點(diǎn)的f(n)進(jìn)行比較，按從小到大的順序重排OPEN表。其算法效率類似于縱向搜索算法，但使用了與問(wèn)題特性相關(guān)的估價(jià)函數(shù)來(lái)確定下一步待擴(kuò)展的節(jié)點(diǎn)，因此是一種啟發(fā)式搜索方法。局部最佳優(yōu)先搜索算法對(duì)OPEN表中所有節(jié)點(diǎn)的f(n)進(jìn)行比較開(kāi)始把S放入OPEN表，計(jì)算估價(jià)函數(shù)f(s)OPEN表為空表？把OPEN表中的第一個(gè)節(jié)點(diǎn)n放入CLOSED表n為目標(biāo)節(jié)點(diǎn)嗎？擴(kuò)展n，計(jì)算所有子節(jié)點(diǎn)的估價(jià)函數(shù)值，并提供它們返回節(jié)點(diǎn)n的指針。失敗成功局部最佳優(yōu)先搜索算法框圖是否是否把子節(jié)點(diǎn)送入OPEN表，并對(duì)其中的所有節(jié)點(diǎn)按估價(jià)函數(shù)值由小到大重排。開(kāi)始把S放入OPEN表，計(jì)算估價(jià)函數(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)先搜索樹(shù)123846(4)75⑦搜索得到的路徑如黃線所示57①④⑤⑥③12384567123845671238456本題采用了簡(jiǎn)單的估價(jià)函數(shù)

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

123845671238456712384567(3)(5)(5)

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

最佳優(yōu)先算法有時(shí)無(wú)法得到最優(yōu)解，因?yàn)樗墓纼r(jià)函數(shù)f的選取時(shí)，5.5A*算法對(duì)估價(jià)函數(shù)加上一些限制，以保證得到最優(yōu)解的啟發(fā)式搜索算法最優(yōu)估價(jià)函數(shù)

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

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

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

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

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

解2：h(n)=P(n)，P(n)定義為每一個(gè)數(shù)碼與其目標(biāo)位置之間距離（不考慮夾在其間的數(shù)碼）的總和，同樣可以斷定至少要移動(dòng)P(n)步才能到達(dá)目標(biāo)，因此有P(n)≤h*(n)，即滿足A*算法的限制條件。A*算法例1：八數(shù)碼問(wèn)題解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：修道士和野人問(wèn)題設(shè)在河的左岸有三個(gè)修道士、三個(gè)野人和一條船，修道士想用這條船把所有的人運(yùn)到河對(duì)岸，但受以下條件的約束：

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

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

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

S=(m,c,b)

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

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

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

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

DiagonalDistance，如果在地圖上允許作斜線方向的運(yùn)動(dòng)，則MahattanDistance修正為DiagonalDistance：h(A)=max(abs(A.x-goal.x),abs(A.y-goal.y))估價(jià)函數(shù)（HeuristicFunction）估價(jià)函數(shù)的正估價(jià)函數(shù)的判優(yōu)一般情形下，我們只需對(duì)估價(jià)函數(shù)的值進(jìn)行比較而取其大者即可，但在幾個(gè)結(jié)點(diǎn)的估價(jià)函數(shù)值相同的情形下，我們需要采取一定的策略來(lái)決定這幾者誰(shuí)更優(yōu)，從而避免對(duì)多個(gè)點(diǎn)的搜索。從而如下代碼可實(shí)現(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...這段代碼計(jì)算始點(diǎn)、當(dāng)前點(diǎn)和終點(diǎn)的矢量積，從而可以判斷這三點(diǎn)是否共線（或近似共線），這樣不同點(diǎn)間即使有微小的差別也會(huì)被放大，從而更利于判斷。估價(jià)函數(shù)的判優(yōu)一般情形下，我們只需對(duì)估價(jià)函數(shù)的值進(jìn)行比較而取改進(jìn)的A*算法a.

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

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

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

BeamSearch。在Ad.

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

HierarchicalA*。這種算法思想是將搜索過(guò)程化，對(duì)每個(gè)簡(jiǎn)單過(guò)程求解從而得全局較優(yōu)解。正如當(dāng)我們到另一城市時(shí)，可分解為從家里“搜索”一條路徑至車站，再?gòu)能囌尽八阉鳌币粭l路徑到另一城市，當(dāng)我們從家里出發(fā)時(shí)，需要考慮的是怎樣盡快地到達(dá)車站，而不是怎樣盡快地到另一城市。f.

DynamicA*(D*)。這種算法主要用于人工智能和機(jī)器人技術(shù)。由于A*算法一開(kāi)始要求獲得全部信息，而這在實(shí)際中有時(shí)是不可能的，而D*算法就是在假定信息不完整的前提下應(yīng)用A*算法，但它會(huì)隨著得到信息的增多而不斷改進(jìn)結(jié)果，這就決定了它對(duì)空間的要求相當(dāng)高，因?yàn)樗枰Ａ粢郧暗乃蝎@得信息及運(yùn)算情形。d.

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

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

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