與或樹搜索1與或樹.ppt

6.1 與或樹 6.2 與或樹搜索 6.3 啟發(fā)式與或樹搜索,6 與或樹搜索,6.1 與或樹 三階梵塔,（1,1,1） （3,3,3）,CBA,三元組 (i, j, k) i 代表金盤A所在的桿號(hào)；j代表金盤B所在的桿號(hào)；k代表金盤C所在的標(biāo)號(hào)。,(ABC) （1,1,1）（1,2,2） （1,2,2）（3,2,2） （3,2,2）（3,3,3）,（1,1,1）,CBA,(1,2,2),（3,3,3）,（3,3,3）,（1,1,1）,（1,2,2）,（3,2,2）,舉例(三階梵塔),與或樹表示,(1)把B、C盤從1號(hào)桿移到2號(hào)桿； (2)把A盤從1號(hào)桿移到3號(hào)桿； (3)把B、C盤從2號(hào)桿移到3號(hào)桿；,舉例(三階梵塔),CBA,在三階梵塔問題中，從左至右的順序排列，得問題的解： (1,1,1)=(1,1,3) (1,1,3)=(1,2,3) (1,2,3)=(1,2,2) (1,2,2)=(3,2,2) (3,2,2)=(3,2,1) (3,2,1)=(3,3,1) (3,3,1)=(3,3,3),對(duì)于復(fù)雜的問題，直接求解往往比較困難。 從原問題出發(fā)，通過運(yùn)用某些規(guī)則不斷進(jìn)行問題分解，重復(fù)進(jìn)行，直到不能在分解或不需要分解為止。 從原問題出發(fā)，通過運(yùn)用某些規(guī)則不斷進(jìn)行問題變換，把原問題變換為若干較容易求的新問題。,復(fù)雜問題簡化,與或樹用來描述一類問題的求解過程：把待解的原問題作為初始節(jié)點(diǎn)，把由原問題經(jīng)一系列分解或變換而得到的可解的簡單問題作為目標(biāo)節(jié)點(diǎn)。與或樹。 節(jié)點(diǎn)：對(duì)應(yīng)問題 子節(jié)點(diǎn)：對(duì)應(yīng)子問題（由節(jié)點(diǎn)分解或變換）,問題的與或樹表示,與或樹的節(jié)點(diǎn)代表問題，其中既有與關(guān)系又有或關(guān)系，整個(gè)樹表示問題空間。,與 分解 問題n為n1 . nk個(gè)子問題。 只有解決所有子問題，才能解決其父輩問題的子問題集合。 問題分解過程用圖表示： 圖中節(jié)點(diǎn)代表問題。與關(guān)系集合中，各個(gè)結(jié)點(diǎn)之間用一段小圓弧連接標(biāo)記。,與節(jié)點(diǎn),或 變換 問題n為n1 . nk個(gè)新問題。 只要解決某個(gè)問題就可解決其父輩問題的節(jié)點(diǎn)集合。,或節(jié)點(diǎn),思考： 問題Q解決方案：？,概念與術(shù)語,本原問題：直接可解的簡單問題（不能再分解或變換）。 終止結(jié)點(diǎn)：本原問題對(duì)應(yīng)的節(jié)點(diǎn)。(可解節(jié)點(diǎn)) 端節(jié)點(diǎn): 在與或樹中無子節(jié)點(diǎn)的節(jié)點(diǎn)。 與節(jié)點(diǎn)： 一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“與”關(guān)系，稱 或節(jié)點(diǎn)： 一個(gè)節(jié)點(diǎn)的子節(jié)點(diǎn)如果是“或”關(guān)系，稱 思考: 終止節(jié)點(diǎn)是端節(jié)點(diǎn)嗎? 注意： 終止節(jié)點(diǎn)一定是端節(jié)點(diǎn)，但端節(jié)點(diǎn)不一定是終止節(jié)點(diǎn)。,可解性判別,一個(gè)節(jié)點(diǎn)是可解，則節(jié)點(diǎn)須滿足下列 條件之一： 1 終止節(jié)點(diǎn)是可解節(jié)點(diǎn); 2一個(gè)與節(jié)點(diǎn)可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都可解； 3一個(gè)或節(jié)點(diǎn)可解，只要其子節(jié)點(diǎn)至少有一個(gè)可解； 一個(gè)節(jié)點(diǎn)是不可解，則節(jié)點(diǎn)須滿足下列條件之一： 1 非終止節(jié)點(diǎn)的端節(jié)點(diǎn)是不可解節(jié)點(diǎn)； 2 一個(gè)與節(jié)點(diǎn)不可解，只要其子節(jié)點(diǎn)至少有一個(gè)不可解； 3 一個(gè)或節(jié)點(diǎn)不可解，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)全都不可解。,問題求解過程就是在一個(gè)與或樹中尋找一個(gè)從初始節(jié)點(diǎn)（原始問題）到目標(biāo)節(jié)點(diǎn)（可解的簡單問題）的路徑問題。,t3,1,3,2,B,5,t1,t4,t2,A,4,1,3,2,B,5,t1,t4,t3,t2,A,4,例1: t 是終止節(jié)點(diǎn),1 可解性？,例2： Q作為初始節(jié)點(diǎn)，把子問題Q11，Q12，Q13作為目標(biāo)節(jié)點(diǎn)，則對(duì)問題Q的求解就是在與或樹中尋找從Q到Q11，Q12，Q1