【正文】 8 4 7 6 5 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 8 3 7 1 4 6 5 1 2 3 8 4 7 6 5 3 4 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 23 24 25 26 22 2 3 4 1 8 5 7 6 2 3 4 1 8 7 6 5 2 8 1 4 3 7 6 5 2 4 8 1 3 7 6 5 2 8 3 1 4 5 7 6 2 8 3 1 5 7 4 6 2 8 1 4 3 7 6 5 2 4 8 1 3 7 6 5 2 8 3 1 6 7 5 4 2 8 1 6 3 7 5 4 8 3 4 2 1 7 6 5 8 1 3 2 4 7 6 5 8 3 2 1 4 7 6 5 8 1 3 2 4 7 6 5 2 8 3 7 4 6 1 5 2 3 7 8 4 6 1 5 2 8 3 7 4 6 1 5 2 8 3 7 1 6 5 4 解的路徑： 1－ 3－ 8－ 16－ 26 2 8 3 1 4 7 6 5 2 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 2 8 3 1 4 7 6 5 1 A*算法（例 h1(x)=0=h*(n)) ?擴展節(jié)點數(shù)： 25 ?生成節(jié)點數(shù)： 44 2 8 3 1 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 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1（ 3） 3(4) 4(5) 5(5) 7(6) A*算法 (例 ) h2(x)=w(x） =h*(n) 2（ 4） 解的路徑： 1－ 3－ 8－ 10－ 11 6(5) 8(4) 9(6) 10(4) 1 2 3 7 8 4 6 5 11(4) 12(6) ?擴展節(jié)點數(shù)： 10 ?生成節(jié)點數(shù)： 12 2 8 3 1 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 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1（ 4） 3(4) 4(6) 5(6) A*算法 (例 ) h3(x)=p(x)=h(n) 2（ 6） 解的路徑： 1－ 3－ 6－ 8－ 9 6(4) 7(6) 8(4) 1 2 3 7 8 4 6 5 9(4) 10(6) ?擴展節(jié)點數(shù)： 4 ?生成節(jié)點數(shù)： 10 2 8 3 1 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 3 1 8 4 7 6 5 2 3 1 8 4 7 6 5 1 2 3 8 4 7 6 5 1 2 3 8 4 7 6 5 1 h*=4,g*=1 W=3 P=3,f=4 啟發(fā)式函數(shù)比較 (例 ) h2(x)=w(x) h3(x)=p(x) W=3 P=5,f=6 h*=2,g*=2 W=3 P=2 f=4 h*=1,g*=3 W=1 P=1,f=4 1 2 3 7 8 4 6 5 h*=4,g*=0 W=3 P=4,f=4 3 6 2 8 9 h*=0,g*=4 W=0 P=0,f=4 4 W=4 P=5,f=6 5 W=4 P=5,f=6 7 W=4 P=4,f=6 10 W=2 P=2,f=6 擴展節(jié)點數(shù)： 4 生成節(jié)點數(shù)： 9 最佳全局搜索算法 A* ? A*算法含義 –在 A算法中，如果滿足條件： h(n)≤h*(n) 則 A算法稱為 A*算法。 改進的條件 ? 可采納性不變 ? 不多擴展節(jié)點 ? 不增加算法的復(fù)雜性 對 h加以限制 ? 定義：一個啟發(fā)函數(shù) h，如果對所有節(jié)點ni和 nj，其中 nj是 ni的子節(jié)點，滿足 h(ni) h(nj) ≤ c(ni, nj) h(t) = 0(t為目標節(jié)點） 或 h(ni) ≤ c(ni, nj) + h(nj) h(t) = 0 則稱 h是單調(diào)的。 算法的可采納性 可納性的含義： 對任一狀態(tài)空間圖，當從初始節(jié)點到目標節(jié)點有路徑存在 時，如果搜索算法總能在 有限步驟內(nèi) 找到一條從初始節(jié)點到目標節(jié)點的 最佳路徑 ，并在此路徑上結(jié)束，則稱該搜索算法是可采納的。 啟發(fā)函數(shù)強弱對結(jié)果的影響 2 ? h(n)滿足單調(diào)性限制下的 A*算法更好 ? 原因： 能夠保證，每當擴展一個節(jié)點時就已經(jīng)找到了通往這個節(jié)點的最佳路徑。 ? 重復(fù)上述過程，直到目標狀態(tài)出現(xiàn)在子節(jié)點中或者沒有可供操作的節(jié)點為止。 ? 基本思想 ? 圖搜索分類 狀態(tài)空間搜索的基本思想 ? 先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現(xiàn)在這些子節(jié)點中。一般來說，在滿足 h(n) ≤h*(n)的前提下， h(n)的值越大越好。 ? 在 h(n)滿足單調(diào)性限制下的 A*算法常被稱為改進的 A*算法。 ? 證明見書 定理 、定理 、定理 A*算法效率問題 ? A*算法評價 ? 如何設(shè)計搜索算法 – 找到最優(yōu)解并使擴展的節(jié)點數(shù)盡可能少 . s(10) A(1) B(5) C(8) G 目標 6 3 1 1 1 8 另一個例子 (有 h(n)h*(n)函數(shù)）： OPEN表 CLOSED表 s(10) s(10) SA(7) SB(8) SC(9) SA(7) s(10) SB(8) SC(9) SAG(14) SBA(5) SC(9) SAG(14) SC(9) SBAG(12) SAG(14) SCB(7) SBAG(12) SAG(14) SCBA(4) SBAG(12) SAG(14) SCBAG(11) SBAG(12) SAG(14) SB(8) SA(7)s(10) SBA(5) SB(8) SA(7) s(10) SC(9) SBA(5) SA(7) s(10) SCB(7) SC(9) SBA(5) SA(7) s(10) SCBA(4)SCB(7) SC(9) SBA(5) SA(7) s(10) SCBAG(11) s A B C G 目標 6 3 1 1 1 8 一個例子 (無 H函數(shù)）： OPEN表 CLOSED表 s(10) s(10) SC(1) SB(3) SA(6) SC(1) s(10) SCB(2) SB(3) SA(6) SCBA(3) SB(3) SA(6) SB(3) SA(6) SCBAG(11) SBA(4) SA(6) SCBAG(11) SA(6) SCBAG(11) SBAG(12) SCBAG(11) SBAG(12) SAG(14) SCB(2) SC(1)s(10) SCBA(3) SCB(2) SC(1) s(10) SB(3) SCBA(3) SCB(2)SC(1) s(10) SBA(4) SB(3) SCBA(3) SCB(2) SC(1) s(10) SA(6) SBA(4) SB(3) SCBA(3) SCB(2)SC(1) s(10) 目標 2： A*算法效率討論 ? A*算法評價 ? 如何設(shè)計搜索算法 – 找到最優(yōu)解并使擴展的節(jié)點數(shù)盡可能少 .