|
|
 |
| TSP Annotated Bibliography |
 |
|
1932
K. Menger, "Das botenproblem", in Ergebnisse eines Mathematischen
Kolloquiums 2 (K. Menger, editor), Teubner, Leipzig,
pages 11-12.
This volume contains a statement of a problem
posed by Karl Menger on February 5, 1930, at a mathematical colloquium
in Vienna. Several historical studies of the TSP (Bock (1963),
Hoffman and Wolfe (1985)) point to this statement as a precursor
of the TSP. Bock (1963) translates Menger's statement as:
"We designate as the Messenger Problem (since this problem is encountered
by every postal messenger, as well as by many travelers) the task of finding,
for a finite number of points whose pairwise distances are known, the shortest
path connecting the points. This problem is naturally always solvable
by making a finite number of trials. Rules are not known which would
reduce the number of trials below the number of permutations of the given
points. The rule, that one should first go from the starting point
to the point nearest this, etc., does not in general result in the shortest
path."
|
|
|
|
