On the Hamiltonian Game (A Traveling Salesman Problem)
Abstract
The purpose of this note is to give a method for solving a problem related to the traveling salesman problem. It seems worthwhile to give a description of the original problem. One formulation is to find the shortest route for a salesman starting from Washington, visiting all the state capitals and then returning to Washington. More generally, to find the shortest closed curve containing n given points in the plane. Clearly, it is sufficient to consider curves made up of line segments joining pairs of the given points. Also, unless all the points lie on a straight line, the optimal path will not pass through any point twice. Hence the problem can be stated as follows: Arrange the n points in a cyclic order so that the sum of the distance between consecutive points is a minimum. In this statement of the problem, arbitrary real numbers can be assigned as the "distances" between ordered pairs of distant points. Thus, the "distance" from A to B need not be the same as B to A. We shall sometimes refer to the "length" of AB instead of the "distance" from A to B. Since there are only a finite number of paths to consider, the problem consists in finding a method for picking out the optimal path when n is moderately large, say n = 50. In this case, there are more than 10 (expn 62) possible paths, so we can not simply try them all. Even for as few as 10 points, some short cuts are desirable.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 05, 1949
- Accession Number
- AD0204961
Entities
People
- Julia Robinson
Organizations
- RAND Corporation