Travelling Salesman's Problem
How To Visit Each Vertex Of A Network In The Most Economical Way
[Please note that no algorithm has, of yet, been produced for this problem.]
A Hamiltonian cycle is a tour which contains every vertex precisely once.
1st Attempt: Use a "greedy" algorithm such as "Nearest Neighbour" algorithm - always taking the next nearest vertex from where you are. This should get you off to a good start, but even when this leads to a Hamiltonian cycle, it might not be the minimum weight.
The Lower Bound
In order to decide if your cycle is the best possible route, or if you should continue to search for a better one, you can calculate the lower bound for the cycle. If your total is near enough to the lower bound, it is sensible to assume you have the best route.
Fig 2. An example of calculating a Hamiltonian Cycle
Fig. 2a shows a network in which you are asked to draw a Hamiltonian cycle for. Fig. 2b shows a possible Hamiltonian cycle for the network. For any Hamiltonian cycle for the network will consist of 2 edges from vertex A and 3 edges linking vertices B, C, D and E.
Therefore, we can work out the lower bound from this information: The two edges from A must have a total weight of 4 + 5 [the two smallest edges from A]. Then by applying Prim's algorithm, to the points A, B, C, D and E, we can see that the minimum weight for them is 5 + 5 + 6 [the three smallest edges linking them]. The lower bound for this network is therefore 25.