【正文】 ? 重復上述過程，直到目標狀態(tài)出現在子節(jié)點中或者沒有可供操作的節(jié)點為止。 ? 基本思想 ? 圖搜索分類 狀態(tài)空間搜索的基本思想 ? 先把問題的初始狀態(tài)作為當前擴展節(jié)點對其進行擴展，生成一組子節(jié)點，然后檢查問題的目標狀態(tài)是否出現在這些子節(jié)點中。 啟發(fā)函數強弱對結果的影響 2 ? h(n)滿足單調性限制下的 A*算法更好 ? 原因： 能夠保證，每當擴展一個節(jié)點時就已經找到了通往這個節(jié)點的最佳路徑。一般來說，在滿足 h(n) ≤h*(n)的前提下， h(n)的值越大越好。 算法的可采納性 可納性的含義： 對任一狀態(tài)空間圖，當從初始節(jié)點到目標節(jié)點有路徑存在 時，如果搜索算法總能在 有限步驟內 找到一條從初始節(jié)點到目標節(jié)點的 最佳路徑 ，并在此路徑上結束，則稱該搜索算法是可采納的。 ? 在 h(n)滿足單調性限制下的 A*算法常被稱為改進的 A*算法。 改進的條件 ? 可采納性不變 ? 不多擴展節(jié)點 ? 不增加算法的復雜性 對 h加以限制 ? 定義：一個啟發(fā)函數 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是單調的。 ? 證明見書 定理 、定理 、定理 A*算法效率問題 ? A*算法評價 ? 如何設計搜索算法 – 找到最優(yōu)解并使擴展的節(jié)點數盡可能少 . s(10) A(1) B(5) C(8) G 目標 6 3 1 1 1 8 另一個例子 (有 h(n)h*(n)函數）： 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函數）： 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*算法評價 ? 如何設計搜索算法 – 找到最優(yōu)解并使擴展的節(jié)點數盡可能少 . 出現多次擴展節(jié)點的原因 ? 在前面的擴展中，并沒有找到從初始節(jié)點到當前節(jié)點的最短路徑，如節(jié)點 A。 ? 可采納性的衡量： f*(n)=g*(n)+h*(n) ? 例 重排九宮問題 f(x)=d(x)+h(x) ? h1(x)=0 ? h2(x):錯位棋牌的個數 ? h3(x):每個將牌與其目標位置之間的距離和 2 8 3 1 4 7 6 5 1 2 3 8 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 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 1 2 3 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é)點數： 25 ?生成節(jié)點數： 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é)點數： 10 ?生成節(jié)點數： 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é)點數： 4 ?生成節(jié)點數： 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