The traveling salesman problem is simple to formulate. He must visit a certain number of cities, say ten, starting from one city and returning to it after having visited all the others. He knows the distances between the cities taken two by two.
What route should the traveling salesman take to minimize the distance travelled? The number of possible paths can be determined quite easily. For this, we choose a town which is considered to be the starting city. Then, we have nine possible choices to continue, eight once this choice is made, etc. We thus obtain 9 x 8 x 7 x… x 1 possible paths.
Like the meaning of journey does not count, the number of possible paths is 9 x 8 x 7 x 6 x 5 x 4 x 3 = 181,440. Comparing their lengths is therefore feasible using a computer in the case of ten cities.
Question :
The algorithm solving the traveling salesman problem presented above is considered inefficient. Why ?
Answer :
This algorithm is inefficient because, when the number of cities increases, it quickly becomes inapplicable. For example, for 20 cities, the number of trips to compare is equal to 60,822,550,204,416,000! If each path is generated in a nanosecond, it takes 60 million seconds to generate them all, which is about two years. Thus, for 21 cities, it will take 42 years, and for 22, almost a millennium!
This problem of traveler of commerce is one of a class of problems that could be solved if one of the Clay Institute’s million-dollar problems were solved in the affirmative. This is the “P = NP” conjecture.
Learn more about Hervé Lehning
Ecole Normale Normale and maths graduate, Hervé Lehning taught his discipline for a good forty years. Mad about cryptography, member of the Association of encryption and information security reservists, he has in particular pierced the secrets of Henri II’s cipher box.
- His blog MATH’WORLD on Futura
- the latest book by Hervé Lehning :
Also to discover: The universe of secret codes from Antiquity to the Internet published in 2012 by Ixelles.
Interested in what you just read?
Subscribe to the newsletter Fun math : every week, Futura deals with a math question for the enjoyment of 7 to 77 year olds. All our newsletters