人工智能的搜索算法

人工智能的搜索算法第1頁，共16頁，2023年，2月20日，星期日在智能過程中，搜索是不可避免的

————Nilsson一個(gè)物理符號(hào)系統(tǒng)解決任何智能問題的充分和必要條件

————Newell第2頁，共16頁，2023年，2月20日，星期日搜索法簡介搜索法是人工智能中問題求解的基本方法可大致分為有信息搜索和無信息搜索約束滿足問題和博弈問題的求解均可表述為搜索過程Agent的學(xué)習(xí)過程亦可表述為搜索過程搜索法的本質(zhì)是在狀態(tài)空間中從問題的初始狀態(tài)搜索到通向目標(biāo)狀態(tài)的路徑第3頁，共16頁，2023年，2月20日，星期日搜索法簡介當(dāng)前的智能計(jì)算方法本質(zhì)上也是搜索方法，如神經(jīng)網(wǎng)絡(luò)、遺傳算法、蟻群算法等搜索法的設(shè)計(jì)主要考慮解路徑的耗散值以及搜索過程中的耗散值——耗費(fèi)最低化第4頁，共16頁，2023年，2月20日，星期日算法性能的評(píng)價(jià)評(píng)價(jià)算法性能的四個(gè)方面：完備性：有解時(shí)能保證找到解（可判定問題）最優(yōu)性：能否找到最優(yōu)解時(shí)間復(fù)雜度空間復(fù)雜度第5頁，共16頁，2023年，2月20日，星期日搜索算法的評(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)空間中最大路徑長度（考慮耗散）第6頁，共16頁，2023年，2月20日，星期日問題的形式化搜索法首先要對(duì)問題進(jìn)行形式化描述問題通?？尚问交x為下述四個(gè)部分Agent所處的初始狀態(tài)Agent可采納的行動(dòng)：后繼函數(shù)目標(biāo)測試：確定當(dāng)前狀態(tài)是否是目標(biāo)狀態(tài)路徑耗散函數(shù)：為每條路徑分配量化的耗散值第7頁，共16頁，2023年，2月20日，星期日舉例：八數(shù)碼問題第8頁，共16頁，2023年，2月20日，星期日盲目搜索廣度優(yōu)先搜索：在下一層節(jié)點(diǎn)被擴(kuò)展之前保證本層節(jié)點(diǎn)都被擴(kuò)展通常用FIFO隊(duì)列實(shí)現(xiàn)能保證找到最淺的目標(biāo)節(jié)點(diǎn)（不一定是最優(yōu)的）在單步耗散相同時(shí)是最優(yōu)算法空間復(fù)雜度大,目標(biāo)節(jié)點(diǎn)較深時(shí)，時(shí)間復(fù)雜度亦很大第9頁，共16頁，2023年，2月20日，星期日盲目搜索代價(jià)一致搜索:與廣度優(yōu)先搜索類似，但首先擴(kuò)展耗費(fèi)最低的節(jié)點(diǎn)須保證算法的完備性（為每一步設(shè)定最小耗散）最壞時(shí)間復(fù)雜度為第10頁，共16頁，2023年，2月20日，星期日深度優(yōu)先搜索首先擴(kuò)展搜索樹中最深最邊緣的未擴(kuò)展節(jié)點(diǎn)通常通過LIFO的棧實(shí)現(xiàn)空間復(fù)雜度低，對(duì)于狀態(tài)復(fù)雜的問題，可變形為回溯搜索，空間復(fù)雜度降為最壞時(shí)間復(fù)雜度通常應(yīng)用中變形為深度有限搜索（需要知識(shí)的支持）,通常l<m第11頁，共16頁，2023年，2月20日，星期日雙向搜索思想基礎(chǔ)：從初始狀態(tài)和目標(biāo)狀態(tài)同時(shí)開始相向搜索，形成兩棵搜索樹若某一待擴(kuò)展節(jié)點(diǎn)出現(xiàn)在另一棵搜索樹中，則找到解后向搜索較難實(shí)現(xiàn)，無固定方法第12頁，共16頁，2023年，2月20日，星期日啟發(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)第13頁，共16頁，2023年，2月20日，星期日A*算法A*算法的要求：啟發(fā)函數(shù)滿足可采納約束：其中是節(jié)點(diǎn)n到目標(biāo)節(jié)點(diǎn)的最低耗散一致性約束：A*算法是可采納算法：當(dāng)解存在時(shí)能保證找到最優(yōu)解當(dāng)滿足時(shí)，A*算法效率最高第14頁，共16頁，2023年，2月20日，星期日A*算法的復(fù)雜性估計(jì)若h(n)滿足：

則有：故A*并不能保證克服指數(shù)爆炸非指數(shù)級(jí)增長的條件：

第15頁，共16頁，2023年，2月20日，