12.4. Traveling Salesman Problem

Try these first

1. 1.

   Define the Traveling Salesman Problem.

   Hint

   Think about routes in delivery planning.

2. 2.

   What does NP-hard mean?

   Hint

   Consider how quickly solutions can be checked.

3. 3.

   What is the goal of the Traveling Salesman Problem?

   • To find the longest route
   • To find the shortest route that visits all cities
   • To find a random route

   Hint

   Focus on what the salesman aims to achieve.

4. 4.

   True or False: The Traveling Salesman Problem can be solved in polynomial time for all instances.

   • True
   • False

   Hint

   Reflect on the complexity classifying problems.

5. 5.

   Given a set of cities and distances between them, write a program that implements a heuristic to approximate a solution to the Traveling Salesman Problem.

   Hint

   Start with a distance matrix and pick the shortest route iteratively.

6. 6.

   Explain how the NP-hard classification affects real-world applications of TSP in industries such as logistics and delivery services.

   Hint

   Reflect on how companies deal with large travel demands.