人工智能第三章(文件)
【正文】 1) 因此 g*(ni)+h(ni) ≤g*(ni+1)+h(ni+1) 單調限制的性質 …… 定理 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的假設） 單調限制的性質 …… 定理 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擴展矛盾。 在滿足 h (n) ≤h*(n)的前提下，啟發(fā)函數(shù)越大，其所包含的啟發(fā)信息越多，所擴展的節(jié)點越少； 8/21/2022 28 A*算法的總結與討論 3. 若啟發(fā)函數(shù)滿足單調限制，則每走一步都在最佳解路上，且啟發(fā)式函數(shù)不減，簡化了算法的第 7步（調整指針）； 4. 當 A*不滿足單調限制時，后擴展節(jié)點的 f函數(shù)值可能比先擴展節(jié)點的 f函數(shù)值小，可以對算法 A*做一些適當?shù)男薷?，以提高算?A*的執(zhí)行效率： 8/21/2022 29 A*算法的總結與討論 保存一個全局變量 F，存放 A*已擴展節(jié)點的估價函數(shù)值的最大值 , 根據(jù)定理 5， F≤f*(s)．若OPEN表中有節(jié)點 n，滿足 f(n)＜ F，由推論知，n最終必將被擴展． 可以不選最小的 f值而選最小的 g值．因為這些節(jié)點最終都必將被擴展．這樣能提高擴展節(jié)點在最佳路徑上的幾率，減少指針的調整，提高算法效率． 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所找到的解路徑的費用。 有時，犧牲可采納性可以提高算法的啟發(fā)能力。 把 OPEN表具有最小 f值的一些節(jié)點打上標記，記住這些結點和通向這些點的最佳路徑，刪去搜索圖其余部分。 ? 判斷啟發(fā)能力的強弱主要是憑經(jīng)驗而不是憑計算． ? 某些實現(xiàn)上的度量是可計算的。 當最佳解路短時，可能有較高的滲透度； 當最佳解路長時，算法產(chǎn)生節(jié)點的數(shù)目將以更快的速度增加，可能有較低的滲透度。使用連接符的費用可以計算解圖的費用． 設從節(jié)點 n到終止節(jié)點集合 N的解圖的費用用 k(n, N)表示，則 k(n, N)遞歸定義如下： 1. 若 n是 N中的元素，則 k（ n,N） =0； 8/21/2022 54 與 /或圖搜索 2. 若有從 n出發(fā)的一個連接符指向它的解圖后繼節(jié)點｛ n1， … ， ni｝，設此連接符的費用為Cn，則 : k(n, N)= Cn+ k(n1, N)+…+k(n i, N) 最佳解圖：具有最低費用的解圖 8/21/2022 55 與 /或圖搜索 假定 h*(n)是從 n出發(fā)的最佳解圖的費用，而 h(n)是 h*(n)的估計值。 8/21/2022 57 與 /或圖搜索 …… 算法 AO* Procedure AO* 1．建立一個只由根節(jié)點構成的搜索圖 G．設s的費用 q(s) = h(s), G’=G． 如果 s是目標，標記 s為 SOLVED. 2．直到 s被標上 SOLVED， do： 3． begin 4． 通過跟蹤從 s出發(fā)的有標記的連接符計算部分解圖 G’（ G的連接符將在以后的步驟中標記） 5．在 G’中選一個非終止的葉節(jié)點 n（以后我們將討論怎樣選這樣一個節(jié)點）． 6．擴展節(jié)點 n產(chǎn)生 n的所有后繼，并把這些后繼連到圖 G上，對于每一個不曾在 G中出現(xiàn)的后繼 nj，設其費用 q(nj)=h(nj)，如果這些后繼中某些節(jié)點是終止節(jié)點，則用 SOLVED標記。 8．直到 S變空， do： 9． begin 10．從 S中刪除節(jié)點 m，這個 m在 G中的后裔不出現(xiàn)在 S中 與 /或圖搜索 …… 算法 AO* 8/21/2022 60 11． 按以下步驟修改 m的費用 q（ m）：對于每一個從 m出發(fā)的指向節(jié)點集合 {n1i， … ， nki}的連接符計算 qi(m)=ci+q(n1i)+…+q(nki) ，這里的 q(nji)或者是在本循環(huán)內部的上述某步驟中算出的值或者是在步驟 6中被
環(huán)評公示相關推薦
鄂ICP備17016276號-1