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