與或樹搜索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,在三階梵塔問(wèn)題中，從左至右的順序排列，得問(wèn)題的解： (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ù)雜的問(wèn)題，直接求解往往比較困難。 從原問(wèn)題出發(fā)，通過(guò)運(yùn)用某些規(guī)則不斷進(jìn)行問(wèn)題分解，重復(fù)進(jìn)行，直到不能在分解或不需要分解為止。 從原問(wèn)題出發(fā)，通過(guò)運(yùn)用某些規(guī)則不斷進(jìn)行問(wèn)題變換，把原問(wèn)題變換為若干較容易求的新問(wèn)題。,復(fù)雜問(wèn)題簡(jiǎn)化,與或樹用來(lái)描述一類問(wèn)題的求解過(guò)程：把待解的原問(wèn)題作為初始節(jié)點(diǎn)，把由原問(wèn)題經(jīng)一系列分解或變換而得到的可解的簡(jiǎn)單問(wèn)題作為目標(biāo)節(jié)點(diǎn)。與或樹。 節(jié)點(diǎn)：對(duì)應(yīng)問(wèn)題 子節(jié)點(diǎn)：對(duì)應(yīng)子問(wèn)題（由節(jié)點(diǎn)分解或變換）,問(wèn)題的與或樹表示,與或樹的節(jié)點(diǎn)代表問(wèn)題，其中既有與關(guān)系又有或關(guān)系，整個(gè)樹表示問(wèn)題空間。,與 分解 問(wèn)題n為n1 . nk個(gè)子問(wèn)題。 只有解決所有子問(wèn)題，才能解決其父輩問(wèn)題的子問(wèn)題集合。 問(wèn)題分解過(guò)程用圖表示： 圖中節(jié)點(diǎn)代表問(wèn)題。與關(guān)系集合中，各個(gè)結(jié)點(diǎn)之間用一段小圓弧連接標(biāo)記。,與節(jié)點(diǎn),或 變換 問(wèn)題n為n1 . nk個(gè)新問(wèn)題。 只要解決某個(gè)問(wèn)題就可解決其父輩問(wèn)題的節(jié)點(diǎn)集合。,或節(jié)點(diǎn),思考： 問(wèn)題Q解決方案：？,概念與術(shù)語(yǔ),本原問(wèn)題：直接可解的簡(jiǎn)單問(wèn)題（不能再分解或變換）。 終止結(jié)點(diǎn)：本原問(wèn)題對(duì)應(yīng)的節(jié)點(diǎn)。(可解節(jié)點(diǎn)) 端節(jié)點(diǎn): 在與或樹中無(wú)子節(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)全都不可解。,問(wèn)題求解過(guò)程就是在一個(gè)與或樹中尋找一個(gè)從初始節(jié)點(diǎn)（原始問(wèn)題）到目標(biāo)節(jié)點(diǎn)（可解的簡(jiǎn)單問(wèn)題）的路徑問(wè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)，把子問(wèn)題Q11，Q12，Q13作為目標(biāo)節(jié)點(diǎn)，則對(duì)問(wèn)題Q的求解就是在與或樹中尋找從Q到Q11，Q12，Q1