AQR Investigation 1.11: Taking a Trip
- Steve Phelps
Drag the points around, change the number of points, and explore the traveling salesman path and the minimum spanning path. The traveling salesman path is the shortest closed path, a path that starts and ends at the same point, where each point is passed through just once. The minimum spanning path shows the shortest path that connects all points. It is possible that the path will pass through a point more than once.
Explore the two paths. Under what conditions are the two paths the same? Under what conditions do the two paths have the same length? Is it possible for the traveling salesman path to be shorter than the minimum spanning path?