第4章 圖搜索策略

第4章圖搜索策略4.1或圖搜索策略4.1或圖搜索策略

圖搜索策略是一種在圖中尋找解路徑的方法。我們首先看看對(duì)于一個(gè)實(shí)際搜索問(wèn)題,應(yīng)該采用什么形式來(lái)表示,是用圖還是用樹(shù),可以作如下比較:(1）用樹(shù)結(jié)構(gòu)，允許搜索圖中有相同結(jié)點(diǎn)出現(xiàn)，。優(yōu)點(diǎn)：控制簡(jiǎn)單。缺點(diǎn)：占空間較大，產(chǎn)生相同結(jié)點(diǎn)多，則時(shí)空均需要較大的代價(jià)4.1或圖搜索策略(2）用圖結(jié)構(gòu)，不允許搜索圖中有相同結(jié)點(diǎn)出現(xiàn)。優(yōu)點(diǎn)：節(jié)省大量空間(相同的結(jié)點(diǎn)只存一次）和時(shí)間(相同結(jié)點(diǎn)不需要重復(fù)產(chǎn)生）。缺點(diǎn)：每產(chǎn)生一個(gè)新的結(jié)點(diǎn)需判斷這個(gè)節(jié)點(diǎn)是否已生成過(guò),因而控制更復(fù)雜，判斷也要占用時(shí)間。碰到具體問(wèn)題時(shí)，要權(quán)衡二者的利弊。若可能產(chǎn)生大量相同結(jié)點(diǎn)，則應(yīng)采用搜索圖。4.1或圖搜索策略圖搜索算法只記錄狀態(tài)空間那些被搜索過(guò)的狀態(tài)，它們組成一個(gè)搜索圖叫G。G由兩張表內(nèi)的節(jié)點(diǎn)組成：Open表：用于存放已經(jīng)生成，且已用啟發(fā)式函數(shù)作過(guò)估計(jì)或評(píng)價(jià)，但尚未產(chǎn)生它們的后繼節(jié)點(diǎn)的那些結(jié)點(diǎn)，也稱(chēng)未考察結(jié)點(diǎn)。Closed表：用于存放已經(jīng)生成，且已考察過(guò)的結(jié)點(diǎn)。一個(gè)結(jié)構(gòu)Tree,它的節(jié)點(diǎn)為G的一個(gè)子集。Tree用來(lái)存放當(dāng)前已生成的搜索樹(shù),該樹(shù)由G的反向邊(反向指針)組成。4.1.1通用或圖搜索算法

或圖通用搜索算法：

設(shè)S0：初始狀態(tài),Sg：目標(biāo)狀態(tài)1.產(chǎn)生一僅由S0組成的open表，即open=(S0)；2.產(chǎn)生一個(gè)空的closed表；3.如果open為空，則失敗退出；4.在open表上按某一原則選出第一個(gè)優(yōu)先結(jié)點(diǎn)，稱(chēng)為n，將n放到closed表中，并從open表中去掉n；4.1.1通用或圖搜索算法5.若n∈Sg，則成功退出；解為在Tree中沿指針從n到s0的路徑，或n本身。(如八皇后問(wèn)題給出n即可，八數(shù)碼問(wèn)題要給出路徑）6.產(chǎn)生n的一切后繼，將后繼中不是n的先輩點(diǎn)的一切點(diǎn)構(gòu)成集合M，將裝入G作為n的后繼,這就除掉了既是n的先輩又是n的后繼的結(jié)點(diǎn)，就避免了回路,節(jié)點(diǎn)之間有偏序關(guān)系存在）4.1.1通用或圖搜索算法7.對(duì)M中的元素P，分別作兩類(lèi)處理：7.1若P∈G，即P不在open表中也不在closed表中，則P根據(jù)一定原則加入open表注1，同時(shí)加入搜索圖G中，對(duì)P進(jìn)行估計(jì)放入Tree中。7.2P∈G，則決定是否更改Tree中P到n的指針注2。8.轉(zhuǎn)3。4.1.1通用或圖搜索算法注1：若生成的后繼節(jié)點(diǎn)放于：（1）Open表的尾部——相當(dāng)于Breadth-first-search；（2）Open表的首部——相當(dāng)于Depth-first-search；（3）根據(jù)啟發(fā)式函數(shù)f的估計(jì)值確定最佳者，放于Open表的首部——相當(dāng)于Best-first-search最佳優(yōu)先搜索。4.1.1通用或圖搜索算法注2:(1)若P∈M且在open表中，這說(shuō)明P在n之前已是某一結(jié)點(diǎn)m的后繼,但本身尚未被考察(未生成P的后繼)，

S0

Path1Path2

nm后擴(kuò)展p先擴(kuò)展P在n之前已是某一結(jié)點(diǎn)m的后繼4.1.1通用或圖搜索算法這說(shuō)明從S0→p至少有兩條路徑，這時(shí)有兩種情況：a．若Path1的代價(jià)<Path2的代價(jià)時(shí)，當(dāng)前路徑較好，要修改p的指針，使其指向n，即標(biāo)出搜索之后的最好路徑；b．若Path1的代價(jià)≥Path2的代價(jià)時(shí)，原路徑較好，不改變p的指針。4.1.1通用或圖搜索算法(2）若p∈M且在closed表中，這說(shuō)明:a.p在n之前已是某一節(jié)點(diǎn)m的后繼，所以需要作如(1)同樣的處理，如下圖右部。b．p在closed表中，說(shuō)明p的后繼也在n之前已生成，我們稱(chēng)為Ps，那么對(duì)Ps同樣可能由于n→p這一路徑的加入又必須比較多條路徑代價(jià)后而取代價(jià)小的一條，如下圖左部。4.1.1通用或圖搜索算法

S0

過(guò)去對(duì)Ps所選現(xiàn)在生成P過(guò)去生成的最優(yōu)路徑的路徑P的路徑kn

PsmP圖2-23p∈M且在closed表中時(shí)不同的最優(yōu)路徑4.1.1通用或圖搜索算法

即過(guò)去對(duì)S0→P而言的最優(yōu)路徑為S0→m→p，現(xiàn)在要從S0→m→p與S0→n→p中求最優(yōu)路徑。同理，若過(guò)去對(duì)S0→Ps而言的最優(yōu)路徑為S0→k→Ps,現(xiàn)在要從｛S0→p→Ps,S0→k→Ps｝中選最優(yōu)路徑。4.1.1通用或圖搜索算法

S0

n

PmPsPs，

S0

n

PmPsPs，

當(dāng)前搜索圖和搜索樹(shù)例2.9設(shè)當(dāng)前搜索圖和搜索樹(shù)分別為：4.1.1通用或圖搜索算法

若啟發(fā)式函數(shù)f(n）為從起點(diǎn)S0到節(jié)點(diǎn)n的最短路徑的長(zhǎng)度，該長(zhǎng)度用邊的數(shù)目表示。設(shè)當(dāng)前擴(kuò)展的節(jié)點(diǎn)是搜索圖中的n，設(shè)p是n的后繼，如下圖2-25(a)，p是已考察節(jié)點(diǎn)，則在擴(kuò)展了節(jié)點(diǎn)n后，P的f值應(yīng)從4減少到2，這時(shí)Tree中P原來(lái)指向m的指針應(yīng)改變指向n，4.1.1通用或圖搜索算法

S0

n

FmPsPPs，

S0

n

FmPsPPs，

擴(kuò)充n的搜索圖修改P指針的搜索樹(shù)4.1.1通用或圖搜索算法

S0

n

FmPsPPs，

P的指針改變后，Tree中指針的修改P的指針改變后，Ps，的路徑自動(dòng)改變了，Ps的f值從4減少到了3，這時(shí)也應(yīng)該修改在Tree中的指針，修改的結(jié)果為圖2-26例：在地圖上尋找城市A至B的最短路徑，實(shí)線表示從S0到某節(jié)點(diǎn)ni所經(jīng)過(guò)的路徑，虛線表示ni與Sg的可選擇的路徑，雙虛線表示ni與Sg的直線距離(可以從地圖上量出）,但并沒(méi)有實(shí)際的道路，則實(shí)線表示的路徑為g(n),雙虛線和虛線表示的路徑都可作為h(n)，虛線表示的路徑為h*(n）。如果以雙虛線表示的路徑作為h(n)，則有h(n）h*(n），g(n）≥g*(n）。S0Sgn4.1.2A算法與A*算法

1．A算法與A*算法定義或圖通用算法在采用如下形式的估計(jì)函數(shù)時(shí),稱(chēng)為A算法。f(n)=g(n)+h(n)其中g(shù)(n)表示從S0到n點(diǎn)的搜索費(fèi)用的估計(jì)，因?yàn)閚為當(dāng)前節(jié)點(diǎn)，搜索已達(dá)到n點(diǎn)，所以g(n)可計(jì)算出。h(n)表示從n到Sg接近程度的估計(jì)，因?yàn)樯形凑业浇饴窂?，所以h(n)僅僅是估計(jì)值。4.1.2A算法與A*算法

若規(guī)定h(n)≥0，并且定義：

f*(n)=g*(n)+h*(n)表示S0經(jīng)點(diǎn)n到Sg最優(yōu)路徑的費(fèi)用，也有人將f*(n)定義為實(shí)際最小費(fèi)用。其中g(shù)*(n)為S0到列n的最小費(fèi)用,h*(n)為n到Sg的實(shí)際最小費(fèi)用。在上例中，雙虛線表示的路徑就可以作為h(n），顯然有g(shù)(n）≥g*(n）h(n）h*(n）

若令h(n）≡0，則A算法相當(dāng)于廣度優(yōu)先，因?yàn)樯弦粚庸?jié)點(diǎn)的搜索費(fèi)用一般比下一層的小。g(n）≡h(n）≡0，則相當(dāng)于隨機(jī)算法。g(n）≡0，則相當(dāng)于最佳優(yōu)先算法。特別是當(dāng)要求

h(n）≤h*(n），就稱(chēng)為這種A算法為A*算法。4.1.2A算法與A*算法

A*算法

設(shè)S0：初態(tài),Sg：目標(biāo)狀態(tài)1.open={S0}；2.closed={}；3.如果open={}，失敗退出；4.在open表上取出f最小的結(jié)點(diǎn)n，n放到closed表中；f(n)=g(n)+h(n)h<=h*4.1.2A算法與A*算法5.若n∈Sg，則成功退出；6.產(chǎn)生n的一切后繼，將后繼中不是n的先輩點(diǎn)的一切點(diǎn)構(gòu)成集合M7.對(duì)M中的元素P，分別作兩類(lèi)處理：7.1若P∈G，則P對(duì)P進(jìn)行估計(jì)加入open表，記入G和Tree。7.2P∈G，則決定更改Tree中P到n的指針并且更改P的子節(jié)點(diǎn)n的指針和費(fèi)用。8.轉(zhuǎn)3。4.1.2A算法與A*算法2．A*算法的性質(zhì)A*算法與一般的最佳優(yōu)先比較，有其特有的性質(zhì)：如果問(wèn)題有解，即S0→Sg存在一條路徑，A*算法一定能找到最優(yōu)解。這一性質(zhì)稱(chēng)為可采納性(admissibility）。（p41例2.11)4.1.2A算法與A*算法下面要證明A*算法的可采納性，證明分兩步：(1）證若問(wèn)題有解，A*一定終止，由如下命題1-3證出。(2）證若問(wèn)題有解，A*終止時(shí)一定找到最優(yōu)解，由如下命題4證出。4.1.2A算法與A*算法命題1對(duì)有限圖而言，A*一定終止。證：考察A*算法，算法終止只有二處：第一處在第5步，找到解時(shí)成功終止。第二處在第3步，open為空時(shí)失敗退出。算法每次循環(huán)從open上去掉一個(gè)點(diǎn)，而有限圖的open表只有有限個(gè)節(jié)點(diǎn)加入，所以找不到解也會(huì)因?yàn)閛pen表為空而停止4.1.2A算法與A*算法命題2若A*不終止，則搜索圖中open表上的點(diǎn)的f值將會(huì)越來(lái)越大。證：設(shè)n為open中任一節(jié)點(diǎn)，d*(n）為從S到n中最短路徑長(zhǎng)度，由于從某一點(diǎn)求出其后繼的費(fèi)用不小于某個(gè)小的正數(shù)e，所以g*(n）≥d*(n）·e而g(n）≥g*(n）≥d*(n）·e又因?yàn)閔(n）≥0所以f(n）≥g(n）≥g*(n）≥d*(n）·e(2-1）4.1.2A算法與A*算法4.1.2A算法與A*算法命題3若問(wèn)題有解，在A*終止前，open表上必存在一點(diǎn)n’，n’位于從S0→Sg的最優(yōu)路徑上，且有f(n’）≤f*(S0）(2-2）f*(S0）表示從S0到Sg的最優(yōu)路的實(shí)際最小費(fèi)用。f*(n）表示從S0經(jīng)過(guò)n到Sg的最優(yōu)路的實(shí)際最小費(fèi)用。4.1.2A算法與A*算法證：令S0=n0，n1，n2，…，nk=Sg為一條最優(yōu)路徑，設(shè)n’∈path(n0，n1，…，nk）中最后一個(gè)出現(xiàn)在open表上的元素。顯然n’一定存在，因?yàn)橹辽儆蠸0=n0必然在open上，只考慮當(dāng)nk還未在closed表中時(shí)，因?yàn)槿鬾k已在closed表中時(shí)，則nk=Sg，A*算法將終止于成功退出。由定義有

f(n’）=g(n’）+h(n’）=g*(n’）+h(n’）(因?yàn)閚’在最優(yōu)路徑上）

≤g*(n’）+h*(n’）=f*(n’）=f*(S0）(由于A*的定義h(n)≤h*(n))所以f(n’）≤f*(S0）成立。4.1.2A算法與A*算法推論1若問(wèn)題有解，A*算法一定終止。

因?yàn)槿鬉*算法不終止，則命題2的f(n）≥g(n）≥g*(n）≥d*(n）·e（2-1）與命題3的

f(n’）≤f*(S0）(2-2）同時(shí)成立，則產(chǎn)生矛盾。4.1.2A算法與A*算法命題4若問(wèn)題有解，A*算法終止時(shí)一定找到最優(yōu)解,即A*算法是可采納的。證：A*終止只有兩種情況。(1)

在第3步,因open為空而失敗退出但由命題3可知：A*終止前，open表上必存在一點(diǎn)n’，滿(mǎn)足f(n’）≤f*(S0）即open表不會(huì)空，所以，不會(huì)終止于第3步。4.1.2A算法與A*算法推論2凡open表中任一點(diǎn)n，若f(n）<f*(S0），最終都將被A*算法挑選出來(lái)求后繼，也即被挑選出來(lái)進(jìn)行擴(kuò)充。證：用反證法，設(shè)f(n）<f*(S0）且n沒(méi)有被選出來(lái)作后繼由命題4,A*算法將找到一條路S0=n0，n1，…，nk=Sg,為最優(yōu)路徑且f(ni)≤f(n)對(duì)一切i=0,1,…,k成立因?yàn)樽顑?yōu)路徑選擇的是ni而不是n，又因?yàn)閚i在最優(yōu)路上,由f(ni)=f*(S0)所以f*(S0)≤f(n)與f(n)<f*(S0)同時(shí)成立,這是一個(gè)矛盾。命題5凡A*算法挑選出來(lái)求后繼的點(diǎn)n必定滿(mǎn)足:f(n）≤f*(S0）(2-3)證明:若n=Sg,由命題4可知,A*一定找到最優(yōu)解，所以f(n）=f*(Sg）≤f*(S0）;若n≠Sg,由命題3可知:存在n’∈open且有f(n’）≤f*(S0）而現(xiàn)在A*算法選中了n而不是n’,所以必有f(n)≤f(n’)≤f*(S0)即f(n）≤f*(S0）定義1

若A1,A2均是A*算法,A1采用f1(x)=g1(x)+h1(x)作為估計(jì)函數(shù)，A2采用f2(x)=g2(x)+h2(x)作為估計(jì)函數(shù)。h1(x),h2(x)都滿(mǎn)足:hi(x)≤hi*(x),i=1,2(2-4)如果h1(x)<h2(x)，則稱(chēng)A2比A1更具有信息(moreinformed)。4.1.2A算法與A*算法命題6若A2比A1更具有信息,對(duì)任一圖的搜索,只要從S0→Sg存在一條路徑,那么,A2所用來(lái)擴(kuò)充的點(diǎn)也一定被A1所擴(kuò)充。證明:在證明之前需要說(shuō)明，在圖搜索過(guò)程中,若某一點(diǎn)有幾個(gè)先輩節(jié)點(diǎn),則只保留最小費(fèi)用的那條路,所以A1和A2搜索的結(jié)果是樹(shù)而不是圖。下面以A2搜索樹(shù)中節(jié)點(diǎn)的深度來(lái)歸納證明。歸納基礎(chǔ)設(shè)A2擴(kuò)充的點(diǎn)n的深度d=0，即n=S0，顯然A1也擴(kuò)充點(diǎn)n，因?yàn)锳1、A2都要從S0開(kāi)始。歸納假設(shè)假設(shè)A1擴(kuò)充了A2搜索樹(shù)中一切深度d≤k的節(jié)點(diǎn)。歸納證明要證明A2搜索樹(shù)中深度d=k+1的任一節(jié)點(diǎn)n也必定為A1所擴(kuò)充。用反證法若A2擴(kuò)充了n，而A1沒(méi)有擴(kuò)充n，將導(dǎo)出矛盾。4.1.2A算法與A*算法

由歸納法假設(shè)可知A1搜索樹(shù)深度小于等于k的節(jié)點(diǎn)包含A2搜索樹(shù)深度小于等于k的節(jié)點(diǎn)，所以如果存在路徑S0→n,d(n）=k+1,則有g(shù)1(n）≤g2(n）(2-5）因?yàn)锳1搜索樹(shù)中從S0→n路徑多些.4.1.2A算法與A*算法

圖2-30A1搜索樹(shù)中從S0→n路徑比A2多一些

由A2算法搜索時(shí)∵A2選的是min{g2(S0→S1→n),g2(S0→S2→n)}由A1算法搜索時(shí)選的是min{g1(S0→S1→n),g1(S0→S2→n),g1(S0→

S3→

n)}A1是從更多的路徑中選最短者∴g1(n)≤g2(n)。4.1.2A算法與A*算法

搜索的費(fèi)用與h(n)有一定的關(guān)系A(chǔ)*算法要求h(n）≤h*(n）但并不是越小越好，也并不是越大越好，下面分兩種情況討論。4.1.2A算法與A*算法1)

h(n)估計(jì)過(guò)低，浪費(fèi)過(guò)多這可以用下圖2-31示意說(shuō)明。h(x)愈小，因?yàn)锳*算法總是找具有小的f值的節(jié)點(diǎn)來(lái)擴(kuò)充，將會(huì)造成一種誤導(dǎo),導(dǎo)致本不是通向解點(diǎn)也要搜索，并求后繼。這樣必定白白浪費(fèi)時(shí)空。

Sgh(n)估計(jì)過(guò)低(2）h(n)估計(jì)過(guò)高，則可能錯(cuò)過(guò)到目標(biāo)。

當(dāng)h(x)超過(guò)它的實(shí)際值時(shí)，則有可能錯(cuò)過(guò)本來(lái)可以到達(dá)的目標(biāo)。在下圖中，若h(B)>AC分枝中任一點(diǎn)的值，則永遠(yuǎn)不會(huì)走B這條路，這將導(dǎo)致可能找不到解。BCASg實(shí)際是1,估計(jì)21.51

另外搜索的費(fèi)用并不完全由搜索節(jié)點(diǎn)數(shù)多少來(lái)確定，若f2(n)計(jì)算遠(yuǎn)比f(wàn)1(n)復(fù)雜，則在比較兩個(gè)搜索算法時(shí)，必須要考慮f的計(jì)算費(fèi)用。一般來(lái)說(shuō)要權(quán)衡如下三個(gè)因素：(1)路徑費(fèi)用；(2)尋找路徑時(shí)所搜索的節(jié)點(diǎn)數(shù)；(3)計(jì)算f所需的計(jì)算量。4.1.2A算法與A*算法若h(x)滿(mǎn)足一定限制,如單調(diào)性限制，則搜索路徑幾乎就是解路徑，因而大大減小了搜索費(fèi)用。

定義2

一個(gè)啟發(fā)式函數(shù)中的h(x)滿(mǎn)足單調(diào)限制，可定義為：如果對(duì)所有ni與nj，nj是ni的后繼，有h(ni)≤h(nj)+c(ni,nj)，并且h(Sg)=0,即nj到目標(biāo)的最佳費(fèi)用估計(jì)不會(huì)大于ni到目標(biāo)的最佳費(fèi)用估計(jì)加上ni至nj的費(fèi)用。

命題7估計(jì)函數(shù)若滿(mǎn)足單調(diào)限制，那么A*所擴(kuò)充的任一點(diǎn)(即用來(lái)求過(guò)后繼的點(diǎn)）n必在最優(yōu)路上。證明思路：令g*(n)代表從S0→n的最優(yōu)路徑費(fèi)用，所以一般有:g(n）≥g*(n）(2-12）下面再利用單調(diào)限制能夠證明：g(n）≤g*(n）(2-13）聯(lián)立(2-12），(2-13），可得g(n）=g*(n)，也就說(shuō)明了n位于最佳路徑上。A*算法的優(yōu)點(diǎn)有：（1）A*算法一定能保證找到最優(yōu)解。（2）若以搜索的節(jié)點(diǎn)數(shù)來(lái)估計(jì)它得效率，則當(dāng)啟發(fā)式函數(shù)h的值單調(diào)上升時(shí)，它的效率只會(huì)提高，不會(huì)降低。（3）有比較合理的漸近性質(zhì)。3．對(duì)A*算法的評(píng)價(jià)A*算法的缺點(diǎn)是：在不僅考慮搜索節(jié)點(diǎn)的多少，而且還要考慮搜索節(jié)點(diǎn)被搜索的次數(shù)的時(shí)候，則當(dāng)h(n）過(guò)低估計(jì)h*(n）時(shí)，有時(shí)會(huì)顯出很高的復(fù)雜性。例2.12就是一例.野人傳教士問(wèn)題4.2與/或圖搜索

4.2.1問(wèn)題歸約求解方法在問(wèn)題求解過(guò)程中,將一個(gè)大的問(wèn)題變換成若干子問(wèn)題,子問(wèn)題又可分解成更小的子問(wèn)題，這樣一直分解到可以直接求解為止,全部子問(wèn)題的解即為大的問(wèn)題的解,這樣的過(guò)程稱(chēng)為問(wèn)題的規(guī)約(ProblemReduction)。并稱(chēng)大的問(wèn)題為初始問(wèn)題，可直接求解的問(wèn)題為本原問(wèn)題。一般說(shuō)來(lái)，歸約方法求解問(wèn)題需要三大要素：1．

初試問(wèn)題的描述。2．一組將問(wèn)題變換成子問(wèn)題的變換規(guī)則。3．

一組本原問(wèn)題的描述。

例2.13符號(hào)積分問(wèn)題4.2.1問(wèn)題歸約求解方法分解時(shí)有三種可能:1.

and2.

or3.

and,or都有從初始問(wèn)題出發(fā),建立子問(wèn)題以及子問(wèn)題的子問(wèn)題,直至把初始問(wèn)題規(guī)約為一個(gè)本原問(wèn)題的集合,這就是問(wèn)題規(guī)約的實(shí)質(zhì)。4.2.1問(wèn)題歸約求解方法4.2.2與/或圖搜索將問(wèn)題求解歸約為與/或圖的時(shí)，作如下規(guī)定：1．根節(jié)點(diǎn)為原始問(wèn)題描述;本原問(wèn)題的節(jié)點(diǎn)為葉節(jié)點(diǎn)。2．可解節(jié)點(diǎn)為：2.1終葉節(jié)點(diǎn)是可解節(jié)點(diǎn)；2.2若n為一非終葉節(jié)點(diǎn)，且含有“或”后繼節(jié)點(diǎn)，則只有當(dāng)后繼節(jié)點(diǎn)中至少有一個(gè)是可解節(jié)點(diǎn)時(shí)，n才可解；2.3若n為非終葉節(jié)點(diǎn)，且含“與”后繼節(jié)點(diǎn)，則只有當(dāng)后繼節(jié)點(diǎn)全部可解時(shí)，n才可解。4.2.2與/或圖搜索3．不可解節(jié)點(diǎn)：3.1沒(méi)有后繼節(jié)點(diǎn)的非終葉節(jié)點(diǎn)為不可解；3.2若n為一非葉節(jié)點(diǎn)含有“或”后繼節(jié)點(diǎn)，則僅當(dāng)全部后繼節(jié)點(diǎn)為不可解時(shí)，n不可解。3.3若n為一非葉節(jié)點(diǎn)含有“與”后繼節(jié)點(diǎn)，則只要有一個(gè)后繼節(jié)點(diǎn)為不可解時(shí)，n為不可解。4．圖中搜索費(fèi)用的計(jì)算

設(shè)從當(dāng)前節(jié)點(diǎn)n到目標(biāo)集Sg費(fèi)用估計(jì)為h(n).4.1若n∈Sg,則h(n)=0;4.2若n有一組由“與”弧連接的后繼節(jié)點(diǎn){n1,n2,…ni}則:h(n)=c1+c2…+ci+…+h(n1)+h(n2)+…+h(ni)4.3若n既有“與”又有“或”弧，則“與”弧算作一個(gè)“或”后繼，再取各or弧后繼中費(fèi)用最小者為n的費(fèi)用。4.2.2與/或圖搜索4.2.3與/或圖搜索的特點(diǎn)1．與/或圖搜索搜索費(fèi)用的估計(jì)

對(duì)與/或圖則不同，其費(fèi)用計(jì)算的規(guī)則是：

n未生成后繼節(jié)點(diǎn)時(shí)，費(fèi)用由n本身決定;

n已生成后繼節(jié)點(diǎn)時(shí)，費(fèi)用由n的后繼節(jié)點(diǎn)的費(fèi)用決定。因?yàn)楹罄^節(jié)點(diǎn)代表分解的子問(wèn)題,子問(wèn)題的難易程度決定原問(wèn)題求解的難易程度，所以不再考慮n本身的難易程度。因此當(dāng)決定了某個(gè)路徑時(shí)，要將后繼節(jié)點(diǎn)的估計(jì)值往回傳送。4.2.3與/或圖搜索的特點(diǎn)例2.14圖2-31為一個(gè)與/或圖的搜索過(guò)程。第一步，A是唯一節(jié)點(diǎn)；4.2.3與/或圖搜索的特點(diǎn)第二步，擴(kuò)展A后，得到節(jié)點(diǎn)B,C和D,因?yàn)锽，C的耗費(fèi)為9，D的耗費(fèi)為6，所以把列D的弧標(biāo)志為出自A最有希望的??；4.2.3與/或圖搜索的特點(diǎn)第三步，選擇對(duì)D的擴(kuò)展，得到E和F的與弧，其耗費(fèi)估計(jì)值為10。此時(shí)回退一步后，發(fā)現(xiàn)與弧BC比D更好，所以將弧BC標(biāo)志為目前最佳路徑；4.2.3與/或圖搜索的特點(diǎn)第四步，在擴(kuò)展B后,再回傳值發(fā)現(xiàn)弧BC的耗費(fèi)為12（6+4+2），所以D再次成為當(dāng)前最佳路徑。4.2.3與/或圖搜索的特點(diǎn)最后求得的耗費(fèi)為:f(A)=min(12,4+4+2+1)=11。以上搜索過(guò)程由兩大步組成：（1)自頂向下，沿當(dāng)前最優(yōu)路產(chǎn)生后繼節(jié)點(diǎn)。（2）由底向下，作估計(jì)值修正，再重新選擇最優(yōu)路。2.與/或圖搜索路徑的選擇由于有“與”連接弧，所以不能像“或”弧那樣只看從節(jié)點(diǎn)到節(jié)點(diǎn)的個(gè)別路徑。有時(shí)路徑長(zhǎng)反而好一些。如：12347856910目標(biāo)不可解搜索雖然從①→②→⑧→⑩→⑤比①→③→⑤更長(zhǎng)，但由于走③分枝的同時(shí)還必須走④，而④不可能通向解,所以有時(shí)走長(zhǎng)點(diǎn)的路徑比短路徑要好一些。12347569108目標(biāo)不可解3.與/或圖搜索的限制與/或圖搜索僅對(duì)不含回路的圖進(jìn)行操作。例如：xy

表示求了x就可以求y.，求了y就可以求x，兩者都不可能求解。4.2.4與/或圖搜索算法AO*

AO*算法：1.令G=Init,計(jì)算h’(Init)。2.在Init標(biāo)志solved之前或h’(Init)變成大于Futility之前，執(zhí)行以下步驟：2.1沿始于Init的已帶標(biāo)志的弧，選出當(dāng)前沿標(biāo)志路上未擴(kuò)展的節(jié)點(diǎn)之一擴(kuò)展（即求后繼節(jié)點(diǎn)），此節(jié)點(diǎn)稱(chēng)為node。4.2.4與/或圖搜索算法AO*2.2生成node的后繼節(jié)點(diǎn)。若無(wú)后繼節(jié)點(diǎn)，則令h’(node)=Futility,說(shuō)明該節(jié)點(diǎn)不可解；若有后繼節(jié)點(diǎn)，稱(chēng)為successor,對(duì)每個(gè)不是node祖先的后繼節(jié)點(diǎn)（避免回路），執(zhí)行下述步驟：2.2.1將successor加入G。2.2.2若successor∈Sg,則標(biāo)志successor為solved，且令h’(successor)=0。2.2.3若successor∈Sg,則求h’(successor)4.2.4與/或圖搜索算法AO*

2.3由底向上作評(píng)價(jià)值修正，重新挑選最優(yōu)路徑。//令S為一節(jié)點(diǎn)集。//S＝｛已標(biāo)志為solved的點(diǎn)，或h’值已//改變,需回傳至其先輩節(jié)點(diǎn)的節(jié)點(diǎn)｝令S初值＝｛node｝,重復(fù)下述過(guò)程，直到S為空時(shí)停止。2.3.1從S中挑選一節(jié)點(diǎn),該節(jié)點(diǎn)的后輩點(diǎn)均不在S中(保證每一正在處理的點(diǎn)都在其先輩節(jié)點(diǎn)之前作處理),此節(jié)點(diǎn)稱(chēng)為current,并從S中刪除;4.2.4與/或圖搜索算法AO*

2.3.2計(jì)算始于current的每條弧的費(fèi)用,即每條弧本身的費(fèi)用加上弧末端節(jié)點(diǎn)h’的值(注意區(qū)分與,或弧的計(jì)算方法),并從中選出極小費(fèi)用的弧作為h’（current）的新值。2.3.3將費(fèi)用最小弧標(biāo)志為出自current的最優(yōu)路徑。2.3.4若current與新的帶標(biāo)志的弧所連接的點(diǎn)均標(biāo)志solved,則current標(biāo)志solved.。2.3.5若current已標(biāo)志為solved或current的費(fèi)用已改變，則需要往回傳，因此要把current的所有先輩節(jié)點(diǎn)加入S中。ABCDstep2.3.1S={A}step2.3.2current：A由于有A→BandC的弧，current的費(fèi)用=1+1+h’(B)+h’(C)=9由于有A→D的弧，current的費(fèi)用=1+5=6A的費(fèi)用=min(9,6)=6;（3）（4）（5）ADEF

h’(E)=4h’(F)=4106

node=D，由step2.2.3，擴(kuò)展D得successor={E,F}，D的耗費(fèi)估計(jì)已經(jīng)改變，向上回傳，導(dǎo)致A的耗費(fèi)為min（9，11）=9，所以，最優(yōu)路徑為A→BC弧。4.2.5對(duì)AO*算法的進(jìn)一步觀察(1)算法中2.3.5步中可能造成無(wú)用的回傳例2.17（7）ABCDE(10)(6)

（3）（5）