Breadth First Search

Breadth-first search (BFS) is a variant of uninformed best-first search, where nodes are expanded in order of increasing depth from the root. Let be the depth of node , which also corresponds to the number of actions in its associated action sequence. Note that this is also the canonical notion of depth, where the root node has a depth of 0.

Definition

Breadth first-search is obtained from best-first search by choosing

together with a FIFO (First-In, First-Out) tie-breaking rule among nodes with equal depth.

Intuitively, breadth-first search explores the search tree level by level.

Analysis

Time and Space Complexity

To find nodes that are at a distance from the root node, BFS takes time and memory, where is the branching factor.

Completeness

When all step costs are identical (equivalently, when the step-cost induces unit-cost transitions), breadth-first search is complete (i.e. guaranteed to find a solution if one exists) for finite branching factor and returns a minimum-depth solution, which coincides with a minimum-cost solution under unit costs.

Implementation

template <typename Env>
struct BFSNode {
    auto generate_child(int action) -> BFSNode {
        auto child = *this;
        child.parent = this;
        child.state.apply_action(action);
        ++child.depth;
        return child;
    }
 
    Env state;
    BFSNode *parent = nullptr;
    int depth = 0;
    double cost = 0;
    int generated_step = 0;
    int expanded_step = 0;
};
 
template <typename Env>
auto bfs_eval_func(const BFSNode<Env> &node) -> double {
    return static_cast<double>(node.depth);
}
 
template <typename Env>
auto bfs(Env initial_state) {
    BFSNode root_node = {
        .state=initial_state, 
        .parent=nullptr,
        .depth=0,
    }
    return best_first_search(root_node, bfs_eval_func);
}