第二章與或圖搜索問題與或圖搜索問題－

對問題進(jìn)行分割后進(jìn)行搜索1梵塔難題123CBA2解題過程（3個圓盤問題）1231231231231231231231233與/或(AND/OR)圖表示與圖、或圖、與或圖ABCD與圖ABC或圖與圖或圖4一些關(guān)于與或圖的術(shù)語HMBCDEFGAN父節(jié)點(diǎn)與節(jié)點(diǎn)弧線或節(jié)點(diǎn)子節(jié)點(diǎn)終葉節(jié)點(diǎn)6梵塔問題與或圖（113）（123）

（111）（113）

（123）（122）

（111）（333）

（122）（322）

（111）（122）

（322）（333）

（321）（331）

（322）（321）

（331）（333）

72.1基本概念與或圖是一個超圖，節(jié)點(diǎn)間通過連接符連接。K-連接符：…...K個8耗散值的計算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點(diǎn)集Cn為連接符的耗散值…...i個nn1n2ni9目標(biāo)目標(biāo)初始節(jié)點(diǎn)sabc10解圖：11能解節(jié)點(diǎn)終節(jié)點(diǎn)是能解節(jié)點(diǎn)若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)時，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)至少有一能解時，該非終節(jié)點(diǎn)才能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時，當(dāng)且僅當(dāng)其子節(jié)點(diǎn)均能解時，該非終節(jié)點(diǎn)才能解。12不能解節(jié)點(diǎn)沒有后裔的非終節(jié)點(diǎn)是不能解節(jié)點(diǎn)。若非終節(jié)點(diǎn)有“或”子節(jié)點(diǎn)，當(dāng)且僅當(dāng)所有子節(jié)點(diǎn)均不能解時，該非終節(jié)點(diǎn)才不能解。若非終節(jié)點(diǎn)有“與”子節(jié)點(diǎn)時，當(dāng)至少有一個子節(jié)點(diǎn)不能解時，該非終節(jié)點(diǎn)才不能解。13

f(n)=g(n)+h(n) 對n的評價實(shí)際是對從s到n這條路徑的評價ns2.2與或圖的啟發(fā)式搜索算法AO*普通圖搜索的情況14與或圖:對局部圖的評價目標(biāo)目標(biāo)初始節(jié)點(diǎn)abc15兩個過程圖生成過程，即擴(kuò)展節(jié)點(diǎn)從最優(yōu)的局部途中選擇一個節(jié)點(diǎn)擴(kuò)展計算耗散值的過程對當(dāng)前的局部圖重新新計算耗散值16AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設(shè)：K連接符的耗散值為K目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n817目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8n4(1)紅色：4黃色：3初始節(jié)點(diǎn)n0n1(2)n5(1)18目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：4黃色：6n3(4)初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)519目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)220目標(biāo)目標(biāo)初始節(jié)點(diǎn)n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點(diǎn)n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)2121AO*算法

AO*算法可劃分成兩個操作階段：第一階段是完成自頂向下的圖生成操作,先通過有標(biāo)記的連接符，找到目前為止最好的一個局部解圖，然后對其中一個非終結(jié)點(diǎn)進(jìn)行擴(kuò)展，并對其后繼結(jié)點(diǎn)賦估計耗散值和加能解標(biāo)記。22AO*算法

第二階段是完成自下向上的耗散值修正計算、連接符(即指針)的標(biāo)記以及結(jié)點(diǎn)的能解標(biāo)記。耗散值的修正從剛被擴(kuò)展的結(jié)點(diǎn)n開始，其修正耗散值q(n)取估計h(n)的所有值中最小的一個，然后根據(jù)耗散值遞歸計算公式逐級向上修正其先輩結(jié)點(diǎn)的耗散值，只有下層耗散值修正后，才可能影響上一層結(jié)點(diǎn)的耗散值，因此必須自底向上一直修正到初始結(jié)點(diǎn)。這由算法中的內(nèi)循環(huán)過程完成。23AO*算法與A算法的區(qū)別AO*算法不能像A算法那樣，單純靠評價某一個結(jié)點(diǎn)來評價局部圖。AO*算法由于k-連接符連接的有關(guān)子結(jié)點(diǎn)，對父結(jié)點(diǎn)能解與否以及耗散值都有影響，因而顯然不能像A算法那樣優(yōu)先擴(kuò)展其中具有最小耗散值的結(jié)點(diǎn)。24AO*算法僅適用于無環(huán)圖的假設(shè)，否則耗散值遞歸計算不能收斂，因而在算法中還必須檢查新生成的結(jié)點(diǎn)已在圖中時，是否是正被擴(kuò)展結(jié)點(diǎn)的先輩結(jié)點(diǎn)