第二章 與或圖搜索問題

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

1、1第二章與或圖搜索問題目標目標初始節(jié)點sabc2第二章與或圖搜索問題與或樹是用于表示問題及其求解過程的又一種形式化方法。對于一個復雜問題，直接求解往往比較困難，因此通過下述方法進行簡化：分解：把一個復雜問題簡化為若干簡單的子問題，重復此過程，直到不需要再分解或者不能再分解為止。若每個子問題都可求解，則原問題可求解。因此下圖稱為“與”樹。PP3P2P13第二章與或圖搜索問題等價變換：對于一個復雜問題，除了可用“分解”方法進行求解外，還可利用同構(gòu)或同態(tài)的等價變換，把它變換為若干個較為容易求解的新問題。若新問題中有一個

2、可求解，則就得到了原問題的解。因此下圖稱為“或”樹PP3P2P14第二章與或圖搜索問題與或樹PP3P2P1P12P11P32P33P3152.1基本概念本原問題：不能再分解或變換，而且可以直接求解的子問題。端節(jié)點與終止節(jié)點：沒有子節(jié)點的節(jié)點稱為端節(jié)點；本原問題所對應(yīng)的節(jié)點稱為終止節(jié)點。顯然，終止節(jié)點一定是端節(jié)點，但端節(jié)點不一定是終止節(jié)點?？山夤?jié)點：滿足下列條件之一者，稱為可解節(jié)點：1.它是一個終止節(jié)點；2.它是一個“或”節(jié)點，且其子節(jié)點中至少有一個是可解節(jié)點；3.它是一個“與”節(jié)點，且其子節(jié)點中全部都是可解節(jié)點。

3、62.1基本概念不可解節(jié)點：關(guān)于可解節(jié)點的三個條件全部不滿足的節(jié)點稱為不可解節(jié)點。解樹：由可解節(jié)點構(gòu)成，并且由這些節(jié)點可推出初始節(jié)點（它對應(yīng)于原始問題）為可解節(jié)點的子樹稱為解樹。7解樹PtttPttt8與或樹的廣度優(yōu)先搜索1.把初始節(jié)點S0放入OPEN表。2.把OPEN表中的第一個節(jié)點（記為節(jié)點n)取出放入CLOSED表。3.如果節(jié)點n可擴展，則作下列工作：3.1擴展節(jié)點n，將其子節(jié)點放入OPEN表的尾部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標識過程使用。3.2考察這些子節(jié)點中有否終止節(jié)點。若有，則標識這些終

4、止節(jié)點為可解節(jié)點，并應(yīng)用可解標識過程對其父節(jié)點、祖父節(jié)點等先輩節(jié)點中的可解節(jié)點進行標識。如果初始節(jié)點S0也被標識為可解節(jié)點，就得到了解樹，搜索成果，退出搜索過程；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。3.3轉(zhuǎn)第2步。9與或樹的廣度優(yōu)先搜索（續(xù)）4.如果節(jié)點n不可擴展，則作下列工作。4.1.標識節(jié)點n為不可解節(jié)點。4.2.應(yīng)用不可解標識過程對節(jié)點n的先輩節(jié)點中不可解的節(jié)點進行標識，如果初始節(jié)點S0也被標識為不可解節(jié)點，則搜索失敗，表明原問題無解，退出搜索過程；如果不能確定S0為不可解節(jié)

5、點，則從OPEN表中刪去具有不可解先輩的節(jié)點。4.3轉(zhuǎn)第2步。10與或樹的廣度優(yōu)先搜索：示例2134t1ABt2t4t3511與或樹的廣度優(yōu)先搜索：示例(1).首先擴展1號節(jié)點，得到2號節(jié)點和3號節(jié)點，由于這兩個子節(jié)點均不是終止節(jié)點，所以接著擴展2號節(jié)點。此時OPEN表中只剩下3號節(jié)點。(2).擴展2號節(jié)點后，得到4號節(jié)點和t1節(jié)點。此時OPEN表中的節(jié)點有：3，4,t1。由于t1是終止節(jié)點，則標識它為可解節(jié)點，并應(yīng)用可解標識過程，對其先輩節(jié)點中的可解節(jié)點進行標識。在此例中，因為t1的父節(jié)點是一個“與”節(jié)點，因此

6、僅有t1可解尚不能確定2號節(jié)點是否為可解節(jié)點。所以繼續(xù)搜索。下一步擴展的節(jié)點是3號節(jié)點。12示例(續(xù))擴展3號節(jié)點得到5號節(jié)點與B節(jié)點，兩者都不是終止節(jié)點，所以接著擴展4號節(jié)點。擴展4號節(jié)點后得到節(jié)點A和t2。由于t2是終止節(jié)點，所以標識它為可解節(jié)點，并用可解標識過程標識出4、2均為可解節(jié)點，但1號節(jié)點目前還不能確定它是否是可解節(jié)點。此時5號節(jié)點是OPEN標中的第一個待考察的節(jié)點，所以下一步擴展5號節(jié)點。擴展5號節(jié)點，得到t3、t4，由于t3、t4均為終止節(jié)點，所以被標識為可解節(jié)點，通過應(yīng)用可解標識過程可得到5、

7、3、1號節(jié)點均為可解節(jié)點。13與或樹的有界深度優(yōu)先搜索1.把初始節(jié)點S0放入OPEN表。2.把OPEN表中的第一個節(jié)點（記為節(jié)點n)取出放入CLOSED表。3.如果節(jié)點n的深度大于等于深度界限，則轉(zhuǎn)第5步的5.1步。4.如果節(jié)點n可擴展，則作下列工作：4.1擴展節(jié)點n，將其子節(jié)點放入OPEN表的首部，并為每個子節(jié)點配置指向父節(jié)點的指針，以備標識過程使用。4.2考察這些子節(jié)點中有否終止節(jié)點。若有，則標識這些終止節(jié)點為可解節(jié)點，并應(yīng)用可解標識過程對其父節(jié)點、祖父節(jié)點等先輩節(jié)點中的可解節(jié)點進行標識。如果初始節(jié)點S0也被

8、標識為可解節(jié)點，就得到了解樹，搜索成果，退出搜索過程；如果不能確定S0為可解節(jié)點，則從OPEN表中刪去具有可解先輩的節(jié)點。4.3轉(zhuǎn)第2步。14與或樹的有界深度優(yōu)先搜索（續(xù)）5.如果節(jié)點n不可擴展，則作下列工作。5.1.標識節(jié)點n為不可解節(jié)點。5.2.應(yīng)用不可解標識過程對節(jié)點n的先輩節(jié)點中不可解的節(jié)點進行標識，如果初始節(jié)點S0也被標識為不可解節(jié)點，則搜索失敗，表明原問題無解