Heuristics: A*-algorithm 3: Unterschied zwischen den Versionen

Version vom 27. Juni 2013, 20:15 Uhr

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.

Contents 1. Definition 2. Idea of A* 3. Function 4. Properties 5. Area of application 6. Example 7. Related algorithms and Disadvantages 8. References

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 ${\displaystyle f(n)}$ (${\displaystyle f(n)}$ can describe for example length, costs etc.). The node with the most minimal value will be analyzed futhermore.

${\displaystyle f(n)=g(n)+h(n)}$

${\displaystyle g(n)}$: previous costs from the start node ${\displaystyle 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

• Node which have to be 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 ${\displaystyle 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: ${\displaystyle L1}$ is an optimal solution with the costs of Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): K*

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

The fact that ${\displaystyle L2}$ is a sub-optimal solution means for ${\displaystyle 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) <=K* , and thats means Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): f(x)<=K* < f(L2) , thus ${\displaystyle f(L1)<f(L2).}$

So the A* does not show the sub-optimal solution ${\displaystyle L2}$ as long there exists an another optimal solution like ${\displaystyle 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.

Example

In this example we have to find the shortest path betwenn node H and node A. For that we use A*-Algorithm.

First Iteration

First of all the two neighbor nodes of H will be analyzed according to their distances and air-line distances. The next step is summing these distances up and choosing the minimal one. These air-line distances are given.

Related algorithms and Disadvantages

A related algorithm to the A*-Algorithm is the Dijkstra-Algorithm. In comparision, the Dijkstra does not use any information about the position of the end node. It searches in all possible ways simoultaneously until the end node is found. The A* does not analyze so many nodes but it must be informed of the position of the end node to use it's heuristic function.

Although the A* does not analyze so much as the Dijkstra there are still some disadvantages in comparision to other algorithms. First of all, during the search all nodes will be saved in the OPEN List and CLOSED LIST which requires a big storage to save these information. So if there exists a very complexe problem, the A* is inapplicable for that. A good example for that is the 15-Puzzle in which the graph has ${\displaystyle 16!=20.922.789.888.000}$ nodes. The next problem is that the heuristic can be very complexe according to the time. If the heuristic does not work with a big preciseness and monotonously than some nodes can be analyzed more than once, thus the required time during the search grows exponentially.

References

1. http://de.wikipedia.org/wiki/A*-Algorithmus 2. http://www.geosimulation.de/methoden/a_stern_algorithmus.htm 3. http://pille.iwr.uni-heidelberg.de/~astar01/ 4. http://www.policyalmanac.org/games/aStarTutorial_de.html 5. http://www.hubertus-becker.de/files/khepera-workout.de.pdf