Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 27
Однако, минимальным вершинным покрытием в рассматриваемом графе будет множество, состоящее всего из одной вершины: вершины с номером 3.
А как же ребро, соединяющее вершины 0 и 1? Оно ведь ни одним концом не входит в 3.
А как же ребро, соединяющее вершины 0 и 1? Оно ведь ни одним концом не входит в 3.
А вот скажите — а где задачи о вершинном покрытии, клике и независимом множестве применяются? Мне интересно, какие прикладные задачи с их помощью решаются. Я в свое время когда читал о них, даже не смог в контестерах задачи такие найти, чтобы проверить правильность реализации алгоритмов.
Возможно, это связано с тем, что на контестах обычно требуются точные детерминированные решения. А для NP-трудных задач на данный момент известны только экспоненциальные по времени решения, что не нравится контестам. Применений у NP-трудных задач действительно много. Поэтому люди и ищут все более и более быстрые и изощрённые способы решения NP-трудных задач.
Например, Вы хотите расставить как можно меньше вышек мобильной связи, но хотите покрыть какой-то набор дорог. Это и есть задача о вершинном покрытии.
Если Вы хотите рассадить в своем зоопарке по клеткам бегемотов, то Вам необходимо решить задачу о независимом множестве. Ведь известно, что бегемот из первой клетки не даст спокойно жить бегемотам из нулевой и третьей клеток (т.к. в графе есть ребра 1-0 и 1-3) и.т.д. Так, Вам нужно выбрать максимальное количество клеток, попарно не соединенных ребрами. Это и есть задача о независимом множестве.
Например, Вы хотите расставить как можно меньше вышек мобильной связи, но хотите покрыть какой-то набор дорог. Это и есть задача о вершинном покрытии.
Если Вы хотите рассадить в своем зоопарке по клеткам бегемотов, то Вам необходимо решить задачу о независимом множестве. Ведь известно, что бегемот из первой клетки не даст спокойно жить бегемотам из нулевой и третьей клеток (т.к. в графе есть ребра 1-0 и 1-3) и.т.д. Так, Вам нужно выбрать максимальное количество клеток, попарно не соединенных ребрами. Это и есть задача о независимом множестве.
Хорошие примеры, спасибо.
Пример для клики не заметил. Если Вы хотите организовать самую большую вечеринку для «своих» (то есть, чтобы на вечеринке каждый знал каждого), то Вам необходимо решить задачу о максимальной клике. Обозначьте друзей вершинами, проведите ребро между двумя вершинами, если два этих друга знакомы и решите задачу о максимальной клике.
Кстати, на английском это не NP-hard, a NP-complete
Однако, извиняюсь — в википедии есть статья NP-hard. Как и NP-complete. Это вроде бы даже разные вещи? Не понял пока. Не расскажите?
По-моему, NP-complete — это NP-hard, для которой известно, что к ней сводятся другие NP-задачи. То есть, доказательство того, что для некоторой NP-complete задачи есть полиномиальный алгоритм, приводит к P = NP.
Извините, я тут не очень пока ориентируюсь. Ответил вот тут: habrahabr.ru/blogs/algorithm/120328/#comment_3945684
alexeygrigorev: Да, конечно расскажу.
mrShadow: Немного уточню.
NP-hard (NP-трудная, NP-сложная) задача — это задача, мгновенно получая ответы на которую, мы смогли бы за полиномиальное время решить любую задачу из класса NP.
Или, что тоже самое, смогли бы решить какую-нибудь NP-полную задачу.
Неформально это значит, что NP-трудная задача не проще, чем все задачи из класса NP. Например, если бы NP-трудная задача решилась за полиномиальное время, то получилось бы, что какая-то NP-полная задача тоже решается за полиномиальное время, то есть P=NP.
NP-complete (NP-полная) задача — это NP-трудная задача, которая сама к тому же принадлежит классу NP.
В классе NP лежат задачи разрешимости (decision problem). Это задачи, на которые есть ответ да/нет. Например, к NP (и NP-полным) задачам относится следующая версия задачи о вершинном покрытии: «Существует ли в графе вершинное покрытие мощности не более k?». Это вопрос на да/нет.
Также бывают задачи оптимизации (NP optimization problem). Это NP-задачи, в которых требуется найти лучшее решение. Это уже не задачи на да/нет. Следовательно, они не лежат в классе NP. Но многие из них являются NP-трудными. Например, NP-трудной является задача из топика: «Найти минимальное вершинное покрытие».
Умея решать NP-сложную задачу (например, задачу из топика) можно быстро решить NP-полную задачу (например, задачу о существовании в графе покрытия <=k). Действительно, пусть мы нашли минимальное вершинное покрытие. Его размер m. Если m<=k, то в графе существует вершинное покрытие мощности <=k, иначе — не существует.
mrShadow: Немного уточню.
NP-hard (NP-трудная, NP-сложная) задача — это задача, мгновенно получая ответы на которую, мы смогли бы за полиномиальное время решить любую задачу из класса NP.
Или, что тоже самое, смогли бы решить какую-нибудь NP-полную задачу.
Неформально это значит, что NP-трудная задача не проще, чем все задачи из класса NP. Например, если бы NP-трудная задача решилась за полиномиальное время, то получилось бы, что какая-то NP-полная задача тоже решается за полиномиальное время, то есть P=NP.
NP-complete (NP-полная) задача — это NP-трудная задача, которая сама к тому же принадлежит классу NP.
В классе NP лежат задачи разрешимости (decision problem). Это задачи, на которые есть ответ да/нет. Например, к NP (и NP-полным) задачам относится следующая версия задачи о вершинном покрытии: «Существует ли в графе вершинное покрытие мощности не более k?». Это вопрос на да/нет.
Также бывают задачи оптимизации (NP optimization problem). Это NP-задачи, в которых требуется найти лучшее решение. Это уже не задачи на да/нет. Следовательно, они не лежат в классе NP. Но многие из них являются NP-трудными. Например, NP-трудной является задача из топика: «Найти минимальное вершинное покрытие».
Умея решать NP-сложную задачу (например, задачу из топика) можно быстро решить NP-полную задачу (например, задачу о существовании в графе покрытия <=k). Действительно, пусть мы нашли минимальное вершинное покрытие. Его размер m. Если m<=k, то в графе существует вершинное покрытие мощности <=k, иначе — не существует.
Да, это синонимы.
Эта задача как раз не из NP. Классу NP принадлежат задачи разрешимости. Это задача оптимизации.
Кроме того NP-трудная отличается от NP тем, что она не легче любой задачи из NP. То есть, она трудная задача. Например, проверить, является ли одно число на 1 больше другого — это тоже задача из NP. Но она не NP-трудная.
Эта задача как раз не из NP. Классу NP принадлежат задачи разрешимости. Это задача оптимизации.
Кроме того NP-трудная отличается от NP тем, что она не легче любой задачи из NP. То есть, она трудная задача. Например, проверить, является ли одно число на 1 больше другого — это тоже задача из NP. Но она не NP-трудная.
Рад, что Вы разобрались.
Но то, что эта задача не из P и не из NP понятно, т.к. в этих классах лежат только задачи разрешимости (т.е. задачи на да/нет).
Но то, что эта задача не из P и не из NP понятно, т.к. в этих классах лежат только задачи разрешимости (т.е. задачи на да/нет).
Любая оптимизационная задача из NP сводится не к некоторому языку из NP.
Тут, видимо, я не очень понятно объяснил именно формальное отличие. То есть, P и NP — это классы (множества) языков. Язык — это просто набор слов (строк, чисел, графов, пар...). Так вот язык, который состоит из графов, имеющих вершинное покрытие не больше k — NP-полный язык. А задача определения вот такого вот k по графу — это не язык. Это задача, которая также трудна, как и все языки из NP. Поэтому задача и называется NP-трудной.
Тут, видимо, я не очень понятно объяснил именно формальное отличие. То есть, P и NP — это классы (множества) языков. Язык — это просто набор слов (строк, чисел, графов, пар...). Так вот язык, который состоит из графов, имеющих вершинное покрытие не больше k — NP-полный язык. А задача определения вот такого вот k по графу — это не язык. Это задача, которая также трудна, как и все языки из NP. Поэтому задача и называется NP-трудной.
Спасибо за статью.
По поводу алгоритма: «Выбираем случайное ребро графа e=(u, v).». А не должно ли случайно быть доволнительно условие, что u и v не должны входить в S?
Возможно, я не очень подробно это описал. Но на каждой итерации алгоритма мы удаляем все ребра, инцидентные выбранным вершинам. Это значит, что мы никогда больше не сможем выбрать ребро, инцидентное вершинам из S.
гм. Теперь ясно. Просто меня немного смутили термины «ребро графа» и «множества ребер» — показалось что изменяется некое множество ребер (изначально состоящее из ребер графа), а граф оставался как есть.
Хотя в примерах итераций действительно третий пункт говорит уже не о каком-то множестве, а о графе.
В остальном же вполне понятный алгоритм и хорошая статья :)
Разве что я бы в конце еще добавил информацию о том, кто впервые описал (если не врет вики и я не ошибаюсь, то Fanica Gavril и Mihalis Yannakakis). Ну и про «1.999» — если не ошибаюсь, так там идет речь об)
— так выйдет чуток поточнее. (фух, давно я в латехном формате не набирал формулы :))
Хотя в примерах итераций действительно третий пункт говорит уже не о каком-то множестве, а о графе.
В остальном же вполне понятный алгоритм и хорошая статья :)
Разве что я бы в конце еще добавил информацию о том, кто впервые описал (если не врет вики и я не ошибаюсь, то Fanica Gavril и Mihalis Yannakakis). Ну и про «1.999» — если не ошибаюсь, так там идет речь об
А вы используете алгоритм в какой то практической задаче, или просто ради научного интереса??
Что нибудь можете сказать по поводу habrahabr.ru/post/225831/?
Что нибудь можете сказать по поводу habrahabr.ru/post/225831/?
А вы используете алгоритм в какой то практической задаче, или просто ради научного интереса??
Нет, я не использую этот алгоритм на практике, но уверен, что он имеет множество практических и теоретических применений.
Что нибудь можете сказать по поводу habrahabr.ru/post/225831/?
Полиномиальное решение задачи о покрытии множества влекло бы равенство P и NP. К сожалению, утверждение теоремы 2 не верно в общем случае. В теореме один Вы описываете некоторые из минимальных покрывающих множеств, но не все. В теореме два Вы говорите, что если выбрать наименьшее из описанных Вами минимальных множеств, то Вы получите наименьшее покрывающее множество. Это было бы верно, если бы Вы рассматривали множество всех минимальных покрытий, однако Вы рассматриваете лишь его подмножество.
То есть, в теореме 1 каждое Ваше решение соответствует минимального множеству, но обратное утверждение не верно. В теореме 2 Вы как раз пользуетесь обратным утверждением: Вы подразумеваете, что каждое минимальное покрытие описывается в теореме 1.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Задача о вершинном покрытии