Heuristics: A*-algorithm 3

Inhaltsverzeichnis

1 A*-Algorithm
2 Idea of the A*
3 Function
4 Characteristics
5 Area of application
6 Example
7 Related algorithms and Disadvantages
8 References

A*-Algorithm

Algorithms search bidirectional and are used to search for a specific destination. One of these algorithms is the A*-Algorithm. The A*-Algorithm is a heuristic search algorithm which was developed in the year 1968 by Peter Hart, Nils J. Nilsson and Bertram Raphael and is used to find the shortest path between two nodes in a complete graph. Today it represents an extension to the Dijkstra-Algorithm and is the most used heuristic algorithm.

Idea of the A*

The A*-Algorithm is based on the shortest-path algorithm of Dijkstra. The first step of Dijkstra is expanding from a start node to the next nodes. Then this step gets repeated until the destination is reached. In the end all paths get summed and the path which has the most minimal costs will be prioritized. In contrast to Dijkstra the A* does not search for all possible paths it searches for these nodes which lead over the fastest path to the end node. So the A* is used for getting the most cost-saving and most-efficient path between start and end node.

Function

All nodes of the graph have a specific value which are noted as $f(n)$ ( $f(n)$ can describe for example length, costs etc.). The node with the most minimal value will be analyzed futhermore.

$f(n)=g(n)+h(n)$

$g(n)$ : previous costs from the start node

$h(n)$ : approximated costs from the current node to the end node

Because of the usage of the heuristic funciton, a more target-oriented search towards the end note is possible. So the course of action by using the A*-Algorithm is like this:

     1.	Note the values of all neighbors of the current node in your OPEN LIST

     2.	Sort the OPEN LIST according to the node's values in an ascending order

     3.	The node with the most minimal value gets deleted from the OPEN LIST and gets written down in the CLOSED LIST. This note is now your current node

     4.	Repeat step 1,2 and 3 until you reach the end note

     5.	Construct your optimal path and show your final CLOSED LIST

During the search the nodes will be classified in three categories:

      •	Unknown nodes: nodes which were not analyzed yet

      •	Known nodes: a path to these nodes is known. All other nodes with their specific value will be saved in the OPEN LIST. 
                     From this list the most cost-saving node gets picked out. It is a kind of list of precedence rating

      •	Nodes which were analyzed: the shortest path to these nodes is known and they can be saved and checked in the CLOSED LIST because every node should be analyzed only once

If the end node is reached, than the A* ends.

Characteristics

If $f(n)$ are the costs for expanding to the end node than there are two conditions for the heuristic

  •The heuristic is admissable if the values do not overrate the costs of the most cost-saving solution

  •The heuristic is monotonous if the path's costs are positive

Some other characteristics of A*

  •Complete: every existent solution will be found

  •Optimal: only the optimal solution will be found although there are more than one valid solutions

So the A* is optimal, if a monotnous heuristic is used.

Claim: The A* always finds the optimal solution.

Evidence: $L1$ is an optimal solution with the costs of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): K*

and  $L2$  is a sub-optimal solution. The heuristic should not overrate the costs of the most cost-saving solution and that is why  $h(L2)=0$ .

The fact that $L2$ is a sub-optimal solution means for $K2$ that:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): K2=f(L2)=g(L2)+h(L2)=g(L2)>K*

The heuristic estimates the real costs, so that for every node $x$ of the fastest path is applied that:

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x) = g(x) + h(x) \leq K*

and thats means

Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x)\leq K* < f(L2)

thus

$f(L1)<f(L2).$

So the A* does not show the sub-optimal solution $L2$ as long there exists an another optimal solution like $L1$ .

Area of application

Theoretically the A* can solve every problem which can be transferred into a graph and in which a heuristic function can be used. Examples are Puzzles, routes through several cities, houses etc.

In general the A* is often used in route planning software or computer games.