What is the Traveling Salesman Problem?
Q: What is the Traveling Salesman Problem?
A: The Traveling Salesman Problem (TSP) is a classic algorithmic problem in the field of computer science and operations research. It focuses on optimization, with better solutions often meaning cheaper, shorter, or faster solutions.
Q: How is TSP expressed?
A: TSP is most easily expressed as a graph describing the locations of a set of nodes.
Q: Who first defined the TSP?
A: The traveling salesman problem was defined in the 1800s by the Irish mathematician W. R. Hamilton and by the British mathematician Thomas Kirkman.
Q: Who studied it further during the 1930s?
A: During the 1930s, mathematicians Karl Menger at Vienna and Harvard studied it further.
Q: What did Hassler Whitney introduce soon after?
A: Hassler Whitney at Princeton University introduced the name "traveling salesman problem" soon after its definition.
Q: What does "better solution" mean in this context?
A: In this context, better solution often means a solution that is cheaper, shorter, or faster.
Q: What algorithm was considered obvious by Menger when studying TSP?
A:Menger considered an obvious brute-force algorithm when studying TSP and observed that using nearest neighbor heuristic does not always yield optimal results.
