【正文】 過程，即擴展節(jié)點 ? 計算耗散值的過程 AO*算法舉例 其中： h(n0)=3 h(n1)=2 h(n2)=4 h(n3)=4 h(n4)=1 h(n5)=1 h(n6)=2 h(n7)=0 h(n8)=0 設： K連接符 的耗散值為 K 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始節(jié)點 n0 n1(2) n4(1) n5(1) 紅色： 4 黃色： 3 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 初始節(jié)點 n0 n4(1) n5(1) 紅色： 4 黃色： 6 n1 n2(4) n3(4) 5 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 紅色： 5 黃色： 6 初始節(jié)點 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 目標 目標 初始節(jié)點 n0 n1 n2 n3 n4 n5 n6 n7 n8 紅色： 5 黃色： 6 初始節(jié)點 n0 n4(1) n5(1) n1 n2(4) n3(4) 5 n6(2) n7(0) n8(0) 2 1 博弈樹搜索 ? 博弈問題 –雙人 –一人一步 –雙方信息完備 –零和 分錢幣問題 （ 7） （ 6,1） （ 5,2） （ 4,3） （ 5,1,1） （ 4,2,1） （ 3,2,2） （ 3,3,1） （ 4,1,1,1） （ 3,2,1,1） （ 2,2,2,1） （ 3,1,1,1,1） （ 2,2,1,1,1） （ 2,1,1,1,1,1） 對方先走 我方必勝 中國象棋 ? 一盤棋平均走 50步，總狀態(tài)數(shù)約為 10的161次方。 ? 極小節(jié)點的上界為 ?。 ? 結(jié)論：不可能窮舉。 ? 若非終節(jié)點有“或”子節(jié)點，當且僅當所有子節(jié)點均不能解時，該非終節(jié)點才不能解。 動態(tài)規(guī)劃 s t 第一階段 第二階段 第三階段 第四階段 第五階段 5，搜索算法實用舉例 ? 漢字識別后處理 ? 一個例子 我錢線載哦栽哉裁劣綏 優(yōu)仍們仿倫奶砧犯扔妨 要耍密窮安壁駐努窯垂 扳報叔嵌奴振技寂敘蔽 奮夯杏蠶香脊秀吞吝番 精猜指潔括治捐活冶桔 種神襯祥科鐘拌樣拎補 漢字識別后處理 ????niii PSP111 )...|()( )()|()()|( OPSOPSPOSP ?二元語法時： ????niii wwPSP11 )|()()(OP為常量 )|( SO用識別信度代替 問題變?yōu)榍? ???niiii wCFwwP11 )()|(最大 第三章 與或圖的搜索 目標 目標 初始節(jié)點 基本概念 ? 與或圖是一個超圖，節(jié)點間通過連接符連接。 s(10) A(1) B(5) C(8) G 目標 6 3 1 1 1 8 前面的例子： OPEN表 CLOSED表 fm s(0+10) s(0+10) 10 A(6+1) B(3+5) C(1+8) s(0+10) C(1+8) 10 A(6+1) B(2+5) s(0+10) C(1+8) B(2+5) 10 A(3+1) s(0+10)C(1+8)B(2+5)A(3+1) 10 G(11+0) h的單調(diào)化方法 ? 如果令： f(n) = max(f(n的父節(jié)點 ), g(n)+h(n)) 則容易證明，這樣處理后的 h是單調(diào)的。 改進的出發(fā)點 OPEN = ( … … … … ) f*(s) f值小于 f*(s)的節(jié)點 f值大于等于 f*(s)的節(jié)點 fm： 到目前為止已擴展節(jié)點的最大 f值，用 fm代替 f*(s) 修正過程 A 1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0。 h單調(diào)的性質(zhì)（續(xù)） ? 定理 6： 若 h(n)是單調(diào)的，則由 A*所擴展的節(jié)點序列其 f值是非遞減的。 ? 對算法加以改進 –能否對算法加以改進，避免或減少節(jié)點的多次擴展。 d=20, N=676, b*= A*的復雜性 ? 一般來說， A*的算法復雜性是指數(shù)型的，可以證明，當且僅當以下條件成立時： abs(h(n)h*(n)) ≤ O(log(h*(n))) A*的算法復雜性才是非指數(shù)型的，但是通常情況下， h與 h*的差別至少是和離目標的距離成正比的。 ? 實驗表明， b*是一個穩(wěn)定的常數(shù)，基本不隨問題規(guī)模變化。 A*算法的性質(zhì)（續(xù) 6） 推論 ： A*選作擴展的任一節(jié)點 n，有 f(n)≤f*(s)。 A*算法的性質(zhì)（續(xù) 2） 引理 ： A*結(jié)束前， OPEN表中必存在 f(n)≤f*(s)。 A算法（續(xù)） ADD(mj, OPEN), 標記 mj到 n的指針； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標記 mk到 n的指針； IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml), 標記 ml到 n的指針 , ADD(ml, OPEN)。 3, n:=FIRST(OPEN)。 ? 啟發(fā)信息的強度 –強：降低搜索工作量，但可能導致找不到最 優(yōu)解 –弱：一般導致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解 希望： ? 引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。 9, GO LOOP。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 3 1 8 4 7 6 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 4 5 6 7 8 9 a b c d 1 2 3 8 4 7 6 5 目標 深度優(yōu)先搜索的性質(zhì) ? 一般不能保證找到最優(yōu)解 ? 當深度限制不合理時，可能找不到解，可以將算法改為可變深度限制 ? 最壞情況時，搜索空間等同于窮舉 ? 與回溯法的差別：圖搜索 ? 是一個通用的與問題無關的方法 寬度優(yōu)先搜索 1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( )。 7, EXPAND(n) →{mi}, G:=ADD(mi, G)。 3, n:=FIRST