The Traveling Salesperson Problem: In Search of Polynomial Time
The Traveling Salesperson Problem is one of the most famous open problems in computer science. What is it, and why is it so important?
GLPK solution of a traveling salesperson problem. Photo by Xpron. Public domain, via Wikimedia commons. Imagine you are planning a road trip. To save time and gas, you want to choose the shortest route that goes through all the cities you want to visit. How do you figure out what path to take? One option is the brute force approach — measuring and comparing the lengths of every possible route to find the shortest one. However, the number of possible paths grows very quickly as you add more destinations. With five cities to visit there are 24 possible routes, but...