Minh
Minh
Minh
Intruduction
A* (pronounced "A-star") is a graph traversal and pathfinding algorithm, which is used in many fields
of computer science due to its completeness, optimality, and optimal efficiency.[1] Given a weighted
graph, a source node and a goal node, the algorithm finds the shortest path (with respect to the
given weights) from source to goal.
Peter Hart, Nils Nilsson and Bertram Raphael of Stanford Research Institute (now SRI International)
first published the algorithm in 1968.[4] It can be seen as an extension of Dijkstra's algorithm. A*
achieves better performance by using heuristics to guide its search.
Compared to Dijkstra's algorithm, the A* algorithm only finds the shortest path from a specified
source to a specified goal, and not the shortest-path tree from a specified source to all possible
goals. This is a necessary trade-off for using a specific-goal-directed heuristic. For Dijkstra's
algorithm, since the entire shortest-path tree is generated, every node is a goal, and there can be no
specific-goal-directed heuristic.
If the heuristic function is admissible – meaning that it never overestimates the actual cost to get to
the goal – A* is guaranteed to return a least-cost path from start to goal.
Algorithm
We create two lists – Open List and Closed List (just like Dijkstra Algorithm)
// A* Search Algorithm
1. Initialize the open list
2. Initialize the closed list
put the starting node on the open
list (you can leave its f at zero)
3. while the open list is not empty
a) find the node with the least f on
the open list, call it "q"
b) pop q off the open list
B) Approximation Heuristics –
There are generally three approximation heuristics to calculate h –
1) Manhattan Distance –
It is nothing but the sum of absolute values of differences in the goal’s x
and y coordinates and the current cell’s x and y coordinates respectively,
i.e.,
h = abs (current_cell.x – goal.x) +
abs (current_cell.y – goal.y)
When to use this heuristic? – When we are allowed to move only in four
directions only (right, left, top, bottom)
The Manhattan Distance Heuristics is shown by the below figure (assume red spot as
source cell and green spot as target cell).
2) Diagonal Distance-
It is nothing but the maximum of absolute values of differences in the
goal’s x and y coordinates and the current cell’s x and y coordinates
respectively, i.e.,
dx = abs(current_cell.x – goal.x)
dy = abs(current_cell.y – goal.y)
h = D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
where D is length of each node(usually = 1) and D2 is diagonal
distance between each node (usually = sqrt(2) ).
3) Euclidean Distance-
As it is clear from its name, it is nothing but the distance between the
current cell and the goal cell using the distance formula
h = sqrt ( (current_cell.x – goal.x)^2 +
(current_cell.y – goal.y)^2 )
Special cases
Dijkstra's algorithm, as another example of a uniform-cost search algorithm, can be viewed as a
special case of A* where h(x) = 0 for all x.[11][12]General depth-first search can be implemented using
A* by considering that there is a global counter C initialized with a very large value. Every time we
process a node we assign C to all of its newly discovered neighbors. After every single assignment,
we decrease the counter C by one. Thus the earlier a node is discovered, the higher its h(x) value.
Both Dijkstra's algorithm and depth-first search can be implemented more efficiently without
including an (x) value at each node.
Multiple goals#
One way to think about this is that we can add a new zero-cost edge from
each of the goals to a new graph node. A path to that new node will
necessarily go through one of the goal nodes.
If you want to search for paths to all of several goals, your best option
may be Dijkstra’s Algorithm with early exit when you find all the goals.
There may be a variant of A* that can calculate these paths; I don’t know.
If you want to search for spot near a single goal, ask A* search to find a
path to the center of the goal area. While processing nodes from the
OPEN set, exit when you pull a node that is near enough
Time Complexity
Considering a graph, it may take us to travel all the edge to reach the destination cell
from the source cell [For example, consider a graph where source and destination
nodes are connected by a series of edges, like – 0(source) –>1 –> 2 –> 3 (target)
So the worse case time complexity is O(E), where E is the number of edges in the
graph
The time complexity is polynomial when the search space is a tree, there is a single goal state, and
the heuristic function h meets the following condition:
H(x) – h*(x) = O(log h*(x))
where h* is the optimal heuristic, the exact cost to get from x to the goal. In other words, the
error of h will not grow faster than the logarithm of the "perfect heuristic" h* that returns the true
distance from x to the goal.[17][23]
Auxiliary Space In the worse case we can have all the edges inside the open list, so
required auxiliary space in worst case is O(V), where V is the total number of
vertices.
The space complexity of A* is roughly the same as that of all other graph search algorithms, as it
keeps all generated nodes in memory.[1] In practice, this turns out to be the biggest drawback of the
A* search, leading to the development of memory-bounded heuristic searches, such as Iterative
deepening A*, memory-bounded A*, and SMA*.
Variants
Anytime A*[30]
Block A*
D*
Field D*
Fringe
Fringe Saving A* (FSA*)
Generalized Adaptive A* (GAA*)
Incremental heuristic search
Reduced A*[31]
Iterative deepening A* (IDA*)
Jump point search
Lifelong Planning A* (LPA*)
New Bidirectional A* (NBA*)[32]
Simplified Memory bounded A* (SMA*)
Theta*