【正文】 改變扇區(qū)部分 但不改變陰影部分 也不改變直徑部分 97 4，其他的搜索算法 ? 爬山法（局部搜索算法） 98 其他的搜索算法（續(xù) 1） ? 隨機(jī)搜索算法 ? 動(dòng)態(tài)規(guī)劃算法 如果對(duì)于任何 n，當(dāng) h(n)=0時(shí)， A*算法就成為了動(dòng)態(tài)規(guī)劃算法。改變陰影部分 轉(zhuǎn) 90176。 96 知識(shí)的靈活應(yīng)用 例：如何轉(zhuǎn)動(dòng)，使得每個(gè)扇區(qū)數(shù)字和為 12。 93 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) 94 h的單調(diào)化方法 ? 如果令： f(n) = max(f(n的父節(jié)點(diǎn) ), g(n)+h(n)) 則容易證明，這樣處理后的 h是單調(diào)的。 3, NEST:={ni|f(ni)fm} IF NEST ≠ ( ) THEN n:=NEST中 g最小的節(jié)點(diǎn) ELSE n:=FIRST(OPEN), fm:=f(n)。 91 改進(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) 92 修正過(guò)程 A 1, OPEN:=(s), f(s)=g(s)+h(s), fm:=0。 90 對(duì)算法加以改進(jìn) ? 一些結(jié)論： – OPEN表上任以具有 f(n) f*(s)的節(jié)點(diǎn)定會(huì)被擴(kuò)展。 88 定理 ? 由單調(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，得證。 87 h單調(diào)的性質(zhì)（續(xù)） ? 定理 ： 若 h(n)是單調(diào)的，則由 A*所擴(kuò)展的節(jié)點(diǎn)序列其 f值是非遞減的。 85 定理 （續(xù) 1） ? 由單調(diào)限制條件，對(duì) P中任意節(jié)點(diǎn) 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中 ) 86 定理 （續(xù) 2） ? 重寫(xiě)上式： 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的情況。 84 定理 ? 設(shè) n是 A*擴(kuò)展的任一節(jié)點(diǎn)。 h(ni) ni nj h(nj) c(ni,nj) 83 h單調(diào)的性質(zhì) ? 定理 ： 若 h(n)是單調(diào)的，則 A*擴(kuò)展了節(jié)點(diǎn) n之后，就已經(jīng)找到了到達(dá)節(jié)點(diǎn) n的最佳路徑。 ? 對(duì)算法加以改進(jìn) –能否對(duì)算法加以改進(jìn)，避免或減少節(jié)點(diǎn)的多次擴(kuò)展。 78 s(10) A(1) B(5) C(8) G 目標(biāo) 6 3 1 1 1 8 一個(gè)例子： 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) 79 出現(xiàn)多次擴(kuò)展節(jié)點(diǎn)的原因 ? 在前面的擴(kuò)展中，并沒(méi)有找到從初始節(jié)點(diǎn)到當(dāng)前節(jié)點(diǎn)的最短路徑，如節(jié)點(diǎn) A。 d=20, N=676, b*= 76 A*的復(fù)雜性 ? 一般來(lái)說(shuō)， A*的算法復(fù)雜性是指數(shù)型的，可以證明，當(dāng)且僅當(dāng)以下條件成立時(shí)： abs(h(n)h*(n)) ≤ O(log(h*(n))) A*的算法復(fù)雜性才是非指數(shù)型的，但是通常情況下， h與 h*的差別至少是和離目標(biāo)的距離成正比的。 ? 使用 h1： d=14, N=539, b*=。 ? 實(shí)驗(yàn)表明， b*是一個(gè)比較穩(wěn)定的常數(shù)，同一問(wèn)題基本不隨問(wèn)題規(guī)模變化。 74 對(duì) h的評(píng)價(jià)方法 ? 平均分叉樹(shù) 設(shè)共擴(kuò)展了 d層節(jié)點(diǎn)，共搜索了 N個(gè)節(jié)點(diǎn)，則 : 其中， b*稱(chēng)為平均分叉樹(shù)。 73 定理 （續(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時(shí)， A2擴(kuò)展的節(jié)點(diǎn) A1一定擴(kuò)展，有 g1(n) ≤ g2(n) (因?yàn)?A2的路 A1均走到了 ) ? 所以： h1(n) ≥ f*(s) g1(n) ≥ f*(s) – g2(n) (B) ? 比較 A、 B兩式，有 h1(n) ≥ h2(n) ，與定理?xiàng)l件矛盾。而由假設(shè)， A1擴(kuò)展了 n的父節(jié)點(diǎn)，即 n已經(jīng)被生成了。（歸納假設(shè)） ? （ 3）當(dāng) d(n)=k+1時(shí)，用反證法。