Glossary · Phase 7 · Software engineering
Invariant
A property that no step can change, which can prove a goal reachable or impossible without searching.
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.
- heuristic: A quick estimate, such as straight-line distance, used to guide a search toward the goal.
- 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.