【正文】 ?剪枝的條件： – 后輩節(jié)點的 ?值 ≤祖先節(jié)點的 ?值時， ?剪枝 – 后輩節(jié)點的 ? 值 ≥祖先節(jié)點的 ?值時， ?剪枝 ?簡記為： – 極小 ≤極大，剪枝 – 極大 ≥極小，剪枝 141 ??剪枝（續(xù)） 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 0 3 0 3 3 0 5 4 1 1 3 1 6 6 1 a b c d e f g h i j k m n 142 ??剪枝的其他應(yīng)用 ?故障診斷 A B C D ?風(fēng)險投資 143 謝謝觀看 /歡迎下載 BY FAITH I MEAN A VISION OF GOOD ONE CHERISHES AND THE ENTHUSIASM THAT PUSHES ONE TO SEEK ITS FULFILLMENT REGARDLESS OF OBSTACLES. BY FAITH I BY FAITH 。 139 1，極小極大過程 0 5 3 3 3 3 0 2 2 3 0 2 3 5 4 1 3 0 6 8 9 3 0 3 3 3 3 2 1 3 6 3 0 3 1 6 0 1 1 極大 極小 a b 140 ??剪枝 ?極大節(jié)點的下界為 ?。 ?假設(shè) 1毫微秒走一步，約需 10的 145次方年。 ?若非終節(jié)點有“與”子節(jié)點時，當(dāng)至少有一個子節(jié)點不能解時，該非終節(jié)點才不能解。 127 不能解節(jié)點 ?沒有后裔的非終節(jié)點是不能解節(jié)點。 ? K連接符： …... K個 124 耗散值的計算 k(n, N) = Cn+k(n1, N)+…+k(n i, N) 其中： N為終節(jié)點集 Cn為連接符的耗散值 …... i個 n n1 n2 ni 125 目標(biāo) 目標(biāo) 初始節(jié)點 ? 解圖： 126 能解節(jié)點 ?終節(jié)點是能解節(jié)點 ?若非終節(jié)點有“或”子節(jié)點時，當(dāng)且僅當(dāng)其子節(jié)點至少有一能解時，該非終節(jié)點才能解。改變扇區(qū)部分 但不改變陰影部分 也不改變直徑部分 116 4，其他的搜索算法 ?爬山法（局部搜索算法） 117 其他的搜索算法（續(xù) 1） ?隨機(jī)搜索算法 ?動態(tài)規(guī)劃算法 如果對于任何 n，當(dāng) h(n)=0時， A*算法就成為了動態(tài)規(guī)劃算法。改變陰影部分 轉(zhuǎn) 90176。 115 知識的靈活應(yīng)用 例：如何轉(zhuǎn)動，使得每個扇區(qū)數(shù)字和為 12。 112 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) 113 h的單調(diào)化方法 ?如果令： f(n) = max(f(n的父節(jié)點 ), g(n)+h(n)) 則容易證明，這樣處理后的 h是單調(diào)的。 3, NEST:={ni|f(ni)fm} IF NEST ≠ ( ) THEN n:=NEST中 g最小的節(jié)點 ELSE n:=FIRST(OPEN), fm:=f(n)。 110 改進(jìn)的出發(fā)點 OPEN = ( … … … … ) f*(s) f值小于 f*(s)的節(jié)點 f值大于等于 f*(s)的節(jié)點 fm： 到目前為止已擴(kuò)展節(jié)點的最大 f值，用 fm代替 f*(s) 111 修正過程 A 1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0。 109 對算法加以改進(jìn) ?一些結(jié)論： – OPEN表上任以具有 f(n) f*(s)的節(jié)點定會被擴(kuò)展。 107 定理 6的證明 ? 由單調(diào)限制條件，有： 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，得證。 106 h單調(diào)的性質(zhì)（續(xù)） ?定理 6： 若 h(n)是單調(diào)的，則由 A*所擴(kuò)展的節(jié)點序列其 f值是非遞減的。 104 定理 5的證明（續(xù) 1） ? 由單調(diào)限制條件，對 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應(yīng)用上不等式，有： g*(nj+1)+h(nj+1) ≤ g*(nk)+h(nk) ? 即： f(nj+1) ≤ g*(n)+h(n) 注意： (nj在 CLOSED中， nj+1在 OPEN中 ) 105 定理 5的證明（續(xù) 2） ?重寫上式： f(nj+1) ≤ g*(n)+h(n) ?另一方面， A*選 n擴(kuò)展，必有： f(n) = g(n)+h(n) ≤ f(nj+1) ?比較兩式，有： g(n) ≤ g*(n) ?但已知 g*(n)是最佳路徑的耗散值，所以只有： g(n) = g*(n)。下面考察 n ≠s的情況。 103 定理 5的證明 ?設(shè) n是 A*擴(kuò)展的任一節(jié)點。 h(ni) ni nj h(nj) c(ni,nj) 102 h單調(diào)的性質(zhì) ?定理 5： 若 h(n)是單調(diào)的，則 A*擴(kuò)展了節(jié)點 n之后，就已經(jīng)找到了到達(dá)節(jié)點 n的最佳路徑。 ?對算法加以改進(jìn) – 能否對算法加以改進(jìn)，避免或減少節(jié)點的多次擴(kuò)展。 97 s(10) A(1) B(5) C(8) G 目標(biāo) 6 3 1 1 1 8 一個例子： OPEN表 CLOSED表 s(10) s(10) A(7) B(8) C(9) A(7) s(10) B(8) C(9) G(14) A(5) C(9) G(14) C(9) G(12) B(7) G(12) A(4) G(12) G(11) B(8) s(10) A(5) B(8) s(10) C(9) A(5) s(10) B(7) C(9) s(10) A(4) B(7) C(9) s(10) 98 出現(xiàn)多次擴(kuò)展節(jié)點的原因 ?在前面的擴(kuò)展中，并沒有找到從初始節(jié)點到當(dāng)前節(jié)點的最短路徑，如節(jié)點 A。 d=20, N=676, b*= 95 A*的復(fù)雜性 ?一般來說， A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時： abs(h(n)h*(n)) ≤ O(log(h*(n))) A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下， h與 h*的差別至少是和離目標(biāo)的距離成正比的。 ?使用 h1： d=14, N=539, b*=。 ?實驗表明， b*是一個比較穩(wěn)定的常數(shù)，同一問題基本不隨問題規(guī)模變化。 93 對 h的評價方法 ?平均分叉樹 設(shè)共擴(kuò)展了 d層節(jié)點，共搜索了 N個節(jié)點，則 : 其中， b*稱為平均分叉樹。 92 定理 4的證明（續(xù) 1） ? 所以有： f1(n) ≥ f*(s) ? 即： g1(n)+h1(n) ≥ f*(s) ? 所以： h1(n) ≥ f*(s) g1(n) ? 另一方面，由于 A2擴(kuò)展了 n，有 f2(n) ≤ f*(s) ? 即： h2(n) ≤ f*(s) – g2(n) (A) ? 由于 d(n)=k時， A2擴(kuò)展的節(jié)點 A1一定擴(kuò)展，有 g1(n) ≤ g2(n) (因為 A2的路 A1均走到了 ) ? 所以： h1(n) ≥ f*(s) g1(n) ≥ f*(s) – g2(n) (B) ? 比較 A、 B兩式，有 h1(n) ≥ h2(n) ，與定理條件矛盾。而由假設(shè)， A1擴(kuò)展了 n的父節(jié)點，即 n已經(jīng)被生成了。（歸納假設(shè)） ?（ 3）當(dāng) d(n)=k+1時，用反證法。 91 定理 4的證明 ?使用數(shù)學(xué)歸納法，對節(jié)點的深度進(jìn)行歸納 ?（ 1）當(dāng) d(n)＝ 0時，即只有