【正文】 66 ??剪枝算法的說明 ? ??剪枝 可以應(yīng)用樹的任何深度，許多情況下可以剪掉整個(gè)子樹 / 其原則是 —如果在節(jié)點(diǎn) n的父節(jié)點(diǎn)或者更上層的節(jié)點(diǎn)有一個(gè)更好的選擇 m，則在實(shí)際游戲 (搜索 )中永遠(yuǎn)不會(huì)到達(dá) n ? ?=到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的 MAX最佳選擇 ? ?=到目前為止在路徑上任意點(diǎn)發(fā)現(xiàn)的 MIN最佳選擇 ? ??搜索不斷更新 ?/?值，當(dāng)某個(gè)節(jié)點(diǎn)的值分別比 ?/?值更差時(shí)剪掉該節(jié)點(diǎn)的剩余分支 第 2章 搜索技術(shù) 67 ??剪枝的效率 ? ??剪枝的效率很大程度上取決于檢查后繼節(jié)點(diǎn)的次序 —應(yīng)該先檢查那些可能最好的后繼 ? 如果能夠先檢查那些最好的后繼，則 ??剪枝算法只需檢查 O(bd/2)個(gè)節(jié)點(diǎn)以決定最佳招數(shù) / 極大極小值算法為 O(bd)—有效分支因子 b到 b的平方根 —效率大大提高 第 2章 搜索技術(shù) 68 本章復(fù)習(xí)提示 ? 嘗試使用搜索方式求解問題 / 注意本章的搜索算法都是通用算法，即沒有考慮具體任務(wù)的相關(guān)知識(shí) ? 具體搜索問題的形式化表示 (初始狀態(tài) /后繼函數(shù) /搜索代價(jià)等 ) ? 了解各種搜索算法 (包括局部搜索和博弈搜索 )的思想、相關(guān)性質(zhì)和性能 ? 嘗試用啟發(fā)式搜索算法 (A*算法 )解決一些游戲問題 ? 約束滿足問題的相關(guān)概念 第 2章 搜索技術(shù) 69 參考書目 ? Stuart Russell / Peter Norvig: AIMA 第 3章 / 第 4章 / 第 5章 / 第 6章 ? 陸汝鈐 編著 : 人工智能 (上冊(cè) ) 第 5章 / 第 6章 / 第 8章 / 第 9章 ? 田盛豐、黃厚寬，人工智能與知識(shí)工程，中國鐵道出版社， 1999年 8月第 1版，第 4章 / 第 9章 第 2章 搜索技術(shù) 70 附錄 A*算法可采納性的證明 第 2章 搜索技術(shù) 71 A*算法可采納性 ? 定理： ? A*算法是可采納的，即若存在從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg的路徑，則 A*算法必能結(jié)束在最佳路徑上 ? 證明的過程： ? 首先證明 A*算法必定成功結(jié)束 ? 其次證明 A*算法結(jié)束時(shí)中止于最佳路徑 第 2章 搜索技術(shù) 72 證明的步驟 ? 證明分為三步： (1)對(duì)于有限圖， A*算法一定成功結(jié)束 (2)對(duì)于無限圖， A*算法一定成功結(jié)束 (3)A*算法必定終止于最佳路徑上 ? 對(duì)于無限圖情況的證明，引入 2個(gè)引理 (1)如果 A*算法不終止，則存在 f值任意大的節(jié)點(diǎn) (2)A*算法結(jié)束前，仍有耗散值更小的節(jié)點(diǎn)待擴(kuò)展 第 2章 搜索技術(shù) 73 定理 1的證明 (1) ? 定理 1— 對(duì)于有限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則 A*算法一定成功結(jié)束 ? 證明： ? 首先證明算法必定會(huì)結(jié)束 ? 由于搜索圖為有限圖，如果算法能找到解，則會(huì)成功結(jié)束；如果算法找不到解，則必然會(huì)由于 Open表變空而結(jié)束。因此， A*算法必然會(huì)結(jié)束 第 2章 搜索技術(shù) 74 定理 1的證明 (2) ? 然后證明算法一定會(huì)成功結(jié)束 ? 由于至少存在一條由初始節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的路徑，設(shè)此路徑為 ? S0= n0， n1 ， … ， nk =Sg ? 算法開始時(shí)，節(jié)點(diǎn) n0在 Open表中，而且路徑中任一節(jié)點(diǎn) ni離開 Open表后，其后繼節(jié)點(diǎn)ni+1必然進(jìn)入 Open表，這樣，在 Open表變?yōu)榭罩?，目?biāo)節(jié)點(diǎn)必然出現(xiàn)在 Open表中 / 因此，算法必定會(huì)成功結(jié)束 ★ 第 2章 搜索技術(shù) 75 引理 1的證明 (1) ? 引理 1—對(duì)無限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，且 A*算法不終止的話，則從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 f值 ? 證明： ? 設(shè) d*(n)是 A*算法生成的從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的最短路徑長度，由于搜索圖中每條邊的代價(jià)都是一個(gè)正數(shù)，令這些正數(shù)中最小的一個(gè)數(shù)是 e, 則有 第 2章 搜索技術(shù) endng ?? )()( **76 引理 1的證明 (2) ? 因?yàn)槭亲罴崖窂降拇鷥r(jià)，故有 ? 又因?yàn)?h(n)≥ 0，故有 ? 如果 A*算法不終止的話，從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 d*(n)值，因此，也將具有任意大的 f值 ★ endng ??? )()(g(n) **第 2章 搜索技術(shù) endngnhngnf ????? )()()()()( *77 引理 2的證明 (1) ? 引理 2—在 A*算法終止前的任何時(shí)刻，Open表中總存在節(jié)點(diǎn) n’，它是從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn)，且滿足 ? 證明： ? 設(shè)從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) t的最佳路徑序列為 S0 = n0， n1， … ， nk =Sg ? 算法開始時(shí)，節(jié)點(diǎn) S0在 Open表中，當(dāng)節(jié)點(diǎn) S0離開 Open進(jìn)入 Closed表時(shí)，節(jié)點(diǎn) n1進(jìn)入 Open表 第 2章 搜索技術(shù) )()(0* Sfnf ??78 引理 2的證明 (2) ? 因此， A*沒有結(jié)束以前，在 Open表中必存在最佳路徑上的節(jié)點(diǎn) ? 設(shè)這些節(jié)點(diǎn)排在最前面的節(jié)點(diǎn)為 n’,則有 f(n’)=g(n’)+h(n’) ? 由于 n’在最佳路徑上，故有 g(n’)=g*(n’), 從而f(n’)=g*(n’)+h(n’) ? 又由于 A*算法滿足 h(n’)≤h*(n’), 故有f(n’)≤g*(n’)+h*(n’)=f*(n’) ? 因?yàn)樵谧罴崖窂缴系乃泄?jié)點(diǎn)的 f*值都應(yīng)相等，因此有 f(n’)≤f*(S0) ★ 第 2章 搜索技術(shù) 79 定理 2的證明 ? 定理 2—對(duì)于無限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，則 A*算法必然會(huì)結(jié)束 ? 證明： (反證法 ) ? 假設(shè) A*算法不結(jié)束，由引理 1知 Open表中的節(jié)點(diǎn)有任意大的 f值，這與引理 2的結(jié)論相矛盾，因此， A*算法只能成功結(jié)束 ★ ? 推論 1—Open表中任一具有 f(n)≤f(S0)的節(jié)點(diǎn) n，最終都被 A*算法選作為擴(kuò)展節(jié)點(diǎn) 第 2章 搜索技術(shù) 80 定理 3的證明 (1) ? 定理 3—A*算法是可采納的，即若存在從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg的路徑，則 A*算法必能結(jié)束在最佳路徑上 ? 證明： ? 證明過程分以下兩步進(jìn)行 ? 先證明 A*算法一定能夠終止在某個(gè)目標(biāo)節(jié)點(diǎn)上 —由定理 1和定理 2可知，無論是對(duì)有限圖還是無限圖， A*算法都能夠找到某個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束 第 2章 搜索技術(shù) 81 定理 3的證明 (2) ? 再證明 A*算法只能終止在最佳路徑上 (反證法 ) ? 假設(shè) A*算法未能終止在最佳路徑上，而是終止在某個(gè)目標(biāo)節(jié)點(diǎn) Sg處，則有f(Sg)=g(Sg)f*(S0) ? 由引理 2可知，在 A*算法結(jié)束前，必有最佳路徑上的一個(gè)節(jié)點(diǎn) n’在 Open表中且有 ? f(n’)≤f*(S0)f(Sg) ? 這時(shí)， A*算法一定會(huì)選擇 n’來擴(kuò)展，而不可能選擇 Sg，從而也不會(huì)去測(cè)試目標(biāo)節(jié)點(diǎn) Sg，這就與假設(shè) A*算法終止在目標(biāo)節(jié)點(diǎn)相矛盾 / 因此， A*算法只能終止在最佳路徑上 ★ 第 2章 搜索技術(shù) 82 推論 2 ? 推論 2—在 A*算法中，對(duì)任何被擴(kuò)展的任一節(jié)點(diǎn) n，都有 f(n)≤ f*(S0) ? 證明： ? 令 n是由 A*選作擴(kuò)展的任一節(jié)點(diǎn)，因此 n不會(huì)是目標(biāo)節(jié)點(diǎn)，且搜索沒有結(jié)束 / 由引理 2可知，在 Open表中有滿足 f(n’)≤f*(S0)的節(jié)點(diǎn) n’ ? 若 n=n’, 則有 f(n)≤f*(S0) ? 否則， 算法既然選擇 n擴(kuò)展，那就必有f(n)≤f(n’) ? 所以有 f(n)≤f*(S0) ★ 第 2章 搜索技術(shù) 83 演講完畢，謝謝觀看！