人工智能第三章(已修改)
2025-08-05 21:56 本頁面
【正文】 8/21/2022 1 人工智能原理 8/21/2022 2 A*算法的可采納性 設(shè) f(n)=g(n)+h(n)，我們稱使用 f(n)做為估價(jià)函數(shù)的 GRAPHSEARCH算法為 算法 A。 其中，假定 g*(n) ≤ g(n) 如果算法 A中使用的啟發(fā)函數(shù) h(n)對任何節(jié)點(diǎn) n都有 h(n)≤h*(n)，則稱其為 算法 A*。 8/21/2022 3 A*算法的可采納性 如果一個(gè)搜索算法對于任何具有解路徑的圖都能找到一條最佳路徑，則稱此算法為可采納的。 可以證明： A*算法是可采納的 （如果解路徑存在， A*一定終止找到最佳解路徑） 8/21/2022 4 定理 1 GRAPHSEARCH對有限圖必然終止。 證明： GRAPHSEARCH算法將在第 3步將 OPEN表中的節(jié)點(diǎn)用光而結(jié)束；或在第 5步，找到目標(biāo)節(jié)點(diǎn)而結(jié)束。 在算法的每一次循環(huán)都要從 OPEN表中刪除一個(gè)節(jié)點(diǎn)，并生成有限個(gè)后繼加到 OPEN表中。 對有限圖來說，顯然這一循環(huán)不能無限進(jìn)行下去。結(jié)論得證。 A*算法的可采納性 8/21/2022 5 引理 1 若 A*不終止， OPEN表中節(jié)點(diǎn)的估價(jià)函數(shù)值可以無限變大。 證明：設(shè) n是 OPEN表中的任的一節(jié)點(diǎn)， d*(n)是隱含圖中從 s到 n的最短路徑的長度， e是圖中每條弧的最小費(fèi)用。 于是有 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*值會(huì)不斷增大，因此f值也會(huì)不斷增大。 A*算法的可采納性 8/21/2022 6 定理 2 若存在 s到 目標(biāo)的路，則 算法 A*終止前的任何時(shí)刻，OPEN表中總存在一個(gè)節(jié)點(diǎn) n’， n’在從 s到目標(biāo)的最佳路徑上，且滿足 f(n’) ≤f*(s) 證明： 設(shè) P： n0,n1,……,n k是一條最佳解路徑，其中， nk是目標(biāo)點(diǎn)， n0=s. 在 A*結(jié)束之前，從左向右掃描序列 P， n’是 P中第一個(gè)在 OPEN表中的節(jié)點(diǎn) (這樣的 n’是存在的：因?yàn)殚_始 n0在 OPEN上，算法結(jié)束前，若擴(kuò)展 ni，則 ni+1在 OPEN上，此時(shí)不可能擴(kuò)展到 nk)。 由 A*的定義，有 f(n’)= g(n’)+ h(n’) A*算法的可采納性 8/21/2022 7 因?yàn)?n’處在通往目標(biāo)的最佳解路徑上， 設(shè) (n0,n1,……, n’)是 s到 n’的最佳解路徑。 n’的所有祖先都在 CLOSED表上，所以 (n0,n1,……, n’) 是 A*發(fā)現(xiàn)的一條通向 n’的最佳解路徑， g(n’)= g*(n’) 由 A*算法知： h(n’)≤h*(n’)， 故 f(n’)≤g*(n’)+h*(n’)= f*(n’) 而對最佳路上任意一點(diǎn) n，有： f*(n’)= f*(s) 因此， f(n’)≤f*(s) 證畢。 A*算法的可采納性 …… 定理 2 8/21/2022 8 定理 3 若存在從 s到目標(biāo)的解路，則算法 A*必終止。 證明： 若算法 A*不終止， 由引理 1知， OPEN表中任意節(jié)點(diǎn)的 f值隨著算法A*的運(yùn)行可以任意增大。 由定理 2知，算法 A*終止前的任何時(shí)刻， OPEN表中總存在一個(gè)節(jié)點(diǎn) n’， 使得 f(n’) ≤f*(s) 。 矛盾。 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*必停止。 若停在第 3步，則 OPEN表中的任一節(jié)點(diǎn)都被擴(kuò)展； 若停在第 5步，則 OPEN表中 f(n)f*(s)= f*(n)的節(jié)點(diǎn)必在找到 ti之前被擴(kuò)展。證畢。 A*算法的可采納性 8/21/2022 10 定理 4 算法 A*是可采納的（即如果解路徑存在， A*一定找到最佳解路徑而終止）． 證明：由定理 3知，算法 A*必終止。 由定理 2知，算法 A*終止前的任何時(shí)刻， OPEN表中總存在一個(gè)節(jié)點(diǎn) n’， 使得 f(n’) ≤f*(s)，算法 A*不會(huì)終止在第 3步，因此必終止在第 5步，因找到一個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束。 設(shè) t是算法 A*找到的目標(biāo)點(diǎn)， （下面用反證法證明 t 在最佳解路上） A*算法的可采納性 8/21/2022 11 若 t 不在最佳解路徑上，則 f(t) = g(t) ＞ f*(s) 由定理 2， A*算法終止前， OPEN表中總有一點(diǎn) n’，使 f(n’)≤f*(s)，因此 f(n’)≤f(t)；在 OPEN表的排序中，節(jié)點(diǎn) n’應(yīng)排在節(jié)點(diǎn) t的前面。 因此，算法 A*算法終止前應(yīng)選 n’去擴(kuò)展，而不會(huì)選 t，與算法 A*終止于 t矛盾。 證畢 A*算法的可采納性 …… 定理 4 8/21/2022 12 定理 5 算
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1