广度优先搜索

BFS = Breadth-First-Search

图搜索算法

属于无信息搜索策略的算法：当前状态下，没有关于目标接近程度的线索。

ref: 《AIMA》第三章

概述

• 使用队列作为基础数据结构，保存正在检查的边界集
• 评价函数为节点深度：即为到达节点的动作数

代码

function BREADTH-FIRST-SEARCH(problem) returns 一个解节点或 failure
    node ← NODE(problem.INITIAL)
    if problem.Is-Goal(node.STATE) then return node  // 检查是否为解
    frontier ← 一个FIFO队列，其中一个元素为node
    reached ← {problem.INITIAL}
    while not Is-Empty(frontier) do
        node ← POP(frontier)
        for each child in EXPAND(problem, node) do
            s ← child.STATE
            if problem.Is-Goal(s) then return child  // 早期目标测试，在扩展后检查，而不是在下一个循环中才检查
            if s不在reached中 then
                将s添加到reached
                将child添加到frontier
    return failure
    
function UNIFORM-COST-SEARCH(problem) returns 一个解节点或 failure
    return BEST-FIRST-SEARCH(problem, PATH-COST)

• 早期目标测试，在 EXPAND 之后（首次检查子节点之后，在当前循环体内，立即判定是否为解，算法是否完成）
  • 对比 Dijkstra算法的后期目标测试：需要在下一次对边界集的检查中判断是否为解

计算复杂度

$$O(b^d)$$

• b 节点的后继数量（每个节点的子节点数量）
• d 为树的层数（深度）