人工智能的搜索算法.pptx

1、人工智能的搜索算法1在智能過程中，搜索是不可避免的 Nilsson一個(gè)物理符號(hào)系統(tǒng)解決任何智能問題的充分和必要條件 Newell2搜索法簡(jiǎn)介搜索法是人工智能中問題求解的基本方法可大致分為有信息搜索和無信息搜索約束滿足問題和博弈問題的求解均可表述為搜索過程Agent的學(xué)習(xí)過程亦可表述為搜索過程搜索法的本質(zhì)是在狀態(tài)空間中從問題的初始狀態(tài)搜索到通向目標(biāo)狀態(tài)的路徑3搜索法簡(jiǎn)介當(dāng)前的智能計(jì)算方法本質(zhì)上也是搜索方法，如神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法等搜索法的設(shè)計(jì)主要考慮解路徑的耗散值以及搜索過程中的耗散值耗費(fèi)最低化4算法性能的評(píng)價(jià)評(píng)價(jià)算法性能的四個(gè)方面：完備性：有解時(shí)能保證找到解（可判定問題）最優(yōu)性：能否找

2、到最優(yōu)解時(shí)間復(fù)雜度空間復(fù)雜度5搜索算法的評(píng)價(jià)搜索法要處理的是狀態(tài)空間圖在人工智能領(lǐng)域，狀態(tài)空間圖是由初始狀態(tài)和后繼函數(shù)隱含表示的（與通常的計(jì)算機(jī)圖搜索算法不同）搜索算法可從以下三個(gè)方面評(píng)價(jià)：b:分支因子d:最淺目標(biāo)節(jié)點(diǎn)的深度m:狀態(tài)空間中最大路徑長(zhǎng)度（考慮耗散）6問題的形式化搜索法首先要對(duì)問題進(jìn)行形式化描述問題通?？尚问交x為下述四個(gè)部分Agent所處的初始狀態(tài)Agent可采納的行動(dòng)：后繼函數(shù)目標(biāo)測(cè)試：確定當(dāng)前狀態(tài)是否是目標(biāo)狀態(tài)路徑耗散函數(shù)：為每條路徑分配量化的耗散值7舉例：八數(shù)碼問題8盲目搜索廣度優(yōu)先搜索：在下一層節(jié)點(diǎn)被擴(kuò)展之前保證本層節(jié)點(diǎn)都被擴(kuò)展通常用FIFO隊(duì)列實(shí)現(xiàn)能保證找到最淺的目標(biāo)

3、節(jié)點(diǎn)（不一定是最優(yōu)的）在單步耗散相同時(shí)是最優(yōu)算法空間復(fù)雜度大,目標(biāo)節(jié)點(diǎn)較深時(shí)，時(shí)間復(fù)雜度亦很大9盲目搜索代價(jià)一致搜索:與廣度優(yōu)先搜索類似，但首先擴(kuò)展耗費(fèi)最低的節(jié)點(diǎn)須保證算法的完備性（為每一步設(shè)定最小耗散）最壞時(shí)間復(fù)雜度為10深度優(yōu)先搜索首先擴(kuò)展搜索樹中最深最邊緣的未擴(kuò)展節(jié)點(diǎn)通常通過LIFO的棧實(shí)現(xiàn)空間復(fù)雜度低，對(duì)于狀態(tài)復(fù)雜的問題，可變形為回溯搜索，空間復(fù)雜度降為最壞時(shí)間復(fù)雜度通常應(yīng)用中變形為深度有限搜索（需要知識(shí)的支持） , 通常lm11雙向搜索思想基礎(chǔ)：從初始狀態(tài)和目標(biāo)狀態(tài)同時(shí)開始相向搜索，形成兩棵搜索樹若某一待擴(kuò)展節(jié)點(diǎn)出現(xiàn)在另一棵搜索樹中，則找到解后向搜索較難實(shí)現(xiàn)，無固定方法12啟發(fā)式搜索使用啟發(fā)信息，對(duì)待擴(kuò)展節(jié)點(diǎn)到目標(biāo)節(jié)點(diǎn)的距離給出估計(jì)定義：f(n):對(duì)經(jīng)過節(jié)點(diǎn)n的最低耗散解的估計(jì)值g(n):初始節(jié)點(diǎn)到節(jié)點(diǎn)n的路徑耗散h(n):從節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的耗散估計(jì)值每次首先擴(kuò)展隊(duì)列中具有最低f(n)的節(jié)點(diǎn)13A*算法A*算法的要求：?jiǎn)l(fā)函數(shù)滿足可采納約束：其中 是節(jié)點(diǎn)n到目