Алгоритмы

Suppose you were asked to plan an itinerary for a traveling salesman who must visit a number of cities. You are given a map on which the distances between the cities are marked and you are asked to find the shortest route that passes through all the cities and returns to the starting point. An approach to this problem that is certain to give the correct answer is to trace all the possible routes, measure their length and pick the shortest one. If the tour included more than a few cities, however, hundreds or thousands of routes would have to be checked. If there were 100 cities, then even the fastest computers would require weeks of calculation to find the shortest path.

In the search for a quicker solution you might try some less rigorous methods. One idea that seems reasonable is always to visit nearby cities before going on to those farther away. You would soon discover, however, that this procedure does not invariably yield the correct answer. Other shortcuts also fail. In fact, the best methods known for solving the problem are not much better than the obvious but laborious procedure of checking all the possible itineraries. Mathematicians now suspect that this problem and many others like it may forever remain beyond our ability to solve in any efficient way. That speculation itself, however, is unconfirmed; although no faster methods of solution have been found, neither has it been proved that faster methods do not exist.

In the problem of the traveling salesman's tour it is not the solution for a particular set of cities that is of the greatest importance but a general method for finding the solution for any cities. Such a method is called an algorithm: it is a precisely stated procedure or set of instructions that can be applied in the same way to all instances of a problem. If the problem is to be solved with the aid of a computer, an algorithm is indispensable, because only those procedures that can be stated in the explicit and unambiguous form of an algorithm can be presented to a computer. Instructions that are vague or that rely on intuition are unacceptable.