Catalogue of Artificial Intelligence Techniques

   

Jump to: Top | Entry | References | Comments

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 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).


References:


Comments:

Add Comment

No comments.