Traveling Salesman Problem
Suppose a salesman plans to visit a set of cities. The classical formulation of the Traveling Salesman Problem (TSP) is as follows.Given a set of cities and a set of distances between the cities, find the route of the minimal length that visits each city exactly once and returns to the initial city.
The TSP is one of the most well-studied problems in combinatorial optimization thanks both to its theoretical importance and its applications in many important fields such as logistics, genome sequencing, and data clustering.