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