Тип: реферат

Язык: английский

Дата добавления: 10.05.2012

Размер файла: 15,8 KB



Краткое описание работы

Some mathematical problems can be solved only by methods too slow for even the fastest computers. More efficient methods have not been found, but neither has it been proved, that there are no better methods by Harry R.Lewis and Christos H. Paradimitrou
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.
An example of an algorithm is the procedure taught in the schools for the subtraction of whole numbers. If each of the steps in this procedure is applied correctly one at a time, the algorithm will always yield the correct result. What is more, once the algorithm has been learned or stored in the memory of a computer or embodied in the circuitry of an electronic calculator, it can be applied to an infinite set of subtraction problems. With this one algorithm the difference between any two whole numbers can be determined.
In principle any problem for which an algorithm can be devised can be solved mechanically. It may therefore seem surprising that there are problems for which algorithms exist but for which we so far have no practical general solution. The algorithms for solving these problems always give a correct answer, but they often require an inordinate amount of time. The problem of the traveling salesman’s tour is among these intractable tasks.