What is the Traveling Salesman Problem (TSP) as defined in the video?

Conditions

• There is a finite set of $n$ cities.
• The objective is to minimize total path length.
• Each city must be visited exactly once.

Reasoning, step by step

1. Identify the problem as a classical optimization problem.
2. State the goal: finding the shortest possible path.
3. Specify the constraint: visiting each city exactly once.
4. Visualize the problem as a route connecting points in a 2D plane.

Example

The narrator defines TSP as finding the shortest possible path through a set of n cities so that each city is visited exactly once. The chart title reads "Traveling Salesman Problem (TSP)"; red points represent cities and green line segments form a tour.

Common misconceptions

• Thinking that TSP is easy to solve because its statement is simple.
• Assuming that the path does not need to return to the starting city (though the video focuses on the tour aspect).

Watch the explanation

Explore next

• Why does the video say TSP is difficult despite its simple statement?
• Which two machine-learning approaches does the playground use for TSP?
• What does greedy crossover do in the genetic-algorithm TSP demo?