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



Add Comment

No comments.