人工智慧---基礎搜尋法(深度限制搜尋法 / 反覆加深深度搜尋法 /雙向搜尋法)

作者:賴雅惠 資料來源:http://cindy.cis.nctu.edu.tw/AI96/team01/Search.html 深度限制搜尋法 (Depth-limited search, DLS) 深度限制搜尋法基本上個DFS的演算法是一樣的，只是事先評估 解可能的深度，而在做DFS時給一個深度的限制。可避免像DFS一樣 走入一條很深或無限深的路徑時，卻無法回頭的問題。 反覆加深深度搜 尋法(Iterative deepening search) 反覆加深深度搜尋法為DFS和DLS之改良，它改善了DFS的缺點 ，就是當有路徑較短的解在其它路上時，我們的搜尋卻走入一條有解 位在較深層(即路徑較長)的路徑中，或者走入一條無限深的路徑，以 至於找到的解不是最佳解或根本找不到解。這個問題可由IDS獲得解 決並且加入DLS的好處。 IDS的主要精神是使用DLS的演算法，但每次呼叫DLS演算法 時所給的搜尋深度是漸漸增加的。其演算法如下：

function ITERATIVE-DEEPENING-SEARCH(problem)      return a solution or sequence     inputs: problem, a problme     for depth = 0 to 無限大 do      if DEPTH-LIMITED-SEARCH(problem,depth) succeeds       then return its result     end    return failure    

圖例如下： * IDS 的時間複雜度同BFS為O(b^d) * IDS 的空間複雜度比BFS低為O(bd) * IDS 保證可以找到最佳解。 * IDS 保證若解存在一定可找到，達到完全性。 雙向搜尋法主要的想法是同時從初始狀態向前搜尋及從葉節點 回溯回去，然後等兩端搜尋在中間相遇才停止搜尋，是希望其搜尋 所花的時間能減半。其時間複雜度為O(2b^(d/2)) = O(b^(d/2))。 然而事實上這個法是不容易實行的，因為從葉節點回溯搜尋是 有其困難性的，讀者不妨想想看。 網路志工聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]--- 發表人 - axsoft 於 2002/08/23 14:17:26