3.5 Uninformed Search Strategies

The third edition of Artificial Intelligence: foundations of computational agents, Cambridge University Press, 2023 is now available (including full text).

3.5.1 Breadth-First Search

In breadth-first search the frontier is implemented as a FIFO (first-in, first-out) queue. Thus, the path that is selected from the frontier is the one that was added earliest.

This approach implies that the paths from the start node are generated in order of the number of arcs in the path. One of the paths with the fewest arcs is selected at each iteration.

Figure 3.5: The order in which paths are expanded in breadth-first search
Example 3.7.

Consider the tree-shaped graph in Figure 3.5. Suppose the start node is the node at the top, and the children of a node are added in a left-to-right order. In breadth-first search, the order in which the paths are expanded does not depend on the location of the goal. The nodes at the end of the first sixteen paths expanded are numbered in order of expansion in the figure. The shaded nodes are the nodes at the ends of the paths of the frontier after the first sixteen iterations.

Example 3.8.

Consider breadth-first search from o⁢103 in the graph given in Figure 3.2. The only goal node is r⁢123. Initially, the frontier is [⟨o⁢103⟩]. This is extended by o⁢103’s neighbors, making the frontier [⟨o103,𝑡𝑠⟩, ⟨o⁢103,b⁢3⟩, ⟨o103,o109⟩]. These are the nodes one arc away from o⁢013. The next three paths chosen are ⟨o⁢103,𝑡𝑠⟩, ⟨o⁢103,b⁢3⟩, and ⟨o⁢103,o⁢109⟩, at which stage the frontier contains

[⟨o103,𝑡𝑠,𝑚𝑎𝑖𝑙⟩,⟨o103,b3,b1⟩,⟨o103,b3,b4⟩,
    ⟨o103,o109,o111⟩,⟨o103,o109,o119⟩].

These are the paths containing two arcs starting at o⁢103. These five paths are the next paths on the frontier chosen, at which stage the frontier contains the paths of three arcs away from o⁢103, namely,

[⟨o103,b3,b1,c2⟩,⟨o103,b3,b1,b2⟩,⟨o103,b3,b4,o109⟩,
    ⟨o103,o109,o119,𝑠𝑡𝑜𝑟𝑎𝑔𝑒⟩,⟨o103,o109,o119,o123⟩].

Note how in breadth-first search each path on the frontier has either the same number of arcs or one more arc than the next element of the frontier that will be selected.

Suppose the branching factor of the search is b. If the next path to be selected on the frontier contains n arcs, there are at least bn-1 elements of the frontier. All of these paths contain n or n+1 arcs. Thus, both space and time complexities are exponential in the number of arcs of the path to a goal with the fewest arcs. This method is guaranteed, however, to find a solution if one exists and will find a solution with the fewest arcs.

Breadth-first search is useful when

  • •

    the problem is small enough so that space is not a problem (e.g., if you already need to store the graph) and

  • •

    you want a solution containing the fewest arcs.

It is a poor method when all solutions have many arcs or there is some heuristic knowledge available. It is not used very often for large problems where the graph is dynamically generated because of its exponential space complexity.