【正文】 ， … ， nk =Sg ? 算法開(kāi)始時(shí)，節(jié)點(diǎn) n0在 Open表中，而且路徑中任一節(jié)點(diǎn) ni離開(kāi) Open表后，其后繼節(jié)點(diǎn)ni+1必然進(jìn)入 Open表，這樣，在 Open表變?yōu)榭罩埃繕?biāo)節(jié)點(diǎn)必然出現(xiàn)在 Open表中 / 因此，算法必定會(huì)成功結(jié)束 ★ 第 2章 搜索技術(shù) 78 引理 1的證明 (1) ? 引理 1—對(duì)無(wú)限圖，如果從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg有路徑存在，且 A*算法不終止的話(huà)，則從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 f值 ? 證明： ? 設(shè) d*(n)是 A*算法生成的從初始節(jié)點(diǎn) S0到節(jié)點(diǎn) n的最短路徑長(zhǎng)度，由于搜索圖中每條邊的代價(jià)都是一個(gè)正數(shù)，令這些正數(shù)中最小的一個(gè)數(shù)是 e, 則有 第 2章 搜索技術(shù) endng ?? )()( **79 引理 1的證明 (2) ? 因?yàn)槭亲罴崖窂降拇鷥r(jià)，故有 ? 又因?yàn)?h(n)≥ 0，故有 ? 如果 A*算法不終止的話(huà)，從 Open表中選出的節(jié)點(diǎn)必將具有任意大的 d*(n)值，因此，也將具有任意大的 f值 ★ endng ??? )()(g(n) **第 2章 搜索技術(shù) endngnhngnf ????? )()()()()( *80 引理 2的證明 (1) ? 引理 2—在 A*算法終止前的任何時(shí)刻，Open表中總存在節(jié)點(diǎn) n’，它是從初始節(jié)點(diǎn)S0到目標(biāo)節(jié)點(diǎn)的最佳路徑上的一個(gè)節(jié)點(diǎn)，且滿(mǎn)足 ? 證明： ? 設(shè)從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) t的最佳路徑序列為 S0 = n0， n1， … ， nk =Sg ? 算法開(kāi)始時(shí)，節(jié)點(diǎn) S0在 Open表中，當(dāng)節(jié)點(diǎn) S0離開(kāi) Open進(jìn)入 Closed表時(shí)，節(jié)點(diǎn) n1進(jìn)入 Open表 第 2章 搜索技術(shù) )()(0* Sfnf ??81 引理 2的證明 (2) ? 因此， A*沒(méi)有結(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*算法滿(mǎn)足 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ù) 82 定理 2的證明 ? 定理 2—對(duì)于無(wú)限圖，如果從初始節(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ù) 83 定理 3的證明 (1) ? 定理 3—A*算法是可采納的，即若存在從初始節(jié)點(diǎn) S0到目標(biāo)節(jié)點(diǎn) Sg的路徑，則 A*算法必能結(jié)束在最佳路徑上 ? 證明： ? 證明過(guò)程分以下兩步進(jìn)行 ? 先證明 A*算法一定能夠終止在某個(gè)目標(biāo)節(jié)點(diǎn)上 —由定理 1和定理 2可知，無(wú)論是對(duì)有限圖還是無(wú)限圖， A*算法都能夠找到某個(gè)目標(biāo)節(jié)點(diǎn)而結(jié)束 第 2章 搜索技術(shù) 84 定理 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’來(lái)擴(kuò)展，而不可能選擇 Sg，從而也不會(huì)去測(cè)試目標(biāo)節(jié)點(diǎn) Sg，這就與假設(shè) A*算法終止在目標(biāo)節(jié)點(diǎn)相矛盾 / 因此， A*算法只能終止在最佳路徑上 ★ 第 2章 搜索技術(shù) 85 推論 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)，且搜索沒(méi)有結(jié)束 / 由引理 2可知，在 Open表中有滿(mǎn)足 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ù) 86 演講完畢，謝謝觀看！ 。人工智能原理 第 2章 搜索技術(shù) （下） 1 本章內(nèi)容 搜索與問(wèn)題求解 無(wú)信息搜索策略 啟發(fā)式搜索策略 局部搜索算法 約束滿(mǎn)足問(wèn)題 博弈搜索 參考書(shū)目 附錄 A*算法可采納性的證明 第 2章 搜索技術(shù) 2 局部搜索算法 局部搜索與最優(yōu)化 爬山法搜索 模擬退火搜索 局部剪枝搜索 遺傳算法 第 2章 搜索技術(shù) 3 局部搜索算法 ? 前面的搜索算法都是保留搜索路徑的，到達(dá)目標(biāo)的路徑就是問(wèn)題的解 — 然而許多問(wèn)題中到達(dá)目標(biāo)的路徑是無(wú)關(guān)緊要的 ? 與系統(tǒng)地搜索狀態(tài)空間 (保留各種路徑 )相對(duì)，不關(guān)心路徑的搜索算法就是局部搜索算法 ? 局部搜索從一個(gè)單獨(dú)的當(dāng)前狀態(tài)出發(fā)，通常只移動(dòng)到相鄰狀態(tài) ? 典型情況下搜索的路徑不保留 第 2章 搜索技術(shù) 4 局部搜索算法的應(yīng)用 ? 應(yīng)用領(lǐng)域 ? 集成電路設(shè)計(jì) ? 工廠場(chǎng)地布局 ? 車(chē)間作業(yè)調(diào)度 (Job Shop Schedule) ? 自動(dòng)程序設(shè)計(jì) ? 電信網(wǎng)絡(luò)優(yōu)化 ? 車(chē)輛尋徑 ? 文件夾管理 ? 局部搜索也稱(chēng)為優(yōu)化算法 — wiki中表示為local search (optimization) 第 2章 搜索技術(shù) 5 局部搜索與最優(yōu)化問(wèn)題 ? 局部搜索算法的優(yōu)點(diǎn)： ? 只使用很少的內(nèi)存 (通常是一個(gè)常數(shù) ) ? 經(jīng)常能在不適合系統(tǒng)化算法的很大或無(wú)限的狀態(tài)空間中找到合理的解 ? 最優(yōu)化問(wèn)題 — 根據(jù)一個(gè)目標(biāo)函數(shù)找到最佳狀態(tài) / 只有目標(biāo)函數(shù)，而不考慮 (沒(méi)有 )“目標(biāo)測(cè)試 ” 和“路徑耗散” ? 局部搜索算法適用于最優(yōu)化問(wèn)題 第 2章 搜索技術(shù) 6 狀態(tài)空間地形圖 (1) 第 2章 搜索技術(shù) 山肩 目標(biāo)函數(shù) 全 局 最 大值 局 部 最 大值 “ 平坦 ” 局部最大值 狀態(tài)空間 當(dāng)前狀態(tài) 7 狀態(tài)空間地形圖 (2) ? 在狀態(tài)圖中，既有“位置” (用狀態(tài)表示 )又有“高度 ”( 用耗散值或目標(biāo)函數(shù)值表示 ) ? 如果高度對(duì)應(yīng)于耗散值，則目標(biāo)是找到全局最小值，即圖中最低點(diǎn) ? 如果高度對(duì)應(yīng)于目標(biāo)函數(shù)，則目標(biāo)是找到全局最大值，即圖中最高峰 ? 如果存在解，則完備的局部搜索算法能夠找到解 ? 而最優(yōu)的局部搜索算法能夠找到全局最大或最小值 第 2章 搜索技術(shù) 8 局部搜索算法 ? 本節(jié)簡(jiǎn)要介紹以下 4種局部搜索算法 / 介紹其算法思想 ? 爬山法搜索 ? 模擬退火搜索 ? 局部剪枝搜索 ? 遺傳算法 ?從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法 (學(xué)習(xí)問(wèn)題歸結(jié)為搜索問(wèn)題 )— 生成后繼假設(shè)的方式 第 2章 搜索技術(shù) 9 爬山法搜索 ? 爬山法 (hillclimbing)—就是向值增加的方向持續(xù)移動(dòng) —登高過(guò)程 / 如果相鄰狀態(tài)中沒(méi)有比它更高的值，則算法結(jié)束于頂峰 ? 爬山法搜索算法思想： (1)令初始狀態(tài) S0為當(dāng)前狀態(tài) (2)若當(dāng)前狀態(tài)已經(jīng)達(dá)標(biāo)，則算法運(yùn)行結(jié)束，搜索成功 (3)若存在一個(gè)動(dòng)作可以作用于當(dāng)前狀態(tài)以產(chǎn)生一個(gè)新?tīng)顟B(tài)，使新?tīng)顟B(tài)的估計(jì)值優(yōu)于當(dāng)前狀態(tài)的估計(jì)值，則放棄當(dāng)前狀態(tài)，并令剛產(chǎn)生的新?tīng)顟B(tài)為當(dāng)前狀態(tài)，轉(zhuǎn) (2) (4)取當(dāng)前狀態(tài)為相對(duì)最優(yōu)解，停止執(zhí)行算法 第 2章 搜索技術(shù) 10 爬山法搜索的局限