人工智能第三章-wenkub
2022-08-21 21:56:54 本頁面
【正文】 是否在 A*的搜索樹中 )。 A*算法的比較 …… 定理 6 8/21/2022 17 當 p(n)=0時， n＝ s．若 s不是目標節(jié)點，這兩個算法都必將擴展 s 。 1. 當 h(n)≡0時，反映了啟發(fā)函數(shù)完全沒有啟發(fā)信息，要擴展較多的節(jié)點． 2. 在具有可采納性的前提下， 0≤h≤h*， h*定出了 h的上界，當 h越接近 h*時，它的啟發(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)． 對于所有非目標節(jié)點，有 h2(n)＞ h1(n)，因此，圖 用算法不但比圖 ，而且擴展的節(jié)點數(shù)要少。 設(shè) t是算法 A*找到的目標點， （下面用反證法證明 t 在最佳解路上） A*算法的可采納性 8/21/2022 11 若 t 不在最佳解路徑上，則 f(t) = g(t) ＞ f*(s) 由定理 2， A*算法終止前， OPEN表中總有一點 n’，使 f(n’)≤f*(s)，因此 f(n’)≤f(t)；在 OPEN表的排序中，節(jié)點 n’應(yīng)排在節(jié)點 t的前面。 若停在第 3步，則 OPEN表中的任一節(jié)點都被擴展； 若停在第 5步，則 OPEN表中 f(n)f*(s)= f*(n)的節(jié)點必在找到 ti之前被擴展。 證明： 若算法 A*不終止， 由引理 1知， OPEN表中任意節(jié)點的 f值隨著算法A*的運行可以任意增大。 A*算法的可采納性 8/21/2022 6 定理 2 若存在 s到 目標的路，則 算法 A*終止前的任何時刻，OPEN表中總存在一個節(jié)點 n’， n’在從 s到目標的最佳路徑上，且滿足 f(n’) ≤f*(s) 證明： 設(shè) P： n0,n1,……,n k是一條最佳解路徑，其中， nk是目標點， n0=s. 在 A*結(jié)束之前，從左向右掃描序列 P， n’是 P中第一個在 OPEN表中的節(jié)點 (這樣的 n’是存在的：因為開始 n0在 OPEN上，算法結(jié)束前，若擴展 ni，則 ni+1在 OPEN上，此時不可能擴展到 nk)。結(jié)論得證。 可以證明： A*算法是可采納的 （如果解路徑存在， A*一定終止找到最佳解路徑） 8/21/2022 4 定理 1 GRAPHSEARCH對有限圖必然終止。8/21/2022 1 人工智能原理 8/21/2022 2 A*算法的可采納性 設(shè) f(n)=g(n)+h(n)，我們稱使用 f(n)做為估價函數(shù)的 GRAPHSEARCH算法為 算法 A。 證明： GRAPHSEARCH算法將在第 3步將 OPEN表中的節(jié)點用光而結(jié)束；或在第 5步，找到目標節(jié)點而結(jié)束。 A*算法的可采納性 8/21/2022 5 引理 1 若 A*不終止， OPEN表中節(jié)點的估價函數(shù)值可以無限變大。 由 A*的定義，有 f(n’)= g(n’)+ h(n’) A*算法的可采納性 8/21/2022 7 因為 n’處在通往目標的最佳解路徑上， 設(shè) (n0,n1,……, n’)是 s到 n’的最佳解路徑。 由定理 2知，算法 A*終止前的任何時刻， OPEN表中總存在一個節(jié)點 n’， 使得 f(n’) ≤f*(s) 。證畢。 因此，算法 A*算法終止前應(yīng)選 n’去擴展，而不會選 t，與算法 A*終止于 t矛盾。 A*算法的比較 8/21/2022 16 定理 6 如果 A1和 A2是兩個 A*算法，算法 A2比 A1有較多的信息，且它們搜索同一個隱含圖。若 s是目標節(jié)點，這兩個算法都不必擴展任意節(jié)點（包括 s）． 假設(shè) p(n) ≤k時， n被算法 A2擴展， n也被算法A1所擴展 . 設(shè) p(n) ＝ k＋ 1，因節(jié)點 n被 A2擴展，由于 n的祖先點被 A2擴展，根據(jù)歸納假設(shè)，節(jié)點 n的在 A2搜索樹中的所有祖先都被算法 A1所擴展． A*算法的比較 …… 定理 6 8/21/2022 18 因此，節(jié)點 n在 A1的搜索樹中，且在 A1的搜索樹中存在一條從 s到 n的路。 單調(diào)限制的性質(zhì) …… 定理 7 8/21/2022 21 當算法 A*選擇 n進行擴展時： 設(shè) P中從 n0開始，串 n0， … ， nt都在CLOSED表中，即 nt是 P中從左向右 CLOSED表中的最后一個節(jié)點，且 nt ≠n. 此時， nt的后繼節(jié)點 nt+1在 OPEN表中． 因為 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+
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1