Heuristic
A quick estimate, such as straight-line distance, used to guide a search toward the goal.
Dijkstra spreads out evenly in every direction, including away from the goal. A star, written A*, adds a guess of the remaining cost, the heuristic, and always expands the place with the lowest cost so far + guessed cost to go. On a map, the straight-line distance is a good guess; on a grid where you can only move up, down, left and right, the Manhattan distance (rows apart plus columns apart) is.
Try it now
Each pop takes the cheapest place in the queue; its distance never changes after that.
Learn it properly
Searching for solutions · Backtracking with pruning, Dijkstra's algorithm and A*, ending with an optimal sliding-puzzle solver. About 45 minutes.
Other terms from the same lesson
- admissible heuristic: A heuristic that never overestimates the real remaining cost, which keeps A* search finding the best answer.
- backtracking: Building an answer one choice at a time and undoing a choice as soon as the partial answer can't work.
- Dijkstra's algorithm: Finding the cheapest route in a map with non-negative costs by always growing from the cheapest place not yet finished.
- invariant: A property that no step can change, which can prove a goal reachable or impossible without searching.
- priority queue: A collection that always hands back its smallest (or most urgent) item next; Python's heapq module provides one.
Never trained an AI?
Teach a small one to write, right in your browser. It takes about 20 seconds and needs no account.