人工智能的搜索算法ppt課件

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

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

3、常用FIFO隊列實現(xiàn)p能保證找到最淺的目標(biāo)節(jié)點不一定是最優(yōu)的）p在單步耗散相同時是最優(yōu)算法p空間復(fù)雜度大,p目標(biāo)節(jié)點較深時，時間復(fù)雜度亦很大)(1dbO盲目搜索p代價一致搜索:p與廣度優(yōu)先搜索類似，但首先擴(kuò)展耗費最低的節(jié)點p須保證算法的完備性為每一步設(shè)定最小耗散）p最壞時間復(fù)雜度為)(*cbO深度優(yōu)先搜索p首先擴(kuò)展搜索樹中最深最邊緣的未擴(kuò)展節(jié)點p通常通過LIFO的棧實現(xiàn)p空間復(fù)雜度低，p對于狀態(tài)復(fù)雜的問題，可變形為回溯搜索，空間復(fù)雜度降為p最壞時間復(fù)雜度p通常應(yīng)用中變形為深度有限搜索需要知識的支持） , 通常lm)(bmO)(mbO)(mO)(lbO雙向搜索p思想基礎(chǔ)：p從初始狀態(tài)和目標(biāo)狀態(tài)同

4、時開始相向搜索，形成兩棵搜索樹p若某一待擴(kuò)展節(jié)點出現(xiàn)在另一棵搜索樹中，則找到解p后向搜索較難實現(xiàn)，無固定方法dddbbb22啟發(fā)式搜索p使用啟發(fā)信息，對待擴(kuò)展節(jié)點到目標(biāo)節(jié)點的距離給出估計p定義：pf(n):對經(jīng)過節(jié)點n的最低耗散解的估計值pg(n):初始節(jié)點到節(jié)點n的路徑耗散ph(n):從節(jié)點n到目標(biāo)節(jié)點的耗散估計值p每次首先擴(kuò)展隊列中具有最低f(n)的節(jié)點)()()(nhngnfA*算法pA*算法的要求：p啟發(fā)函數(shù)滿足可采納約束：p其中 是節(jié)點n到目標(biāo)節(jié)點的最低耗散p一致性約束：pA*算法是可采納算法：當(dāng)解存在時能保證找到最優(yōu)解p當(dāng)滿足 時，A*算法效率最高)()(*nhnh)(*nh)(),()(11nhnancnh)()(,*nhnhnA*算法的復(fù)雜性估計p若h(n)滿足：p p 則有：p故A*并不能保證克服指數(shù)爆炸p非指數(shù)級增長的條件：p 0,1)()()(*mnhnhnhp0),()(ceOzEcN)(log