Теория алгоритмов. Зюзысов В.М. - 64 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

Составители: 

Рубрика: 

6 NP-полнота
В этом разделе мы рассмотрим класс задач, называемых «NP-полными». Для этих
задач не найдены полиномиальные алгоритмы, однако не доказано, что таких алгоритмов
не существует. Примеры таких задач приведены в конце предыдущего раздела. Изучение
NP-полных задач связано с так называемым вопросом P≠NP. Этот вопрос был поставлен в
1971 году
и является сейчас одной из наиболее интересных и сложных проблем теории
вычислений.
Большинство специалистов полагают, что NP-полные задачи нельзя решить за
полиномиальное время. Дело в том, что если хотя бы для одной NP-полной задачи
существует решающий ее полиномиальный алгоритм, то и для всех NP-полных задач
такие алгоритмы существуют
. В настоящее время известно очень много NP-полных задач
– многие из них практически важные. Все попытки найти для них полиномиальные
алгоритмы оказались безуспешными. По-видимому, таких алгоритмов нет вовсе.
Зачем программисту знать о NP-полных задачах? Если для некоторой задачи
удается доказать ее NP-полноту, есть основания считать ее практически
неразрешимой. В
этом случае лучше потратить время на построение приближенного алгоритма, чем
продолжать искать быстрый алгоритм, решающий ее точно.
Содержание этого раздела взято из [13]. Для понимания материала могут
потребоваться элементарные понятия теории графов.
6.1 Задачи разрешения и задачи оптимизации
В теории NP-полноты рассматриваются только задачи разрешения – задачи, в
которых требуется дать ответ «да» или «нет» на некоторый вопрос. Формально задачу
разрешения можно рассматривать как функцию, отображающую множество условий I во
множество {0,1} (1 = «да», 0 = «нет»). Многие задачи можно тем или иным способом
преобразовать к такому виду. Например, с задачей SHORTEST-PATH поиска кратчайшего
пути в графе связана задача разрешения PATH: «по заданному графу G = (V, E), паре
вершин u, v ∈ V и натуральному числу k определить, существует ли в G путь между
вершинами u и v, длина которого не превосходит k». Пусть четверка i = <G, u, v, k>
является условием задачи PATH. Тогда PATH(i) = 1,
если длина кратчайшего пути между
вершинами u и v не превосходит k, и PATH(i) = 0 в противном случае.
Часто встречаются задачи оптимизации, в которых требуется минимизировать
или максимизировать значение некоторой величины. Прежде чем ставить вопрос о NP-
полноте таких задач, их следует преобразовать в задачу разрешения. Обычно в качестве
такой задачи разрешения
рассматривают задачу проверки, является ли некоторое число
верхней (или нижней) границей для оптимизируемой величины. Так, например, мы
перешли от задачи оптимизации SHORTEST-PATH к задаче разрешения PATH, добавив в
условие задачи границу длины пути k.
Если после этого получается задача, не имеющая полиномиального алгоритма
разрешения, то тем самым установлена трудность исходной задачи. В
самом деле, если
для оптимизационной задачи имеется быстрый алгоритм, то и полученную из неё задачу
разрешения можно решить быстро (надо просто сравнить ответ этого алгоритма с
заданной границей). Таким образом, можно исследовать временную сложность задач
оптимизации.
Мы будем использовать строковое представление задач. Для каждого
представления e множества I входов абстрактной задачи
Q мы получаем свою строковую
задачу, которую мы в дальнейшем обозначаем e(Q). Мы не будем подробно описывать
используемое представление в конкретных задачах, считая, что оно выбрано достаточно
разумно и экономно (целые числа задаются двоичной записью, конечные множества –
списком элементов и т.п.). Нам понадобятся также следующие определения.

Страницы