D1 3.2 - Travelling salesman upper bounds
You will distinguish the practical and classical travelling salesman problems, create a complete network of shortest distances, and find upper bounds using nearest neighbour and doubled minimum spanning trees with shortcuts.
What an upper bound promises
Can the same nearest-neighbour rule produce a tour of length from one starting town and from another? Yes. A quick method can give a usable route without proving it is the best route.
You already know
A minimum spanning tree connects all nodes with least total arc weight. A Hamiltonian cycle visits every node once before returning to its start. A tour starts and finishes at the same node and visits every required node.
The travelling salesman problem concerns visiting nodes. Route inspection concerns covering arcs. You may be allowed to pass through a town again without needing to drive along every road.
Practical and classical travelling salesman problems
In the practical problem, find a shortest closed route visiting every node at least once; nodes may be revisited.
In the classical problem, find a shortest Hamiltonian cycle: each node is visited once, apart from returning to the start. Here the classical problem is considered on complete undirected networks satisfying the triangle inequality.
Any actual permitted tour of length proves that the optimum is no greater than . This makes an upper bound. A smaller upper bound gives a stronger guarantee; an algorithmic tour need not attain the optimum.
Key idea
An upper bound comes from a route you can actually use. Choose the smallest valid upper bound found, and include the return to the start.
Check which task the route is meant to accomplish.
A complete network of shortest distances
For a road network, replace each pair of towns by a link weighted with its shortest road distance. The resulting complete network can include a link where no direct road exists. Expanding each link back into its actual shortest road path gives a usable practical route.
Triangle inequality for shortest distances
For any three nodes ,
Travelling by a shortest route cannot be longer than the particular route that goes via .
Not in the formula booklet: learn it.
This permits shortcuts: in the complete network, omitting an already visited intermediate node cannot increase the length. A Hamiltonian cycle there may expand to a road route with repeated towns. Keep the abstract cycle and the actual road itinerary distinct.
[DIAGRAM: asset_name: Roads before shortest-distance completion; asset_slug: 9fm0-d1-170-road-network; caption: The direct roads do not yet form a complete shortest-distance network.; description: Four towns A, B, C, D with undirected roads AB2, BC3, CD4, DA10 and BD8; there is no direct AC road.]
Worked example 1: replacing roads by shortest links
Question. Roads have weights , with no direct road. Construct the complete shortest-distance matrix. Interpret its cycle as an actual road route.
Plan. Compare direct roads with indirect paths, then expand the final -to- link when interpreting the cycle.
The other three direct roads are already shortest. Thus
Why replace the direct weight by ? A complete shortest-distance link represents a journey, not necessarily one road.
Answer. The matrix is displayed above. The cycle has length . Its actual road itinerary is , because the shortest return from uses .
Check. The road sum is , and every town is visited.
Worked example 2 changes only , from weight to weight . Every shortest distance depending on that road must be updated.
Worked example 2: a changed road changes several links
Question. Construct the shortest-distance matrix when . Interpret the same cycle .
Plan. Recalculate indirect distances, retaining the same distinction between a complete-network link and an actual road.
Why does change even though its direct road still has weight ? Its shortest road path uses , whose weight has fallen.
Answer. The cycle length is . Its road itinerary remains .
Check. Its expanded length is .
Shortest-distance completion preserves the practical optimum: any complete-network cycle expands to a valid road tour of the same length. Conversely, a road tour can have repeated visits shortcut in the complete network without increasing its length. This justifies solving the practical road problem through a classical metric network.
Watch out
Wrong: report only the complete-network cycle when the question asks which towns are actually passed through. Right: expand every indirect link into its road path, including repeated towns.
Reduce the same road weight once more.
Nearest neighbour upper bounds
Nearest neighbour chooses the closest unvisited node from the current node. It does not look ahead to the eventual cost of returning, which is why the starting node and tie choices can matter.
Nearest neighbour algorithm
Start at the specified node. Repeatedly travel to a nearest unvisited node. When every node has been visited, return to the starting node. Sum all links of this closed tour.
Resolve a tie as instructed; if no rule is given, either tied choice is valid. We use alphabetical choices in the following traces. Trying more starts can improve the upper bound, but does not in general prove optimality.
Not in the formula booklet: learn it.
Continue this lesson.
You’re previewing NovaLearn without an account. Create a free account to read the rest.
Create free account