A* Search Algorithm

GPTKB entity

Statements (52)
Predicate Object
gptkbp:instanceOf gptkb:search_engine
graph traversal algorithm
pathfinding algorithm
gptkbp:appliesTo maps
unweighted graphs
weighted graphs
grids
gptkbp:category gptkb:artificial_intelligence
computer science
operations research
robotics
search algorithms
graph algorithms
pathfinding
gptkbp:closedList set of visited nodes
gptkbp:completeness complete
gptkbp:complexity O(b^d)
gptkbp:expandsNodes lowest estimated total cost first
gptkbp:f(n) g(n) + h(n)
gptkbp:g(n) cost from start to n
gptkbp:generalizes gptkb:Dijkstra's_algorithm
gptkb:Best-First_Search
gptkbp:h(n) heuristic estimate from n to goal
gptkbp:hasVariant gptkb:IDA*
gptkb:Theta*
gptkb:Weighted_A*
A*E
https://www.w3.org/2000/01/rdf-schema#label A* Search Algorithm
gptkbp:input graph
start node
goal node
gptkbp:introduced gptkb:Bertram_Raphael
gptkb:Nils_Nilsson
gptkb:Peter_Hart
gptkbp:introducedIn 1968
gptkbp:openList priority queue
gptkbp:optimalityCondition admissible heuristic
gptkbp:optimizedFor optimal with admissible heuristic
gptkbp:output shortest path
gptkbp:publishedIn gptkb:IEEE_Transactions_on_Systems_Science_and_Cybernetics
gptkbp:relatedTo gptkb:Dijkstra's_algorithm
gptkb:Greedy_Best-First_Search
gptkbp:searchStrategy best-first search
gptkbp:spaceComplexity O(b^d)
gptkbp:usedIn gptkb:artificial_intelligence
robotics
video games
route planning
gptkbp:usesCostFunction true
gptkbp:usesHeuristicFunction true
gptkbp:bfsParent gptkb:Graph_Algorithms
gptkbp:bfsLayer 6