Структуры данных и эффективность алгоритмов. 4
![]()
|
Труднорешаемые задачи и NP-полнота. [8, 4 гл.34.]Различные задачи и алгоритмы их решения имеют различную временную сложность, и выяснение того, какие алгоритмы «достаточно эффективны», а какие «совершенно неэффективны», всегда будет зависеть от конкретной ситуации. Но возникает вопрос: Когда нужно считать, что задача действительно труднорешаема? В теории принято эту границу проводить между полиномиальными и экспоненциальными алгоритмами. Полиномиальным алгоритмом (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность равна O(p(n)), где p(n) – некоторая полиномиальная функция. Алгоритмы, временная сложность которых не поддается подобной оценке, называют «экспоненциальными». Различие между двумя указанными типами алгоритмов становятся особенно существенными при решении задач большого размера, и проявляются еще более убедительно, если проанализировать влияние увеличения быстродействия ЭВМ на время работы алгоритмов. Например, для T(n)=2n увеличение скорости вычислений в 10 раз приводит лишь к тому, что размер наибольшей задачи, разрешимой за один час, возрастет только (ориентировочно) на 3,3, в то время как для T(n)= ![]() ![]() Эффект десятикратного ускорения при последующем увеличении скорости вычислений. Большинство экспоненциальных алгоритмов – это просто варианты полного перебора, в то время как полиномиальные алгоритмы обычно можно построить лишь тогда, когда удается более глубоко проникнуть в суть решаемой задачи. Имеется широко распространенное соглашение, согласно которому задача не считается «хорошо решаемой» до тех пор, пока для неё не получен полиномиальный алгоритм. Поэтому задачу принято называть труднорешаемой, если для её решения не существует полиномиального алгоритма. Здесь надо зафиксировать несколько уточнений:
Уже отмечалось раньше, что даже экспоненциальный (в худшем случае) алгоритм может хорошо работать на практике, как например симплекс-метод для задач линейного программирования. Но подобные примеры очень редки, и, к сожалению, на сегодняшний день даже нет полноценных объяснений, почему эти алгоритмы успешно работают на практике... методы доказательства оценок для среднего времени работы тоже относятся к разряду очень сложных математических вопросов.
Например, в варианте задачи коммивояжера требуется найти все маршруты (требуемого вида) длины, не превосходящей В. Можно построить индивидуальную задачу о коммивояжере, в которой имеется экспоненциальное число требуемых маршрутов, поэтому не существует алгоритма с полиномиальной временной сложностью, который все их перечисляет. Этот аспект труднорешаемости видимо естественнее трактовать как указание на то, что постановка не реалистична, поскольку запрошено больше информации, чем когда-либо сможем использовать. В связи с этим этот аспект труднорешаемости исключается из здесь обсуждаемых рассмотрений. В связи с вышесказанным сделаем некоторые уточнения. Введем понятие абстрактной задачи: Определим абстрактную задачу (abstract problem) Q как бинарное отношение между множеством ![]() Поскольку как было заявлено выше, число решений может быть может быть достаточно велико, а нас интересует максимальная по всем экземплярам сложность решения, мы будем рассматривать только задачи распознавания (decision problems), т.е. задачи, которые имеют только два возможных ответа – «да» или «нет». Обычно для кандидатов в труднорешаемые задачи естественным образом формулируются соответствующие задачи распознавания, которые решаются не труднее, но остаются при этом кандидатами в труднорешаемые. Например, задачу распознавания Путь, соответствующую задаче Кратчайший путь, может быть сформулирована следующим образом: Пусть ![]() ![]() ![]() ![]() Многие абстрактные задачи являются не задачами принятия решения, а задачами оптимизации (optimization problems), в которых некоторое значение подлежит минимизации или максимизации. Однако обычно не составляет труда сформулировать задачу оптимизации как задачу принятия решения, которая не сложнее исходной. Причины труднорешаемости задач достаточно сложно анализируемы. Зачастую незначительное изменение условия задачи переводит ее из одного класса в другой. Приведем примеры таких ситуаций: Поиск самых коротких и самых длинных простых путей в графе. В дальнейшем мы убедимся, что поиск кратчайшего пути от некоторой вершины отдельно взятого источника в ориентированном графе G = ( V, Е) можно найти в течение времени O(VE). Однако поиск самого длинного пути между двумя вершинами оказывается сложным. Задача по определению того, содержит ли граф простой путь, количество ребер в котором не меньше заданного числа, является труднорешаемой. Эйлеров и Гамильтонов циклы. Эйлеров цикл (Euler tour) связанного ориентированного графа G = (У, Е) — это цикл, в котором переход по каждому ребру G осуществляется ровно один раз, хотя допускается неоднократное посещение некоторых вершин. Определить наличие Эйлерова цикла (а также найти составляющие его ребра) можно в течение времени О (Е). Гамильтонов цикл (hamiltonian cycle) ориентированного графа G = (V, Е) — это простой цикл, содержащий все вершины из множества V. Задача по определению того, содержится ли в ориентированном графе Гамильтонов цикл, является труднорешаемой. 2-CNF- и З- CNF-выполнимость. Булева формула содержит переменные, принимающие значения 0 и 1, булевы операторы, такие как & (И), V (ИЛИ) и ![]() ![]() ![]() Понятие труднорешаемой задачи оказывается, по существу, независимым и от способа кодирования задачи, и от модели детерминированного вычислителя, используемых при определении временной сложности. При определенных условиях можно доказать, что для различных схем кодирования и различных моделей вычислителя имеет место полиномиальная сводимость соответствующих алгоритмов решения задач (с помощью моделирования за полиномиальное время). Рассмотрим задачу принятия решения, скажем, задачу А, которую хотелось бы решить в течение полиномиального времени. Назовем входные данные отдельно взятой задачи экземпляром этой задачи. Кроме того предположим, что существует другая задача принятия решения, скажем, В, для которой заранее известно, как решить ее в течение полиномиального времени. Наконец, предположим, что имеется процедура с приведенными ниже характеристиками, преобразующая любой экземпляр ![]() ![]() 1. Это преобразование занимает полиномиальное время. 2. Ответы являются идентичными, т.е. в экземпляре ![]() ![]() ![]() Назовем такую процедуру алгоритмом сведения. Эта процедура предоставляет описанный ниже способ решения задачи А в течение полиномиального времени. 1. Заданный экземпляр ![]() ![]() 2. Запускается алгоритм, решающий экземпляр ![]() 3. Ответ для экземпляра ![]() ![]() Поскольку для выполнения каждого из перечисленных выше этапов требуется полиномиальное время, это относится и ко всему процессу в целом, что дает способ решения экземпляра ![]() Первые результаты о труднорешаемости задач – классические результаты о неразрешимости. Но в данном контексте нас интересуют только разрешимые задачи. Поскольку все труднорешаемые задачи так или иначе связаны с перебором большого (часто экспоненциального) числа вариантов, то возникает вопрос: а можно ли найти решение задачи не перебирая всех её вариантов. Попытка построить модель вычислителя, который не учитывает время на перебор вариантов решения, приводит к понятию недетерминированного вычислителя. Именно эта (недетерминированная) «нереалистичная» модель вычислителя играет важную роль в постановке проблемы об NP-полноте. В дальнейшем нас будут интересовать труднорешаемые задачи, для которых имеется полиномиальный алгоритм решения, но для недетерминированного вычислителя (для которого надо ещё определить понятие – время работы). Классическая модель недетерминированного вычислителя - это недетерминированная машина Тьюринга. Для программистов видимо более удобной является модель недетерминированной RAM-машины или можно воспользоваться любым процедурным языком программирования – убрать всё лишнее (что загромождает рассуждения, но не дает ничего нового с учетом полиномиальной сводимости), но добавить:
Этот оператор устанавливает значение логической переменной V , важный деликатный вопрос – как? Он может установить значение либо true, либо false, но не в вероятностном смысле, а в смысле альтернативных вариантов срабатывания. Можно рассмотреть вариант работы программы, когда при текущем выполнении он установит значение true, но можно рассмотреть альтернативный вариант работы программы, когда при текущем выполнении он установит значение false, и при каждом повторном выполнении он может альтернативно поступить независимо от предыдущих вариантов срабатывания.
Любой изальтернативных вариантов работы такого вычислителя на заданном входе, который завершается оператором «успех», будем называть принимающим вычислением (для этого входа). Такой алгоритм решает задачу распознавания в следующем смысле: для заданного входа отвечает на поставленный вопрос – «да», если имеется хотя бы одно принимающее вычисление для этого входа, и отвечает на поставленный вопрос – «нет», если для этого входа нет принимающих вычислений, т.е. в любом из альтернативных вариантов работы на этом входе алгоритм завершает работу оператором «неудача» либо даже бесконечно циклит. Время работы такого недетерминированного алгоритма на входе с ответом «да» – минимальное время по всем принимающим вычислениям, а на входе с ответом «нет» – считается единицей. Время работы (в худшем) на входах длины n – максимальное время работы по всем входам длины n. Заметим, что временная сложность такого алгоритма вычисляется только по принимающим вычислениям. Алгоритмы, описанные в терминах недетерминированного вычислителя естественно трактовать как математическую формализацию интуитивного понятия переборный алгоритм. Специфические возможности оператора недетерминированного выбора с учетом специфики определений понятий «алгоритм решает задачу» и «время работы» такого алгоритма позволяют представить решение задачи распознавания в виде двух стадий - стадии угадывания и стадии проверки, смысл этих двух стадий поясним на примере. Рассмотрим пример переборного решения задачи «Коммивояжер». В условии даны: множество городов, расстояния между ними и число В. Спрашивается: существует ли проходящий через все города маршрут длины, не превосходящей В. Полиномиальный детерминированный алгоритм решения этой задачи не известен, но можно предложить следующий полиномиальный недетерминированный алгоритм:
Не представляет труда на основе этой схемы предложить детерминированный (переборный) алгоритм, но поскольку количество перебираемых маршрутов экспоненциально, естественно мы получим экспоненциальный алгоритм. Основное назначение «полиномиального недетерминированного алгоритма» состоит в объяснении понятия «проверяемости» за полиномиальное время», а не в том, чтобы служить реалистичным методом решения задач распознавания свойств. При каждом входе такой алгоритм имеет не одно, а несколько возможных вычислений - по одному для каждой возможной догадки. Имеется еще одно важное отличие «решения» задачи распознавания недетерминированным алгоритмом от решения детерминированным алгоритмом, а именно в первом случае отсутствует симметрия между ответами «да» и «нет». Если задача: «Дано I; верно ли, что для I выполняется свойство X?» может быть решена полиномиальным (детерминированным) алгоритмом, то такое же утверждение справедливо и для дополнительной задачи; "Дано I, верно ли, что для I не выполняется свойство X?». Это следует из того, что детерминированный алгоритм останавливается при всех входах, поэтому достаточно поменять местами ответы «да» и «нет». Совершенно не очевидно, что то же самое верно для всех задач, разрешимых за полиномиальное время недетерминированными алгоритмами. Например, дополнение задачи «Коммивояжер»: дано множество городов, расстояния между ними и граница В; верно ли, что нетмаршрута, проходящего через все города и имеющего длину, не превосходящую В? Для выяснения, имеет ли поставленный вопрос ответ «да», не известен способ, который был бы короче, чем проверка всех (или почти всех) возможных маршрутов. Несмотря на интенсивные исследования в этой области, никому не удалось установить, замкнут ли класс NP относительно операции дополнения. Другими словами, следует ли из соотношения ![]() ![]() ![]() ![]() ![]() ![]() На рис. представлены четыре возможные ситуации. На каждой диаграмме одна область, содержащая другую, указывает, что внутренняя область является собственным подмножеством внешней. В части а) рисунка показана ситуация, соответствующая равенству Р = NP = co-NP. ![]() Большинство исследователей считает этот сценарий наименее вероятным. В части б) показано, что если класс NP замкнут относительно дополнения (NP=coNP), не обязательно справедливо равенство Р = NP. В части в изображена ситуация, когда Р = NP ![]() ![]() ![]() ![]() Класс P (полиномиальных задач распознавания) – множество задач распознавания, для которых существует полиномиальный детерминированный алгоритм решения. Класс NP (недетерминировано полиномиальных задач распознавания) – множество задач распознавания, для которых существует полиномиальный недетерминированный алгоритм решения. Очевидно включение P NP, поскольку детерминированный алгоритм по определению является недетерминированным. Но есть много причин считать это включение строгим. Полиномиальные недетерминированные алгоритмы определенно оказываются более мощными, чем полиномиальные детерминированные, и не известны общие методы их превращения в детерминированные полиномиальные. Если P не совпадает с NP, то различие между P и NP-P очень существенно. Все задачи из P могут быть решены (детерминированными) полиномиальными алгоритмами, а все задачи из NP-P труднорешаемы, и математическим уточнением понятия переборная задача распознавания служит задача из NP-P. В исследованиях проблемы PNP важное положение занимает понятие полиномиальная сводимость, используя ранее введенное понятие (и обозначение) сводимости - задача A полиномиально сводима к задаче B , если A p(n)B для некоторого полинома p(n). ЗадачаA называется NP-полной, если A NP и для любой другой задачи B NP имеет место полиномиальная сводимость B к A. Честь быть «первой» NP-полной задачей выпала на долю задачи распознавания выполнимости формул булевой логики. Рассмотрим язык L, образованный всеми цепочками, представляющими выполнимые булевы формулы (т. е. формулы, принимающие значение 1 на некотором наборе 0-1-значений переменных). Мы утверждаем, что L принадлежит NP . Недетерминированный алгоритм, распознающий L, начинает с того, что "угадывает" выполняющий набор 0-1-значений пропозициональных переменных во входной цепочке, если такой набор существует. Затем угаданное значение 0 или 1 каждой переменной подставляется вместо всех вхождений этой переменной во входную цепочку. Далее вычисляется значение полученного выражения, чтобы проверить его совпадение с 1. Это вычисление осуществляется за время, пропорциональное длине выражения, многими алгоритмами синтаксического анализа. Но даже и без них не трудно вычислить значение булевой формулы за ![]() Кук С.А. показал как формулами булевой логики можно описать работу любой программы недетерминированного вычислителя и на этой основе доказал полиномиальную сводимость любой NP-задачи к задаче о выполнимости. Таким образом, важную роль в доказательстве NPполноты играет сведение. Если вспомнить, что при доказательстве NP-полноты требуется показать, насколько сложной является задача, а не насколько она простая, доказательство NP- полноты с помощью сведения с полиномиальным временем работы выполняется обратно описанному выше способу. Продвинемся в разработке этой идеи еще на шаг и посмотрим, как с помощью сведения с полиномиальным временем показать, что для конкретной задачи В не существует алгоритмов с полиномиальным временем работы. Предположим, что имеется задача принятия решения А, относительно которой заранее известно, что для нее не существует алгоритма с полиномиальным временем работы. Предположим также, что имеется преобразование, позволяющее в течение полиномиального времени преобразовать экземпляры задачи А в экземпляры задачи В. Теперь с помощью простого доказательства "от противного" можно показать, что для решения задачи В не существует алгоритмов с полиномиальным временем работы. Предположим обратное, т.е. что существует решение задачи В в виде алгоритма с полиномиальным временем работы. Тогда, воспользовавшись методом сведения можно получить способ решения задачи А в течение полиномиального времени, а это противоречит предположению о том, что таких алгоритмов для задачи А не существует. Если речь идет о NP-полноте, то здесь нельзя предположить, что для задачи А вообще не существует алгоритмов с полиномиальным временем работы. Однако методология аналогична в том отношении, что доказательство NP-полноты задачи В основывается на предположении о NP-полноте задачи А. Методом (полиномиального) сведения на сегодняшний день доказана NP-полнота обширнейшего семейства задач в различных областях: в булевой логике, в теории графов, в арифметике, при разработке сетей, в теории множеств и разбиений, при хранении и поиске информации, при планировании вычислительных процессов, в математическом программировании, в алгебре и теории чисел, при создании игр и головоломок, в теории автоматов и языков, при оптимизации программ, в биологии, в химии, физике и т.п. ![]() k-кликой в графе G называют k-узельный полный подграф (каждая пара различных узлов в этом подграфе соединена ребром) графа G. Задача о клике формулируется так: содержит ли данный граф G ![]() Пример задачи о клике для графа G на рис. при k=3 можно закодировать цепочкой 3 (1,2) (1,4) (2,3) (2,4) (3,4) (3,5) (4, 5). Первое число представляет значение k. За ним идут пары узлов, соединенных ребрами, причем узел ![]() ![]() ![]() Задача о клике принадлежит классу NP. Недетерминированная машина Тьюринга сначала может "догадаться", какие k узлов составляют полный подграф, а затем проверить, что любая пара этих узлов соединена ребром, при этом для проверки достаточно ![]() ![]() Для изучения важных NP-полных задач, касающихся неориентированных графов, нам понадобятся следующие определения. Определения. Пусть G=(V, Е) — неориентированный граф. 1. Узельным покрытием графа G называется такое подмножество ![]() 2. Гамильтоновым циклом называется цикл в графе G, содержащий все узлы из V. ![]() 3. Граф G называется k-раскрашиваемым, если существует такое приписывание целых чисел 1, 2,. . ., k, называемых цветами, узлам графа G, что никаким двум смежным узлам не приписан один и тот же цвет. Хроматическим числом графа G называется такое наименьшее число k, что граф G ![]() Для представления важных NP-полных задач об ориентированных графах нам понадобятся следующие определения. Определения. Пусть G—(V, Е) — ориентированный граф. 1. Множеством узлов, разрезающих циклы, называется такое подмножество ![]() 2. Множеством ребер, разрезающих циклы, называется такое подмножество ![]() 3. Ориентированным гамильтоновым циклом называется цикл в ориентированном графе G, содержащий все узлы из V. Теорема 10.2. Следующие задачи принадлежат классу NP 1. (Выполнимость) Выполнима ли данная булева формула? 2. (Клика) Содержит ли данный неориентированный граф k- клику? 3. (Узельное покрытие) Имеет ли данный неориентированный граф узельное покрытие размера k? 4. (Гамильтонов цикл) Имеет ли данный неориентированный граф гамильтонов цикл? 5. (Раскрашиваемость) Является ли данный неориентированный граф k-раскрашиваемым? 6. (Множество узлов, разрезающих циклы) Имеет ли данный ориентированный граф k-элементное множество узлов, разрезающих циклы? 7. (Множество ребер, разрезающих циклы) Имеет ли данный ориентированный граф k-элементное множество ребер, разрезающих циклы? 8. (Ориентированный гамильтонов цикл) Имеет ли данный ориентированный граф ориентированный гамильтонов цикл? 9. (Покрытие множествами) Существует ли для данного семейства множеств ![]() ![]() ![]() 10. (Точное покрытие) Существует ли для данного семейства множеств ![]() Теорема . Задача о клике полиномиально трансформируема в задачу об узельном покрытии. Поэтому задача об узельном покрытии NP-полна. Доказательство. Пусть дан неориентированный граф G - (V, E). Рассмотрим его дополнение ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() ![]() Чтобы узнать, существует ли ![]() ![]() ![]() Оригинальные идеи Кука оказались удивительно плодотворными. Они позволили свести много разнообразных вопросов о сложности в единый вопрос: «Верно ли, что NP-полные задачи труднорешаемы?» |