與或樹搜索1與或樹.ppt

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