A Hamiltonian cycle is a tour that contains every node precisely once. Therefore, the classic travelling salesman problem is to find the Hamiltonian cycle of minimum weight - i.e. the shortest route passing through each node once.
As the number of nodes increases the number of possible Hamiltonian cycles increases very rapidly. For n nodes the number of Hamiltonian cycles is .
The method of evaluating all Hamiltonian cycles therefore has exponential order. A 600MHz processor evaluating cycles for 20 nodes takes about 3 years. Testing each of these cycles to find the optimal solution is generally too time consuming to be feasible for most problems, so finding a reasonably good solution with the Nearest Neighbour algorithm suffices.
The Nearest Neighbour algorithm
- Choose any starting node
- Consider the arcs which join the previously chosen node to nodes not yet chosen. Choose the arc with minimum weight and add this node to the tour.
- Repeat 2 until all nodes have been added
- Add the arc which joins the last node to the first.
Disadvantages
- The algorithm does not necessarily give the best solution - it chooses the best route at each node without considering future problems
- It may lead to an incomplete tour.
The Lower Bound algorithm
This finds the lower weight limit of a Hamiltonian cycle. If the Nearest Neighbour algorithm gives an answer which is significantly higher than the lower bound, it suggests there is a better solution. If the NN algorithm gives an answer which equals the lower bound, the tour is optimum.
- Choose any node, X. Find the total of the 2 smallest weight arcs joined to X.
- Consider the network obtained by ignoring X and any arcs that join to X. Find the total weight of the minimum connector for this network.
- The sum of the two totals is the lower bound.
Tour Improvement
This algorithm attempts to improve the best solution found so far.
- Let 1, 2, 3 ... n be the successive nodes of a Hamiltonian tour (NB n+1=1, n+2=2, n+3=3)
- Let d(V,W) be the weight of the arcs between V and W
- Let i =1
- If
then swap
and
. (I.e. for i=1, if the weight between node 1 and the node 3 plus the weight between node 2 and node 4 is less than the weight between node 1 and node 2 plus the weight between node 3 and node 4, swap the second and third nodes.)
- Replace i by i + 1
- If
then go to step 2. (I.e. repeat until i is greater than the number of nodes in the tour.)
Also See
See the other D1 notes:
- Algorithms
- Sorting algorithms
- Packing algorithms
- Graphs and networks
- Minimum connector problems
- The shortest path
- Route inspection
- The travelling salesman problem
- Linear programming
- The simplex algorithm