Пример: Транспортная логистика
Я ищу:
На главную  |  Добавить в избранное  

Иностранныеязыки /

Алгоритмы

←предыдущая  следующая→
1 2 3 4 5 



Скачать реферат


The Efficiency Of Algorithms.

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.

The efficiency of computer algorithms is a topic of obvious practical importance. It is also of interest in more formal areas of mathematics. There are some problems in mathematics and logic for which no algorithm can ever be written, and there are many others for which efficient, fast algorithms are already known. Between these two groups is a third class of problems that can always be solved in principle, but for which there are only inefficient (and therefore largely unusable) algorithms. For some of these difficult problems mathematicians have been able to demonstrate that efficient algorithms can never be designed. For many of the most important problems, however, there is only the suspicion that good algorithms are impossible.

A given problem can have more than one algorithm for its solution. For example, children in Europe learn a procedure for subtraction slightly different from the one taught in the U.S. Both of the subtraction algorithms, however, give the same result in the same amount of time. That is not invariably the case with different algorithms for solving the same problem. One celebrated problem that can be solved by either a "fast" algorithm or a "slow" one is the problem of the Koenigsberg bridges.

In the I8th-century German city of Koenigsberg (which is now the Russian city of Kaliningrad) a park was built on the banks of the river Pregel and on two islands in the river. Within the park seven bridges connected the islands and the riverbanks. A popular puzzle of the time asked if it was possible to walk through the park by a route that crossed each of the bridges once and only once.

For the solution of the problem the size and shape of the islands and the length of the bridges are immaterial: the only essential information is the pattern of interconnections. This information can be presented compactly in the mathematical structure known as a graph, which is merely a set of points with lines drawn to join them. In the case of the Koenigsberg park each of the riverbanks, and each of the islands is condensed to a single point, and each of the bridges is represented by a line between two points. Thus the graph consists of four points and seven lines. If the lines are labeled, any path through the park can be specified by a simple listing of labels.

The obvious approach to the problem is to list all the paths that cross all the bridges and to eliminate from consideration those that cross any bridge more than once. This is the technique of exhaustive search, similar to the one employed in the problem of the traveling salesman. When the mathematician Leonard Euler was presented with the problem of the Koenigsberg bridges, he recognized the limitations of the technique and found another method. In recognition of his contribution a path that traverses each line of a graph exactly once is now called an Eulerian path.

Euler wrote: "The particular problem of the seven bridges of Koenigsberg could be solved by carefully tabulating all possible paths, thereby ascertaining by inspection which of them, if any, met the requirement. This method of solution, however, is too tedious and too difficult because of the large number of possible combinations, and in other problems where many more bridges are involved it could not be used at all."

Euler's alternative method is much simpler. He showed that a tour of the kind sought must exist if the graph meets two conditions. First, it must be possible to go from any point in the graph to any other point by following the lines of the graph: in other words, the graph may not be disconnected. Second, every point of the graph, with two possible exceptions, must be at the junction of an even number of lines.

It is not hard to understand why a graph cannot have an Eulerian path unless it meets these conditions. All regions of the graph must be connected to one another if there is to be any path that traverses all the lines. Each point must have an even number of lines because half of them are required to reach the point and the other half to leave it. Two points with an odd number of lines can be allowed if they are chosen as the starting and finishing points of the path. Demonstrating that any graph that meets these conditions actually has an Eulerian path requires a somewhat more complicated argument, which we shall not present here, but Euler was able to give a rigorous proof.

It is an easy matter to express Euler's solution to this problem in an algorithm that could be executed by a computer. The first requirement, connectivity, can be established by marking some point of the graph, then similarly marking all points connected to it by lines, then all the points connected to the newly marked points, and so on. The graph is connected if at the end all points have been marked. The second requirement is just as easily tested: the machine is instructed to examine each point of the graph and count the number of lines that terminate at that point. If no more than two of the points have an odd number of lines, the graph has an Eulerian path. The park at Koenigsberg met the first condition but not the second, and so there was no Eulerian tour of the seven bridges.

Euler's method is unquestionably the more economical approach to the problem of Koenigsberg bridges: it requires that each point and line of the graph be listed just once, whereas the exhaustive search is not completed until every path that crosses all the bridges has been listed. The number of such paths is much larger than the number of points and lines in the graph. In that sense Euler's method is the better algorithm, but how much better? How can the difference be measured and how can one fell if the difference is significant?

For a graph with only four points and seven lines both techniques are fast enough to be considered practical. Suppose, however, that more islands and bridges were added to the park, or in other words that more points and lines were added to graph. If the problem is being solved by Euler's method, each new point merely adds one item to the list of points that must be checked. If the paths are to be examined by exhaustive search, on the other hand, then with each new point and line the size of the list is multiplied by some factor. A moderate increase in the size of the graph results in an explosive increase in the number of paths. Ultimately

←предыдущая  следующая→
1 2 3 4 5 



Copyright © 2005—2007 «Mark5»