2.5 Полиноминальная сводимость.

Если один из алгоритмов имеет полиномиальную сложность, а другой требует, например, экспоненциального количества шагов (памяти), как показано выше, использование экспоненциальных алгоритмов может иметь смысл только для небольших входных параметров задачи. На больших данных любой полиномиальный алгоритм будет лучше любого экспоненциального.

В случаях, когда для двух алгоритмов, решающих одну задачу, известна полиномиальная оценка сложности, имеет смысл находить наиболее точно приближенное к величине сложности значение полиномов и сравнивать их сначала по максимальной степени, а если она окажется одинаковой, по коэффициенту перед максимальной степенью.

Принципиально иная ситуация имеет место в том случае, если вопрос о существовании полиномиального алгоритма решения некоторой задачи остается открытым. Тогда в первую очередь нужно выяснить ответ на этот вопрос и потом предпринимать действия по дальнейшей оптимизации. Если ответ положительный, можно пытаться искать наилучший из полиномиальных алгоритмов решения. Если полиномиального алгоритма решения задачи не существует, имеет смысл рассмотреть возможность нахождения "быстрого" алгоритма приближенного решения задачи.

При выяснении существования для задачи полиномиального алгоритма, все оценки можно делать с точностью до полиномиальных преобразований. Например, перед решением задачу можно преобразовать в другую форму, если затраты на этот процесс не превысят полиномиальное время, поскольку это не скажется на выводе о существовании полиномиального алгоритма для исходной задачи.

Помочь доказать существование или отсутствие полиномиального алгоритма решения некоторой задачи может понятие полиномиальной сводимости.

Пусть имеются две массовые задачи S1 и S2. Пусть A1 - произвольный алгоритм решения задачи S1. Пусть существуют два алгоритма полиномиальной сложности P21 и P12: P21 получает на входе описание индивидуальной задачи типа S2 и преобразует его в описание некоторой индивидуальной задачи типа S1; P12 получает на вход решение задачи типа S1 и преобразует его в решение задачи типа S2.

Если алгоритмы P21 и P12 таковы, что после преобразования описания индивидуальной задачи S2 алгоритмом P21 в описания индивидуальной задачи S1, решения полученной задачи S1 и преобразования полученного решения с помощью P12, мы получим решение исходной индивидуальной задачи S2, говорят, что задача S2 полиноминально сводится к задаче S1, и пишут S2 ∝ S1 (рисунок 4).

Рисунок 4. Полиноминальная сводимость.

Иными словами, S2 ∝ S1, если связка алгоритмов A2 = P12A1P21 решает индивидуальную задачу s типа S2:

P12(A1(P21(условия s))) = ответ на s.

2.6 Классы задач в форме распознавания свойств.

Будем говорить, что задача сформулирована в форме распознавания свойств, если ответ на задачу "Да" или "Нет". Если нам встретилась задача не в форме распознавания, ее можно переформулировать таким образом, чтобы она попала в наш класс задач. Например, рассмотрим следующую задачу:

Дана контурная карта с обозначенными на ней n странами и требуется раскрасить ее в разные цвета таким образом, чтобы любые два государства, соприкасающиеся участком границы, имели различный цвет.

Задача в оптимизационной форме: Дана контурная карта. Требуется раскрасить ее в минимально возможное число цветов.

Задача, переформулированная в форме распознавания свойств: Дана контурная карта и число k. Существует ли допустимая раскраска этой карты в k цветов.

Очевидно, если решена задача в оптимизационной форме, то ответ на переформулированную задачу в форме распознавания будет получен простым сравнением полученного минимального числа цветов со значением k. Следовательно, в форме распознавания задача не становится сложнее исходной задачи.

С другой стороны, если решена задача в форме распознавания, может быть решена задача о нахождении числа цветов в минимальной раскраске. Для ее решения достаточно перебрать все k от 1 до n. То есть, сложность задачи нахождения минимального числа цветов в допустимой раскраске не выше n * T (n), где T (n) – оценка сложности алгоритма решения задачи в форме распознавания. Эта задача полиноминально эквивалентна задаче в форме распознавания.

Рассмотрим два класса задач в форме распознавания свойств, - P и NP.

Класс P определяется, как класс всех задач в форме распознавания, для которых существует полиномиальный алгоритм решения. К классу P, например, относятся переформулированная в форме распознавания свойств задача нахождения минимального элемента массива:

Дан массив чисел длины n и номер ячейки k. Правда ли, что в k-той ячейке находится минимальный элемент массива. Сложность решения этой задачи O(n)

Класс NP (от Non-deterministic Polynomial) определяется, как класс всех задач в форме распознавания, для которых существует недетерминированная машина Тьюринга, вычисляющая ответ на эту задачу за полиномиальное время.

Недетерминированная машина Тьюринга отличается от машин детерминированных тем, что в ее программе допускается наличие нескольких команд с одинаковой левой частью. Другими словами, в некоторый момент времени недетерминированная машина Тьюринга может оказаться в конфигурации, из которой у нее определено более чем один вариант дальнейших действий. Таким образом, условие определенности алгоритма здесь не выполняется. В общем случае у недетерминированного алгоритма есть целое дерево различных вариантов хода выполнения.

Что делать, если мы столкнулись с такой развилкой? В таком случае недетерминированная машина может копировать себя необходимое число раз и все копии начинают выполнять каждая свою возможную последовательность действий. Копии машины работают независимо и одновременно (рисунок 5). Как только хотя бы одна копия машины заканчивает вычисления с ответом "Да", все копии завершают свою работу. В случае отрицательного ответа, машина может не остановиться.

Рисунок 5: Схема работы недетерминированного алгоритма.

Можно также говорить об угадывающем устройстве. Тогда считаем, что подойдя к развилке, машина безошибочно угадывает, какой именно переход нужно выбрать, чтобы получить ответ "Да", если это возможно.

Определение 3.2.9 . Говорят, что недетерминированная машина Тьюринга принимает слово α, если существует, хотя бы одна ветвь дерева вычислений, где машина останавливается и дает ответ "Да".

Можно привести альтернативное определение класса NP.

Задача в форме распознавания принадлежит классу NP, если, когда на задачу дан ответ "Да" и приведено доказательство решения - некоторые дополнительные сведения, - можно за полиномиальное время проверить, что это правда.

2.7 NP -полные задачи

Следующая теорема была доказана Куком в 1971 году.

Теорема. Любая задача из класса N P полиноминально сводится к задаче о выполнимости.

Таким образом, задача о выполнимости в некотором смысле не проще всех остальных задач из класса NP. Все подобные ей задачи названы NP -полными. Или же, что то же самое, задача называется NP -полной, если она принадлежит классу NP и к ней полиноминально сводятся все задачи из класса NP.

Задача о выполнимости выглядит следующим образом: дано логическое выражение в конъюнктивной нормальной форме. Является ли функция, реализуемая этой формулой, выполнимой?

Другими словами, дана булева функция f (x1, x2, ..., xn), определенная своей КНФ: (D1) ∧ (D2) ∧…∧ (Dk). Требуется ответить на вопрос, существует ли такой набор значений логических переменных a1, a2, ..., an, что f (a1, a2, ..., an) = 1.

3 Задача о клике

Напомним, что клика - это максимальный по включению вершин полный подграф графа. В оптимизационной форме задача о клике выглядит следующим образом:

Дан граф G = (V, E). Необходимо найти наибольшую клику графа (клику графа с наибольшим для этого графа числом вершин).

Используем обозначение ϕ(G) - размер наибольшей клики в графе G. Тогда задачу о клики можно переформулировать в форме распознавания следующим образом:

Дан граф G = (V, E) и целое число b > 0. Правда ли, что ϕ(G) ≥ b.

То есть необходимо ответить на вопрос, существует ли в графе в графе G полный подграф с b вершинами.

Докажем N P -полноту задачи о клике, сведя к ней известную нам N P - полную задачу о выполнимости.

ВЫПОЛНИМОСТЬ ∝ КЛИКА.

Покажем, что задача о выполнимости сводится за полиномиальное время к задаче о клике.

Пусть нам поставлена следующая задача о выполнимости: дана конъюнктивная нормальная форма A = D1 ∧ D2 ∧ ... ∧ Dk, где Di - дизъюнкт, i = 1, k. Построим граф G = (V, E) следующим образом: V (G) = {(α, i) | α - литерал в Di}, E(G) = {((α, i), (β, j)) | i /= j, α /= β}.

1)Пусть A выполнима. Значит на определенном наборе значений переменных A = 1. Тогда в каждом дизъюнкте Di найдется хотя бы один литерал αi = 1. Рассмотрим вершины (αi, i) и (αj , j) при i /= j. Поскольку на выбранном наборе значений переменных αi = 1 и αj = 1, то αi /= αj . Следовательно, вершины (αi, i) и (αj , j) соединены ребром в графе G. Таким образом, множество вершин {(αi, i) | i = 1, k} порождает полный подграф в графе G.

2) Пусть теперь в графе G есть клика размера k с вершинами (α1, 1), (α2, 2), ...(αk, k). Тогда αi /= αj , ∀i, j = 1, k. Следовательно, можно таким образом подобрать значения переменных, чтобы все αi принимали значение 1 одновременно. Следовательно, A - выполнима.

Итак, мы показали, что формула A является выполнимой тогда и только тогда, когда в графе G имеется клика размера k.

Осталось заметить, что построение графа G можно выполнить за полиномиальное время от размера СКНФ A.

Переформулированная в форме распознавания задача о клике принадлежит классу NP , так как, если ответ на задачу "да" и нам дано множество вершин, образующих полный подграф в графе G, мы можем за полиномиальное время проверить, правда ли каждая из этих вершин смежная с каждой. Задача о клике является NP – полной задачей.

4. Алгоритмы поиска клики

Поскольку задача о клике является NP – полной задачей, эффективного алгоритма поиска Клики, скорее всего, нет. По крайней мере, пока не доказано, что P=NP. Однако всегда можно перебрать все подмножества размера k во множестве вершин V и проверить, есть ли среди них клика. Для этого потребуется Ω(k^2*сочетания из V по k) действий (V – число вершин в графе). При любом фиксированном k эта величина полиноминально зависит от размера графа G. Однако в общей постановке задачи k может быть любым числом, не превосходящим |V|, и алгоритм не является полиноминальным.

Алгоритм Брона – Кербоша.

Одним из самых быстрых алгоритмов поиска клики был признан алгоритм Брона – Кербоша. Разработанный голландскими математиками Броном и Кербошем в 1973 году.

Алгоритм использует тот факт, что всякая клика в графе является его максимальным по включению полным подграфом. Начиная с одиночной вершины (образующей полный подграф), алгоритм на каждом шаге пытается увеличить уже построенный полный подграф, добавляя в него вершины из множества кандидатов. Высокая скорость обеспечивается отсечением при переборе вариантов, которые заведомо не приведут к построению клики, для чего используется дополнительное множество, в которое помещаются вершины, которые уже были использованы для увеличения полного подграфа.

Алгоритм оперирует тремя множествами вершин графа:

Множество compsub — множество, содержащее на каждом шаге рекурсии полный подграф для данного шага. Строится рекурсивно.

Множество candidates — множество вершин, которые могут увеличить compsub

Множество not — множество вершин, которые уже использовались для расширения compsub на предыдущих шагах алгоритма.

Алгоритм является рекурсивной процедурой, применяемой к этим трем множествам.

ПРОЦЕДУРА extend (candidates, not):

1 ПОКА candidates НЕ пусто И not НЕ содержит вершины, СОЕДИНЕННОЙ СО ВСЕМИ вершинами из candidates, ВЫПОЛНЯТЬ:

2 Выбираем вершину v из candidates и добавляем ее в compsub

3 Формируем new_candidates и new_not, удаляя из candidates и not вершины, не СОЕДИНЕННЫЕ с v

4 ЕСЛИ new_candidates и new_not пусты

5 ТО compsub – клика

6 ИНАЧЕ рекурсивно вызываем extend (new_candidates, new_not)

7 Удаляем v из compsub и candidates, и помещаем в not

Вычислительная сложность линейна относительно количества клик в графе. В работе ученых Стэндфордского университета «The worst-case time complexity for generating all maximal cliques and computational experiments» (Худшая по времени сложность для вычисления максимальных кликов и вычислительные эксперименты) было показано, что в худшем случае алгоритм работает за O(3^n/3), где n — количество вершин в графе.

Список использованной литературы.

1. Томас Кормен, Чарльз Лейзер, Рональд Ривест. «Алгоритмы. Построение и анализ»

2. Просолупов. Е. В. «Конспект курса: Основы дискретной математики»

3. В.Ф. Горьковой. «Лекции по Дискретной математике»

14