A traveling salesman has to travel through a bunch of cities, in
such a way that the expenses on traveling are minimized.
This is the infamous Traveling Salesman
Problem (aka TSP) problem (formal
defintion). It belongs to a family of problems, called
NP-complete problem. It is conjectured that all those problems
requires exponential time to solve them.
In our case, this means that to find the optimal solution you have to
go through all possible routes, and the numbers of routes increases
exponential with the numbers of cities.
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
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.
Description of Algorithms
x2 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(n2log(n))
time ,since the input is a complete graph (n is the number of
inserted points).
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.
x1.5 Algorithm:
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.
The approximation ratio bound is 1.5, although the argument here is a bit more complicated. Note: This applet doesn't actually implement minimum weighted
matching but uses an approximation method
(which can be used directly
on the input points by clicking "Match points").
Iterative Algorithm:
We generated an arbitrary initial solution, by visiting
all points in order they were inserted.
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).
Removing Intersections Scheme:
This algorithm is applied on already computed TSP tour. It performs a
loop which stops only after all intersections have been removed (which
must happen after at most n2times).
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.