Поиск по сайту
Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ реферат на тему: Алгоритмыroom assignment, once it is discovered, can easily be exhibited. Of course, a solution could be found by exhaustive search, albeit inefficiently. With luck a suitable assignment, if there is one, can be guessed quickly.
Map coloring is a problem in the class NP that concerns mathematicians more than it does cartographers. The question is whether the countries on a given map can be colored with a given number of colors so that no two countries that share a border have the same color. It is easy to find out if a map can be colored with two colors, it can be if there are no places on the map where an odd number of countries meet at one point. It is even easier to tell if a map can be colored with four colors; indeed, there is no need even to look at the map, since Kenneth Appel and Wolfgang Haken of the University of Illinois proved in 1975 that four colours suffice for any map. Surprisingly, however, no efficient algorithm is known for determining whether three colors are enough for a given map. The problem is in the class NP, since a correctly colored map can-serve to certify a yes answer.
Map coloring can be regarded as a special case of another problem called graph coloring. Any map can be converted into a graph by reducing each country to a point and drawing a line between two points if the corresponding countries share a border. Coloring the graph is then equivalent to coloring the map, subject to the rule that two points connected by a line cannot have the same color. Graph coloring, however, is a more general problem, with applications outside graph theory. For example, a graph can represent the scheduling of work in a factory. Each point of the graph stands for some job to be done, and two points are connected by a line, if the jobs cannot be done concurrently, perhaps because they require the same piece of machinery. A coloring of the graph with three colors would then supply a schedule dividing the work of the factory into three shifts. Like map coloring, the graph-coloring problem is in the class NP.
It often happens that if one problem can be solved efficiently, so can many others. For example, if an efficient algorithm could be found for the problem of graph coloring, it could be applied with only minor modifications to the problems of map coloring and factory scheduling. Map coloring and factory scheduling are therefore said to be efficiently reducible to graph coloring. In the past several years it has become apparent that some of the problems in the class NP have a remarkable property: all the problems in NP are efficiently reducible to them. These elite problems within the class NP are called NP-complete. If any one of them has an efficient algorithm, then every problem in NP can be solved efficiently.
The first proof that a problem is NP-complete was presented in 1971 by Stephen A. Cook of the University of Toronto. His reasoning follows a path essentially parallel to the path of Turing's earlier work on mathematical machines and their relation to problems of formal logic. Cook stated his proof in terms of the prepositional calculus, the formal language in which separate logical statements, which individually may be either true or false, are joined together by the lexical elements "and," "or" and "not." In general a sentence in the propositional calculus can be shown to be either true or false depending on which of its component statements are assumed to be true or false. Certain sentences, however, cannot
первая ... 2 3 4 5 6 Не нашли нужную работу? Закажи реферат, курсовую, диплом на заказ Внимание! Студенческий отдых и мегатусовка после сессии!
Рефераты и/или содержимое рефератов предназначено исключительно для ознакомления, без целей коммерческого использования. Все права в отношении рефератов и/или содержимого рефератов принадлежат их законным правообладателям. Любое их использование возможно лишь с согласия законных правообладателей. Администрация сайта не несет ответственности за возможный вред и/или убытки, возникшие или полученные в связи с использованием рефератов и/или содержимого рефератов.
|
Обратная связь. |