A* search algorithm
Algoritmo de búsqueda A*
- Date
- 1968 · confidence high
- Place
- Stanford Research Institute, Menlo Park, California, United States
- Credited to
- Peter E. Hart, Nils J. Nilsson and Bertram Raphael
- Field
- Knowledge & symbols
What it is
Developed for the Shakey robot project, A* combines the actual cost travelled so far with a heuristic estimate of the remaining cost to find the shortest path in a graph both optimally and efficiently.
What it led to
- Route planning in video games, robotics and GPS systems
- Formalisation of heuristic admissibility and consistency (Hart, 1985)
- Variants such as IDA* and bounded-memory search algorithms