人工智能的搜索算法

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

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

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

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