Return to my Computer pages
Go to my home page
© Copyright 2000, Jim Loy
A travelling salesman (starting in Los Angeles) must visit the above 21 cities and return home, making a loop. He would like to travel in the most efficient way (cheapest way or shortest distance or some other criterion). We can draw paths between each pair of cities, 210 paths in all (20+19+18+...). Each of these pairs of cities has a number associated with it, showing the efficiency of the path between them (price, distance, or whatever). And there are 20!/2 (1,216,451,004,088,320,000) possible loops including all 21 cities (half of the loops are backwards versions of other loops). The brute force way of finding the most efficient loop would be to list them all, and total up the numbers between pairs of cities. No computer can list 1,216,451,004,088,320,000 loops in any reasonable length of time. So the brute force method is impractical, except for a small number of cities.
The amount of time it takes to count the cities is roughly proportional to the number (n) of cities. Sorting the cities alphabetically using a bubble sort would be proportional to n^2 (n squared). Sorting by a more efficient method, like Quick Sort would be proportional to n log n (where log is the base 2 log), which is much less than n^2 for large n. Well, listing the loops of these cities is proportional to n!, which takes much much more time than these other processes. Of course, you don't need to list them all. Most loops are very inefficient. You can throw out loops that zig-zag back and forth across the country. You may be able to throw out loops that intersect themselves. Here is a relatively efficient loop (assuming that straight line distance is the accepted criterion):
Now, is this the most efficient loop? I don't know. Nobody knows, in general (there are trivial maps that can be solved easily). There are many ways to produce a relatively efficient loop, like mine above. But the only known ways to guarantee that the loop is the most efficient are all much too slow for any forseeable computer.
Problems that are this difficult are called NP-Hard problems. By the way, NP stands for "nondeterministic polynomial." All such problems have been shown to be equivalent. If you can find the solution to one of these, the solutions to all of them would follow.