人工智能原理知識(shí)表示教學(xué)課件

人工智能原理第2章搜索技術(shù)(下)第2章搜索技術(shù)本章內(nèi)容2.1搜索與問(wèn)題求解22無(wú)信息搜索策略23啟發(fā)式搜索策略24局部搜索算法p>→2.5約束滿足問(wèn)題2.6博弈搜索參考書目附錄A算法可采納性的證明第2章搜索技術(shù)24局部搜索算法24.1局部搜索與最優(yōu)化242爬山法搜索24.3模擬退火搜索244局部剪枝搜索24.5遺傳算法第2章搜索技術(shù)局部搜索算法前面的搜索算法都是保留搜索路徑的,到達(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ù)局部搜索算法的應(yīng)用集成電路設(shè)計(jì)工廠場(chǎng)地布局車間作業(yè)調(diào)度°自動(dòng)程序設(shè)計(jì)電信網(wǎng)絡(luò)優(yōu)化車輛尋徑文件夾管理(《《第2章搜索技術(shù)2.4.1局部搜索與最優(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ù),而不考慮(沒有)“目標(biāo)測(cè)試”和“路徑耗散”局部搜索算法適用于最優(yōu)化問(wèn)題第2章搜索技術(shù)狀態(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ù)局部搜索算法本節(jié)簡(jiǎn)要介紹以下4種局部搜索算法介紹其算法思想爬山法搜索模擬退火搜索局部剪枝搜索遺傳算法從搜索的角度看遺傳算法也是搜索假設(shè)空間的一種方法(學(xué)習(xí)問(wèn)題歸結(jié)為搜索問(wèn)題)—生成后繼假設(shè)的方式第2章搜索技術(shù)2.4.2爬山法搜索爬山法(Chill-climbing)就是向值增加的方向持續(xù)移動(dòng)一登高過(guò)程/如果相鄰狀態(tài)中沒有比它更高的值,則算法結(jié)束于頂峰·爬山法搜索算法思想(1)令初始狀態(tài)S為當(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ài),使新狀態(tài)的估計(jì)值優(yōu)于當(dāng)前狀態(tài)的估計(jì)