人工智能第三章(編輯修改稿)
2024-08-20 21:56 本頁面
【文章內(nèi)容簡介】 g*(ni)+h(ni) ≤g*(ni+1)+h(ni+1) 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 23 因為 t≤k－ 1，所以 tk 利用傳遞性，我們得到 g*(nt+1)+h(nt+1) ≤ g*(nt+2)+h(nt+2) ≤ ... ≤ g*(nk)+h(nk) 而 g(nt+1)= g*(nt+1) 所以 f(nt+1) ≤g*(nk)+h(nk)＝ g*(n)+h(n) 又已知 g*(n) ≤ g(n) (算法 A的假設） 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 24 若 g*(n)g (n),則： f(nt+1)g (n)+h(n)=f(n) 說明 A*算法選擇 n擴展時， OPEN表中有nt+1的 f值比 f(n)小，與 A*選擇 n擴展矛盾。 因此有： g(n)=g*(n)． 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 25 定理 8 如果 A*算法啟發(fā)式函數(shù) h滿足單調(diào)限制，則 A*所擴展的節(jié)點序列的估價函數(shù)值是非遞減的． 證明：設 n1和 n2是 A*擴展的點序列中相鄰的兩點， n1在前 。 若擴展 n1時， n2在 OPEN表上，顯然 : f(n1) ≤ f(n2) 單調(diào)限制的性質(zhì) …… 定理 8 8/21/2022 26 若擴展 n1時， n2不在 OPEN表上（自然也不在CLOSED上），則 A*擴展完 n1后，立刻擴展 n2 ，n2是 n1的后繼點。于是，擴展 n2時有： f(n2)=g(n2)+h(n2) =g*(n1)+c(n1,n2)+h(n2) =g(n1)+c(n1,n2)+h(n2) (由定理 7） 由單調(diào)性， c(n1,n2)+h(n2) ≥ h(n1) 所以 f(n2) ≥ g(n1)+h(n1) = f(n1) 單調(diào)限制的性質(zhì) …… 定理 8 8/21/2022 27 A*算法的總結(jié)與討論 1. A*算法搜索隱含圖時， 有解必停，且必停在最佳解路上； 2. A*算法啟發(fā)函數(shù)的啟發(fā)能力在于它所具有的啟發(fā)性信息。 在滿足 h (n) ≤h*(n)的前提下，啟發(fā)函數(shù)越大，其所包含的啟發(fā)信息越多，所擴展的節(jié)點越少； 8/21/2022 28 A*算法的總結(jié)與討論 3. 若啟發(fā)函數(shù)滿足單調(diào)限制，則每走一步都在最佳解路上，且啟發(fā)式函數(shù)不減，簡化了算法的第 7步（調(diào)整指針）； 4. 當 A*不滿足單調(diào)限制時，后擴展節(jié)點的 f函數(shù)值可能比先擴展節(jié)點的 f函數(shù)值小，可以對算法 A*做一些適當?shù)男薷?，以提高算?A*的執(zhí)行效率： 8/21/2022 29 A*算法的總結(jié)與討論 保存一個全局變量 F，存放 A*已擴展節(jié)點的估價函數(shù)值的最大值 , 根據(jù)定理 5， F≤f*(s)．若OPEN表中有節(jié)點 n，滿足 f(n)＜ F，由推論知，n最終必將被擴展． 可以不選最小的 f值而選最小的 g值．因為這些節(jié)點最終都必將被擴展．這樣能提高擴展節(jié)點在最佳路徑上的幾率，減少指針的調(diào)整，提高算法效率． 8/21/2022 30 算法 A的啟發(fā)能力 定義 設 A1和 A2是兩個啟發(fā)式算法，它們分別使用估價函數(shù) f1和 f2，如果在尋找解路徑的過程中， A1所用的計算費用比 A2少，則說 A1比 A2有較強的啟發(fā)能力，也可以說估價函數(shù) f1比 f2有較強的啟發(fā)能力． 8/21/2022 31 算法 A的啟發(fā)能力 算法 A的啟發(fā)能力受如下三個重要因素的影響 （ 1）算法 A所找到的解路徑的費用。 （ 2）算法 A在尋找這條解路徑的過程中所需要擴展的節(jié)點數(shù)。 （ 3）計算啟發(fā)函數(shù)所需要的計算量。 8/21/2022 32 h(n) ≤ h*(n) 保證了 A*的可采納性，可采納性可能意味著算法需要擴展更多的節(jié)點，使總的費用提高。 有時，犧牲可采納性可以提高算法的啟發(fā)能力。 例： h(n)=P(n)+3S(n) P(n)：每個數(shù)碼離“家”距離的和 S(n)：對 n的記分 算法 A的啟發(fā)能力 8/21/2022 33 有時，把估價函數(shù)寫成： f=g+?h的形式 ?很小時，強調(diào) 寬度優(yōu)先 ?很大時，強調(diào) 啟發(fā)分量 一般 ?與深度成反比。 算法 A的啟發(fā)能力 8/21/2022 34 正向搜索：從初始節(jié)點到目標的搜索 反向搜索：從目標節(jié)點到初始節(jié)點的搜索 雙向搜索：正向和反向搜索的結(jié)合 搜索需要產(chǎn)生的節(jié)點數(shù) 寬度優(yōu)先搜索，使用雙向搜索要優(yōu)越許多 對于啟發(fā)式搜索，評價單向搜索和雙向搜索的優(yōu)劣很復雜，使用不當可能是單向搜索量的二倍。 有關算法 8/21/2022 35 分階段搜索：為了完成搜索過程，可對搜索圖進行修剪，釋放出
環(huán)評公示相關推薦
鄂ICP備17016276號-1