Finding a Route Is Easier Than Proving It’s Best
Imagine a delivery driver who must visit every city once and return to the starting point. A computer can quickly produce a reasonable tour: it might repeatedly choose a nearby unvisited city, then improve the result by swapping portions of the route. But a good route is not necessarily the shortest possible one.
That gap is the heart of the traveling salesman problem. Finding one workable itinerary is relatively easy; certifying that no better itinerary exists can require ruling out a vast number of alternatives.
Why the Possibilities Multiply
With each added city, there are many new ways to arrange the stops. In a straightforward exhaustive search, the computer checks possible orders, calculates each tour’s total distance, and keeps the shortest. The number of orders grows roughly like a factorial: adding a few cities can multiply the work rather than merely add a few more calculations.
Algorithms can cut down that search by using clever bounds. For example, if part of a route already costs more than the best complete route found so far, there is no reason to finish exploring that option. This can make many practical instances manageable, but it does not guarantee that every large instance will be solved quickly.
The Hard Part Is the Guarantee
A computer may find a route that is extremely short and still lack a proof that it is optimal. That proof matters when the goal is not just to get a useful answer, but to know that no shorter tour exists. For real logistics, a near-best route may be perfectly adequate; for a mathematical benchmark or a strict optimization requirement, the remaining gap matters.
So the problem is not that computers cannot plan a trip. It is that, as the map grows, the cost of ruling out every better trip can explode—and a convincing answer may be easier to find than to certify.
