人工智能/搜索/穷举搜索/广度优先搜索

简介

广度优先搜索 (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