A best-first pathfinding algorithm that combines the actual cost of the path so far with an estimate of the remaining cost to the goal, guaranteeing the shortest path when the estimate never overstates the true remaining distance; widely used in games and route planning.
Facts
Time Complexity
Time Complexity (category)Exponential Time -- O(2^n) 1 Classification
Design TechniqueHeuristic or Approximation 1 Credited ToPeter Hart, Nils Nilsson and Bertram Raphael (1968) 2 Connections
Credited To
Source Wikipedia, A* search algorithm
In Field
Invented By
Source Wikipedia, A* search algorithm
Uses Design Technique
Sources
1. A* Search Algorithm (Wikipedia)
Wikipedia infobox: time complexity exponential
exponential
Wikipedia: design technique heuristic-approximation
heuristic-approximation
View the Source2. Wikipedia, A* search algorithm
Lead section
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.
Credited To: Nils John Nilsson, History section
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International) first published the algorithm in 1968.
View the SourceWikidata: A* Search Algorithm
Wikidata Q277680, class allow-list match (w-wdresolver-0926)View the Source Reader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.