liveBook · Manning

Breadth-first search

As explained in Applied Reinforcement Learning

Breadth-first search explores graph or tree nodes in order of their distance from a starting node, typically using a FIFO queue.

Breadth-first search explores a tree level by level. A FIFO queue keeps shallow possibilities ahead of deeper ones, so BFS does not pursue a deep route while shallower alternatives remain. section 7.2 section 7.5

Finding a delivery route

Treat the depot as the root and each next customer visit as a child. Remove a partial route from the queue, add its unvisited customer continuations, and enqueue them. BFS finds a solution with the fewest stops; it is optimal by cost only when each step has equal cost. section 7.2

BFS is useful when:

  • A shallowest solution is preferred, and equal-cost steps make fewest steps equivalent to lowest cost. section 7.2
  • Memory use and search growth are acceptable; exhaustive routing can become infeasible as the number of customers grows. section 7.5
Figure 7.2 Breadth-First Search (BFS) algorithm and flow.

Use the flow diagram to follow the queue-based traversal. section 7.2

How Applied Reinforcement Learning covers it

How deep it goes
Explains queue-based traversal and its guarantees, then flags memory costs and exhaustive routing limits.
Examples
Uses a depot-and-customer route tree to illustrate searching partial routes and comparing completed routes.
What you can do after
Apply BFS with a FIFO queue to search level by level and find minimum-step solutions when step costs are equal.
How it connects
Connects BFS with tree search, depth-first search, and Monte Carlo tree search.

Also explained in

Compare how 10 books explain breadth-first search →

Related concepts

This explainer was generated by Manning's knowledge graph from the text of Applied Reinforcement Learning. The section links point to the parts of the book it draws on.