Catalogue of Artificial Intelligence Techniques
Keywords: admissibility, graph searching
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 will be found when the search reaches depth , and this is guaranteed to be before any node of depth greater than is searched. This property is called admissibility. Breadth-first search is asymptotically optimal in time (see entry for Iterative Deepening).
- Korf, R.E., Search: A Survey of Recent Results, Exploring Artificial Intelligence (Survey talks from the National Conferences on Artificial Intelligence)
, ed.), Morgan Kaufmann, San Mateo, California, 1988, pp.197--237 (Chapter 6).