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