# Catalogue of Artificial Intelligence Techniques

View Maths as: Images | MathML

## Breadth-first Search

**Keywords:**
admissibility, graph searching

### Categories: Search

Author(s): **Dave Plummer**

An uninformed graph searching strategy in which each level is searched before going to the next deeper level. This strategy is guaranteed to terminate with the shortest possible path to the goal node, if such a path exists, since any path to the solution that is of length $n$ will be found when the search reaches depth $n$ , and this is guaranteed to be before any node of depth greater than $n$ is searched. This property is called admissibility. Breadth-first search is asymptotically optimal in time (see entry for Iterative Deepening).

### References:

- Korf, R.E.,
*Search: A Survey of Recent Results*,*Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)*(Shrobe, H.E. , ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).

### Comments:

No comments.