【文章內(nèi)容簡介】 84567（ 6）（ 5） （ 5）12 38 456712 38 4567（ 5） （ 7）12 38 456712384567（ 6） （ 7）1 2 38 4567（ 5）81 3245671 2 38 4567（ 5） （ 7）圖 八數(shù)碼難題的有序搜索樹12 3846（ 4）3334A算法? 利用評價函數(shù) f(n) = g(n) + h(n) 來排列 OPEN表節(jié)點順序的圖搜索算法稱為 A算法 。? 實現(xiàn)類型：局部擇優(yōu)搜索、全局擇優(yōu)搜索局部擇優(yōu)搜索 類似深度優(yōu)先? 基本思想：在當前擴展的子節(jié)點中選 f(x) 值最小的子節(jié)點為下一個考察的節(jié)點? 實現(xiàn)：節(jié)點 n擴展后的各子節(jié)點計算出估價值后，按由小到大次序放到 OPEN表的首部? 分析：可把深度優(yōu)先、代價樹的深度優(yōu)先看成其特例。全局擇優(yōu)搜索 類似廣度優(yōu)先? 節(jié)點 n擴展后的各子節(jié)點計算出估價值后，送入 OPEN表，然后 OPEN表中全部節(jié)點按估價值由小到大排35 A*算法 (Algorithm A*)? 幾個有用的記號 f（ x） =g（ x） +h（ x）f*(x) = g*（ x） +h*（ x）g*（ x）：從節(jié)點 S到節(jié)點 x的一條最佳路徑的實際代價 h*（ x）：從節(jié)點 x到某目標節(jié)點的一條最佳路徑的代價f*(x)： 從 S開始約束通過節(jié)點 x的一條最佳路徑的代價? 分析：g是 g*（ x）的估計；對于 g（ n）來說，一個明顯的選擇就是搜索樹中從Ｓ到 n這段路徑的代價，這一代價可以由從 n到Ｓ尋找指針時，把所遇到的各段弧線的代價加起來給出（這條路徑就是到目前為止用搜索算法找到的從 S到 n的最小代價路徑 )。這個定義包含了 g（ x） ≥ g*（ x ） 。h是 h*（ x）的估計；對于 h（ n），它依賴于有關問題的領域的啟發(fā)信息。36A*算法 又稱最佳圖搜索算法，由著名人工智能學者Nilsson提出 。? 定義：如果 A算法中使用的啟發(fā)函數(shù) h(n)對任何節(jié)點 n都有h(n)≤h*(n)，則稱其為 A*算法 (Algorithm A*)。? 對于寬度優(yōu)先搜索算法， h(n)=0，滿足 h(n)≤h*(n)。寬度優(yōu)先算法是 A*算法的特殊情形。? A*算法的性質(zhì)：（ 1）可采納性– 如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳解路徑。則稱此算法是可采納的。– 結論： A*算法是可采納的? 證明：– 對有限圖， A*算法一定會在有限步結束– 對無限圖，只有從 S0到 Sg有路徑存在，則 A*算法也必然會結束– A*算法一定會終止在最優(yōu)路徑上37a)對有限圖， A*算法一定會在有限步結束證明：因為搜索圖為有限圖，所以會出現(xiàn)以下情況：– 算法找到解，則成功結束（算法第 4步）– 算法找不到解，則必然會因 OPEN表變空而結束（算法第 2步）b)對無限圖，只有從 S0到 Sg有路徑存在，則 A*算法也必然會結束證明 ： （分 2步）– 第 1步證明 ： A*結束前 ,OPEN表中必存在節(jié)點 n，它 是最佳路徑上的一個節(jié)點，且滿足 f(n)=f*(s)? 證明 : 設從初始節(jié)點 s到目標節(jié)點 t的一條最佳路徑序列為 (n0 = s, n1, …, nk = t) 38? 算法初始化時 ,s在 OPEN中 ,由于 A*沒有結束 ,在 OPEN中存在最佳路徑上的節(jié)點。設 OPEN表中的第一個 節(jié)點 n是 處在最佳路徑序列中 (至少有一個這樣的節(jié)點 ,因 s一開始是在 OPEN上 ),顯然 n的先輩節(jié)點 np,已在 CLOSED中 ,因此能找到 s到 np,的最佳路徑 ,而 n也在最佳路徑上 ,因而 s到 n的最佳路徑也能找到 ,因此有：f(n)=g(n)+h(n)=g*(n)+h(n)≤g*(n)+h*(n)=f*(n) 因為：最佳路徑上的所有節(jié)點的 f*值都應相等所以 f(n)≤f*(s)。 [證畢 ]? 第 2步證明 A*算法一定會終止證明： （反證法）? 假定 A*不結束 ,設：e圖中各邊的最小代價d*(n)從 s到任一節(jié)點 n的最短路徑長度 (設每個弧的長度均為 1)39 所以 g*(n)≥ d*(n)e因 g(n) ≥ g*(n) 所以 g(n) ≥ d*(n)e因 h(n) ≥ 0 (設 h(n) ≥ 0) 所以 f(n) = g(n) + h(n) ≥ g(n)所以 f(n) ≥ d*(n)e若 A*不結束 ,則隨著搜索的進行， d*(n)會無限增大 ,所以 f值將增到任意大，這與第 1步證明的結果 “ f(n)≤f*(s)” 矛盾，因 f*(s)一定是有限值。所以， A*算法一定會終止c) A*算法一定會終止在最優(yōu)路徑上證明：反證法若 A*算法不是在最優(yōu)路徑上終止，而是在某個目標節(jié)點 t結束則 f(t) = g(t) f*(s)而根據(jù) b)證明可知：在 A*結束前， OPEN表中存在最優(yōu)路徑上的節(jié)點 n, 且有 f(n) ≤f*(s), 所以 f(n) ≤f*(s) f(t) 這時算法 A*應選 n作為當前點擴展 , 不可能選 t, 從而也不會去測試目標節(jié)點 t, 即這與假定 A*選 t結束矛盾。所以 A*只能結束在最佳路徑上。 [證畢 ]40（ 2） A*算法的最優(yōu)性 （信息性）? 應用 A*的過程中 ,如果選作擴展的節(jié)點 n,其評價函數(shù)值 f(n)=f*(n),則不會去擴展多余的節(jié)點就可找到解。可以想像到 f(n)越接近于 f*(n),擴展的節(jié)點數(shù)就會越少 ,即啟發(fā)函數(shù)中 ,應用的啟發(fā)信息 (問題知識 )愈多 ,擴展的節(jié)點數(shù)就較少。? 定理 : 有 A*算法 A1， A2, A1： f1(n) = g1(n) + h1(n) A2： f2(n) = g2(n) + h2(n) 若 A2比 A1有較多的啟發(fā)信息 (即對所有非目標節(jié)點均有 h2(n) h1(n)), 則在搜索過程中， 被 A2擴展的節(jié)點也必定由 A1擴展 , 即 A1擴展的節(jié)點不會比 A2擴展的節(jié)點少，亦即 A2擴展的節(jié)點集是 A1擴展的節(jié)點集的子集 。 41證明 : 使數(shù)學歸納法 , 對節(jié)點的深度應用歸納法 。 (1) 對深度 d(n)=0的節(jié)點 (即初始節(jié)點 s), 若 s為目標節(jié)點 , 則 A1和A2都不擴展 s, 否則 A1和 A2都擴展了 s (2) 設深度 d(n) ≤k時 , 對所有路徑的端節(jié)點 , 定理結論都成立。 (3) 證明 d(n)=k+1時 , 所有路徑的端節(jié)點 ,結論成立 。（ 反證法）設 A2搜索樹上有一個節(jié)點 n(d(n)=k+1)被 A2擴展了 ,而對應于 A1搜索樹上的這個節(jié)點 n,沒有被 A1擴展 。根據(jù)歸納法假設條件 ,A1擴展了 n的父節(jié)點 ,n是在 A1搜索樹上 ,因此 A1結束時 ,n必定保留在其 OPEN表上 ,n沒有被 A1選擇擴展 ,有 f1(n)≥ f*(s),即 g1(n)+h1(n)≥ f*(s)所以 h1(n)≥ f*(s)g1(n)16