人工智能第三章-文庫吧資料
2024-08-06 21:56本頁面
【正文】 滲透度： P = L / T ＝ 18 / 43 = 若一個算法每次選取的節(jié)點(diǎn)都在解路徑上，則L＝ T ， P＝ 1； 一般搜索的滲透度 P1 ； 無信息的搜索 P1； 滲透度大，所產(chǎn)生的搜索樹向縱深發(fā)展； 滲透度小，所產(chǎn)生的搜索樹沿水平方向發(fā)展。 ? 判斷啟發(fā)能力的強(qiáng)弱主要是憑經(jīng)驗(yàn)而不是憑計算． ? 某些實(shí)現(xiàn)上的度量是可計算的。 分階段搜索并不能保證找到一條解路徑。 把 OPEN表具有最小 f值的一些節(jié)點(diǎn)打上標(biāo)記，記住這些結(jié)點(diǎn)和通向這些點(diǎn)的最佳路徑，刪去搜索圖其余部分。 算法 A的啟發(fā)能力 8/21/2022 34 正向搜索：從初始節(jié)點(diǎn)到目標(biāo)的搜索 反向搜索：從目標(biāo)節(jié)點(diǎn)到初始節(jié)點(diǎn)的搜索 雙向搜索：正向和反向搜索的結(jié)合 搜索需要產(chǎn)生的節(jié)點(diǎn)數(shù) 寬度優(yōu)先搜索，使用雙向搜索要優(yōu)越許多 對于啟發(fā)式搜索，評價單向搜索和雙向搜索的優(yōu)劣很復(fù)雜，使用不當(dāng)可能是單向搜索量的二倍。 有時，犧牲可采納性可以提高算法的啟發(fā)能力。 （ 3）計算啟發(fā)函數(shù)所需要的計算量。 在滿足 h (n) ≤h*(n)的前提下，啟發(fā)函數(shù)越大，其所包含的啟發(fā)信息越多，所擴(kuò)展的節(jié)點(diǎn)越少； 8/21/2022 28 A*算法的總結(jié)與討論 3. 若啟發(fā)函數(shù)滿足單調(diào)限制，則每走一步都在最佳解路上，且啟發(fā)式函數(shù)不減，簡化了算法的第 7步（調(diào)整指針）； 4. 當(dāng) A*不滿足單調(diào)限制時，后擴(kuò)展節(jié)點(diǎn)的 f函數(shù)值可能比先擴(kuò)展節(jié)點(diǎn)的 f函數(shù)值小，可以對算法 A*做一些適當(dāng)?shù)男薷?，以提高算?A*的執(zhí)行效率： 8/21/2022 29 A*算法的總結(jié)與討論 保存一個全局變量 F，存放 A*已擴(kuò)展節(jié)點(diǎn)的估價函數(shù)值的最大值 , 根據(jù)定理 5， F≤f*(s)．若OPEN表中有節(jié)點(diǎn) n，滿足 f(n)＜ F，由推論知，n最終必將被擴(kuò)展． 可以不選最小的 f值而選最小的 g值．因?yàn)檫@些節(jié)點(diǎn)最終都必將被擴(kuò)展．這樣能提高擴(kuò)展節(jié)點(diǎn)在最佳路徑上的幾率，減少指針的調(diào)整，提高算法效率． 8/21/2022 30 算法 A的啟發(fā)能力 定義 設(shè) A1和 A2是兩個啟發(fā)式算法，它們分別使用估價函數(shù) f1和 f2，如果在尋找解路徑的過程中， A1所用的計算費(fèi)用比 A2少，則說 A1比 A2有較強(qiáng)的啟發(fā)能力，也可以說估價函數(shù) f1比 f2有較強(qiáng)的啟發(fā)能力． 8/21/2022 31 算法 A的啟發(fā)能力 算法 A的啟發(fā)能力受如下三個重要因素的影響 （ 1）算法 A所找到的解路徑的費(fèi)用。 若擴(kuò)展 n1時， n2在 OPEN表上，顯然 : f(n1) ≤ f(n2) 單調(diào)限制的性質(zhì) …… 定理 8 8/21/2022 26 若擴(kuò)展 n1時， n2不在 OPEN表上（自然也不在CLOSED上），則 A*擴(kuò)展完 n1后，立刻擴(kuò)展 n2 ，n2是 n1的后繼點(diǎn)。 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 21 當(dāng)算法 A*選擇 n進(jìn)行擴(kuò)展時： 設(shè) P中從 n0開始，串 n0， … ， nt都在CLOSED表中，即 nt是 P中從左向右 CLOSED表中的最后一個節(jié)點(diǎn)，且 nt ≠n. 此時， nt的后繼節(jié)點(diǎn) nt+1在 OPEN表中． 因?yàn)?P是從 s到 nk的最佳路，所以 : g(nt+1)= g*(nt+1) 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 22 由已知 h(n)滿足 單調(diào)限制，對任意 i=0,…,k 1,有 g*(ni)+h(ni) ≤g*(ni)+c(ni, ni+1)+ h(ni+1) 而 ni和 ni+1都在最佳路徑上，故 g*(ni+1) =g*(ni)+c(ni, ni+1) 因此 g*(ni)+h(ni) ≤g*(ni+1)+h(ni+1) 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 23 因?yàn)?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的假設(shè)） 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 24 若 g*(n)g (n),則： f(nt+1)g (n)+h(n)=f(n) 說明 A*算法選擇 n擴(kuò)展時， OPEN表中有nt+1的 f值比 f(n)小，與 A*選擇 n擴(kuò)展矛盾。 A*算法的比較 …… 定理 6 8/21/2022 19 定義 如果啟發(fā)函數(shù) h對任何節(jié)點(diǎn) ni和 nj，只要 nj是 ni的后繼，都有 h(ni
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1