In computer science, A* is a computer algorithm that is widely used in pathfinding and graph traversal, the process of plotting an efficiently traversable path between points, called nodes. Noted for its performance and accuracy, it enjoys widespread use. Peter Hart, Nils Nilsson and Bertram Raphael first described the algorithm in 1968. It is an extension of Edsger Dijkstra's 1959 algorithm. A* achieves better performance (with respect to time) by using heuristics. However, when the heuristics are monotone, it is actually equivalent to running Dijkstra.
A* uses a best-first search and finds the least-cost path from a given initial node to one goal node (out of one or more possible goals).
It uses a distance-plus-cost heuristic function to determine the order in which the search visits nodes in the tree. The distance-plus-cost heuristic is a sum of two functions:
- the path-cost function, which is the cost from the starting node to the current node;
- and an admissible "heuristic estimate" of the distance to the goal.
Graphical Ontology Browser
- Click on a node to jump to the content of that node
- Pan to see the rest of the graph
- Scroll the mousewheel up and down to zoom in and out
- Rearrange the nodes in the graph by dragging a node to a different position