人工智能的搜索算法.pptx

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

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

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