Подходы к решению NP-полных задач

⇐ ПредыдущаяСтр 7 из 8Следующая ⇒

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

1. Анализируется структура NPC. Оказывается, что в этом классе можно выделить «более легкие» и «более сложные» задачи. И уже в зависимости от того, какой является ваша задача Z, вы можете подбирать методы решения.

2. Для задач в оптимизационной форме требования к точности можно ослабить, т.е. вместо оптимального искать приближенное решение.

3. Наложить на задачу дополнительные ограничения, тогда получается некоторый частный случай. Таким образом попытаться получить нетривиальный полиномиально разрешимый вариант исходной задачи из NPC.

4. Задачу всегда можно решить полным перебором. В некоторых случаях комбинаторная структура задачи позволяет разработать достаточно сложные и тонкие алгоритмы «направленного перебора», которые теоретически будут экспоненциальными, но на практике могут успешно использоваться.

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

NP-полнота в сильном смысле. Псевдополиномиальные алгоритмы

Пусть I – некоторая индивидуальная задача массовой задачи Z. Отметим, что задавая условие задачи (слово I в некотором алфавите) мы должны задать «комбинаторные» параметры задачи - число вершин, число ребер, число переменных, число дизъюнкций, ребра графа и т.п. – и «числовые» параметры: веса ребер графа, вектора объемов и стоимостей в задаче о рюкзаке, веса камней в задаче о камнях и т.п. Обозначим через num(I) – максимальное число, которое используется при задании I.

Разумная кодировка предполагает, что для записи num(I) потребуется слово длины log(num(I)). Поэтому в P лежат задачи, для которых существуют алгоритмы решения с трудоемкостью, полиномиальной по |I| и log(num(I)).

Опр. Алгоритм решения задачи называется псевдополиномиальным, если он решает задачу за время, ограниченное полиномом от |I| и num(I).

Для большинства задач из NPC нет не только полиномиальных, но и псевдополиномиальных алгоритмов, поэтому наличие для задачи из NPC псевдополиномиального алгоритма, что она в каком-то смысле «проще», чем задача, для которой нет псевдополиномиального алгорима.

Примером задачи, имеющей псевдополиномиальный алгоритм является задача о рюкзаке. Есть ряд похожих на эту задачу – задачи рюкзачного типа, для которых тоже построены псевдополиномиальные алгоритмы. Поэтому на практике вам стоит проверить свою задачу на наличие псевдополиномиального алгоритма, тогда при малых значениях num(I) она будет сравнительно легко решаться. (Подробнее см. [6]).

Рассмотрим теперь задачи, для которых пока нет псевдополиномиального алгоритма. Для некоторых из них доказано, что они являются NP-полными даже тогда, когда num(I)≤ p(|I|), где p(|I|)– полином от |I|. Такие задачи называются NP –полными в сильном смысле (сильно NP-полными).

Таким образом, класс NPC разбивается на три части: задачи с известными псевдополиномиальными алгоритмами; задачи, для которых не построены псевдополиномиальные алгоритмы, но и не доказано, что они сильно NP-полные; сильно NP-полные задачи. Если вам придется иметь дело с последними, то, по-видимому, ничего не остается как использовать либо эвристические алгоритмы, либо методы направленного перебора (см. ниже).

Приближенные алгоритмы

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

Опр. Пусть дана задача Z=( F, c ) и – c (x*) значение функции стоимости c на оптимальном решении x*. Пусть дан некоторый алгоритм W, результатом работы которого будет выдача некоторого решения x’, а c _W(x’)– значение функции стоимости на решении x’. Будем говорить, что алгоритм W является ε -приближенным (или алгоритмом с оценкой точности ε ), если выполняется следующее соотношение: |( c _W(x’)- c (x*))/ c (x*) |≤ ε.

Опр. Пусть дана задача Z=( F, c ) и – c (x*) значение функции стоимости c на оптимальном решении x*. Пусть дан некоторый алгоритм W, результатом работы которого будет выдача некоторого решения x’, а c _W(x’)– значение функции стоимости на решении x’. Будем говорить, что алгоритм W является эвристическим, если про соотношение c _W(x’) и c (x*) ничего не известно.

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

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

Из вершины 1 идем в вершину i₁ такую, что ребро (1, i₁) имеет минимальный вес среди всех ребер вида (1, j), на втором шаге из вершины i₁ идем в вершину i₂ 1 такую, что ребро (i₁, i₂) имеет минимальный вес среди всех ребер вида (i₁, j), j 1; из вершины i₂ идем в вершину i₃ 1, i₂ такую, что ребро (i₂, i₃) имеет минимальный вес среди всех ребер вида (i₂, j), j 1, i₂. И так далее. На последнем шаге замыкаем цикл.

Легко привести пример того, что этот алгоритм может не находить оптимального решения. Трудоемкость алгоритма не превосходит O(n²), но мы ничего не можем сказать про соотношение c _W(x’) и c (x*).

А как обстоят дела с приближенными алгоритмами для этой задачи?

Теорема. Если P NP, то при любом ε > 0 не существует ε – приближенного алгоритма для задачи коммивояжера.

Доказательство. От противного. Пусть такой алгоритм W для некоторого ε > 0 существует. Покажем, что тогда P=NP. Для этого мы докажем, что алгоритм W решает задачу гамильтонов цикл. Так как эта последняя является NP-полной, то отсюда и будет следовать равенство P=NP.

Пусть входом задачи гамильтонов цикл является граф G=(V, E). Постоим на его основе условие некоторой вспомогательной задачи коммивояжера на |V| городах, а расстояние между городами i и j положим равным 1, если ребро (i, j) есть в графе G, и равным 2+ ε |V|, если такого ребра в графе нет.

Применим наш полиномиальный алгоритм W для получения ε –приближенного решения вспомогательной задачи коммивояжера. Докажем, что этот алгоритм выдаст обход коммивояжера длины |V| тогда и только тогда, когда в G есть гамильтонов цикл. Очевидно, что, если такой обход выдан, то каждое ребро в нем имеет длину единица, т.е. соответствует ребру графа G, а выданный обход, таким образом, гамильтонову циклу этого графа. И наоборот, если в графе G есть гамильтонов цикл, то алгоритм обязательно выдаст обход длины |V| потому, что в случае выдачи любого другого обхода (а в этом случае минимальное значение длины такого обхода не меньше |V|-1+2+ ε |V|) нарушается свойство ε –приближенности алгоритма:

(|V|-1+2+ ε |V|-|V|)/|V|=1/|V|+ ε > ε.

Теорема доказана.

В некотором смысле ситуация с приближенными алгоритмами для задачи коммивояжера типична для NP-трудных задач: полиномиальные эвристические алгоритмы всегда есть, а полиномиальных приближенных (для общего случая) нет.

Теорема. Если для задачи о клике существует ε – приближенный алгоритм для некоторого ε > 0, то тгда для этой задачи можно будет построить ε – приближенный алгоритм для любого 1> ε > 0.

Однако, в отличие от точных алгоритмов, полиномиальные приближенные можно построить для интересных частных случаев NP-трудных задач. Например, для задачи коммивояжера с неравенством треугольника (для любых трех вершин i, j, k длина ребра (i, j) не превосходит суммы длин ребер (i, k)и (k, j)) существуют приближенные алгоритмы. Одним из самых первых был 1/2-приближенный алгоритм Кристофидеса.

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

⇐ Предыдущая 1 2 3 4 5 678 Следующая ⇒