Home | Bookmarks | Papers | Blog |

Applet By Kreimer Natasha.

If you want to get a notion of what numbers we are talking about look
at this:

the number of routes with 50 cities is (50-2)!, which is

12,413,915,592,536,072,670,862,289,047,373,375,038,521,486,354,677,760,000,000,000

An alternative approach would be to compute a solution which is not optimal, but is guarenteed to be close the optimal solution. We present here an applet that implements such an approximation algorithm for the Euclidean TSP problem.

__In our case__ we have
points in the plane (i.e. cities) and the cost of the traveling
between two points is the distance between them.
In other words, we have a map with cities, any two of which are
connected by a direct straight road (yeh, sure!) and we want to find a
shortest tour for our poor traveling salesman, who "wants" to visit every city.

The applet implements the following approximation algorithms:

**x2 Algorithm**- returns tour which is no worse than twice as long as an optimal tour.**x1.5 Algorithm**- returns tour which is no worse than one and half as long as an optimal tour.**Iterative algorithn**- Generate an arbitrary tour, and try iteratively to improve it locally. This algorithm does not have a performance guarantee. This algorithm can be run independently on input points or can be applied on output tours of above constant ratio bound algorithms.

The solution generated by those algorithms can be further improved by applying on it:

- Iterative algorithm for removing intersections in the tour - whenever there is an intersection, the tour can improved by "flipping" the tour.
- The iterative algorithm.

- find Minimum Spanning Tree (MST).
- perform preoder tree walk on MST, and construct a list of the vertices as we encounter them. (i.e. each vertex will appear only one - corresponding to its first encounter)
- the output tour is hamiltonian cycle that visits the vertices in order of this list.

The running time of this algorithm is **O(n ^{2}log(n))**
time ,since the input is a complete graph (

The lenght of the resulting tour is at most
twice of the optimal tour, since its lenght is at most twice that of
the **MST**, and the optimal tour is longer than the MST.

- find Minimum Spanning Tree (MST).
- find minimum weighted matching between odd vertices of MST.
- find an Euler tour in resulting graph and create list of vertices that represents it.
- find Hamilton cycle (which is in fact TSP tour) by visiting vertices in order of created list when only first appearance of vertex in list is encountered and any other appearance is skipped.

Then in each iteration:

- Select two random cities
- Interchange the two cities predecessors
- Calculate the weight of resulting tour.
- If new weight is smaller then old one - if so, replace the old tour by the new tour, else undo (2).

Each loop goes through all the pairs of edges in the tour and checks if they intersect.

- If so then two new edges will replace them. New edges created by interchanging the original edge's endpoints. To preserve TSP tour completeness the path between the original edges is reversed.

**The Applet:**

Source code

Back to the Workshop home page