Wikibooks

Artificial Intelligence/Search/Exhaustive search/Breadth-first search

< Artificial Intelligence | Search | Exhaustive search

Introduction

edit

Breadth-first search (BFS) technique is a systematic search strategy which begins at an initial node (an initial state) and from the initial node search actions are applied downward on a tree structure in a breadth-wise order.

The search action consists of:

  1. Selecting a node as a current node
  2. Testing the current node for meeting the goal test criteria
  3. If the goal state is not reached, select the next node in a breadth-wise order
  4. The search ends either when all the nodes have been searched or if the goal has been found.

In the car key example, the BFS search order follows node sequence: 1, 2, 3, 4, 5… and so on in breadth-first order. The BFS search will first go through all the rooms, then all the desks, then all the drawers in that sequence. 

               1.(  Home  )
                /    |     \
               /     |      \
       2.(room A)  3.(room B)  4.(room C)
             /   *car key
            /        | 
       5.(desk1)  6.(desk2)

Figure 1 Car key search space

Implementation

edit

BFS can be implemented using a list or a queue data structure. Initially the list contains just the initial state. The search algorithm involves the repeated testing and removing of the first node from the front of the list, and then finding and appending the node’s successors to the list. This process continues until the first node in the list is the goal state or the list is empty.

Continuing with the car key example, the list is initialized to: 

[ 1 (home) ]

After node 1 fails the goal test, it is removed from the list and the successor node 2, 3, 4 are appended to the list: 

[2. (room A), 3 (room B), 4 (room C)]

When Node 2 is tested and removed, and node 5 is appended: 

[3 (room B), 4 (room C), 5 (desk1)]

The search is successfully terminated when node 3 is identified as the goal state i.e. the car key is found in room B.

Advantages and Disadvantages

edit

BFS is an exhaustive search algorithm. It is simple to implement. And it can be applied to any search problem. Comparing BFS to depth-first search algorithm, BFS does not suffer from any potential infinite loop problem , which may cause the computer to crash whereas depth first search goes deep down searching. One disadvantage of BFS is that it is a ‘blind’ search, when the search space is large the search performance will be poor compared to other heuristic searches.

BFS will perform well if the search space is small. It performs best if the goal state lies in upper left-hand side of the tree. But it will perform relatively poorly relative to the depth-first search algorithm if the goal state lies in the bottom of the tree. BFS will always find the shortest path if the weight on the links are uniform.So BFS is complete and optimal. As we discussed memory utilization is poor in BFS, so we can say that BFS needs more memory as compared to DFS.

References

edit
Retrieved from "https://en.wikibooks.org/w/index.php?title=Artificial_Intelligence/Search/Exhaustive_search/Breadth-first_search&oldid=3222339"