Лекции - Структуры и алгоритмы компьютерной обработки данных / 22.NP-полные задачи. Полиномиальная сводимость. Типичные NP задачи

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

К классу NP относятся задачи, решение которых проверяется полиномиальным алгоритмом.

Введем понятие полиномиальная сводимость (редукция). Задача А полиномиально сводима к задаче B, если существуют полиномиальные алгоритмы, преобразующие исходные данные А в исходные данные B, и результат B в результат А.

NP-трудная задача – задача, к которой сводится любая задача из класса NP.

NP –полная задача – NP-трудная задача, принадлежащая классу NP.

Доказательство NP-полноты

Для того, чтобы доказать, что задача A из класса NP NP-полная, выбирается некоторая NP-полная задача B и доказывается ее полиномиальная сводимость к А. Тогда и любая другая задача класса NP сводится к А в два шага, первый из которых – сводимость к B.

В 1971 году Кук доказал NP-полноту задачи о выполнимости конъюнктивной нормальной формы.

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

• Задача коммивояжера

• Гамильтонов цикл

• Задача о рюкзаке

• Задача о суммах элементов подмножества (найти подмножество элементов, сумма которых равна L)

Для NP-полных задач не найден полиномиальный алгоритм и не доказано, что его не существует (проблема P=NP).

NP-полные задачи на графах

• Наибольшее независимое множество

• Наибольшая клика

• Наименьшее доминирующее множество

• Наименьшее покрытие

• Наименьшая вершинная раскраска

Наибольшее независимое множество

Независимое множество – множество вершин графа, такое что его любые две вершины не смежны.

Пример: {2,3}, {1,8}, {1,4,6,8}, {2,3,5,7}.

Множество называется максимальным, если не существует другого независимого множества, в которое бы оно входило. Наибольшее независимое множество – максимальное с наибольшим количеством вершин.

Поиск решения производится перебором множеств. На каждом шаге пытаемся расширить множество, добавив в него вершину. Если это невозможно, пробуем другие варианты выбора вершин.

Наибольшая клика

Клика – полный подграф. В клике все вершины попарно смежны. Клике в графе G соответствует независимое множество в графе G’ (дополнение графа G). Наибольшей клике соответствует наибольшее независимое множество. В нашем примере - {1,4,6,8} или {2,3,5,7}.

Наименьшее доминирующее множество

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

1	1	1	0	1	0	0	0
1	1	0	1	0	1	0	0
1	0	1	1	0	0	0	0
0	1	1	1	0	0	1	0
1	0	0	0	1	1	0	1
0	1	0	0	1	1	1	0
0	0	0	1	0	1	1	1
0	0	0	0	1	0	1	1

Задача о наименьшем покрытии

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

Задача о раскраске

Правильной вершинной раскраской неориентированного графа называется функция C: V →N, удовлетворяющая условию

То есть смежные вершины должны иметь разные цвета.

Необходимо найти раскраску

графа в минимальное количес-

тво цветов. Пример – составле-

ние расписания экзаменов

Теорема о четырех красках

При изучении раскраски географических карт в 1879 году Кели выдвинул гипотезу: любая карта раскрашиваема в четыре цвета. В терминах теории графов: любой планарный граф (ребра которого располагаются на плоскости без пересечений) может быть раскрашен в четыре цвета.

Теорема около 97 лет оставалась недоказанной, пока в 1976 году Хейкен и Аппель не свели раскраску произвольной карты к большому количеству частных карт, которые были раскрашены с помощью компьютера.

Приближенный метод решения задачи о раскраске

1. Получаем правильную раскраску, закрашивая очередную вершину в минимально возможный цвет. Пусть при этом использовалось q цветов.

2. Если существует раскраска, использующая только q-1 цветов, то все вершины, окрашенные в цвет q, должны быть окрашены в цвет g, меньший q. Найдем вершину с минимальным номером, окрашенную в цвет q, и просмотрим вершины, смежные с найденной. Находим очередную смежную вершину и стараемся окрасить ее в другой цвет <q. Если это получается, то перекрашиваем вершины с большими номерами по методу правильной раскраски.

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

Приближенные методы решения задачи коммивояжера

• Метод локальной оптимизации

• Алгоритм Эйлера (D/Dopt<2)

• Алгоритм Кристофидеса (D/Dopt<1.5)

Метод локальной оптимизации

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

Шаг 2. Пока происходит улучшение решения, выполнять следующий шаг, иначе перейти на шаг 4.

Шаг 3. Для всех пар номеров городов i<j

di-1,i +di,j +dj,j+1 >di-1,j +dj,i +di,j+1 для смежных городов, то есть j=i+1

di-1,i +di,i+1 +dj-1,j +dj,j+1 >di-1,j +dj,i+1 +dj-1,i +di,j+1 для несмежных городов.

Если одно из неравенств выполняется, то найдено лучшее решение. Следует откорректировать ранее найденное решение и вернуться на шаг 2.

Шаг 4. Закончить работу алгоритма.

Алгоритм Эйлера

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

Шаг 1. Строится минимального остовное дерево (алгоритмы Прима или Краскала).

Шаг 2. Путем дублирования каждого ребра дерево преобразуется в эйлеров граф.

Шаг 3. Находим в построенном графе эйлеров цикл.

Шаг 4. Эйлеров цикл преобразуем в гамильтонов цикл. Метод преобразования: последовательность вершин эйлерова цикла сокращается так, чтобы каждая вершина графа в получившемся цикле встречалась ровно один раз.

Шаг 5. Закончить работу алгоритма. Получено приближенное решение задачи коммивояжера.

Алгоритм Кристофидеса

Шаг 1. Строится минимальное остовное дерево (алгоритм Прима или Краскала).

Шаг 2. На множестве вершин дерева, имеющих нечетную степень, находится паросочетание минимального веса. Таких вершин в любом графе - четное число.

Шаг 3. Каркас преобразуется в эйлеров граф путем присоединения ребер, соответствующих найденному паросочетанию.

Шаг 4. В построенном графе находится эйлеров маршрут.

Шаг 5. Эйлеров маршрут преобразуется в маршрут коммивояжера