Algorithm Implementation/Search

In general, search involves taking a state in the search space, pushing all of the possible next states into a data structure, then retrieving the next state to move to from the data structure and continuing the search from there. The choice of data structure affects the type of search.

Depth-first search (DFS) uses a stack (First-In Last-Out) data structure, where the most recently inserted state is chosen each time.

Breadth-first search (BFS) uses a queue (First-In First-Out) data structure, where the least recently inserted state is chosen each time.

A* search uses a priority queue data structure with a heuristic to determine the order of the traversal of the search space. As long as this heuristic is not overly pessimistic, the first path found by A* is the shortest path. A pessimistic heuristic may be acceptable if finding a short enough path quickly is preferred to finding the optimal path.

Generally, where BFS is applicable and an acceptable heuristic exists, A* is faster than BFS. BFS can be thought of as a degenerate case of A* with a maximally optimistic heuristic.


This article is issued from Wikibooks. The text is available under Creative Commons Attribution-Share Alike 4.0 unless otherwise noted. Additional terms may apply for the media files.