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

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

1、第二章與或圖搜索問題目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabcEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.1基本思想當(dāng)一問題較復(fù)雜時(shí)，可通過(guò)分解或變換，將其轉(zhuǎn)化為一系列較簡(jiǎn)單的子問題，然后通過(guò)對(duì)這些子問題的求解來(lái)實(shí)現(xiàn)對(duì)原問題的求解。分解如果一個(gè)問題P可以歸約為一組子問題P1,P2,…,Pn，并且只有當(dāng)所有子問題Pi都有解時(shí)原問題P才有解，任何一個(gè)子問題Pi無(wú)解都會(huì)導(dǎo)致原問題P無(wú)解，則稱此種

2、歸約為問題的分解。即分解所得到的子問題的“與”與原問題P等價(jià)。等價(jià)變換如果一個(gè)問題P可以歸約為一組子問題P1,P2,…,Pn，并且子問題Pi中只要有一個(gè)有解則原問題P就有解，只有當(dāng)所有子問題Pi都無(wú)解時(shí)原問題P才無(wú)解，稱此種歸約為問題的等價(jià)變換，簡(jiǎn)稱變換。即變換所得到的子問題的“或”與原問題P等價(jià)。2.1問題歸約法Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.2PP1P2P

3、3與樹P1P2P3或樹PPP1P2P3P12P12P31P32P33與/或樹(1)與樹分解(2)或樹等價(jià)變換(3)與/或樹2.1問題歸約法2.問題的與/或樹表示Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.3(4)端節(jié)點(diǎn)與終止節(jié)點(diǎn)在與/或樹中，沒有子節(jié)點(diǎn)的節(jié)點(diǎn)稱為端節(jié)點(diǎn)；本原問題所對(duì)應(yīng)的節(jié)點(diǎn)稱為終止節(jié)點(diǎn)?？梢?，終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)卻不一定是終止節(jié)點(diǎn)。(5)可解節(jié)點(diǎn)

4、與不可解節(jié)點(diǎn)在與/或樹中，滿足以下三個(gè)條件之一的節(jié)點(diǎn)為可解節(jié)點(diǎn)：①任何終止節(jié)點(diǎn)都是可解節(jié)點(diǎn)。②對(duì)“或”節(jié)點(diǎn)，當(dāng)其子節(jié)點(diǎn)中至少有一個(gè)為可解節(jié)點(diǎn)時(shí)，則該或節(jié)點(diǎn)就是可解節(jié)點(diǎn)。③對(duì)“與”節(jié)點(diǎn)，只有當(dāng)其子節(jié)點(diǎn)全部為可解節(jié)點(diǎn)時(shí)，該與節(jié)點(diǎn)才是可解節(jié)點(diǎn)。同樣，可用類似的方法定義不可解節(jié)點(diǎn)：①不為終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)。②對(duì)“或”節(jié)點(diǎn)，若其全部子節(jié)點(diǎn)都為不可解節(jié)點(diǎn)，則該或節(jié)點(diǎn)是不可解節(jié)點(diǎn)。③對(duì)“與”節(jié)點(diǎn)，只要其子節(jié)點(diǎn)中有一個(gè)為不可解節(jié)點(diǎn)，則該與節(jié)點(diǎn)是不可解節(jié)點(diǎn)。Evaluationonly.CreatedwithAspose.Slides

5、for.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.4Pttt解樹(6)解樹由可解節(jié)點(diǎn)構(gòu)成，并且由這些可解節(jié)點(diǎn)可以推出初始節(jié)點(diǎn)（它對(duì)應(yīng)著原始問題）為可解節(jié)點(diǎn)的子樹為解樹。在解樹中一定包含初始節(jié)點(diǎn)。例如，右圖給出的與或樹中，用紅線表示的子樹是一個(gè)解樹。在該圖中，節(jié)點(diǎn)P為原始問題節(jié)點(diǎn)，用t標(biāo)出的節(jié)點(diǎn)是終止節(jié)點(diǎn)。根據(jù)可解節(jié)點(diǎn)的定義，很容易推出原始問題P為可解節(jié)點(diǎn)。問題歸約求解過(guò)程就實(shí)際上就是生成解樹，即證明原始節(jié)點(diǎn)是可解節(jié)點(diǎn)的過(guò)程。這一過(guò)程涉及到搜索的問題，對(duì)于

6、與/或樹的搜索將在后面詳細(xì)討論。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.5例4.4三階梵塔問題。要求把1號(hào)鋼針上的3個(gè)金片全部移到3號(hào)鋼針上，如下圖所示。解：這個(gè)問題也可用狀態(tài)空間法來(lái)解，不過(guò)本例主要用它來(lái)說(shuō)明如何用歸約法來(lái)解決問題。為了能夠解決這一問題，首先需要定義該問題的形式化表示方法。設(shè)用三元組(i,j,k)表示問題在任一時(shí)刻的狀態(tài)，用“→”表示狀態(tài)的轉(zhuǎn)換。上述

7、三元組中i代表金片C所在的鋼針號(hào)j代表金片B所在的鋼針號(hào)k代表金片A所在的鋼針號(hào)1231232.1問題歸約法2.問題的與/或樹表示Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.6利用問題歸約方法，原問題可分解為以下三個(gè)子問題：(1)把金片A及B移到2號(hào)鋼針上的雙金片移動(dòng)問題。即(1,1,1)→(1,2,2)(2)把金片C移到3號(hào)鋼針上的單金片移動(dòng)問題。即(1,2,2)→(3

8、,2,2)(3)把金片A及B移到3號(hào)鋼針的雙金片移動(dòng)問題。即(3,2,2)→((3,3,3)其中，子問題(1)和(3)都是一個(gè)二階梵塔問題，它們都還可以再繼續(xù)進(jìn)行分解；子問題(2)是本原問題，它已不需要再分解。三階梵塔問題的分解過(guò)程可用如下圖與/或樹來(lái)表示(1,1,1)→(3