3.4啟發(fā)式搜索策略啟發(fā)信息和估價(jià)函數(shù)A*算法

寬度優(yōu)先、深度優(yōu)先搜索屬于盲目搜索（按規(guī)定的路線(xiàn)搜索）。盲目搜索效率低，耗費(fèi)過(guò)多的計(jì)算空間與時(shí)間。2.若選擇最有希望的節(jié)點(diǎn)加以擴(kuò)展(NOT按規(guī)定的路線(xiàn)盲目搜索)，則搜索效率將會(huì)大為提高。Background

andQuestions:e.g.1Astofig.,whichone,thechildrenA,BandCofS,wouldbehopefultogetgoalorgetgoalwithlittlecost?MakechoiceForeachstepsearching.3.4.1啟發(fā)信息和估價(jià)函數(shù)啟發(fā)信息：

與具體問(wèn)題求解相關(guān)的控制性知識(shí)。CanmakechoiceUsefulforsearchingsolution.e.g.2busdebitcardsforstudentsorregularpeopleBlindsearchingisstillusefulinsomecases.估價(jià)函數(shù)：Expressionoftheusefulinformation

估計(jì)OPEN表中各擴(kuò)展節(jié)點(diǎn)的重要程度，給它們排定擴(kuò)展次序。4定義評(píng)價(jià)函數(shù)/估計(jì)函數(shù)f:

f（n）＝g（n）＋h（n）

其中n是被評(píng)價(jià)的節(jié)點(diǎn)。

g(n)：表示從初始節(jié)點(diǎn)S到節(jié)點(diǎn)n的路徑的代價(jià)；

h(n)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的路徑的代價(jià)；

f(n表示從初始節(jié)點(diǎn)S經(jīng)過(guò)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的路徑的代價(jià)。33…n11定義一個(gè)評(píng)價(jià)函數(shù)f…gnhnfn33…xn11定義一個(gè)評(píng)價(jià)函數(shù)f…gnhnfn3.4.2局部擇優(yōu)搜索基本思想： 當(dāng)一個(gè)節(jié)點(diǎn)擴(kuò)展后,在它的所有子節(jié)點(diǎn)中，選估價(jià)函數(shù)f(n)最優(yōu)者作為下一個(gè)考察的節(jié)點(diǎn)。例1：用局部擇優(yōu)搜索策略求解八數(shù)碼問(wèn)題。

估價(jià)函數(shù)定義為f(n)=g（n）+h(n)。其中，

g（n）=d(n)表示搜索depth,等代價(jià)時(shí),g（n）對(duì)局部擇優(yōu)搜索沒(méi)有影響.g(n)issamewhensearchingamongthechildren.

h(n)=w(n)表示結(jié)點(diǎn)n的格局與目標(biāo)結(jié)點(diǎn)D格局相比位置不符的數(shù)碼個(gè)數(shù)。So,估價(jià)函數(shù)定義為f(n)=w(n)。例1局部擇優(yōu)搜索樹(shù)-1：CompareNo.cardsnotintheposition在它的所有子節(jié)點(diǎn)中，選估價(jià)函數(shù)f(n)最優(yōu)者等代價(jià)時(shí),g（n）對(duì)局部擇優(yōu)搜索沒(méi)有影響.例1局部擇優(yōu)搜索樹(shù)-2：例1局部擇優(yōu)搜索樹(shù)-3：局部擇優(yōu)搜索隨機(jī)性如果改搜索No.3格局為其具有相同估值的兄弟格局，如圖所示。請(qǐng)補(bǔ)充搜索樹(shù)的其余部分。2 318 47 6 51234562 318 47 6 524102局部擇優(yōu)搜索隨機(jī)性Bestsolution局部擇優(yōu)搜索小結(jié)主要在單因素、單極值情況下使用；在多因素，多極值情況下，找不到最佳解。

AsforNo.3anditsbrother,twotopvalues局部擇優(yōu)搜索亦稱(chēng)“瞎子爬山法”。asforfig.找不到最佳解。

Think找不到最佳解?Maybemaketheleftoneasthefirstchoice:differentsearchingroutscasuallyReturntoComparewithglobalAlgorithm?3.4.3全局擇優(yōu)搜索特點(diǎn)：對(duì)所有已生成而未擴(kuò)展的節(jié)點(diǎn)，從中選出估價(jià)函數(shù)f(n)最優(yōu)的節(jié)點(diǎn)進(jìn)行擴(kuò)展。例1：八數(shù)碼問(wèn)題如果將估計(jì)函數(shù)定義為：f(n)=g(n)+h(n)其中，nforglobalnodesgeneratedalreadyandnotdevelopedg(n)=d(n)代表結(jié)點(diǎn)n的擴(kuò)展深度,eachstepcostsame

h(n)=w(n)表示結(jié)點(diǎn)n的格局與目標(biāo)結(jié)點(diǎn)D格局相比位置不符數(shù)碼個(gè)數(shù)。

全局擇優(yōu)搜索例1全局擇優(yōu)搜索樹(shù)：Clickherefornextstep例2局部擇優(yōu)搜索樹(shù)-1：例1全局擇優(yōu)搜索樹(shù)八數(shù)碼問(wèn)題，如果用局部擇優(yōu)搜索策略求解，搜索No.2格局后，必將沿箭頭所示方向搜索。請(qǐng)補(bǔ)充搜索樹(shù)的其余部分。

全局擇優(yōu)搜索可避免局部擇優(yōu)搜索隨機(jī)性例2局部擇優(yōu)搜索樹(shù)-2：Compare

globalandlocale.g.1globle擇優(yōu)搜索樹(shù)h(n)＝W(n)AvoidTrapbranchOtherwiselocal擇優(yōu)搜索樹(shù)：f(n)＝W(n)GlobalFirstGlobalchange全局擇優(yōu)搜索小結(jié)think?

algorithm&OPENDS：在OPEN表中保留所有已生成而未擴(kuò)展的節(jié)點(diǎn)，并用估價(jià)函數(shù)f(n)對(duì)它們?nèi)窟M(jìn)行估計(jì)，andsort!得到的不一定是實(shí)際上的最佳解。Answer:Designproperf(n).otherwisejustlikepointdirection.

從所有已生成而未擴(kuò)展的節(jié)點(diǎn)中，選出最優(yōu)的節(jié)點(diǎn)進(jìn)行擴(kuò)展。avoidtrappinginthelocalbestQuestionS：①howmanyh(w)ofthestatesare？②whichonewouldbemorehopefullyforbestsolution?③whichonecostlittlefromtheinitialtothecurrent?1 2 38 47 6 5 2 318 47 6 51 2 378 4 6 5a)b)c)w=0w=2w=2g=xg=10g=20

S0Analyze：

c)meanscostmuchtofindaROUThopefullytothegoal.1 2 38 47 6 5 2 318 47 6 51 2 378 4 6 5a)b)c)P=0P=2P=2g=xg=10g=203.4.4A*算法特點(diǎn)：對(duì)狀態(tài)空間搜索算法中的擴(kuò)展節(jié)點(diǎn)選擇原則進(jìn)行了限制。選用了一個(gè)比較特殊的估價(jià)函數(shù)。性質(zhì):采納性單調(diào)性信息性271)基本思想：定義一個(gè)評(píng)價(jià)函數(shù)f:

f（n）＝g（n）＋h（n）

其中n是被評(píng)價(jià)的節(jié)點(diǎn)。

g*(n)：表示從初始節(jié)點(diǎn)S到節(jié)點(diǎn)n的最短路徑的代價(jià)；

h*(n)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的最短路徑的代價(jià)；

f*(n)=g*(n)+h*(n)：表示從初始節(jié)點(diǎn)S經(jīng)過(guò)節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)G的最短路徑的代價(jià)。

f（n）、g（n）和h（n）則分別表示是對(duì)f*（n）、g*（n）和h*（n）三個(gè)函數(shù)值的的估計(jì)值。Requirement1:g（n）>0meansS0=!SgNotification:whilesearching①Generally,g（n）>=g*(n)②Trendis,g（n）descend.e.g.ifnwillbesearchedsecondtime,g（n2）<=g（n1）,otherwise,g（n2）routwillbeabandonedinsolution,keepg（n1）.最佳圖搜索算法A﹡

（OptimalSearch）29

Requirement2:算法給h(n)加上如下的限制條件，h(n)≤h*(n)則算法轉(zhuǎn)換為A*算法。2）A*算法性質(zhì)：A*算法，具有可采納性?？刹杉{（Admissibility）：一般地說(shuō)，對(duì)任意一個(gè)圖，當(dāng)s到目標(biāo)節(jié)點(diǎn)有路徑存在時(shí)，如果搜索算法總是在找到一條從s到目標(biāo)節(jié)點(diǎn)的最佳路徑上結(jié)束，則稱(chēng)該搜索算法是可采納的。30e.g.1八數(shù)碼問(wèn)題

31啟發(fā)函數(shù)根據(jù)任意節(jié)點(diǎn)與目標(biāo)之間的差異來(lái)定義，“不在位”將牌個(gè)數(shù)估計(jì)，取h(n)＝W(n)。thinking?W(n)≤h*(n)盡管對(duì)具體的h*(n)是多少很難確切知道，但能確定得出：至少要移動(dòng)W(n)步才能達(dá)到目標(biāo)。八數(shù)碼問(wèn)題啟發(fā)函數(shù)-11 2 38 47 6 51 2 3 8 47 6 5a)W(n)=1steps=12 318 47 6 5b)W(n)=3steps=328316 47 5c)W(n)=4steps=5h*meansleaststepsTothegoal32

啟發(fā)函數(shù)根據(jù)任意節(jié)點(diǎn)與目標(biāo)之間的距離的信息P(n)來(lái)定義P(n)定義為每一個(gè)將牌與其目標(biāo)位置之間距離的總和，取h(n)＝P(n)。

thinking?P(n)≤h*(n)八數(shù)碼問(wèn)題啟發(fā)函數(shù)-21 2 38 47 6 51 2 3 8 47 6 5a)P(n)=1steps=12 318 47 6 5b)P(n)=3steps=328316 47 5c)P(n)=5steps=5c)P(8)=2P(6)=1P(2)=1P(1)=1h(n)=P(n)

搜索樹(shù)331 2 38 47 6 534取不同啟發(fā)函數(shù)，應(yīng)用A*算法求得最佳解時(shí)所擴(kuò)展和生成的節(jié)點(diǎn)數(shù)

35h(n)=w(n)

搜索樹(shù)DevelopNo.6GenerateNo.8-1(excepts0)local擇優(yōu)搜索樹(shù)-1：f(n)＝W(n)DevelopNo.10GenerateNo.20Blind搜索樹(shù)?More!37①OPEN:＝（s），f（s）:＝g（s）+h（s）;

②LOOP：IFOPEN＝（）THENEXIT（FAIL）；

③n:＝FIRST（OPEN）；

④REMOVE（n，OPEN），ADD（n，CLOSED）；

⑤IFGOAL（n）THENEXIT（SUCCESS）；⑥EXPAND（n）→{mi}，計(jì)算f（mi

）＝g（mi）+h（mi）；

g（mi）是從s通過(guò)n到mi的代價(jià)(g（mi）=0forlocalbest)h(mi

)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的代價(jià)的估計(jì)；

f（mi）是從s通過(guò)n、mi到目標(biāo)節(jié)點(diǎn)代價(jià)的估計(jì)。⑦OPEN中的節(jié)點(diǎn)按f值從小到大排序(childrensortingforlocalbest)；pointerfrommiton⑧GOLOOP；g(mi)：根據(jù)已經(jīng)搜索的結(jié)果，按照從初始節(jié)點(diǎn)s到節(jié)點(diǎn)mi的路徑，計(jì)算這條路徑的代價(jià)就可以了。h(mi)：是與問(wèn)題有關(guān)的，需要根據(jù)具體的問(wèn)題來(lái)定義。Algorithm38①OPEN:＝（s），f（s）:＝g（s）+h（s）;

②LOOP：IFOPEN＝（）THENEXIT（FAIL）；

③n:＝FIRST（OPEN）；

④IFGOAL（n）THENEXIT（SUCCESS）；

⑤REMOVE（n，OPEN），ADD（n，CLOSED）；

⑥EXPAND（n）→{mi}，計(jì)算f（n，mi

）＝g（n，mi）+h（mi）；

g（n，mi）是從s通過(guò)n到mi的代價(jià)h(mi

)：表示從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的代價(jià)的估計(jì)；

f（n，mi）是從s