人工智能課件第2章3

2.4.2A算法與A*算法

1．A算法與A*算法定義或圖通用算法在采用如下形式的估計(jì)函數(shù)時(shí),稱為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ì)值。2.4.2A算法與A*算法1．A算法與A*算法定義1例2.10在地圖上尋找城市A至B的最短路徑，雙虛線表示ni與Sg的直線距離(可以從地圖上量出）,虛線表示ni與Sg的路徑，則實(shí)線表示的路徑為g(n），虛線表示的路徑為h(n）。A=S0B=Sgn1n2n3n4n5例2.10在地圖上尋找城市A至B的最短路徑，雙虛線表示ni22.4.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到點(diǎn)n的最小費(fèi)用,h*(n)為n到Sg的實(shí)際最小費(fèi)用。在上例中，雙虛線表示的路徑就可以作為h*(n），顯然有g(shù)(n）≥g*(n）。h(n）h*(n）2.4.2A算法與A*算法若規(guī)定h(n)≥0，并且3

若令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），就稱為這種A算法為A*算法。若令h(n）≡0，則A算法相當(dāng)于廣度優(yōu)先，因?yàn)樯弦粚庸?jié)點(diǎn)4A*算法設(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*A*算法55.若n∈Sg，則成功退出；6.產(chǎn)生n的一切后繼，將后繼中不是n的先輩點(diǎn)的一切點(diǎn)構(gòu)成集合M7.對(duì)M中的元素P，分別作兩類處理：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。5.若n∈Sg，則成功退出；62．A*算法的性質(zhì)A*算法與一般的最佳優(yōu)先比較，有其特有的性質(zhì)：如果問題有解，即S0→Sg存在一條路徑，A*算法一定能找到最優(yōu)解。這一性質(zhì)稱為可采納性(admissibility）。（p35例2.11)2．A*算法的性質(zhì)7下面要證明A*算法的可采納性，證明分兩步：(1）證若問題有解，A*一定終止，由如下命題1-3證出。(2）證若問題有解，A*終止時(shí)一定找到最優(yōu)解，由如下命題4證出。下面要證明A*算法的可采納性，證明分兩步：8命題1對(duì)有限圖而言，A*一定終止。證：考察A*算法，算法終止只有二處：第一處在第5步，找到解時(shí)成功終止。第二處在第3步，open為空時(shí)失敗退出。算法每次循環(huán)從open上去掉一個(gè)點(diǎn)，而有限圖的open表只有有限個(gè)節(jié)點(diǎn)加入，所以找不到解也會(huì)因?yàn)閛pen表為空而停止命題1對(duì)有限圖而言，A*一定終止。9命題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）命題2若A*不終止，則搜索圖中open表上的點(diǎn)的f值將會(huì)10命題3若問題有解，在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)過n到Sg的最優(yōu)路的實(shí)際最小費(fèi)用。命題3若問題有解，在A*終止前，open表上必存在一點(diǎn)n11證：令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*算法將終止于成功退出。證：令S0=n0，n1，n2，…，nk=Sg為一條最優(yōu)路徑，12由定義有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）成立。由定義有13推論1若問題有解，A*算法一定終止。因?yàn)槿鬉*算法不終止，則命題2的(2-1）與命題3的(2-1）同時(shí)成立，則產(chǎn)生矛盾。推論1若問題有解，A*算法一定終止。14命題4若問題有解，A*算法終止時(shí)一定找到最優(yōu)解,即A*算法是可采納的。證：A*終止只有兩種情況。(1)

在第3步,因open為空而失敗退出但由命題3可知：A*終止前，open表上必存在一點(diǎn)n’，滿足f(n’）≤f*(S0）即open表不會(huì)空，所以，不會(huì)終止于第3步。命題4若問題有解，A*算法終止時(shí)一定找到最優(yōu)解,即A*算15推論2凡open表中任一點(diǎn)n，若f(n）<f*(S0），最終都將被A*算法挑選出來(lái)求后繼，也即被挑選出來(lái)進(jìn)行擴(kuò)充。證：用反證法，設(shè)f(n）<f*(S0）且n沒有被選出來(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è)矛盾。推論2凡open表中任一點(diǎn)n，若f(n）<f*(S0），16命題5凡A*算法挑選出來(lái)求后繼的點(diǎn)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）命題5凡A*算法挑選出來(lái)求后繼的點(diǎn)n必定滿足:17定義1若A1,A2均是A*算法,A1采用f1(x)=g1(x)+h1(x)作為估計(jì)函數(shù)，A2采用f2=g2(x)+h2(x)作為估計(jì)函數(shù)。h1(x),h2(x)都滿足:hi(x)≤hi*(x),i=1,2(2-4)如果h1(x)<h2(x)，則稱A2比A1更具有信息(moreinformed)。定義1若A1,A2均是A*算法,A1采用f1(x)=g118命題6若A2比A1更具有信息,對(duì)任一圖的搜索,只要從S0→Sg存在一條路徑,那么,A2所用來(lái)擴(kuò)充的點(diǎn)也一定被A1所擴(kuò)充。證明:在證明之前需要說明，在圖搜索過程中,若某一點(diǎn)有幾個(gè)先輩節(jié)點(diǎn),則只保留最小費(fèi)用的那條路,所以A1和A2搜索的結(jié)果是樹而不是圖。下面以A2搜索樹中節(jié)點(diǎn)的深度來(lái)歸納證明。命題6若A2比A1更具有信息,對(duì)任一圖的搜索,只要從S0→19

歸納基礎(chǔ)設(shè)A2擴(kuò)充的點(diǎn)n的深度d=0，即n=S0，顯然A1也擴(kuò)充點(diǎn)n，因?yàn)锳1、A2都要從S0開始。歸納假設(shè)假設(shè)A1擴(kuò)充了A2搜索樹中一切深度d≤k的節(jié)點(diǎn)。歸納證明要證明A2搜索樹中深度d=k+1的任一節(jié)點(diǎn)n也必定為A1所擴(kuò)充。用反證法若A2擴(kuò)充了n，而A1沒有擴(kuò)充n，將導(dǎo)出矛盾。歸納基礎(chǔ)設(shè)A2擴(kuò)充的點(diǎn)n的深度d=0，即n=S0，顯然20

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

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

由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)。由A2算法搜索時(shí)23

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

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

Sgh(n)估計(jì)過低(1(1)

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

另外搜索的費(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)說要權(quán)衡如下三個(gè)因素：(1)路徑費(fèi)用；(2)尋找路徑時(shí)所搜索的節(jié)點(diǎn)數(shù)；(3)計(jì)算f所需的計(jì)算量。另外搜索的費(fèi)用并不完全由搜索節(jié)點(diǎn)數(shù)多少來(lái)確定，若f2(n)27若h(x)滿足一定限制,如單調(diào)性限制，則搜索路徑幾乎就是解路徑，因而大大減小了搜索費(fèi)用。

定義2一個(gè)啟發(fā)式函數(shù)中的h(x)滿足單調(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)用。這個(gè)要求相當(dāng)一個(gè)三角不等式。若h(x)滿足一定限制,如單調(diào)性限制，則搜索路徑幾乎就是解路28命題7估計(jì)函數(shù)若滿足單調(diào)限制，那么A*所擴(kuò)充的任一點(diǎn)(即用來(lái)求過后繼的點(diǎn)）n必在最優(yōu)路上。證明思路：令g*(n）代表從S0→n的最優(yōu)路徑費(fèi)用，所以一般有g(shù)(n）≥g*(n）(2-12）下面再利用單調(diào)限制能夠證明：g(n）≤g*(n）(2-13）聯(lián)立(2-12），(2-13），可得g(n）=g*(n），也就說明了n位于最佳路徑上。命題7估計(jì)函數(shù)若滿足單調(diào)限制，那么A*所擴(kuò)充的任一點(diǎn)(即用293．對(duì)A*算法的評(píng)價(jià)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ì)。A*算法的缺點(diǎn)是：

3．對(duì)A*算法的評(píng)價(jià)30在不僅考慮搜索節(jié)點(diǎn)的多少，而且還要考慮搜索節(jié)點(diǎn)被搜索的次數(shù)的時(shí)候，則當(dāng)h(n）過低估計(jì)h*(n）時(shí)，有時(shí)會(huì)顯出很高的復(fù)雜性。在不僅考慮搜索節(jié)點(diǎn)的多少，而且還要考慮搜索節(jié)點(diǎn)被搜索的次數(shù)的31例題：走迷宮算法假設(shè)某個(gè)精靈從A點(diǎn)走到B點(diǎn)，而A，B點(diǎn)之間隔著半堵墻。如下圖所示，左邊的淺色方塊代表起點(diǎn)A，右邊的淺色方塊代表終點(diǎn)B，正中間的深灰色填充區(qū)域代表墻。求從A點(diǎn)到B點(diǎn)的一條（最短）路徑例題：走迷宮算法32人工智能課件第2章333算法總結(jié)（1）添加起始位置到OpenList中（2）重復(fù)下面的步驟：(2.1).在OpenList中尋找F值最低的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)稱為當(dāng)前位置。(2.2)把當(dāng)前位置交換到CloseList中，即從OpenList中刪除該節(jié)點(diǎn)并添加到CloseList中。(2.3)對(duì)于當(dāng)前位置的8個(gè)鄰域，操作如下：算法總結(jié)34如果該區(qū)域走不通或該區(qū)域已經(jīng)在CloseList中，則忽略該區(qū)域。否則做下面的操作。如果該區(qū)域不在OpenList中，則把該區(qū)域添加到OpenList中，并使該區(qū)域的父指針指向當(dāng)前位置。如果該區(qū)域已經(jīng)在OpenList中，則計(jì)算一下當(dāng)前區(qū)域到該區(qū)域的G累加值。如果這個(gè)G值比原來(lái)該區(qū)域的G值還小，則說明這條路徑很好。如果是這樣，將該區(qū)域的父指針指向當(dāng)前區(qū)域，并重新計(jì)算該區(qū)域的G值和F值。如果OpenList是按F值排序的，則現(xiàn)在需要重新排序。如果該區(qū)域走不通或該區(qū)域已經(jīng)在CloseList中，則忽略該35(2.4)當(dāng)下面任意一個(gè)條件滿足時(shí)，停止搜索。目標(biāo)區(qū)域已經(jīng)被加入到OpenList中，即路徑找到了。沒有找到目標(biāo)區(qū)域，并且OpenList已經(jīng)為空，即沒有可達(dá)路徑。(3)保存路徑。利用父指針從目標(biāo)區(qū)域往回走直到回到起始點(diǎn)。(2.4)當(dāng)下面任意一個(gè)條件滿足時(shí)，停止搜索362.5問題歸約與AO*算法2.5問題歸約與AO*算法37

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

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

一組本原問題的描述。

例2.13符號(hào)積分問題一般說來(lái)，歸約方法求解問題需要三大要素：39分解時(shí)有三種可能:1.

and2.

or3.

and,or都有從初始問題出發(fā),建立子問題以及子問題的子問題,直至把初始問題規(guī)約為一個(gè)本原問題的集合,這就是問題規(guī)約的實(shí)質(zhì)。分解時(shí)有三種可能:402.5.2與/或圖搜索將問題求解歸約為與/或圖的時(shí)，作如下規(guī)定：1．與或圖中始點(diǎn)(根)為原始問題描述;與或圖中對(duì)應(yīng)于本原問題的節(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才可解。

2.5.2與/或圖搜索將問題求解歸約為與/或圖的時(shí)，作如下413．不可解節(jié)點(diǎn)：3.1沒有后繼節(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為不可解。3．不可解節(jié)點(diǎn)：424．與或圖中搜索費(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)。其中ci為n到ni弧的費(fèi)用。4.3若n既有“與”又有“或”弧，則“與”弧算作一個(gè)“或”后繼，再取各or弧后繼中費(fèi)用最小者為n的費(fèi)用。4．與或圖中搜索費(fèi)用的計(jì)算：設(shè)從當(dāng)前節(jié)點(diǎn)n到目標(biāo)集Sg費(fèi)用估432.5.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)代表分解的子問題,子問題的難易程度決定原問題求解的難易程度，所以不再考慮n本身的難易程度。因此當(dāng)決定了某個(gè)路徑時(shí)，要將后繼節(jié)點(diǎn)的估計(jì)值往回傳送。

2.5.3與/或圖搜索的特點(diǎn)

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

表示求了x就可以求y.，求了y就可以求x，兩者都不可能求解。3.與/或圖搜索的限制與/或圖搜索僅對(duì)不含回路的圖進(jìn)行操502.5.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)稱為node。2.5.4與/或圖搜索算法AO*AO*算法：512.2生成node的后繼節(jié)點(diǎn)。若無(wú)后繼節(jié)點(diǎn)，則令h’(node)=Futility,說明該節(jié)點(diǎn)不可解；若有后繼節(jié)點(diǎn)，稱為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)。2.2生成node的后繼節(jié)點(diǎn)。522.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ù)下述過程，直到S為空時(shí)停止。2.3.1從S中挑選一節(jié)點(diǎn),該節(jié)點(diǎn)的后輩點(diǎn)均不在S中(保證每一正在處理的點(diǎn)都在其先輩節(jié)點(diǎn)之前作處理),此節(jié)點(diǎn)稱為current,并從S中刪除;2.3由底向上作評(píng)價(jià)值修正，重新挑選最優(yōu)路徑。532.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中。2.3.2計(jì)算始于current的每條弧的費(fèi)用,即54ABCDstep2.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）ABCDstep2.3.1S={A}55ADEF

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弧。ADEFh’(E)=4562.5.5對(duì)AO*算法的進(jìn)一步觀察

(1)算法中2.3.5步中要將費(fèi)用已改變的某一節(jié)點(diǎn)所有祖先加入S,然后修改祖先的費(fèi)用。例2.17（7）ABCDE(10)(6)

（3）（5）當(dāng)從E往回傳時(shí)，若實(shí)際上走A→B這條路總是不好時(shí)，則從E→B回傳是浪費(fèi)，是無(wú)用的回傳，所以完全回傳至一切祖先的費(fèi)用很大。2.5.5對(duì)AO*算法的進(jìn)一步觀察

(1)算法中2.357若僅沿標(biāo)志往回傳，又可能找不到最優(yōu)解。如下圖所示：CDABCDEFGABEFGH（11）（14）(13)(10)(13)(18)(15)

擴(kuò)展G(11)

(5)(6)(3)(5)(6)

(3)(5)(10)(9)若僅沿標(biāo)志往回傳，又可能找不到最優(yōu)解。如下圖所示：CD58由H→G回傳時(shí),若只沿“→”標(biāo)志往上傳至C，再回至E,則E仍為（6）而實(shí)際上應(yīng)為（11），B仍為（13）而實(shí)際上應(yīng)為（18）。這樣導(dǎo)致A將又選擇A→B這條路，實(shí)際這條路徑比A→C更差。所以順路徑標(biāo)志往上傳遞修正的AO*算法不一定保證能找到最優(yōu)解。由H→G回傳時(shí),若只沿“→”標(biāo)志往上傳至C，再回至E,則59（2）算法沒有考慮子目標(biāo)之間的相互依賴關(guān)系。例2.18美國(guó)總統(tǒng)候選人

美國(guó)出生美國(guó)公民(5)(3)

移民（少數(shù)）(2)ABCD（2）算法沒有考慮子目標(biāo)之間的相互依賴關(guān)系。例2.18602.5.6用AO*算法求解一個(gè)智力難題設(shè)有12個(gè)硬幣，凡輕于或重于真幣者，即為假幣（只有一枚假幣），要設(shè)計(jì)一個(gè)算法來(lái)識(shí)別假幣，并指出它是輕于還是重于真幣，且利用天平的次數(shù)不多于3次。2.5.6用AO*算法求解一個(gè)智力難題設(shè)有12個(gè)硬幣，凡輕611.問題表示將硬幣的重量分為4種類型標(biāo)準(zhǔn)型（Standart）標(biāo)記為S輕標(biāo)型（LightorStandard）標(biāo)記為L(zhǎng)S重標(biāo)型（HeavyorStandard）標(biāo)記為HS輕重標(biāo)準(zhǔn)型（LightorHeavyorStandard）標(biāo)記為L(zhǎng)HS1.問題表示62問題狀態(tài)可以表示一個(gè)五元組：（LHS，LS，HS，S，T）其中前4個(gè)元素表示當(dāng)前這四種類型硬幣的個(gè)數(shù)，T表示所剩稱硬幣的次數(shù)。初始狀態(tài):(12,0,0,0,3)目標(biāo)狀態(tài):(0,1,0,11,0）或（0,0,1,11,0）問題狀態(tài)可以表示一個(gè)五元組：632如何利用AO*算法求解首先考慮如何取硬幣的問題。設(shè)當(dāng)前的狀態(tài)為（lhs，ls，hs，s，t）,用函數(shù)PICKUP([lhs1,ls1,hs1,s1],[lhs2,ls2,hs2,s2])表示本次分別從（lhs,ls,hs,s,t）中取出了[lhs1,ls1,hs1,s1]個(gè)硬幣放在天平的左邊,取出了[lhs2,ls2,hs2,s2]個(gè)硬幣放在天平的右邊。對(duì)于PICKUP應(yīng)默認(rèn)有如下性質(zhì)成立：0<lhs1+ls1+hs1+s1=lhs2+ls2+hs2+s2≤6，即天平兩邊的硬幣數(shù)相等且小于等于6lhs1+lhs2≤lhs∧ls1+ls2≤ls∧hs1+hs2≤hs∧s1+s2≤s,即取出的硬幣數(shù)小于等于相應(yīng)類型原有的硬幣數(shù)。

2如何利用AO*算法求解64然后令PICKUP()等于－1，0，1，分別表示天平左傾、平衡和右傾。這樣，有以下規(guī)則：L規(guī)則：ifPICKUP([lhs1,ls1,hs1,s1],[lhs2,ls2,hs2,s2])=-1∧（lhs,ls,hs,s,t）Then（lhs’,ls’,hs’,s’,t-1） 其中：s’＝s+ls-ls2+hs-hs1+lhs-(lhs1+lhs2);ls’=ls2+lhs2;hs’=lhs1+hs1;lhs’=0

這四個(gè)公式的含義分別是：若天平左傾，則在左天平的狀態(tài)為L(zhǎng)S的硬幣，在右天平的狀態(tài)為HS的硬幣和未放在天平上的硬幣都是標(biāo)準(zhǔn)的，即hs2+hs1+(lhs-lhs1-lhs2)+(ls-ls1-ls2)+(hs-hs1-hs2)個(gè)硬幣的狀態(tài)都改變?yōu)闃?biāo)準(zhǔn)型；右天平原有的ls2個(gè)輕標(biāo)準(zhǔn)型的硬幣仍然為輕標(biāo)準(zhǔn)型，右天平原有的lhs2個(gè)輕重標(biāo)準(zhǔn)型硬幣改變?yōu)檩p標(biāo)準(zhǔn)型；左天平原有的hs1個(gè)重標(biāo)準(zhǔn)型的硬幣仍然為重標(biāo)準(zhǔn)型，左天平原有的lhs1個(gè)輕重標(biāo)準(zhǔn)型硬幣改變?yōu)橹貥?biāo)準(zhǔn)型；只要不平衡，就不存在LHS型的硬幣，所有的硬幣都可以確定為L(zhǎng)S，HS或S型，即lhs’=0。

然后令PICKUP()等于－1，0，1，分別表示天平左傾、平65B規(guī)則：ifPICKUP([lhs1,ls1,hs1,s1],[lhs2,ls2,hs2,s2])=0∧（lhs,ls,hs,s,t）Then（lhs’,ls’,hs’,s’,t-1） 其中：s’＝s+ls1+ls2+hs1+hs2+lhs1+lhs2;ls’=ls-ls1-ls2;hs’=hs-hs1-hs2;lhs’=lhs-lhs1-lhs2

這四個(gè)公式的含義分別是：若天平平衡，則所有在天平上的硬幣都是標(biāo)準(zhǔn)型，即ls1+ls2+hs1+hs2+lhs1+lhs2個(gè)硬幣的狀態(tài)都改變?yōu)闃?biāo)準(zhǔn)型；左、右天平原有的輕標(biāo)準(zhǔn)型的硬幣改變?yōu)闃?biāo)準(zhǔn)型，所以從ls中減去ls1和ls2；左右天平原有的重標(biāo)準(zhǔn)型硬幣改變?yōu)闃?biāo)準(zhǔn)型，所以也要從hs中減去hs1和hs2；在平衡情況下，LHS型的硬幣要減去左右天平原有的輕重標(biāo)準(zhǔn)型的硬幣，即lhs’=lhs-hs1-lhs2。

B規(guī)則：ifPICKUP([lhs1,ls1,hs1,s166R規(guī)則：ifPICKUP([lhs1,ls1,hs1,s1],[lhs2,ls2,hs2,s2])=1∧（lhs,ls,hs,s,t）Then（lhs’,ls’,hs’,s’,t-1） 其中：s’＝s+ls-ls1+hs-hs2+lhs-(lhs1+lhs2);ls’=ls1+lhs1;hs’=lhs2+hs2;lhs’=0

這四個(gè)公式的含義于L規(guī)則的含義類似：若天平右傾，則在左天平的狀態(tài)為HS的硬幣和在右天平的狀態(tài)為L(zhǎng)S的硬幣以及未放在天平上的硬幣都是標(biāo)準(zhǔn)的，即hs1+hs2+(lhs-lhs1-lhs2)+(ls-ls1-ls2)+(hs-hs1-hs2)個(gè)硬幣的狀態(tài)都改變?yōu)闃?biāo)準(zhǔn)型；左天平原有的ls1個(gè)輕標(biāo)準(zhǔn)型的硬幣仍然為輕標(biāo)準(zhǔn)型，左天平原有的lhs1個(gè)輕重標(biāo)準(zhǔn)型硬幣改變?yōu)檩p標(biāo)準(zhǔn)型；右天平原有的hs2個(gè)重標(biāo)準(zhǔn)型的硬幣仍然為重標(biāo)準(zhǔn)型，右天平原有的lhs2個(gè)輕重標(biāo)準(zhǔn)型硬幣改變?yōu)橹貥?biāo)準(zhǔn)型；因?yàn)椴黄胶猓琹hs’=0。

R規(guī)則：ifPICKUP([lhs1,ls1,hs1,s1673．如何在問題空間中搜索

利用AO*算法對(duì)該問題搜索時(shí)，用PICKUP表示一種選取方法，不同的選取方法之間是“或”的關(guān)系，當(dāng)選定一種PICKUP后，就必須考慮它的值為-1,0,1的情況下，下層的節(jié)點(diǎn)都可解，則三種情況之間的關(guān)系為“與”的關(guān)系。說明該問題的搜索圖是與/或圖，我們采取的搜索算法是AO*算法。

3．如何在問題空間中搜索68定義該算法的評(píng)價(jià)函數(shù)為：h((lhs,ls,hs,s,t))=lhs+ls+hs-1顯然有h((0,1,0,11,0))=0和h((0,0,1,11,0))=0即h(Sg1)=h(Sg2)=0由于問題的本原問題對(duì)應(yīng)的節(jié)點(diǎn)是可解節(jié)點(diǎn)，因此Sg1和Sg2為可解節(jié)點(diǎn)。不可解節(jié)點(diǎn)可以定義為：如果節(jié)點(diǎn)n=(lhs,ls,hs,s,t)中t=0,且(lhs,ls,hs,s)不屬于{(0,1,0,11),(0,0,1,11,0)}，則n為不可解節(jié)點(diǎn)。

定義該算法的評(píng)價(jià)函數(shù)為：69人工智能課件第2章3704.問題的推廣從上述計(jì)算過程中觀察到稱硬幣的次數(shù)與硬幣枚數(shù)之間的關(guān)系有：稱3次可在（33－3）/2=12個(gè)硬幣中找出假幣；稱4次可在（34－3）/2=39個(gè)硬幣中找出假幣；稱5次可在（35－3）/2=120個(gè)硬幣中找出假幣。定理：使用天平k次可從（3k－3）/2個(gè)硬幣中找出假幣。

證明略

4.問題的推廣712.6約束滿足法2.6.1約束滿足問題AI中許多問題(比如視覺問題)可以歸納為約束滿足問題：目標(biāo)是找出某個(gè)狀態(tài)，它能滿足一個(gè)給定的約束集中的一切約束條件。約束滿足問題并沒有引入新的搜索方法，還是使用已討論過的方法求解，但搜索空間有兩個(gè)：（1）問題狀態(tài)空間；（2）隨狀態(tài)空間變化而變化的約束空間。而且在兩個(gè)空間中的搜索并行進(jìn)行，并可以利用的搜索規(guī)則和啟發(fā)式函數(shù)涉及約束空間的當(dāng)前位置的信息。

2.6約束滿足法2.6.1約束滿足問題722.6.2約束滿足問題求解約束滿足問題求解的一般過程：（1）從搜索圖中挑選一個(gè)未求后繼的節(jié)點(diǎn)；（2）將約束推理規(guī)則作用到新選節(jié)點(diǎn)，從而產(chǎn)生新的約束；（3）若約束集含有矛盾，則報(bào)告此路不通，從而結(jié)束此分支的搜索；（4）若約束已完全滿足且到達(dá)一個(gè)完全解，則報(bào)告成功；（5）若約束即未找到矛盾，又未達(dá)到完全解，則產(chǎn)生新的與當(dāng)前約束集相容的點(diǎn)并插入圖中。

2.6.2約束滿足問題求解73例題：密碼算術(shù)問題SEND＋MORE——————MONEY

要求：（1）每個(gè)字母賦一個(gè)十進(jìn)制數(shù)。（2）代入后使坐標(biāo)加法成立。

例題：密碼算術(shù)問題74Theend!Theend!752.4.2A算法與A*算法

1．A算法與A*算法定義或圖通用算法在采用如下形式的估計(jì)函數(shù)時(shí),稱為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ì)值。2.4.2A算法與A*算法1．A算法與A*算法定義76例2.10在地圖上尋找城市A至B的最短路徑，雙虛線表示ni與Sg的直線距離(可以從地圖上量出）,虛線表示ni與Sg的路徑，則實(shí)線表示的路徑為g(n），虛線表示的路徑為h(n）。A=S0B=Sgn1n2n3n4n5例2.10在地圖上尋找城市A至B的最短路徑，雙虛線表示ni772.4.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到點(diǎn)n的最小費(fèi)用,h*(n)為n到Sg的實(shí)際最小費(fèi)用。在上例中，雙虛線表示的路徑就可以作為h*(n），顯然有g(shù)(n）≥g*(n）。h(n）h*(n）2.4.2A算法與A*算法若規(guī)定h(n)≥0，并且78

若令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），就稱為這種A算法為A*算法。若令h(n）≡0，則A算法相當(dāng)于廣度優(yōu)先，因?yàn)樯弦粚庸?jié)點(diǎn)79A*算法設(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*A*算法805.若n∈Sg，則成功退出；6.產(chǎn)生n的一切后繼，將后繼中不是n的先輩點(diǎn)的一切點(diǎn)構(gòu)成集合M7.對(duì)M中的元素P，分別作兩類處理：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。5.若n∈Sg，則成功退出；812．A*算法的性質(zhì)A*算法與一般的最佳優(yōu)先比較，有其特有的性質(zhì)：如果問題有解，即S0→Sg存在一條路徑，A*算法一定能找到最優(yōu)解。這一性質(zhì)稱為可采納性(admissibility）。（p35例2.11)2．A*算法的性質(zhì)82下面要證明A*算法的可采納性，證明分兩步：(1）證若問題有解，A*一定終止，由如下命題1-3證出。(2）證若問題有解，A*終止時(shí)一定找到最優(yōu)解，由如下命題4證出。下面要證明A*算法的可采納性，證明分兩步：83命題1對(duì)有限圖而言，A*一定終止。證：考察A*算法，算法終止只有二處：第一處在第5步，找到解時(shí)成功終止。第二處在第3步，open為空時(shí)失敗退出。算法每次循環(huán)從open上去掉一個(gè)點(diǎn)，而有限圖的open表只有有限個(gè)節(jié)點(diǎn)加入，所以找不到解也會(huì)因?yàn)閛pen表為空而停止命題1對(duì)有限圖而言，A*一定終止。84命題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）命題2若A*不終止，則搜索圖中open表上的點(diǎn)的f值將會(huì)85命題3若問題有解，在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)過n到Sg的最優(yōu)路的實(shí)際最小費(fèi)用。命題3若問題有解，在A*終止前，open表上必存在一點(diǎn)n86證：令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*算法將終止于成功退出。證：令S0=n0，n1，n2，…，nk=Sg為一條最優(yōu)路徑，87由定義有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）成立。由定義有88推論1若問題有解，A*算法一定終止。因?yàn)槿鬉*算法不終止，則命題2的(2-1）與命題3的(2-1）同時(shí)成立，則產(chǎn)生矛盾。推論1若問題有解，A*算法一定終止。89命題4若問題有解，A*算法終止時(shí)一定找到最優(yōu)解,即A*算法是可采納的。證：A*終止只有兩種情況。(1)

在第3步,因open為空而失敗退出但由命題3可知：A*終止前，open表上必存在一點(diǎn)n’，滿足f(n’）≤f*(S0）即open表不會(huì)空，所以，不會(huì)終止于第3步。命題4若問題有解，A*算法終止時(shí)一定找到最優(yōu)解,即A*算90推論2凡open表中任一點(diǎn)n，若f(n）<f*(S0），最終都將被A*算法挑選出來(lái)求后繼，也即被挑選出來(lái)進(jìn)行擴(kuò)充。證：用反證法，設(shè)f(n）<f*(S0）且n沒有被選出來(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è)矛盾。推論2凡open表中任一點(diǎn)n，若f(n）<f*(S0），91命題5凡A*算法挑選出來(lái)求后繼的點(diǎn)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）命題5凡A*算法挑選出來(lái)求后繼的點(diǎn)n必定滿足:92定義1若A1,A2均是A*算法,A1采用f1(x)=g1(x)+h1(x)作為估計(jì)函數(shù)，A2采用f2=g2(x)+h2(x)作為估計(jì)函數(shù)。h1(x),h2(x)都滿足:hi(x)≤hi*(x),i=1,2(2-4)如果h1(x)<h2(x)，則稱A2比A1更具有信息(moreinformed)。定義1若A1,A2均是A*算法,A1采用f1(x)=g193命題6若A2比A1更具有信息,對(duì)任一圖的搜索,只要從S0→Sg存在一條路徑,那么,A2所用來(lái)擴(kuò)充的點(diǎn)也一定被A1所擴(kuò)充。證明:在證明之前需要說明，在圖搜索過程中,若某一點(diǎn)有幾個(gè)先輩節(jié)點(diǎn),則只保留最小費(fèi)用的那條路,所以A1和A2搜索的結(jié)果是樹而不是圖。下面以A2搜索樹中節(jié)點(diǎn)的深度來(lái)歸納證明。命題6若A2比A1更具有信息,對(duì)任一圖的搜索,只要從S0→94

歸納基礎(chǔ)設(shè)A2擴(kuò)充的點(diǎn)n的深度d=0，即n=S0，顯然A1也擴(kuò)充點(diǎn)n，因?yàn)锳1、A2都要從S0開始。歸納假設(shè)假設(shè)A1擴(kuò)充了A2搜索樹中一切深度d≤k的節(jié)點(diǎn)。歸納證明要證明A2搜索樹中深度d=k+1的任一節(jié)點(diǎn)n也必定為A1所擴(kuò)充。用反證法若A2擴(kuò)充了n，而A1沒有擴(kuò)充n，將導(dǎo)出矛盾。歸納基礎(chǔ)設(shè)A2擴(kuò)充的點(diǎn)n的深度d=0，即n=S0，顯然95

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

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

由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)。由A2算法搜索時(shí)98

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

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

Sgh(n)估計(jì)過低(1(1)

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

另外搜索的費(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)說要權(quán)衡如下三個(gè)因素：(1)路徑費(fèi)用；(2)尋找路徑時(shí)所搜索的節(jié)點(diǎn)數(shù)；(3)計(jì)算f所需的計(jì)算量。另外搜索的費(fèi)用并不完全由搜索節(jié)點(diǎn)數(shù)多少來(lái)確定，若f2(n)102若h(x)滿足一定限制,如單調(diào)性限制，則搜索路徑幾乎就是解路徑，因而大大減小了搜索費(fèi)用。

定義2一個(gè)啟發(fā)式函數(shù)中的h(x)滿足單調(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)用。這個(gè)要求相當(dāng)一個(gè)三角不等式。若h(x)滿足一定限制,如單調(diào)性限制，則搜索路徑幾乎就是解路103命題7估計(jì)函數(shù)若滿足單調(diào)限制，那么A*所擴(kuò)充的任一點(diǎn)(即用來(lái)求過后繼的點(diǎn)）n必在最優(yōu)路上。證明思路：令g*(n）代表從S0→n的最優(yōu)路徑費(fèi)用，所以一般有g(shù)(n）≥g*(n）(2-12）下面再利用單調(diào)限制能夠證明：g(n）≤g*(n）(2-13）聯(lián)立(2-12），(2-13），可得g(n）=g*(n），也就說明了n位于最佳路徑上。命題7估計(jì)函數(shù)若滿足單調(diào)限制，那么A*所擴(kuò)充的任一點(diǎn)(即用1043．對(duì)A*算法的評(píng)價(jià)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ì)。A*算法的缺點(diǎn)是：

3．對(duì)A*算法的評(píng)價(jià)105在不僅考慮搜索節(jié)點(diǎn)的多少，而且還要考慮搜索節(jié)點(diǎn)被搜索的次數(shù)的時(shí)候，則當(dāng)h(n）過低估計(jì)h*(n）時(shí)，有時(shí)會(huì)顯出很高的復(fù)雜性。在不僅考慮搜索節(jié)點(diǎn)的多少，而且還要考慮搜索節(jié)點(diǎn)被搜索的次數(shù)的106例題：走迷宮算法假設(shè)某個(gè)精靈從A點(diǎn)走到B點(diǎn)，而A，B點(diǎn)之間隔著半堵墻。如下圖所示，左邊的淺色方塊代表起點(diǎn)A，右邊的淺色方塊代表終點(diǎn)B，正中間的深灰色填充區(qū)域代表墻。求從A點(diǎn)到B點(diǎn)的一條（最短）路徑例題：走迷宮算法107人工智能課件第2章3108算法總結(jié)（1）添加起始位置到OpenList中（2）重復(fù)下面的步驟：(2.1).在OpenList中尋找F值最低的節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)稱為當(dāng)前位置。(2.2)把當(dāng)前位置交換到CloseList中，即從OpenList中刪除該節(jié)點(diǎn)并添加到CloseList中。(2.3)對(duì)于當(dāng)前位置的8個(gè)鄰域，操作如下：算法總結(jié)109如果該區(qū)域走不通或該區(qū)域已經(jīng)在CloseList中，則忽略該區(qū)域。否則做下面的操作。如果該區(qū)域不在OpenList中，則把該區(qū)域添加到OpenList中，并使該區(qū)域的父指針指向當(dāng)前位置。如果該區(qū)域已經(jīng)在OpenList中，則計(jì)算一下當(dāng)前區(qū)域到該區(qū)域的G累加值。如果這個(gè)G值比原來(lái)該區(qū)域的G值還小，則說明這條路徑很好。如果是這樣，將該區(qū)域的父指針指向當(dāng)前區(qū)域，并重新計(jì)算該區(qū)域的G值和F值。如果OpenList是按F值排序的，則現(xiàn)在需要重新排序。如果該區(qū)域走不通或該區(qū)域已經(jīng)在CloseList中，則忽略該110(2.4)當(dāng)下面任意一個(gè)條件滿足時(shí)，停止搜索。目標(biāo)區(qū)域已經(jīng)被加入到OpenList中，即路徑找到了。沒有找到目標(biāo)區(qū)域，并且OpenList已經(jīng)為空，即沒有可達(dá)路徑。(3)保存路徑。利用父指針從目標(biāo)區(qū)域往回走直到回到起始點(diǎn)。(2.4)當(dāng)下面任意一個(gè)條件滿足時(shí)，停止搜索1112.5問題歸約與AO*算法2.5問題歸約與AO*算法112

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

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

一組本原問題的描述。

例2.13符號(hào)積分問題一般說來(lái)，歸約方法求解問題需要三大要素：114分解時(shí)有三種可能:1.

and2.

or3.

and,or都有從初始問題出發(fā),建立子問題以及子問題的子問題,直至把初始問題規(guī)約為一個(gè)本原問題的集合,這就是問題規(guī)約的實(shí)質(zhì)。分解時(shí)有三種可能:1152.5.2與/或圖搜索將問題求解歸約為與/或圖的時(shí)，作如下規(guī)定：1．與或圖中始點(diǎn)(根)為原始問題描述;與或圖中對(duì)應(yīng)于本原問題的節(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才可解。

2.5.2與/或圖搜索將問題求解歸約為與/或圖的時(shí)，作如下1163．不可解節(jié)點(diǎn)：3.1沒有后繼節(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為不可解。3．不可解節(jié)點(diǎn)：1174．與或圖中搜索費(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)。其中ci為n到ni弧的費(fèi)用。4.3若n既有“與”又有“或”弧，則“與”弧算作一個(gè)“或”后繼，再取各or弧后繼中費(fèi)用最小者為n的費(fèi)用。4．與或圖中搜索費(fèi)用的計(jì)算：設(shè)從當(dāng)前節(jié)點(diǎn)n到目標(biāo)集Sg費(fèi)用估1182.5.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)代表分解的子問題,子問題的難易程度決定原問題求解的難易程度，所以不再考慮n本身的難易程度。因此當(dāng)決定了某個(gè)路徑時(shí)，要將后繼節(jié)點(diǎn)的估計(jì)值往回傳送。

2.5.3與/或圖搜索的特點(diǎn)

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

表示求了x就可以求y.，求了y就可以求x，兩者都不可能求解。3.與/或圖搜索的限制與/或圖搜索僅對(duì)不含回路的圖進(jìn)行操1252.5.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)稱為node。2.5.4與/或圖搜索算法AO*AO*算法：1262.2生成node的后繼節(jié)點(diǎn)。若無(wú)后繼節(jié)點(diǎn)，則令h’(node)=Futility,說明該節(jié)點(diǎn)不可解；若有后繼節(jié)點(diǎn)，稱為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)。2.2生成node的后繼節(jié)點(diǎn)。1272.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ù)下述過程，直到S為空時(shí)停止。2.3.1從S中挑選一節(jié)點(diǎn),該節(jié)點(diǎn)的后輩點(diǎn)均不在S中(保證每一正在處理的點(diǎn)都在其先輩節(jié)點(diǎn)之前作處理),此節(jié)點(diǎn)稱為current,并從S中刪除;2.3由底向上作評(píng)價(jià)值修正，重新挑選最優(yōu)路徑。1282.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中。2.3.2計(jì)算始于current的每條弧的費(fèi)用,即129ABCDstep2.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）ABCDstep2.3.1S={A}130ADEF

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弧。ADEFh’(E)=41312.5.5對(duì)AO*算法的進(jìn)一步觀察

(1)算法中2.3.5步中要將費(fèi)用已改變的某一節(jié)點(diǎn)所有祖先加入S,然后修改祖先的費(fèi)用。例2.17（7）ABCDE(10)