A* algorithm

Presentation

A* algorithm is an algorithm of search for way in a graph between a initial Nœud and a final node. It uses an evaluation Heuristique on each node to consider the best way passing there, and visits then the nodes by order of this heuristic evaluation. It is a simple algorithm, not requiring a pretreatment, and consuming only little memory.

Intuition

Let us start with an example of motivation. One is with the intersection has and one wants to go to the intersection B which one knows that it is in the north of our current location. For this traditional case, the graph on which the algorithm will work represents the chart, where its arcs represent the ways and its Nœud S the intersections of the ways.

If a research in width were made as carries it out the Algorithme of Dijkstra, one would seek all the points in a fixed circular ray, gradually increasing this circle to seek intersections more and more far from our starting point. This could be an effective strategy if one did not know where our destination is, as the police force seeking a criminal in cushy job.

However, it is a waste of time if one knows more information on our destination. A better strategy is to directly explore with each intersection the first which goes towards north, because the shortest way is the straight line. As long as the road allows it, one continues Certainly to advance by taking the ways approaching the most intersection B. will have one to return behind from time to time, but on the typical charts it is a strategy much faster. Moreover, often this strategy will find the best route, as research in width would do it. It is the gasoline of the search for A* way.

However, as for all the algorithms of search for way, their effectiveness strongly depends on the problem which one wishes to solve (i.e.: graph). Thus a* algorithm does not guarantee to find a route more quickly than another algorithm, and in a Labyrinthe, the only manner of reaching the destination could be contrary to the position of the destination, and the nodes closest to this destination could not be on the shortest way, which can cost much computing time.

Property

An algorithm of research which guarantees always to find the way shortest with a goal calls “acceptable algorithm”. If A* uses heuristics which never over-estimates the distance (or more generally the cost) from the goal, A* can be proven acceptable. Heuristics which makes A* acceptable itself is called “acceptable heuristics”.

If the evaluation simply always returns zero, which is never an over-estimate, then, A* will carry out a possible implementation of the algorithm of Dijkstra and will always find the solution optimal. The best heuristics, although usually impracticable to calculate, is the real minimal distance (or more generally real costs) to the goal. An example of acceptable heuristics practices is the distance from the hot line to the goal on the chart.

One can show that A* does not consider more nodes than all the other acceptable algorithms of research, provided that the alternate algorithm does not have a more precise heuristic evaluation. In this case, A* is the data-processing algorithm most effective guaranteeing to find the way shortest.

Description

A* starts with a selected node. It applies to this node a “cost” (usually zero for the initial node). A* estimates then the distance which separates this node from the goal to reach. The sum of the cost and the evaluation represents the Heuristique assigned with the driving way with this node. The node is then added to a priority queue, usually called open list .

The algorithm withdraws the first node of the priority queues (due to the operation of a queue, the node with the lowest heuristics is withdrawn in first). If the queue is empty, there is no way of the initial node to the node of arrival, which stops the algorithm. If the node selected is the node of arrival, A* rebuilds the complete way and stops. For this rebuilding one makes use of part of the information saved in the list commonly called closed list described low.

If the node is not the node of arrival, of new nodes are created for all the acceptable contiguous nodes; the manner exact to do that depends on the problem to treat. For each successive node, A* calculates its cost and stores it with the node. This cost is calculated starting from the sum of the cost of its ancestor and the cost of the operation to reach this new node.

The algorithm also maintains the list of nodes which were checked, usually called closed list . If a node lately product is already in this list with an equal or lower cost, no operation is made on this node nor on its counterpart being in the list.

After, the evaluation of the distance from the new node to the node of arrival is added to the cost to form the heuristics of the node. This node is then added to the priority waiting list, unless an identical node in this list does not have already lower or equal heuristics.

Once the three stages carried out above for each new contiguous node, the original node taken of the priority queue is added to the list of the checked nodes. The next node is then withdrawn from the priority queue and the process starts again.

The two structures open list and closed list are not necessary if one can guarantee that the first way produced with any node is shortest. This situation emerges if the heuristics is not only acceptable but also “monotonous”, meaning that the difference between the heuristics in two unspecified nodes connected does not over-estimate the real distance between these nodes. It is not possible that in very rare cases.

Pseudocode

Paramètres:

START : starting node

GOAL : node of arrival

OPEN : list nodes to be treated (in general: represented like a file of priority)

CLOSED : list treated nodes

NR : many nodes

H (I) : outdistance estimated of a node I with the node of arrival ( I ∈ {1, 2,…, NR})

G (I) : real distance from a node I with the starting node ( I ∈ {1, 2,…, NR})

F (I) : summon distances H (I) and G (I)

relative () : relative of a node I ( relative (X) gives the position in relative () of the node preceding X ))

To initialize the list OPEN with vacuum
To initialize the list CLOSED with vacuum

To add START to the list OPEN
As long as the list OPEN is not empty

Retirer the node N list OPEN such as F (N) is smallest
If N is GOAL to turn over the solution;
If not to add N to CLOSED
For each successor n´ of the node N

Heuristic H = estimate of the cost of n´ to GOAL
To store in G_tmp G (n´) , the cost G (N) + the cost to go from N to n´
To store in F_tmp F (n´) , G (n´) + H; it is the heuristics

If n´ is already in OPEN with a F (n´) better one passes at the point n´ according to
If n´ is already in CLOSED with a F (n´) better one passes at the point n´ according to
Mettre N in relative ()
Mettre G_tmp in G ()
Mettre F_tmp in F (n´)
Retirer n´ of the two lists OPEN and CLOSED
Ajouter n´ to the list OPEN

Examples

Example of a simple research programme of shorter way by the algorithm A*

See too

an article on '' gamedev.net '' to include/understand the operation of the algorithm A*
an article describing the algorithm HPA* which makes it possible to optimize research in the graphs of big size

Random links: