The Traveling Salesman Problem 4: Spanning Tree Heuristic

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

The traveling salesman problem is NP-hard, that is, there is no polynomial-time algorithm that solves it. Instead, we look for approximation algorithms based on heuristic (common sense) rules. One of the easiest to state is the following: obtain the minimum spanning tree of the given points (with Kruskal's algorithm or Prim's algorithm) and then traverse it in preorder (in which we visit the root first and then recursively do a preorder traversal of each of its subtrees). As we can choose the root of the tree to be any point, there are several possible answers. Choose the best of them. The solutions obtained by this method are of length at most twice the optimal. Because of its speed, it can be used with other heuristics, for example 2-opt, to improve the result.

Contributed by: Jaime Rangel-Mondragon (August 2012)
Based on work by: Ed Pegg Jr
Open content licensed under CC BY-NC-SA




[1] E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, and D. B. Shmoys, eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization, New York: John Wiley & Sons, 1985.

Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.