人工智能第三章-文庫(kù)吧
2025-07-09 21:56 本頁(yè)面
【正文】 法 A*選擇的任意擴(kuò)展點(diǎn)都有 f(n)≤f*(s) 證明：若 n是目標(biāo)點(diǎn)，由定理 4， f(n)≤f*(s) 若 n不是目標(biāo)點(diǎn)，由定理 2 ， A*算法終止前，OPEN表中總有一點(diǎn) n’，使 f(n’)≤f*(s) 此時(shí)，算法 A*選擇 n而沒(méi)有選擇 n’，必有： f(n)≤ f(n’)≤f*(s) 證畢。 A*算法的可采納性 8/21/2022 13 定義 設(shè) A1和 A2是兩個(gè) A*算法，分別使用如下兩個(gè)估價(jià)函數(shù)： f1(n)=g1(n)+h1(n) f2(n)=g2(n)+h2(n) 其中， h1(n)和 h2(n)是 h*的兩個(gè)下界．若對(duì)于所有的非目標(biāo)節(jié)點(diǎn) n，都有 h2(n)＞ h1(n)，則稱算法A2比算法 A1有較多的信息． A*算法的比較 8/21/2022 14 討論：?jiǎn)l(fā)函數(shù)的啟發(fā)能力在于它所具有的啟發(fā)性信息。 1. 當(dāng) h(n)≡0時(shí)，反映了啟發(fā)函數(shù)完全沒(méi)有啟發(fā)信息，要擴(kuò)展較多的節(jié)點(diǎn)． 2. 在具有可采納性的前提下， 0≤h≤h*， h*定出了 h的上界，當(dāng) h越接近 h*時(shí)，它的啟發(fā)能力就越大． A*算法的比較 8/21/2022 15 例 八碼難題的 A*算法的比較． 圖 ： f1(n)=d(n)， h1(n)≡0，采用寬度優(yōu)先搜索 ； 圖 ： f2(n)=d(n)+w(n)， h2(n)≡w(n)． 對(duì)于所有非目標(biāo)節(jié)點(diǎn)，有 h2(n)＞ h1(n)，因此，圖 用算法不但比圖 ，而且擴(kuò)展的節(jié)點(diǎn)數(shù)要少。 A*算法的比較 8/21/2022 16 定理 6 如果 A1和 A2是兩個(gè) A*算法，算法 A2比 A1有較多的信息，且它們搜索同一個(gè)隱含圖。若該圖存在解路徑，當(dāng)這兩個(gè)算法終止時(shí)， A2所擴(kuò)展的每一節(jié)點(diǎn)也必由 A1所擴(kuò)展，即： A2擴(kuò)展的節(jié)點(diǎn)數(shù) ≤A1擴(kuò)展的節(jié)點(diǎn)數(shù) 證明：對(duì) A2搜索樹(shù)中的節(jié)點(diǎn)深度使用數(shù)學(xué)歸納法。設(shè) n是 A2所擴(kuò)展的任一節(jié)點(diǎn)， p(n)記 n在搜索樹(shù)中的深度，往證 n被 A1擴(kuò)展。 A*算法的比較 …… 定理 6 8/21/2022 17 當(dāng) p(n)=0時(shí)， n＝ s．若 s不是目標(biāo)節(jié)點(diǎn)，這兩個(gè)算法都必將擴(kuò)展 s 。若 s是目標(biāo)節(jié)點(diǎn)，這兩個(gè)算法都不必?cái)U(kuò)展任意節(jié)點(diǎn)（包括 s）． 假設(shè) p(n) ≤k時(shí)， n被算法 A2擴(kuò)展， n也被算法A1所擴(kuò)展 . 設(shè) p(n) ＝ k＋ 1，因節(jié)點(diǎn) n被 A2擴(kuò)展，由于 n的祖先點(diǎn)被 A2擴(kuò)展，根據(jù)歸納假設(shè)，節(jié)點(diǎn) n的在 A2搜索樹(shù)中的所有祖先都被算法 A1所擴(kuò)展． A*算法的比較 …… 定理 6 8/21/2022 18 因此，節(jié)點(diǎn) n在 A1的搜索樹(shù)中，且在 A1的搜索樹(shù)中存在一條從 s到 n的路。由于 A2搜索樹(shù)中點(diǎn) n之前的樹(shù)是 A1搜索中點(diǎn) n之前的樹(shù)的子樹(shù)， g1(n) ≤ g2(n) 又因?yàn)?h1(n) h2(n)，所以 f1(n) f2(n). 由于 n被 A2擴(kuò)展，由定理 5知： f2(n) ≤ f*(s) 故 f1(n) f2(n) ≤ f*(s) . 由推論知，點(diǎn) n必被 A1擴(kuò)展，歸納完成。 A*算法的比較 …… 定理 6 8/21/2022 19 定義 如果啟發(fā)函數(shù) h對(duì)任何節(jié)點(diǎn) ni和 nj，只要 nj是 ni的后繼，都有 h(ni)－ h(nj)≤c(ni, nj) h(t)=0 （ t是目標(biāo)節(jié)點(diǎn)） 則稱啟發(fā)函數(shù) h滿足單調(diào)限制． 單調(diào)限制 8/21/2022 20 定理 7 如果 A*算法的啟發(fā)函數(shù) h滿足單調(diào)限制，則當(dāng)算法 A*選擇節(jié)點(diǎn) n擴(kuò)展時(shí)，就已經(jīng)發(fā)現(xiàn)了通向節(jié)點(diǎn) n的最佳路徑，即 g(n)=g*(n)． 證明：設(shè) n是算法 A*選出擴(kuò)展的任一節(jié)點(diǎn)。 ?若 n=s，則 g(n)=g*(n)=0，算法 A*已發(fā)現(xiàn)通向 s的最佳路徑． ?若 n≠s，設(shè)序列 P=(s=n0， n1， … ， nk=n)是從 s到 n的一條最佳路徑 (不知道是否在 A*的搜索樹(shù)中 )。 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 21 當(dāng)算法 A*選擇 n進(jìn)行擴(kuò)展時(shí)： 設(shè) P中從 n0開(kāi)始，串 n0， … ， nt都在CLOSED表中，即 nt是 P中從左向右 CLOSED表中的最后一個(gè)節(jié)點(diǎn)，且 nt ≠n. 此時(shí)， 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)限制，對(duì)任意 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) 因此
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1