人工智能入門課件第3章 圖搜索策略

第3章圖搜索策略同學們，大家好，這節(jié)課我們繼續(xù)學習圖通用搜索算法或圖通用搜索算法具有通用性，可以演變?yōu)槎喾N搜索策略。在算法的第4步，如果約定每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于：

Open表的尾部，算法相當于廣度有限；

Open表的首部，算法相當于深度優(yōu)先；

根據(jù)啟發(fā)式函數(shù)f的估計值確定最佳者，放于Open表的首部，算法相當于最佳優(yōu)先。

下面我們給出衍生出的這些算法的實際跟蹤步驟在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。11.產(chǎn)生僅由S0組成的Open表，即Open＝(A)；21.產(chǎn)生一個空的Closed表；31.Open＝(A)，不為空；41.在Open表取出第一個結(jié)點A稱為n，放n到Closed表中，此時Open＝()，Closed＝(A)51.n=A，不是目標；61.產(chǎn)生A的后繼B和C，此時M=(B，C)71.對M中的元素B、C，它們不在Open表中，也不在Closed表中，加入到Open表，此時Open＝(B，C)，再將反向邊(B，A)、(C，A)加入到Tree中，Tree={(B，A),(C，A)}。81.轉(zhuǎn)3。第一輪開始和結(jié)束后，算法搜索的結(jié)果為：第二輪搜索為：32.Open＝(B，C)，不為空；42.在Open表取出第一個結(jié)點B，放到Closed表中，并從Open表中去掉B，此時Open＝(C)，Closed＝(A，B)52.n=B，不是目標；62.產(chǎn)生B的后繼D、E，此時M=(D，E)72.對M中的元素D、E，它們不在Open表中也不在Closed表中，加入到Open表，Open＝(C，D，E)，反向邊(D,B),(E，B)加入到Tree中，Tree={(B，A),(C，A),(D,B),(E，B)}。82.轉(zhuǎn)3。11.產(chǎn)生僅由S0組成的Open表，即Open＝(A)；21.產(chǎn)生一個空的Closed表；31.Open＝(A)，不為空；41.在Open表取出第一個結(jié)點A稱為n，放n到Closed表中，此時Open＝()，Closed＝(A)在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。3.1或圖搜索策略在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。3.1或圖搜索策略在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個節(jié)點，然后在7.1步中，若生成的后繼節(jié)點放于Open表的尾部。下面我們對上述第（1）種情況進行算法步驟的跟蹤。例3.2假定下圖的搜索目標是圖中的G節(jié)點，跟蹤廣度優(yōu)先搜索的搜索過程。3.1或圖搜索策略說明:(1)

若P∈M且在open表中，這說明P在n之前已是某一結(jié)點m的后繼,但本身尚未被考察(未生成P的后繼)，

S0

Path1Path2

nm

后擴展p先擴展

P在n之前已是某一結(jié)點m的后繼

作者朱福喜朱三元3.1或圖搜索策略這說明從S0→p至少有兩條路徑，這時有兩種情況：

a．若Path1的代價<Path2的代價時，當前路徑較好，要修改p的指針，使其指向n，即標出搜索之后的最好路徑；

b．若Path1的代價≥Path2的代價時，原路徑較好，不改變p的指針。3.1或圖搜索策略(2）若p∈M且在closed表中，這說明:a.p在n之前已是某一節(jié)點m的后繼，所以需要作如(1)同樣的處理，如下圖右部。

b．p在closed表中，說明p的后繼也在n之前已生成，我們稱為Ps，那么對Ps同樣可能由于n→p這一路徑的加入又必須比較多條路徑代價后而取代價小的一條，如下圖左部。3.1或圖搜索策略

S0

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

kn

PsmP圖3-2p∈M且在closed表中時不同的最優(yōu)路徑3.1或圖搜索策略

即過去對S0→P而言的最優(yōu)路徑為S0→m→p，現(xiàn)在要從S0→m→p與S0→n→p中求最優(yōu)路徑。同理，若過去對S0→Ps而言的最優(yōu)路徑為S0→k→Ps,現(xiàn)在要從｛S0→p→Ps,S0→k→Ps｝中選最優(yōu)路徑。3.1.2A算法與A*算法

1．A算法與A*算法定義或圖通用算法第（4）步“在open表上按某一原則選出一個結(jié)點”定義為：按啟發(fā)式函數(shù)f的值的從小到大排列，然后取出第一個節(jié)點，并采用如下形式的估計函數(shù)時,稱為A算法。

f(n)=g(n)+h(n)其中g(shù)(n)表示從S0到n點費用的估計，因為n為當前節(jié)點，搜索已達到n點，所以g(n)可計算出。h(n)表示從n到Sg接近程度的估計，因為尚未找到解路徑，所以h(n)僅僅是估計值。3.1.2A算法與A*算法進一步，若規(guī)定h(n)≥0，并且定義：

f*(n)=g*(n)+h*(n)表示S0經(jīng)點n到Sg最優(yōu)路徑的費用，或?qū)嶋H最小費用。其中g(shù)*(n)為S0到n的最小費用,h*(n)為n到Sg的實際最小費用。在下例中，雙虛線表示的路徑就可以作為h(n），顯然有：

g(n）≥g*(n）

h(n）

h*(n）例：在地圖上尋找城市A至B的最短路徑，雙虛線表示ni與Sg的直線距離(可以從地圖上量出）,虛線表示ni與Sg的可選擇的路徑，實線表示從S0出發(fā)已經(jīng)走過的路徑為g(n);則實線表示的路徑為g(n),粗實線表示g*(n)，虛線和雙虛線表示的路徑為h(n)。h*(n)?

在f(n)中若令：h(n）≡0，則A算法相當于廣度優(yōu)先，因為上一層節(jié)點的搜索費用一般比下一層的小。

g(n）≡h(n）≡0，則相當于隨機算法。

g(n）≡0，則相當于最佳優(yōu)先算法。特別是當要求：

h(n）≤h*(n）就稱為這種A算法為A*算法。

A*算法

設(shè)S0：初態(tài),Sg：目標狀態(tài)1.open={S0}；2.closed={}；3.如果open={}，失敗退出；4.在open表上取出f最小的結(jié)點n，n放到closed表中；其中：

f(n)=g(n)+h(n)h<=h*5.若n∈Sg，則成功退出；6.產(chǎn)生n的一切后繼，將后繼中不是n的先輩點的一切點構(gòu)成集合M7.對M中的元素P，分別作兩類處理：

7.1若P∈G，則P對P進行估計加入open表，記入G和Tree。

7.2P∈G，則決定更改Tree中P到n的指針并且更改P的子節(jié)點n的指針和費用。8.轉(zhuǎn)3。2．A*算法的性質(zhì)

A*算法與一般的最佳優(yōu)先比較，有其特有的性質(zhì)：如果問題有解，即S0→Sg存在一條路徑，A*算法一定能找到最優(yōu)解。這一性質(zhì)稱為可采納性(admissibility）。（

例3.4).野人傳教士問題

作者朱福喜朱三元3.2與/或圖搜索

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

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

一組本原問題的描述。

例3.6符號積分問題分解時有三種可能:1.

and2.

or3.

and,or都有從初始問題出發(fā),建立子問題以及子問題的子問題,直至把初始問題規(guī)約為一個本原問題的集合,這就是問題規(guī)約的實質(zhì)。

3.2.2“與/或圖”的構(gòu)造方法將問題求解歸約為與/或圖的時，作如下規(guī)定：1．根節(jié)點為原始問題描述;

本原問題的節(jié)點為葉節(jié)點。2．可解節(jié)點為：

2.1終葉節(jié)點是可解節(jié)點；

2.2若n為一非終葉節(jié)點，且含有“或”后繼節(jié)點，則只有當后繼節(jié)點中至少有一個是可解節(jié)點時，n才可解；

2.3若n為非終葉節(jié)點，且含“與”后繼節(jié)點，則只有當后繼節(jié)點全部可解時，n才可解。3．不可解節(jié)點

3.1沒有后繼節(jié)點的非終葉節(jié)點為不可解；

3.2若n為一非葉節(jié)點含有“或”后繼節(jié)點，則僅當全部后繼節(jié)點為不可解時，n不可解。

3.3若n為一非葉節(jié)點含有“與”后繼節(jié)點，則只要有一個后繼節(jié)點為不可解時，n為不可解。

作者朱福喜朱三元4．圖中搜索費用的計算設(shè)從當前節(jié)點n到目標集Sg費用估計為h(n).4.1若n∈Sg,則h(n)=0;4.2若n有一組由“與”弧連接的后繼節(jié)點{n1,n2,…ni}則:h(n)=c1+c2…+ci+…+h(n1)+h(n2)+…+h(ni)4.3若n既有“與”又有“或”弧，則“與”弧算作一個“或”后繼，再取各or弧后繼中費用最小者為n的費用。3.2.3與/或圖搜索的過程1．與/或圖搜索搜索費用的估計

對與/或圖則不同，其費用計算的規(guī)則是：

n未生成后繼節(jié)點時，費用由n本身決定;

n已生成后繼節(jié)點時，費用由n的后繼節(jié)點的費用決定。因為后繼節(jié)點代表分解的子問題,子問題的難易程度決定原問題求解的難易程度，所以不再考慮n本身的難易程度。因此當決定了某個路徑時，要將后繼節(jié)點的估計值往回傳送。例3.7圖3-9為一個與/或圖的搜索過程。第一步，A是唯一節(jié)點；第二步，擴展A后，得到節(jié)點B,C和D,因為B，C的耗費為9，D的耗費為6，所以把列D的弧標志為出自A最有希望的弧；第三步，選擇對D的擴展，得到E和F的與弧，其耗費估計值為10。此時回退一步后，發(fā)現(xiàn)與弧BC比D更好，所以將弧BC標志為目前最佳路徑；第四步，在擴展B后,再回傳值發(fā)現(xiàn)弧BC的耗費為12（6+4+2），所以D再次成為當前最佳路徑。

最后求得的耗費為:f(A)=min(12,4+4+2+1)=11。以上搜索過程由兩大步組成：（1)自頂向下，沿當前最優(yōu)路產(chǎn)生后繼節(jié)點。（2）由底向下，作估計值修正，再重新選擇最優(yōu)路。2.與/或圖搜索的限制與/或圖搜索僅對不含回路的圖進行操作。例如：

x

y

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

AO*算法：1.令G=Init,計算h’(Init)。2.在Init標志solved之前或h’(Init)變成大于Futility之前，執(zhí)行以下步驟：

2.1沿始于Init的已帶標志的弧，選出當前沿標志路上未擴展的節(jié)點之一擴展（即求后繼節(jié)點），此節(jié)點稱為node。2.2生成node的后繼節(jié)點。若無后繼節(jié)點，則令h’(node)=Futility,說明該節(jié)點不可解；若有后繼節(jié)點，稱為successor,對每個不是node祖先的后繼節(jié)點（避免回路），執(zhí)行下述步驟：

2.2.1將successor加入G。

2.2.2若successor∈Sg,則標志successor為solved，且令h’(successor)=0。

2.2.3若successor∈Sg,則求h’(successor)

2.3由底向上作評價值修正，重新挑選最優(yōu)路徑。

//令S為一節(jié)點集。

//

S＝｛已標志為solved的點，或h’值已//改變,需回傳至其先輩節(jié)點的節(jié)點｝令S初值＝｛node｝,重復下述過程，直到S為空時停止。

2.3.1從S中挑選一節(jié)點,該節(jié)點的后輩點均不在S中(保證每一正在處理的點都在其先輩節(jié)點之前作處理),此節(jié)點稱為current,并從S中刪除;

2.3.2計算始于current的每條弧的費用,即每條弧本身的費用加上弧末端節(jié)點h’的值(注意區(qū)分與,或弧的計算方法),并從中選出極小費用的弧作為