A*

From Algorithmist
Jump to navigation Jump to search

The A* algorithm is a pathfinding algorithm meant to determine the shortest distance between two points.

Implementation[edit]

The algorithm relies on a priority queue, containing a set of nodes pertaining to the current pathfinding situation. In determining which child nodes to follow, it uses a function that quickly estimates the cost from travelling from the starting point to the goal.

Pseudocode is as follows:

 let g(x) be current cost spent travelling as spent on the current node path.
 let d(x) be estimated cost to destination (e.g. straight-bird distance)
 let c(x,y) be cost of travelling from node x to node y. 
 Add all routes from initial node to priority queue.  
 for each route in priority queue (take lowest of g(x)+c(x,y))
  Add all routes from remote to priority queue.  Node y will have cost added to g(x).
  Stop if destination is reached.  

Heuristic[edit]

The A* algorithm relies on a heuristic that estimates the distance between the current node and the destination; this heuristic should be the cost to travel from the current point to the destination if there were no interceding factors.

If the heuristic always provides a distance of zero, the algorithm becomes an Exhaustive Search; specifically a Breadth-First Search (unless it otherwise provides a wrong answer.) If the heuristic provides a distance equal to the minimum travel time, it will provide the correct answer. If it larger than the minimum distance, the algorithm is faster but won't always provide the shortest route.

The A* algorithm can be modified to perform Depth-First Search. First, the heuristic function initially returns a very high value for the first path, which gradually decreases as new paths are found.

Optimizations[edit]

The following optimizations can be used

  • Dynamic programming (for heuristics or already solved A* searches)
  • Removal of backtracking (unless required by the context)