《搜索與或圖搜索》PPT課件

《《搜索與或圖搜索》PPT課件》由會(huì)員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫(kù)。

1、第四章與或圖搜索內(nèi)容4.0與或樹表示4.1與/或樹的一般搜索4.2與/或樹的廣度優(yōu)先搜索4.3與/或樹的深度優(yōu)先搜索4.4與／或樹的啟發(fā)式搜索4.5博弈樹的啟發(fā)式搜索與或圖搜索24.0與或樹表示不同于狀態(tài)空間方法的另外一種形式化方法?；舅枷耄寒?dāng)一個(gè)問題比較復(fù)雜時(shí)，直接進(jìn)行求解往往比較困難。可通過歸約（分解或變換），將它轉(zhuǎn)化為一系列較簡(jiǎn)單的問題。通過對(duì)這些較簡(jiǎn)單問題的求解來(lái)實(shí)現(xiàn)對(duì)原問題的求解。與或圖搜索34.0與或樹表示【例4.0】設(shè)有四邊形ABCD和A′B′C′D′，證明它們?nèi)?。與或圖搜索44.0與或樹表示分析：原問題分解為兩個(gè)子問題：與或圖搜索54.0與或樹表示與或圖搜索64

2、.0與或樹表示4.0.1分解問題P可以歸約為一組子問題{P1,P2,……,Pn}。只有當(dāng)所有子問題Pi(i＝1，2，……，n)都有解時(shí),原問題P才有解。即分解所得到的子問題的“與”和原問題P等價(jià)。與樹K-連接符P1P2P3P…...K個(gè)與或圖搜索74.0與或樹表示4.0.2等價(jià)變換問題P可以歸約為一組子問題{P1,P2,……,Pn}。這些子問題Pi中只要有一個(gè)有解則原問題P就有解，只有當(dāng)所有子問題Pi都無(wú)解時(shí)原問題P才無(wú)解。即變換所得到的子問題的“或”與原問題P等價(jià)。或樹把一個(gè)原問題變換為若干個(gè)子問題可用一個(gè)“或樹”來(lái)表示。P1P2P3P與或圖搜索84.0與或樹表示4.0.3與或樹

3、如果一個(gè)問題既需要通過分解，又需要通過變換才能得到其本原問題，則其歸約過程可用一個(gè)“與/或樹”來(lái)表示。PP1P2P3P31P32P33P11P12原始問題本原問題（終止節(jié)點(diǎn)）端節(jié)點(diǎn)———沒有子節(jié)點(diǎn)的節(jié)點(diǎn)，即葉子節(jié)點(diǎn)；終止節(jié)點(diǎn)——可解節(jié)點(diǎn)，即本原問題。t與或圖搜索94.0與或樹表示Pttt4.0.4解樹由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)(它對(duì)應(yīng)著原始問題)為可解節(jié)點(diǎn)的子樹。在解樹中一定包含初始節(jié)點(diǎn)。與或圖搜索104.0與或樹表示【例4.1】三階梵塔問題。解：用三元組表示問題在任一時(shí)刻的狀態(tài)：(i,j,k)i：代表金片C所在的鋼針號(hào)；j:代表金片B所在的鋼針號(hào)；k;代表

4、金片A所在的鋼針號(hào)；123123ABC與或圖搜索11123(1,1,1)123(1,2,2)123(3,2,2)123(3,3,3)ABC與或圖搜索12(1,1,1)->(3,3,3)(1,1,1)->(1,2,2)(1,2,2)->(3,2,2)(3,2,2)->(3,3,3)(1,1,1)->(1,1,3)(1,1,3)->(1,2,3)(1,2,3)→(1,2,2)(3,2,2)->(3,2,1)(3,2,1)→(3,3,1)(3,3,1)→(3,3,3)三階梵塔問題的與或樹在該與/或樹中，有7個(gè)終止節(jié)點(diǎn)，它們分別對(duì)應(yīng)著7個(gè)本原問題。如果把這些本原問題從左至右排列起來(lái)，即得到

5、了原始問題的解：與或圖搜索134.0與或樹表示目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc與或圖搜索14內(nèi)容4.0與或樹表示4.1與/或樹的一般搜索4.2與/或樹的廣度優(yōu)先搜索4.3與/或樹的深度優(yōu)先搜索4.4與／或樹的啟發(fā)式搜索4.5博弈樹的啟發(fā)式搜索與或圖搜索154.1與/或樹的一般搜索與/或樹的搜索過程實(shí)際上是一個(gè)不斷尋找解樹的過程。其一般搜索過程如下：（1）把原始問題作為初始節(jié)點(diǎn)S0，并把它作為當(dāng)前節(jié)點(diǎn)；（2）應(yīng)用分解或等價(jià)變換操作對(duì)當(dāng)前節(jié)點(diǎn)進(jìn)行擴(kuò)展；（3）為每個(gè)子節(jié)點(diǎn)設(shè)置指向父節(jié)點(diǎn)的指針；（4）選擇合適的子節(jié)點(diǎn)作為當(dāng)前節(jié)點(diǎn)，反復(fù)執(zhí)行第（2）步和第（3）步，在此期間需要多次調(diào)用可解標(biāo)記過程或不

6、可解標(biāo)記過程，直到初始節(jié)點(diǎn)被標(biāo)記為可解節(jié)點(diǎn)或不可解節(jié)點(diǎn)為止。與或圖搜索164.1與/或樹的一般搜索在與/或樹中，除端節(jié)點(diǎn)和終止節(jié)點(diǎn)外，一個(gè)節(jié)點(diǎn)的可解性完全是由其子節(jié)點(diǎn)來(lái)決定的。對(duì)與節(jié)點(diǎn)，只有其所有子節(jié)點(diǎn)都為可解時(shí)它才為可解，只要有一個(gè)子節(jié)點(diǎn)不可解它就是不可解的；對(duì)或節(jié)點(diǎn)，只要有一個(gè)子節(jié)點(diǎn)可解它就是可解的，僅當(dāng)所有子節(jié)點(diǎn)都是不可解時(shí)它才為不可解?？山鈽?biāo)記過程由可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為可解節(jié)點(diǎn)的過程。不可解標(biāo)記過程由不可解子節(jié)點(diǎn)來(lái)確定其父節(jié)點(diǎn)、祖父節(jié)點(diǎn)為不可解節(jié)點(diǎn)的過程。與或圖搜索174.1與/或樹的一般搜索搜索解樹的過程中，節(jié)點(diǎn)刪除策略：①如果搜索過程確定某個(gè)節(jié)點(diǎn)為可解節(jié)

7、點(diǎn)，則其不可解的后裔節(jié)點(diǎn)就可從搜索樹中刪去；②如果搜索過程能確定某個(gè)節(jié)點(diǎn)為不可解節(jié)點(diǎn)，則其后裔節(jié)點(diǎn)也可從搜索樹中刪去。與或圖搜索18內(nèi)容4.0與或樹表示4.1與/或樹的一般搜索4.2與/或樹的廣度優(yōu)先搜索4.3與/或樹的深度優(yōu)先搜索4.4與／或樹的啟發(fā)式搜索4.5博弈樹的啟發(fā)式搜索與或圖搜索194.2與/或樹的廣度優(yōu)先搜索與/或樹的廣度優(yōu)先搜索算法：（1）把初始節(jié)點(diǎn)S0放人Open表中；（2）把Open表的第一個(gè)節(jié)點(diǎn)取出放入Closed表，并記該節(jié)點(diǎn)為n；（3）如果節(jié)