【正文】 當 n＝ s時，定理顯然成立。下面考察 n ≠s的情況。 ? 設 P＝ (n0=s, n1, n2, …, n k=n)是 s到 n的最佳路徑 ? P中一定有節(jié)點在 CLOSED中，設 P中最后一個出現(xiàn)在 CLOSED中的節(jié)點為 nj，則nj+1在 OPEN中。 85 定理 （續(xù) 1） ? 由單調限制條件，對 P中任意節(jié)點 ni有： h(ni) ≤ C(ni, ni+1)+h(ni+1) g*(ni)+h(ni) ≤ g*(ni)+C(ni, ni+1)+h(ni+1) ? 由于 ni 、 ni+1在最佳路徑上，所以： g*(ni+1) = g*(ni)+C(ni, ni+1) ? 帶入上式有： g*(ni)+h(ni) ≤ g*(ni+1)+h(ni+1) ? 從 i=j到 i=k1應用上不等式，有： g*(nj+1)+h(nj+1) ≤ g*(nk)+h(nk) ? 即： f(nj+1) ≤ g*(n)+h(n) 注意： (nj在 CLOSED中， nj+1在 OPEN中 ) 86 定理 （續(xù) 2） ? 重寫上式： f(nj+1) ≤ g*(n)+h(n) ? 另一方面， A*選 n擴展，必有： f(n) = g(n)+h(n) ≤ f(nj+1) ? 比較兩式，有： g(n) ≤ g*(n) ? 但已知 g*(n)是最佳路徑的耗散值，所以只有： g(n) = g*(n)。得證。 87 h單調的性質（續(xù)） ? 定理 ： 若 h(n)是單調的，則由 A*所擴展的節(jié)點序列其 f值是非遞減的。即 f(ni) ≤ f(nj)。 88 定理 ? 由單調限制條件，有： h(ni) – h(nj) ≤ C(ni, nj) = f(ni)g(ni) = f(nj)g(nj) f(ni)g(ni) f(nj)+g(nj) ≤ C(ni, nj) = g(ni)+C(ni, nj) f(ni)g(ni) f(nj)+ g(ni)+C(ni, nj) ≤ C(ni, nj) f(ni) f(nj) ≤ 0，得證。 89 h單調的例子 ? 8數(shù)碼問題： – h為“不在位”的將牌數(shù) 1 h(ni) h(nj) = 0 (nj為 ni的后繼節(jié)點 ) 1 h(t) = 0 c(ni, nj) = 1 滿足單調的條件。 90 對算法加以改進 ? 一些結論： – OPEN表上任以具有 f(n) f*(s)的節(jié)點定會被擴展。 – A*選作擴展的任一節(jié)點，定有 f(n)≤f*(s)。 91 改進的出發(fā)點 OPEN = ( … … … … ) f*(s) f值小于 f*(s)的節(jié)點 f值大于等于 f*(s)的節(jié)點 fm： 到目前為止已擴展節(jié)點的最大 f值，用 fm代替 f*(s) 92 修正過程 A 1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0。 2, LOOP: IF OPEN=( ) THEN EXIT(FAIL)。 3, NEST:={ni|f(ni)fm} IF NEST ≠ ( ) THEN n:=NEST中 g最小的節(jié)點 ELSE n:=FIRST(OPEN), fm:=f(n)。 4, …, 8: 同過程 A。 93 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) 94 h的單調化方法 ? 如果令： f(n) = max(f(n的父節(jié)點 ), g(n)+h(n)) 則容易證明，這樣處理后的 h是單調的。 95 IDA*算法 (Iterative Deepening A*) ? 基本思想：回溯與 A*的結合 ? 算法簡介（非嚴格地） 1，設初始值 f0； 2，集合 S＝ NULL； 3，用回溯法求解問題，如果節(jié)點 n的 f值大于 f0，則將該節(jié)點放入集合 S中，并回溯； 4，如果在 3中找到了解，則結束； 5，如果 3以失敗結束，則 f0＝ S中節(jié)點的最小 f值； 6，返回到 2。 96 知識的靈活應用 例：如何轉動，使得每個扇區(qū)數(shù)字和為 12。 1 3 5 5 1 4 4 1 3 3 2 5 2 3 1 2 3 1 2 2 5 5 2 3 4 2 5 4 3 4 3 3 分析： 陰影部分數(shù)字和： 48 直徑部分數(shù)字和： 24 轉 45176。改變陰影部分 轉 90176。改變直徑部分 但不改變陰影部分 轉 180176。改變扇區(qū)部分 但不改變陰影部分 也不改變直徑部分 97 4，其他的搜索算法 ? 爬山法（局部搜索算法） 98 其他的搜索算法（續(xù) 1） ? 隨機搜索算法 ? 動態(tài)規(guī)劃算法 如果對于任何 n，當 h(n)=0時， A*算法就成為了動態(tài)規(guī)劃算法。 99 動態(tài)規(guī)劃 s t 第一階段 第二階段 第三階段 第四階段 第五階段 100 5，搜索算法實用舉例 ? 漢字識別后處理 ? 一個例子 我錢線載哦栽哉裁劣綏 優(yōu)仍們仿倫奶砧犯扔妨 要耍密窮安壁駐努窯垂 扳報叔嵌奴振技寂敘蔽 奮夯杏蠶香脊秀吞吝番 精猜指潔括治捐活冶桔 種神襯祥科鐘拌樣拎補 101 漢字識別后處理 ????niii PSP111 )...|()( )()|()()|( OPSOPSPOSP ?二元語法時： ????niii wwPS11 )|()()(OP為常量 )|( SO用識別信度代替 問題變?yōu)榍? ???niiii wCFwwP11 )()|(最大 102 演講完畢，謝謝觀看！