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

Aktuelle Version vom 8. Juli 2013, 07:52 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. If the A* algorithm finds a solution, then there is no better one. It finds an optimal solution.

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.

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 ${\displaystyle h'(i)}$ which estimates the length of 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 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 ${\displaystyle 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 ${\displaystyle 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 ${\displaystyle 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.

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.

In the first step you put the start node, which will be here A, in the OPEN list. Because there is no other element in the OPEN list you chose A as the next node to visit and move it to the CLOSED list. Now you have to expand As neighboars, which are in our case B,C and D. That mean you calculate for every one of these nodes their ${\displaystyle f'(i)}$, set their reference to node A and put them on the OPEN list. Our lists now look like this:

OPEN: 2, 3, 4

CLOSED: 1

If we illustrate that as an search tree we get the following tree. The colors have the following meanings:

Green nodes: the last node added to our solution

Red edges: edges which are part of the already fixed solution

Blue edges: edges from the minimal spanning tree

Black edges: the two shortest edges which connect the MST with the already fixed solution

As you can see in the diagram solution 4, that means node D, has the smallest estimated distance to complete the TSP, so we have to put it on the CLOSED list and expand the neighboar nodes of it. Our OPEN and CLOSED list now looks like that:

OPEN: 2, 3, 5, 6

CLOSED: 1, 4

In the next step we look in our OPEN list and chose that node (solution) which hase the smallest estimated distance. We now have the choice between 6 and two because both have the value 2180. In this case it doesn't matter which one you chose so we decide us for 6. We now expand all its neighboars, determine their ${\displaystyle f'(i)}$, set the back reference to 6 and add them to the OPEN list.

OPEN: 2, 3, 5, 7, 8

CLOSED: 1, 4, 6

Now we found two solution for our TSP: Solution 7 and 8. Because we want to minimize the distance we have to travel we would decide us for solution 7. But this solution has not the smallest estimated distance in the OPEN list, so instead of putting 7 on our CLOSED list to end the search, we put 2 on the CLOSED list and expand its neighboars. ${\displaystyle f'(2)=2180>2320=f(7)}$

OPEN: 3, 5, 7, 8, 9, 10

CLOSED: 1, 4, 6, 2

Because 9 (or node C) has the smallest value we put it on the CLOSED list and add it's neighboar nodes D (as 11) and E (as 12) to the OPEN list.

OPEN: 3, 5, 7, 8, 9, 10, 11, 12

CLOSED: 1, 4, 6, 2, 9

Now we would normally chose D (or 11) to be expanded but this is not possible, because this would lead to an invalid solution. So we decide us for the next smallest, which is E (or 12).

OPEN: 3, 5, 7, 8, 9, 10, 11, 12

CLOSED: 1, 4, 6, 2, 9, 12

Because we now have a valid solution, which is also the optimal one, we can end the algorithm and do our tour through Kaiserslautern on the path Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): A \rightarrow B \rightarrow C \rightarrow E \rightarrow D \rightarrow A

with the total distance of 2320. Because this tour lenght is equal to one of solution 7 we also could chose the path Fehler beim Parsen (http://mathoid.testme.wmflabs.org Serverantwort ist ungültiges JSON.): A \rightarrow D \rightarrow E \rightarrow C \rightarrow B \rightarrow A