Traveling Salesman

  1. Assuming you start at point A, in what order should you travel to the other points so that you travel the shortest possible distance? How many possible combinations are there?Screen Shot 2019-06-11 at 5.23.30 PM.png
  2. Same questions as number one, but with 6 points total now:Screen Shot 2019-06-11 at 5.26.45 PM.png
  3. And one more time, but with 8 points:Screen Shot 2019-06-11 at 5.29.12 PM.png
  4. What do you notice about the number of possible combinations as the number of points grows? Can you create a rule for this?
  5. The Traveling Salesman problem developed from a question about the most efficient way for a salesman to travel to a list of US cities. Let’s say you want to visit Houston, Chicago, Los Angeles, Nashville, New York City, and Boston starting from Washington D.C. What would be the best route to take?
  6. Unexpectedly, this has applications in astronomy for determining the most efficient order for a telescope to observe celestial bodies to minimize movement and maximize observation time. Now, let’s say a telescope is hoping to observe 50 objects in the night sky. How many possible paths are there?
  7. Thinking about your answer to question 5, let’s say it takes one minute for a computer to evaluate every 10 paths. How long will it take to evaluate the most efficient order in which to view the celestial bodies?
  8. Obviously, simply testing every path is impractical, therefore mathematicians are trying to figure out a way to be more efficient. Thinking about your work in questions 1, 2, 3, and 5 can you propose a way to reduce the number of necessary calculations?
  9. The Traveling Salesman problem is referred to as an NP-Hard problem rather than an NP-complete. Do some research into these terms and explain what is is mathematicians are trying to prove.