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

Version vom 17. Juni 2013, 16:48 Uhr

The Idea of the Algorithm

The A* (or A star) algorithm is a search algorithm which finds the shortest path between two nodes. It is considered as an extension of the Dijkstra algorithm, but tries to improve the runtime by using a heuristic to find the optimal solution. An example for such an heuristic would be the air-line distance (euclidean distance) between the start- and endpoint.

To decide which path the algorithm should take through the graph it uses this cost function:

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

${\displaystyle f(i)}$ represents the estimated total costs of a path from the start node, through the node ${\displaystyle i}$ to the endnode. ${\displaystyle g(i)}$ is the distance from the start node to node ${\displaystyle i}$. ${\displaystyle h'(i)}$ is the estimated distance from ${\displaystyle i}$ to the end node, this estimated value is the result of the heuristic function.The function ${\displaystyle f'(i)}$ has to full fill the criteria that it doesn't overestimate the real distance to the endnode.

Normally the A* algorithm is used to find the shortest path from node a to node b in a graph, but you can also modify it to solve the TSP problem. For that you need an function ${\displaystyle h'(i)}$ which estimates the rest of the TSP path.

${\displaystyle h'(i)=lenght(MST)+length(two\ shortest\ connections)}$

${\displaystyle length(MST)}$ is the length of the minimal spanning tree, which can be build up from the not already visited nodes. ${\displaystyle length(two\ shortest\ connections)}$ is the length of the two shortest edges, which connect the already visited nodes with the MST.

Now that we have a heuristic to determine the total length of a TSP we can have a look on how we find the shortest path in the TSP.

Example

To illustrate the way of the A* algorithm we will use a typical TSP problem. Imagine you want to make a sightseeing tour through Kaiserslautern and you want to visit the sights A,B,C,D,E which are connected by ways with the given lengths shown in the diagram.

Because you are lazy person you want to minimize the distance you have to walk between the different sights. This also includes that you want to walk a way only once. To solve this TSP you decide to use the A* algorithm.

Steps of the A* algorithm

1. We add our start node to the so called OPEN list. This is the list of nodes which are potential canidates to be the next node in our path. Because we only can put our start node in here right now this will also be the next node to visit. In our example this would be the node A.
2. Now we have a look at our OPEN list. If it is empty we end the algorithm with no result. (At the moment this makes no sense, but because the algorithm is iterative it will be used later.)
3. In this step we chose that node (named n) from the OPEN list which has the minimal ${\displaystyle f'(i)}$. This node will be deleted from the OPEN list and will be added to the CLOSED list. The CLOSED list contains the already visited nodes which will not considered in our later searches. In our example the only node in the OPEN list is the start node A. This is also the node with the minimal distance, so it will be added to the CLOSED list.
4. If node n is the destination node (or in our case for the TSP: if n is node which complets the TSP path), the algorithm has found the optimal solution. In our example this is for the first step not the case because we only have node A which doesn't complete the TSP path.
5. Otherwise if the node n is not the destination node (or the node which complets the TSP path) we expand n.