【正文】 )－ h(nj)≤c(ni, nj) h(t)=0 （ t是目標節(jié)點） 則稱啟發(fā)函數(shù) h滿足單調(diào)限制． 單調(diào)限制 8/21/2022 20 定理 7 如果 A*算法的啟發(fā)函數(shù) h滿足單調(diào)限制，則當算法 A*選擇節(jié)點 n擴展時，就已經(jīng)發(fā)現(xiàn)了通向節(jié)點 n的最佳路徑，即 g(n)=g*(n)． 證明：設 n是算法 A*選出擴展的任一節(jié)點。若 s是目標節(jié)點，這兩個算法都不必擴展任意節(jié)點（包括 s）． 假設 p(n) ≤k時， n被算法 A2擴展， n也被算法A1所擴展 . 設 p(n) ＝ k＋ 1，因節(jié)點 n被 A2擴展，由于 n的祖先點被 A2擴展，根據(jù)歸納假設，節(jié)點 n的在 A2搜索樹中的所有祖先都被算法 A1所擴展． A*算法的比較 …… 定理 6 8/21/2022 18 因此，節(jié)點 n在 A1的搜索樹中，且在 A1的搜索樹中存在一條從 s到 n的路。設 n是 A2所擴展的任一節(jié)點， p(n)記 n在搜索樹中的深度，往證 n被 A1擴展。 A*算法的比較 8/21/2022 16 定理 6 如果 A1和 A2是兩個 A*算法，算法 A2比 A1有較多的信息，且它們搜索同一個隱含圖。 A*算法的可采納性 8/21/2022 13 定義 設 A1和 A2是兩個 A*算法，分別使用如下兩個估價函數(shù)： f1(n)=g1(n)+h1(n) f2(n)=g2(n)+h2(n) 其中， h1(n)和 h2(n)是 h*的兩個下界．若對于所有的非目標節(jié)點 n，都有 h2(n)＞ h1(n)，則稱算法A2比算法 A1有較多的信息． A*算法的比較 8/21/2022 14 討論：啟發(fā)函數(shù)的啟發(fā)能力在于它所具有的啟發(fā)性信息。 因此，算法 A*算法終止前應選 n’去擴展，而不會選 t，與算法 A*終止于 t矛盾。 由定理 2知，算法 A*終止前的任何時刻， OPEN表中總存在一個節(jié)點 n’， 使得 f(n’) ≤f*(s)，算法 A*不會終止在第 3步，因此必終止在第 5步，因找到一個目標節(jié)點而結束。證畢。 A*算法的可采納性 8/21/2022 9 推論 OPEN表中的任一滿足 f(n)f*(n)的節(jié)點 n，最終將被算法 A*選作擴展節(jié)點 證明：設目標節(jié)點集為 {ti}，顯然， f(ti)≥f*(s) 由定理 3知， A*必停止。 由定理 2知，算法 A*終止前的任何時刻， OPEN表中總存在一個節(jié)點 n’， 使得 f(n’) ≤f*(s) 。 A*算法的可采納性 …… 定理 2 8/21/2022 8 定理 3 若存在從 s到目標的解路，則算法 A*必終止。 由 A*的定義，有 f(n’)= g(n’)+ h(n’) A*算法的可采納性 8/21/2022 7 因為 n’處在通往目標的最佳解路徑上， 設 (n0,n1,……, n’)是 s到 n’的最佳解路徑。 于是有 g*(n)≥d*(n).e 又 g(n)≥g*(n)≥d*(n).e ， f(n)= g(n)+h(n) ，且 h(n) ≥0 因此 f(n)≥ g(n)≥ d*(n) .e 若 A*不終止， OPEN表中節(jié)點的 d*值會不斷增大，因此f值也會不斷增大。 A*算法的可采納性 8/21/2022 5 引理 1 若 A*不終止， OPEN表中節(jié)點的估價函數(shù)值可以無限變大。 對有限圖來說，顯然這一循環(huán)不能無限進行下去。 證明： GRAPHSEARCH算法將在第 3步將 OPEN表中的節(jié)點用光而結束；或在第 5步，找到目標節(jié)點而結束。 8/21/2022 3 A*算法的可采納性 如果一個搜索算法對于任何具有解路徑的圖都能找到一條最佳路徑，則稱此算法為可采納的。8/21/2022 1 人工智能原理 8/21/2022 2 A*算法的可采納性 設 f(n)=g(n)+h(n)，我們稱使用 f(n)做為估價函數(shù)的 GRAPHSEARCH算法為 算法 A。 其中，假定 g*(n) ≤ g(n) 如果算法 A中使用的啟發(fā)函數(shù) h(n)對任何節(jié)點 n都有 h(n)≤h*(n)，則稱其為 算法 A*。 可以證明： A*算法是可采納的 （如果解路徑存在， A*一定終止找到最佳解路徑） 8/21/2022 4 定理 1 GRAPHSEARCH對有限圖必然終止。 在算法的每一次循環(huán)都要從 OPEN表中刪除一個節(jié)點，并生成有限個后繼加到 OPEN表中。結論得證。 證明：設 n是 OPEN表中的任的一節(jié)點， d*(n)是隱含圖中從 s到 n的最短路徑的長度， e是圖中每條弧的最小費用。 A*算法的可采納性 8/21/2022 6 定理 2 若存在 s到 目標的路，則 算法 A*終止前的任何時刻，OPEN表中總存在一個節(jié)點 n’， n’在從 s到目標的最佳路徑上，且滿足 f(n’) ≤f*(s) 證明： 設 P： n0,n1,……,n k是一條最佳解路徑，其中， nk是目標點，