Рейтинг@Mail.ru
Rambler's Top100




Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

реферат на тему: Алгоритмы

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

branches like a tree, and the problem itself is called the spanning-tree problem. The spanning-tree problem can be solved correctly and quite efficiently by a method called the greedy algorithm, devised by Joseph B. Kruskal of Bell Laboratories. The procedure is simply to connect the closest pair of cities, then the next-closest and so on without adding any superfluous lines (lines joining cities that are already linked indirectly). It is far from obvious that this method always yields the shortest network, but it does, and it has the pleasant property of requiring no foresight and no reconsideration of earlier decisions. The greedy algorithm can be relied on to find the shortest network between cities under the rules specified, but in general that network will not be the shortest possible one. Further savings can be achieved by establishing junction points between cities. The properties of networks with such junctions were studied by the Swiss mathematician Jakob Steiner. It can be shown that any shortest network must be arranged so that each junction point is made up of three lines that meet at angles of 120 degrees. This rule provides some guidance in evaluating networks, but there are many possible networks with Steiner junction points. No algorithm has been discovered that finds the best network quickly.

The problem of the traveling salesman's tour is closely related. Again one is given a set of cities, but now one is asked to find the shortest round-trip tour. As a first guess the greedy algorithm suggests that perhaps the salesman should always go to the nearest city he has not yet visited, but this procedure does not work. Indeed, the problem is notorious for having resisted all attempts to find an efficient solution. Optimization problems are not fundamentally different from those that ask yes-or-no questions; in fact, every optimization problem can be rewritten in a yes-or-no form. In the traveling salesman problem, for example, we might be given a length along with a set of cities and asked to state whether a tour can be constructed that does not exceed the specified length. This yes-or-no problem cannot be harder than the associated optimization problem, because if the optimum tour could be found by some efficient method, it would be a trivial task to determine whether it exceeds a given number. Hence if the yes-or-no version is computationally intractable, one cannot hope to solve the optimization problem itself efficiently. For this reason certain optimization problems, such as that of the traveling salesman's tour and that of placing Steiner junction points, are said to be

NP-complete. Optimization problems are encountered often in engineering, economics, operations research and other fields. The discovery that at least some of these problems are NP-complete is therefore of considerable practical interest. Since the NP-complete problems probably have no efficient algorithms, there would seem to be little point in expending further effort in seeking optimum solutions. An alternative that has recently been adopted is to seek approximate solutions that are good even if they are not precisely optimal. One technique that has been applied to the traveling salesman problem offers a solution that may not be optimum but is guaranteed to be no worse than twice the optimum path. The procedure starts with the shortest spanning tree, which can be generated efficiently by the greedy algorithm. This network
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ




can be converted into a tour of the cities by traversing each line twice and returning to the origin. It is known that the optimum spanning tree must be shorter than any possible tour of the cities, since a tour can be converted into a spanning tree (albeit one without any branches) by simply omitting one segment. Thus twice the length of the optimum spanning tree cannot be longer than twice the optimum tour. The method is a polynomial-time algorithm. Recently Nicos Christofides of the Imperial College of Science and Technology in London has found a way to improve the algorithm so that it yields a tour guaranteed to be no more than half again as long as the optimum. A more profound compromise gives up not only the requirement that a solution be optimal but also the insistence that a less than optimum solution be guaranteed to fall within a specified range. Instead the assurance is given that the solution will not often deviate far from the optimum. An underlying assumption of such techniques is that the maps encountered in practice are not concocted to confound basically plausible techniques; such maps are encountered frequently only when they are constructed by computer scientists to reveal the flaws in methods proposed by their colleagues. Indeed, if the salesman's tour algorithms discussed above are applied to "natural" maps, they deliver far more than they promise. The resulting tours are not 100 percent or 50 percent longer than the optimum but closer to 5 percent. A reasonable assumption about the properties of many maps is that cities are randomly placed. A theorem describing the statistical properties of optimum tours through such randomly distributed points was proved in 1958 by Jillian Beardwood, J. H. Halton and John M. Hammersley of the University of Oxford. Relying on that theorem, Karp has shown that a simple method of constructing tours almost always yields near-optimum results, when it is applied to maps with many cities. Karp begins by dividing the map into many small regions. Within each of these regions the cities are sufficiently few to find the optimum tour by exhaustive search, even though that method involves an exponential-time algorithm. The tours of the small areas are then linked by a variant of the greedy algorithm. Perhaps significantly, the method is not very different from the method usually adopted by people solving the problem manually. Efficient but approximate solutions can be found for many NP-complete optimization problems. From the standpoint of mathematics, however, the important question is whether NP is identical with P. The repeated failure of attempts to find an efficient algorithm for the NP-complete problems has created considerable confidence that NP and P are not the same. There is now suspicion that they are not identical, but the proof of their distinctness may be beyond present mathematical capabilities. The question may join that select group of mathematical enigmas that remain unresolved for decades, and the solution may have to await the development of new methods in mathematics.

скачать реферат
первая   ... 3 4 5 6

Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ

Внимание! Студенческий отдых и мегатусовка после сессии!


Обратная связь.

IsraLux отзывы Израиль отзывы