資源描述：
《與或圖的搜索算法》由會員上傳分享，免費在線閱讀，更多相關內(nèi)容在教育資源-天天文庫。
1、第二章與或圖搜索問題與或圖搜索問題－ 對問題進行分割后進行搜索1梵塔難題123CBA2解題過程（3個圓盤問題）1231231231231231231231233與/或(AND/OR)圖表示與圖、或圖、與或圖ABCD與圖ABC或圖與圖或圖4BCDEFGAHMBCDEFGAN與或圖5一些關于與或圖的術語HMBCDEFGAN父節(jié)點與節(jié)點弧線或節(jié)點子節(jié)點終葉節(jié)點6梵塔問題與或圖（113）（123）（111）（113）（123）（122）（111）（333）（122）（322）（111）（122）（322）（333）（321）（331）（322）（321）（331）（3
2、33）72.1基本概念與或圖是一個超圖，節(jié)點間通過連接符連接。K-連接符：…...K個8耗散值的計算k(n,N)=Cn+k(n1,N)+…+k(ni,N)其中：N為終節(jié)點集Cn為連接符的耗散值…...i個nn1n2ni9目標目標初始節(jié)點sabc10解圖：11能解節(jié)點終節(jié)點是能解節(jié)點若非終節(jié)點有“或”子節(jié)點時，當且僅當其子節(jié)點至少有一能解時，該非終節(jié)點才能解。若非終節(jié)點有“與”子節(jié)點時，當且僅當其子節(jié)點均能解時，該非終節(jié)點才能解。12不能解節(jié)點沒有后裔的非終節(jié)點是不能解節(jié)點。若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。若非終節(jié)點有
3、“與”子節(jié)點時，當至少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。13f(n)=g(n)+h(n)對n的評價實際是對從s到n這條路徑的評價ns2.2與或圖的啟發(fā)式搜索算法AO*普通圖搜索的情況14與或圖:對局部圖的評價目標目標初始節(jié)點abc15兩個過程圖生成過程，即擴展節(jié)點從最優(yōu)的局部途中選擇一個節(jié)點擴展計算耗散值的過程對當前的局部圖重新新計算耗散值16AO*算法舉例其中：h(n0)=3h(n1)=2h(n2)=4h(n3)=4h(n4)=1h(n5)=1h(n6)=2h(n7)=0h(n8)=0設：K連接符的耗散值為K目標目標初始節(jié)點n0n1n2n3n4n5n
4、6n7n817目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8n4(1)紅色：4黃色：3初始節(jié)點n0n1(2)n5(1)18目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：4黃色：6n3(4)初始節(jié)點n0n4(1)n5(1)n1n2(4)519目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)n8(0)220目標目標初始節(jié)點n0n1n2n3n4n5n6n7n8紅色：5黃色：6初始節(jié)點n0n4(1)n5(1)n1n2(4)n3(4)5n6(2)n7(0)
5、n8(0)2121AO*算法AO*算法可劃分成兩個操作階段：第一階段是完成自頂向下的圖生成操作,先通過有標記的連接符，找到目前為止最好的一個局部解圖，然后對其中一個非終結(jié)點進行擴展，并對其后繼結(jié)點賦估計耗散值和加能解標記。22AO*算法第二階段是完成自下向上的耗散值修正計算、連接符(即指針)的標記以及結(jié)點的能解標記。耗散值的修正從剛被擴展的結(jié)點n開始，其修正耗散值q(n)取估計h(n)的所有值中最小的一個，然后根據(jù)耗散值遞歸計算公式逐級向上修正其先輩結(jié)點的耗散值，只有下層耗散值修正后，才可能影響上一層結(jié)點的耗散值，因此必須自底向上一直修正到初始結(jié)點。這由算法中
6、的內(nèi)循環(huán)過程完成。23AO*算法與A算法的區(qū)別AO*算法不能像A算法那樣，單純靠評價某一個結(jié)點來評價局部圖。AO*算法由于k-連接符連接的有關子結(jié)點，對父結(jié)點能解與否以及耗散值都有影響，因而顯然不能像A算法那樣優(yōu)先擴展其中具有最小耗散值的結(jié)點。24AO*算法僅適用于無環(huán)圖的假設，否則耗散值遞歸計算不能收斂，因而在算法中還必須檢查新生成的結(jié)點已在圖中時，是否是正被擴展結(jié)點的先輩結(jié)點。AO*與A的區(qū)別25A算法有OPEN表和CLOSED表，而AO*算法只用一個與或圖結(jié)構，它代表到目前為止已顯式生成的部分搜索圖，圖中每一個結(jié)點的h(n)值是估計最佳解圖，而不是估計解
7、路徑。AO*與A的區(qū)別26
