Heuristics: A*-algorithm 1

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:

$f'(i)=g(i)+h'(i)$

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

The Estimator for the TSP

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 $h'(i)$ which estimates the length of the rest of the TSP path.

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

$length(MST)$ is the length of the minimal spanning tree, which can be build up from the not already visited nodes. $length(two\ shortest\ connections)$ is the length of the shortest edge from the start node plus the shortest lenght of the last node of our already fixed solution, which both connect the already visited nodes with the MST.

Steps of the A* algorithm

1. Add the start node s to the OPEN list.
2. If the OPEN list is empty, end the algorithm with no result. In this case a solution can not found.
3. Chose node n from the OPEN list which has the minimal $f'(i)$ and move it from the OPEN to the CLOSED list.
4. If node n is the destination node the algorithm has found the optimal solution and terminates. To get the shortest path from the start node to the end node travel back from n to s.
5. Otherwise expand n. That mean you create the successor n' from n with a reference from n' back to n and determine for every successor n' the following values:
   1. If n' doesn't exist in the OPEN- or CLOSED list, estimate $f'(n')=g(n')+h'(n')$ and put Node n' on the OPEN list.
   2. If n' already exist in the OPEN- or CLOSED list and you have found a better connection, then you have to update the back reference of n' and its value for $f'(n')$.
   3. If n' is on the CLOSED list and its reference was modified then put n' back on the OPEN list. (This only applys for none monoton estimaters. In our case this step can be left out because our estimator for the TSP is monoton.)
6. Go to step 2.

Example

Now that we know how the A* algorithm works and 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.

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.

Fehler beim Erstellen des Vorschaubildes: Die Miniaturansicht konnte nicht am vorgesehenen Ort gespeichert werden

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.