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

⇐ ПредыдущаяСтр 2 из 2

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

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

Соответственно, на такой машине за полиномиальное время можно реализовать как все полиномиальные так и некоторые неполиномиальные алгоритмы.

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

Говорят, что задача A за полиномиальное время может быть сведена к задаче B (обозначение A µB), если существует полиномиальный алгоритм модификации за полиномиальное время любого примера I_А задачи A в пример задачи B так, что если ответ на пример I_А "ДА", тогда и только тогда, когда ответ на пример I_B тоже "ДА".

Соответственно, имея полиномиальный алгоритм решения какой-нибудь NP-трудной задачи, можно получить полиномиальный алгоритм решения любой задачи из класса NP, включая все NP-полные задачи и окажется, что NP=P. Но поскольку ни для одной NP-трудной задачи не построен полиномиальный алгоритм решения, общепринята гипотеза NP≠P.

NP- полная задача распознавания (ЗР) - NP-трудная ЗР класса NP.

Класс NP-полных задач (NPC или NP-complete) образуют все NP-полные задачи.

Т.к. NP-трудная задача - задача, к которой полиномиально сводится любая задача из класса NP. То при наличии полиномиального алгоритма решения какой-нибудь NP-трудной задачи, можно было бы получить полиномиальный алгоритм решения любой задачи из класса NP, включая все NP-полные задачи и оказалось бы, что NP=P. Но поскольку ни для одной NP-трудной задачи не построен полиномиальный алгоритм решения, общепринята гипотеза NP≠P.

NP-трудная экстремальная задача (ЭЗ) – ЭЗ, соответствующая которой задача распознавания является NP-трудной (полной).

Понятие полиномиальной сводимости транзитивно.

Соответственно, для доказательства NP-трудности задачи достаточно полиномиально свести к ней некоторую NP-трудную (полную) задачу.

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

Т.е. если AµB то: если A NP-трудная задача то и B NP-трудная задача, если B не является NP-трудной задачей то и A не является NP-трудной

Наряду с разделением задач на NP- трудные и полиномиально разрешимые,

NP-трудные задачи подразделяются на:

· задачи, имеющие псевдополиномиальные алгоритмы решения(иногда называемые NP-трудные в обычном смысле),

· NP-трудные в сильном смысле задачи, не имеющие псевдополиномиального алгоритма.

* * *

Пример. NP-трудная задача, имеющая псевдополиномиальный алгоритм решения – “Разбиение”: Заданы целые положительные числа a₁, a₂, …,a_r и число А, такие что . Требуется определить, существует ли множество XÌN={1, 2, …, r} такое, что .

Т.к. Разбиение µ P2//Cmax => P2//Cmax является NP-трудной.

Пример. NP-трудная в сильном смысле задача – "3-Разбиение"

* * *

Классификации алгоритмов решения задач дискретной оптимизации:

Классификация по трудоемкости:

· Полиномиальные алгоритмы O(n^d);

· Псевдо-полиномиальные алгоритмы O((An)^d);

· Экспоненциальные алгоритмы O(n^dyⁿ)

Классификация по точности:

· Точные алгоритмы (как правило, в этих алгоритмах применяют различные способы сокращения перебора);

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

· Приближенные алгоритмы с гарантированными оценками качества. Для них можно оценить абсолютную/относительную погрешность, т.е. отклонение полученного значения целевой функции от оптимального;

· Приближенные алгоритмы с регулируемой точностью. Время их работы зависит от выбранной пользователем необходимой точности.

* * *

Примеры точных алгоритмов:

Методы сокращенного перебора (метод ветвей и границ) – для сокращения перебора вычисляются нижние оценки целевой функции (при ее минимизации) и используются комбинаторные свойства задачи:

Метод динамического программирования;

Задачи теории расписаний формулируются как задачи целочисленного линейного программирования, т.е. задачи поиска минимума функции ∑с_jx_j при условиях ∑a_ijx_j ≥ b_i и x_i ≥ 0

и т.д.

Примеры приближенных алгоритмов:

Полиномиально-эвристические

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

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

Аппроксимационная схема – допускающая поиск решения с относительной погрешностью не более V заданного ε за время, полиноминально зависящее от 1/ε и от размерности входной информации – вполне полиномиальная аппроксимационная схема (FPTAS)

и т.д.

Гибридные алгоритмы, которые используют несколько методов.

Дата добавления: 2018-02-28; просмотров: 2458; Мы поможем в написании вашей работы!

Поделиться с друзьями:

⇐ Предыдущая 12

Мы поможем в написании ваших работ!