人工智慧---基礎搜尋法(廣度優先搜尋法 Breadth-First Search, BFS )

作者:賴雅惠 資料來源:http://cindy.cis.nctu.edu.tw/AI96/team01/Search.html 廣度優先搜尋法是一個簡單的搜尋策略，其根節點先被展開， 然後再展開被根節點展開的所有節點，接著再展開它們的後繼者， 就這樣一層一層地展開所有的節點，直到找到目標解。簡單的說， 所有在深度(depth)為d的節點皆會比所有在深度為d+1的節點早被展 開。實作時可呼叫GENERAL-SEARCH演算法，把佇列函數設為"把 新展開的狀態放在佇列的後面"，如下所示：

Function BREADTH-FIRST-SEARCH(problem) return a solution          or failure      return GENERAL-SEARCH(problem, ENQUEUE-AT-END)

在展開0,1,2,3個節點之後的BFS 樹： # BFS 保證一定能找到解，如何解存在的話。(完全性) # BFS 找到的第一個解一定是路徑最短的。(最佳解) # BFS 所需的搜尋時間為： 設b為分枝因數，d為目標節點所在的深度，那最多會被展開 的節點數為 1 + b + b^2 + b^3 + b^3 + .... + b^d ，所以搜尋的時 間複雜度為 O( b^d )。 # BFS 所需的記憶體空間為：(設分枝因數為 10) 由上表可看出BFS在解的位置在很深的地方時，它所需的時 間及空間高的嚇人，有時並不適合使用，有必要再加以改良。 網路志工聯盟----Visita網站http://www.vista.org.tw ---[ 發問前請先找找舊文章 ]--- 發表人 - axsoft 於 2002/08/23 14:17:00