A traveling salesman must visit customers in a given number of cities scattered across the country. The problem is to find the shortest route that takes the traveler just once to each city before returning home.
![](https://i0.wp.com/www.sciencenews.org/wp-content/uploads/2004/12/4704.jpg?resize=232%2C300&ssl=1)
![](https://i0.wp.com/www.sciencenews.org/wp-content/uploads/2004/12/4705.jpg?resize=144%2C168&ssl=1)
![](https://i0.wp.com/www.sciencenews.org/wp-content/uploads/2004/12/4706.jpg?resize=300%2C188&ssl=1)
![](https://i0.wp.com/www.sciencenews.org/wp-content/uploads/2004/12/4707.gif?resize=148%2C150&ssl=1)
Listing all possible routes, calculating the length of each one, and picking the shortest is one possible strategy for solving the problem. For a large number of cities, however, such a brute-force approach requires a huge amount of computation.