人工智慧/搜尋/窮舉搜尋/廣度優先搜尋

簡介

廣度優先搜尋 (BFS) 技術是一種系統搜尋策略，它從初始節點（初始狀態）開始，並從初始節點開始，以廣度優先的順序在樹結構上向下應用搜索操作。

搜尋操作包括

選擇一個節點作為當前節點
測試當前節點是否滿足目標測試條件
如果目標狀態沒有達到，則以廣度優先的順序選擇下一個節點
搜尋在所有節點都被搜尋過或找到目標時結束。

在汽車鑰匙示例中，BFS 搜尋順序遵循節點序列：1、2、3、4、5……等等，以廣度優先的順序。BFS 搜尋將首先遍歷所有房間，然後遍歷所有桌子，然後按順序遍歷所有抽屜。

               1.(  Home  )
                /    |     \
               /     |      \
       2.(room A)  3.(room B)  4.(room C)
             /   *car key
            /        | 
       5.(desk1)  6.(desk2)

圖 1 汽車鑰匙搜尋空間

實現

BFS 可以使用列表或佇列資料結構實現。最初，列表只包含初始狀態。搜尋演算法涉及反覆測試和刪除列表前面的第一個節點，然後找到並追加該節點的後繼節點到列表中。此過程一直持續到列表中的第一個節點是目標狀態或列表為空。

繼續使用汽車鑰匙示例，列表初始化為

[ 1 (home) ]

在節點 1 失敗目標測試後，它從列表中刪除，並且後繼節點 2、3、4 被追加到列表中

[2. (room A), 3 (room B), 4 (room C)]

當節點 2 被測試並刪除，並且節點 5 被追加時

[3 (room B), 4 (room C), 5 (desk1)]

當節點 3 被識別為目標狀態時，搜尋成功終止，即汽車鑰匙在房間 B 中被找到。

優點和缺點

BFS 是一種窮舉搜尋演算法。它易於實現。它可以應用於任何搜尋問題。將 BFS 與深度優先搜尋演算法進行比較，BFS 不受任何潛在的無限迴圈問題的影響，這可能會導致計算機崩潰，而深度優先搜尋會深入搜尋。BFS 的一個缺點是它是一種“盲目”搜尋，當搜尋空間很大時，與其他啟發式搜尋相比，搜尋效能會很差。

如果搜尋空間很小，BFS 的效能會很好。如果目標狀態位於樹的左上角，它表現最好。但如果目標狀態位於樹的底部，與深度優先搜尋演算法相比，它的效能會相對較差。如果連結上的權重是統一的，BFS 將始終找到最短路徑。因此，BFS 是完整的且最佳的。正如我們所討論的，BFS 中的記憶體利用率很差，因此我們可以說 BFS 比 DFS 需要更多記憶體。

參考資料

維基百科 (2008/10/10)。 http://en.wikipedia.org/wiki/Breadth-first_search
Cawsey A. 1998. 人工智慧的本質。歐洲，Prentice Hall