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

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

Open表的尾部，算法相當(dāng)于廣度有限；

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

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

下面我們給出衍生出的這些算法的實(shí)際跟蹤步驟在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。11.產(chǎn)生僅由S0組成的Open表，即Open＝(A)；21.產(chǎn)生一個(gè)空的Closed表；31.Open＝(A)，不為空；41.在Open表取出第一個(gè)結(jié)點(diǎn)A稱為n，放n到Closed表中，此時(shí)Open＝()，Closed＝(A)51.n=A，不是目標(biāo)；61.產(chǎn)生A的后繼B和C，此時(shí)M=(B，C)71.對(duì)M中的元素B、C，它們不在Open表中，也不在Closed表中，加入到Open表，此時(shí)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表取出第一個(gè)結(jié)點(diǎn)B，放到Closed表中，并從Open表中去掉B，此時(shí)Open＝(C)，Closed＝(A，B)52.n=B，不是目標(biāo)；62.產(chǎn)生B的后繼D、E，此時(shí)M=(D，E)72.對(duì)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)生一個(gè)空的Closed表；31.Open＝(A)，不為空；41.在Open表取出第一個(gè)結(jié)點(diǎn)A稱為n，放n到Closed表中，此時(shí)Open＝()，Closed＝(A)在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。3.1或圖搜索策略在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。3.1或圖搜索策略在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。在或圖通用搜索算法的第4步，每次取出Open表的第一個(gè)節(jié)點(diǎn)，然后在7.1步中，若生成的后繼節(jié)點(diǎn)放于Open表的尾部。下面我們對(duì)上述第（1）種情況進(jìn)行算法步驟的跟蹤。例3.2假定下圖的搜索目標(biāo)是圖中的G節(jié)點(diǎn)，跟蹤廣度優(yōu)先搜索的搜索過程。3.1或圖搜索策略說明:(1)

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

S0

Path1Path2

nm

后擴(kuò)展p先擴(kuò)展

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

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

a．若Path1的代價(jià)<Path2的代價(jià)時(shí)，當(dāng)前路徑較好，要修改p的指針，使其指向n，即標(biāo)出搜索之后的最好路徑；

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

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

S0

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

kn

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

即過去對(duì)S0→P而言的最優(yōu)路徑為S0→m→p，現(xiàn)在要從S0→m→p與S0→n→p中求最優(yōu)路徑。同理，若過去對(duì)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表上按某一原則選出一個(gè)結(jié)點(diǎn)”定義為：按啟發(fā)式函數(shù)f的值的從小到大排列，然后取出第一個(gè)節(jié)點(diǎn)，并采用如下形式的估計(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ì)值。3.1.2A算法與A*算法進(jìn)一步，若規(guī)定h(n)≥0，并且定義：

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

g(n）≥g*(n）

h(n）

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

在f(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）就稱為這種A算法為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*5.若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。2．A*算法的性質(zhì)

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

例3.4).野人傳教士問題

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

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

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

一組本原問題的描述。

例3.6符號(hào)積分問題分解時(shí)有三種可能:1.

and2.

or3.

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

3.2.2“與/或圖”的構(gòu)造方法將問題求解歸約為與/或圖的時(shí)，作如下規(guī)定：1．根節(jié)點(diǎ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才可解。3．不可解節(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為不可解。

作者朱福喜朱三元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)用。3.2.3與/或圖搜索的過程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ì)值往回傳送。例3.7圖3-9為一個(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)前最佳路徑。

最后求得的耗費(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)路。2.與/或圖搜索的限制與/或圖搜索僅對(duì)不含回路的圖進(jìn)行操作。例如：

x

y

表示求了x就可以求y.，求了y就可以求x，兩者都不可能求解。3.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)稱為node。2.2生成node的后繼節(jié)點(diǎn)。若無后繼節(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.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.2計(jì)算始于current的每條弧的費(fèi)用,即每條弧本身的費(fèi)用加上弧末端節(jié)點(diǎn)h’的值(注意區(qū)分與,或弧的計(jì)算方法),并從中選出極小費(fèi)用的弧作為