[tsp-mst-exercise]The traveling salesperson problem (TSP) can be solved with the minimum-spanning-tree (MST) heuristic, which estimates the cost of completing a tour, given that a partial tour has already been constructed. The MST cost of a set of cities is the smallest sum of the link costs of any tree that connects all the cities.
-
Show how this heuristic can be derived from a relaxed version of the TSP.
-
Show that the MST heuristic dominates straight-line distance.
-
Write a problem generator for instances of the TSP where cities are represented by random points in the unit square.
-
Find an efficient algorithm in the literature for constructing the MST, and use it with A graph search to solve instances of the TSP.
Answer
Improve This Solution
View Answer