Programming Praxis

The traveling salesman problem is classic: Find the minimum-length tour that visits each city on a map exactly once, returning to the origin. It is an important problem in practice; consider, for instance, that the cities are soldering points on a large circuit board, each of which must be visited by a soldering robot. It is also an important problem in mathematics, and is known to be in NP, meaning that optimal solutions for non-trivial problems are impossible. Nonetheless, there exist heuristic algorithms that do a good job at minimizing the tour length.

We will examine the traveling salesman problem in an occasional series of exercise, beginning with today’s exercise that looks at the brute-force solution of examining all possible tours. The algorithm is simple: First, select a tour at random, then determine all possible permutations of the tour. Second, determine the length of each tour. Third, report the tour with minimum length as the solution.

Your task is to write a program that solves the traveling salesman problem using the brute-force algorithm. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2