【正文】 72 定理 ? 使用數(shù)學(xué)歸納法，對節(jié)點的深度進行歸納 ? （ 1）當(dāng) d(n)＝ 0時，即只有一個節(jié)點，顯然定理成立。 70 A*算法的性質(zhì)（續(xù) 7） 定理 ：設(shè)對同一個問題定義了兩個 A*算法 A1和 A2，若 A2比 A1有較多的啟發(fā)信息，即對所有非目標(biāo)節(jié)點有 h2(n) h1(n)，則在具有一條從 s到 t的路徑的隱含圖上，搜索結(jié)束時，由 A2所擴展的每一個節(jié)點，也必定由 A1所擴展，即 A1擴展的節(jié)點數(shù)至少和 A2一樣多。 ?如果 n≠ n’，由于 A*選擇 n擴展，而不是n’，所以有 f(n) ≤ f(n’ )≤f*(s)。 ?由引理 A*結(jié)束前， OPEN中存在節(jié)點 n’， f(n’ )≤f*(s) ?設(shè)此時 A*選擇 n擴展。得證。 68 可采納性的證明 ? 由定理 、 A*一定找到一條路徑結(jié)束 ? 設(shè)找到的路徑 s→ t 不是最佳的（ t為目標(biāo)） 則： f(t) = g(t) f*(s) ? 由引理 OPEN中存在 f(n)≤f*(s)的節(jié)點n，所以 f(n) ≤ f*(s) f(t) ? 因此 A*應(yīng)選擇 n擴展，而不是 t。得證。 由定理 ，知 A*一定結(jié)束，由 A*的結(jié)束條件， OPEN表中 f(t)最小時才結(jié)束。 引理 ： A*如果不結(jié)束，則 OPEN中所有的 n有f(n) f*(s) 引理 ：在 A*結(jié)束前，必存在節(jié)點 n，使得 f(n) ≤ f*(s) 所以，如果 A*不結(jié)束，將導(dǎo)致矛盾。 存在一個節(jié)點 n， n在 最佳路徑上。 63 A*算法的性質(zhì)（續(xù) 2） 引理 ： 對無限圖，若有從初始節(jié)點 s到目標(biāo)節(jié)點 t的路徑，則 A*不結(jié)束時，在 OPEN表中即使最小的一個 f值也將增到任意大，或有 f(n)f*(s)。 60 A*條件舉例 ? 8數(shù)碼問題 – h1(n) = “不在位”的將牌數(shù) – h2(n) = 將牌“不在位”的距離和 2 8 3 1 6 4 7 5 1 2 3 4 5 7 6 8 將牌 1： 1 將牌 2： 1 將牌 6： 1 將牌 8： 2 61 A*算法的性質(zhì) ? A*算法的假設(shè) 設(shè) ni、 nj是任意兩個節(jié)點，有： C(ni, nj) ? 其中 ?為大于 0的常數(shù) ? 幾個等式 f*(s) = f*(t) = h*(s) = g*(t) = f*(n) 其中 s是初始節(jié)點， t是目標(biāo)節(jié)點， n是 s到 t的最佳路徑上的節(jié)點。 53 A算法（續(xù)） ADD(mj, OPEN), 標(biāo)記 mj到 n的指針； IF f(n, mk)f(mk) THEN f(mk):=f(n, mk), 標(biāo)記 mk到 n的指針； IF f(n, ml)f(ml,) THEN f(ml):=f(n, ml), 標(biāo)記 ml到 n的指針 , ADD(ml, OPEN)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 3, n:=FIRST(OPEN)。 50 1，啟發(fā)式搜索算法 A（ A算法） ? 評價函數(shù)的格式： f(n) = g(n) + h(n) f(n)：評價函數(shù) h(n)：啟發(fā)函數(shù) 51 符號的意義 ? g*(n)：從 s到 n的最短路徑的耗散值 ? h*(n)：從 n到 g的最短路徑的耗散值 ? f*(n)=g*(n)+h*(n)：從 s經(jīng)過 n到 g的最短路徑的耗散值 ? g(n)、 h(n)、 f(n)分別是 g*(n)、 h*(n)、 f*(n)的估計值 52 A算法 1, OPEN:=(s), f(s):=g(s)+h(s)。 ? 啟發(fā)信息的強度 –強：降低搜索工作量，但可能導(dǎo)致找不到最 優(yōu)解 –弱：一般導(dǎo)致工作量加大，極限情況下變?yōu)? 盲目搜索，但可能可以找到最優(yōu)解 48 希望： ? 引入啟發(fā)知識，在保證找到最佳解的情況下，盡可能減少搜索范圍，提高搜索效率。 ? 思想 首先給回溯法一個比較小的深度限制，然后逐漸增加深度限制，直到找到解或找遍所以分支為止。 9, GO LOOP。 7, IF 目標(biāo)在 {mi}中 THEN EXIT(SUCCESS)。 5, REMOVE(n, OPEN), ADD(n, CLOSED)。 3, n:=FIRST(OPEN)。 41 2 3 1 8 4 7 6 5 2 3 1 8 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 8 3 1 4 7 6 5 2 8 3 1 6 4 7 5 2 8 3 1 6 4 7 5 2 8 3 7 1 4 6 5 8 3 2 1 4 7 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 7 8 4 6 5 1 2 3 8 4 7 6 5 2 8 3 6 4 1 7 5 2 8 3 1 6 7 5 4 8 3 2 1 4 7 6 5 2 8 3 7 1 4 6 5 2 8 1 4 3 7 6 5 2 8 3 1 4 5 7 6 1 2 3 4 5 6 7 8 9 a b c d 1 2 3 8 4 7 6 5 目標(biāo) 42 深度優(yōu)先搜索的性質(zhì) ? 一般不能保證找到最優(yōu)解 ? 當(dāng)深度限制不合理時，可能找不到解，可以將算法改為可變深度限制 ? 最壞情況時，搜索空間等同于窮舉 ? 與回溯法的差別：圖搜索 ? 是一個通用的與問題無關(guān)的方法 43 寬度優(yōu)先搜索 1, G:=G0(G0=s), OPEN:=(s), CLOSED:=( )。