Лекция № 13
Тема:
«Анализ сложности и оптимальности алгоритмов»
План лекции
1. Понятие сложности задач
2. Вычислительная сложность.
3. Классификация задач по сложности
4. Соотношение между классами P и NP
5. NP-полные задачи
1. Понятие сложности задач
Под задачей понимается некоторый вопрос, на который нужно найти (вычислить) ответ. Задачи бывают массовыми (общими) и частными (индивидуальными).
Общая задача определяется:
ü списком параметров – свободных переменных, конкретные значения которых неопределенны;
ü формулировкой условий – свойств, которыми должен обладать ответ (решение задачи).
Массовые задачи часто называют алгоритмическими проблемами. Частная задача получается из массовой, если всем параметрам массовой задачи придать конкретные значения – здесь исходные данные. В общем случаи для любой алгоритмически разрешимой задачи существует несколько разрешающих алгоритмов. С практической точки зрения важно не просто существование разрешающих алгоритмов, а поиск среди них наиболее простого и наименее трудоемкого.
Под сложностью задачи принято понимать минимальную из сложностей алгоритмов, решающих эту задачу. Компьютерные науки пока не накопили достаточно сведений для того, чтобы задача минимизации сложности алгоритма была поставлена математически строго.
Поэтому без ответов остаются такие вопросы, связанные с нижней оценкой сложности алгоритмов, а значит, и сложности задач:
ü Существует ли для заданной задачи алгоритм минимальной сложности?
ü Как убедиться, что найденный алгоритм действительно минимальный или, напротив, не минимальный?
ü Можно ли для рассматриваемой задачи доказать, что никакой разрешающий ее алгоритм не может быть проще найденной нижней оценки сложности?
При разработке алгоритмов можно наблюдать, что для некоторых задач можно построить алгоритм полиномиальной сложности. Такие задачи называют полиномиальными. Полиноминально разрешимые задачи можно успешно решать на компьютере и даже в тех случаях, когда они имеют большую размерность.
Для других задач не удается найти полиномиальный алгоритм. поэтому их называют трудноразрешимыми. К классу трудноразрешимых задач относится большое число задач алгебры, математической логики, теории графов, теории автоматов и других разделов дискретной математики.
В большинстве своем это так называемые переборные задачи. Переборная задача характеризуется экспоненциальным множеством вариантов, среди которых нужно найти решение, и может быть решена алгоритмом полного перебора. Переборный алгоритм имеет экспоненциальную сложность и может хорошо работать только для небольших размеров задачи. С ростом размера задачи число вариантов быстро растет, и задача становится практически неразрешимой методом перебора.
Многие из переборных задач являются экспоненциальными по постановке. Экспоненциальные по постановке задачи не представляют особого интереса для теории алгоритмов, поскольку для них, очевидно, невозможно получить алгоритм полиномиальной сложности.
Возникает вопрос: если известно, что некоторая задача алгоритмически разрешима, то неудача в разработке для нее полиномиального разрешающего алгоритма является следствием неумения конкретного разработчика или следствием каких-то свойств самой задачи? Ответ на этот вопрос дает классическая теория алгоритмов, которая классифицирует задачи по сложности.
При этом классифицируются лишь распознавательные задачи – задачи, имеющие распознавательную форму. В распознавательной форме суть задачи сводится к распознаванию некоторого свойства, а ее решение – один из двух ответов: «да» или «нет». С точки зрения математической логики задаче распознавания свойства соответствует предикат Р(х), где х – множество фактических значений входных переменных задачи.
Существуют задачи, которые изначально имеют распознавательную форму. Например, являются ли два графа изоморфными? Другой пример – задача о выполнимости булевой функции, которая является исторически первой распознавательной задачей, глубоко исследованной в теории алгоритмов.
Многие задачи, которые в исходной постановке представлены в иной форме (к ним относятся задачи дискретной оптимизации), довольно просто приводятся к распознавательной форме.
Например, если требуется найти хроматическое число графа, то формулируют вопрос: верно ли, что заданный граф является k – раскрашиваемый, где k – заданное целое положительное число. Между тем, имеются задачи, которые нельзя привести к распознавательной форме. Это, в первую очередь, конструктивные задачи – задачи на построение объектов дискретной математики, обладающих заданными свойствами: генерация всех подмножеств конечного множества; генерация всех n! различных перестановок; построение плоской укладки графа; построение остовного дерева графа и т. п. Такие задачи могут быть как трудноразрешимыми, так и полиноминально разрешимыми. Они пока не попадают под существующую в теории алгоритмов классификацию.
2. Вычислительная сложность
В предыдущем разделе мы ввели
понятие алгоритма, определив его как точное предписание, задающее процесс
преобразования исходных данных в результаты. Обычно требуется, чтобы алгоритмы обладали следующими пятью
свойствами (проверим приведенный в предыдущем разделе алгоритм Евклида на
соответствие этим свойствам):
1. Результативность. Алгоритм должен давать некоторый результат. В
данном случае этот результат – НОД.
2. Конечность. Работа алгоритма должна заканчиваться за конечное число
шагов. Алгоритм Евклида обладает этим свойством, т.к. максимумы из X и Y
образуют убывающую последовательность натуральных чисел, не могущую быть
бесконечной.
3. Определённость. Все предписания алгоритма должны допускать
однозначную трактовку и быть понятными исполнителю (например, компьютеру). Т.е.
исполнитель должен обладать средствами выполнения всех инструкций. В данном
случае машина должна уметь сравнивать и вычитать натуральные числа .
4. Массовость. Алгоритм должен давать решения целой группы задач,
отличающихся исходными данными. Алгоритм Евклида позволяет найти НОД любой пары
натуральных чисел.
5. Детерминированность. Многократное применение к одному и тому же
набору исходных данных должно давать одинаковый результат. Применительно к
алгоритму Евклида это также справедливо.
Но кроме того, огромное значение
имеет
6. Эффективность. Все шаги алгоритма должны быть такими, чтобы
исполнитель мог выполнить их за конечное время, лежащее в некоторых разумных
пределах. И если речь идёт о вычислительной машине, то – в пределах разумных
ограничений используемой памяти.
Именно с эффективностью алгоритма
интуитивно связано понятие “стоимости“, понимаемой как количественная оценка
требуемых для его реализации ресурсов. Более точный смысл понятию стоимости
позволяет придать понятие сложности
алгоритмов. Оно овеществляет стоимость во времени и в пространстве,
позволяет оценить время выполнения и объём требуемой памяти.
Вообще можно сказать, что по мере
накопления опыта работы в некоторой области знаний, каждый из нас начинает
интуитивно чувствовать, что та или иная задача более или менее трудна, чем
другая. Разумеется, такого субъективного, не выраженного количественной мерой
понятия как “легче” или “труднее”, нам не достаточно. Как же можно (и можно
ли?) определить действительную сложность задачи?
Сложность алгоритма оценивают по
его динамическим характеристикам, а не по статическим: например, большая
программа может выполняться очень быстро, а короткая – очень долго. На практике сложность алгоритма
обычно связывают с основным его параметром, существенно влияющим на количество
выполняемых действий. Как правило, это размер массива обрабатываемых данных
(размер задачи).
Кроме того, естественно считать
критерием качества алгоритма решение наихудшего из возможных случаев его
применения.
Таким образом, сложностью
алгоритма называется выраженная в виде
функции от размерности входных данных верхняя граница числа операций,
необходимых для реализации алгоритма.
Сложность задачи – это
сложность наилучшего алгоритма, известного для ее решения. Поэтому она зависит
от уровня развития методов решения. Здесь возникают три принципиальных вопроса:
1. До какого предела можно
улучшать данный алгоритм?
2. Ведет ли учет сложности к
появлению некоторой классификации задач?
3. Существуют ли методы перехода
из одного класса в другой, т.е. от более сложных задач к более простым?
Например, время работы алгоритма,
выполняющего только операции чтения и занесения n данных в оперативной памяти, определяется формулой t=an+b,
где a – время чтения-записи, b – суммарное время вспомогательных
операций. Здесь имеет место линейная зависимость от n, и сложность алгоритма поэтому называется линейной. Коэффициенты a и b
неизвестны, но зависят от ЭВМ,
транслятора и т.д. Поэтому интересен характер зависимости от основного
параметра, говорят о теоретической сложности, учитывая ту функцию от основного
параметра, которая определяет сложность. В данном случае это O(n).
Сортировка с помощью
прямого обмена ("пузырьковая сортировка") n элементов массива представляет собой следующий процесс:
определяется наименьший элемент во всем массиве и производится его обмен с
первым элементом; затем определяется наименьший элемент в оставшейся части массива
и производится его обмен со вторым элементом и т.д. Значит, всего выполняется n–1 сравнений при поиске первого
элемента, n–2 сравнений при поиске
второго элемента и т.д.
(n–1)+(n–2)+...+1=(
– n)/2
Это полином второй
степени (говорят, что сложность алгоритма полиномиальна,
а в данном случае – квадратична). Для больших n можно считать, что сложность O().
Если сложность
алгоритма оценивается по уже написанной программе, то вместо числа сравнений
вычисляется число повторений внутренних циклов
for k:=1 to n–1 do
begin min:=A [k];
for i:=k+1 to n do
if
min>A[i] then min:=A[i];
A[i]:=A[k];
A[k]:=min;
еnd;
Внешний цикл
выполняется n–1 раз. Внутренний цикл
при каждом повторении внешнего срабатывает в среднем (при равномерном разбросе
величин) n/2 раз. Умножив, получаем
ту же самую величину.
При больших значениях
n за асимптотическую оценку можно
взять , т.е. сложность имеет порядок O().
Оценками времени работы
алгоритма являются максимальное, минимальное и среднее время его выполнения.
Они могут совпадать или не совпадать. В приведённой процедуре сортировки они
совпадают, а в алгоритме Евклида не совпадают. Максимальное число шагов –
циклов очевидно определяется ситуацией вида A=max, B=1. Тогда, если за параметр n взять значение | A–B |, то максимальная оценка сложности – порядка O(n).
Но минимальная оценка сложности при AB соответствует ситуации A=2B. Результат в этом случае достигается
за один шаг, а сложность – O(1) не
зависит от n.
"Усовершенствуем"
алгоритм Евклида, прекращая его выполнение в том случае, если оказывается, что
одно из чисел делится на другое. Тогда это и есть НОД:
X:=A; Y:=B;
while X modY 0 or YmodX 0 do
if X>Y then X:=X–Y else Y:=Y–X;
NOD:=min(X, Y)
В нашем примере (см.
раздел 3.1) вместо пяти выполнится только один шаг, а в случае равенства одного
из двух исходных чисел A и B единице, так же как в случае кратности
одного числа другому, преобразования вообще не производятся.
Тем не менее – скорее
интуитивно – следует считать среднее значение оценки сложности линейно
зависящим от |A–B|, хотя достаточно низкий коэффициент можно установить
статистически.
Также можно улучшить
и алгоритм сортировки, о чем будет
сказано далее.
Однако в большом
числе задач верхние и нижние оценки совпадают на уровне порядка. Например,
оценим сложность алгоритма умножения матриц размера n:
for i:=1 to n do
for j:=1 to n do
begin C[i,
j]:=0;
for k:=1 to n do
C[i, j]:=C[i, j]+A[i, k]*B[k, j]
end;
Очевидно, что общее
количество операций, выполняемых в трех вложенных циклах, пропорционально 
. И как бы мы ни совершенствовали
алгоритм, объективно существует число операций для решения задачи, такое, что
верхние и нижние оценки сложности совпадают: O()=o(). В целом эта оценка также
полиномиальная.
Итак, рассмотрим
некоторый алгоритм A. Почти всегда
существует параметр n,
характеризующий объём его данных. Пусть функция T(n) – время выполнения A.
Пусть f – некоторая функция от n. Говорят, что алгоритм A имеет теоретическую (асимптотическую)
сложность O(f(n)), если
Если алгоритм
выполняется за фиксированное время, не
зависящее от размера задачи, говорят, что его сложность равна O(1).
Это определение
обобщается в случае, если время выполнения существенно зависит от нескольких
параметров. Например, алгоритм, определяющий, входит ли множество m элементов в множество n элементов, может иметь в зависимости
от используемых структур данных сложность O(m´n) или O(m+n).
Практически время выполнения алгоритма может зависеть от значений данных, как мы видели выше. Время выполнения некоторых алгоритмов сортировки (см. далее) существенно сокращается, если первоначально эти данные частично упорядочены. Чтобы учитывать это, сохраняя возможность анализировать алгоритм независимо от их данных, различают:
Максимальную сложность, определяемую значением Tmax(n) – время выполнения
алгоритма, когда выбранный набор n
данных порождает наиболее долгое время выполнения алгоритма;
Среднюю сложность, определяемую значением Tср(n) – средним временем
выполнения алгоритма, применённого к n
произвольным данным.
Эти понятия без труда
распространяются на измерение стоимости в единицах объёма памяти: можно
говорить о средней и максимальной пространственной сложности.
3. Классификация задач по сложности
Задачи, как и алгоритмы принято классифицировать по сложности. Множество всех распознавательных задач, для которых существует полиномиальный разрешающий алгоритм, образуют класс Р. Ясно, что распознавательные трудноразрешимые задачи не принадлежат классу Р. Класс NP – это множество распознавательных задач, которые могут быть разрешены за полиномиальное время на недетерминированной машине Тьюринга (НМТ). Оракул предлагает решения, которые после проверки верификатором приобретают «юридическую» силу. Таким образом, задачи класса NP являются «полиноминально проверяемыми».
Например, в задаче коммивояжера оракул предлагает некоторую перестановку всех вершин графа, а верификатор проверяет, образует ли эта перестановка гамильтонов цикл графа. Ясно, что такую проверку можно выполнить с полиномиальной сложностью – надо лишь проверить смежность соседних вершин. Построить одну перестановку вершин тоже можно с полиномиальной сложностью. Оба шага решения задачи полиномиальные, поэтому задача коммивояжера принадлежит классу NP. Трудноразрешимой ее делает факториальное число повторений этих шагов. Следует отметить, что такую двухшаговую процедуру поиска решения можно применить к любой распознавательной задаче полиномиальной сложности.
Полиномиальные по сложности алгоритмы относят к классу P-сложных.
Среди экспоненциальных выделяют алгоритмы, основанные на переборе, и их
выделяют в класс NP-сложных (т.е. формально возможно существование
экспоненциальных алгоритмов, основанных не на переборе. Например, n!, растущий быстрее, чем 
). К NP-сложным относятся, например, задачи линейного
целочисленного программирования, составление расписания, поиск кратчайшего пути
в лабиринте и т.д. Обратим внимание, что все это дискретные задачи.
Например, булевская задача о рюкзаке:
Ее можно решить, перебирая
булевские n-мерные векторы-варианты.
Число вариантов равно . Т.е. при больших n
задача труднорешаемая, а далее, с учетом ограниченных
возможностей вычислительных средств – практически неразрешимая. Но к классу NP относятся и неразрешимые задачи,
например, десятая проблема Гильберта: “Существует ли алгоритм, который по
данному полиному p(
, ... , 
) c целыми коэффициентами распознает, имеет ли уравнение p=0 решение в целых числах”. Доказано,
что такого алгоритма в принципе не существует, хотя можно методом перебора
попытаться решить эту задачу. Если ограничиться областью поиска | xi |X, то
сложность его составляет 
.
Классическая задача о
коммивояжере (k1): Есть конечный
набор городов C={
, 
, ... , 
} и расстояний между ними d(
,
). Необходимо найти упорядоченный набор этих городов 
такой, что
(1)
Т.е. надо найти путь обхода всех n городов (без повторного посещения)
минимальной длины.
Это NP-сложная задача; поиск решения требует проверки n! перестановок n городов. Сложность задачи O(n!) (еще раз напомним, что n! растет быстрее, чем ). При этом не обязательно выполняется правило треугольника:
Проиллюстрированная конкретная
задача имеет решение < , , 
, ,>, определяющее минимально возможный маршрут длиной 27.
Выделим в классе NP-сложных
задач задачи распознавания свойств,
которые имеют два решения – “да” или “нет”.
Видоизменим задачу о коммивояжере
(т.е. сформулируем задачу k2):
Условие: Задано множество городов C={, ... , } и расстояний d(ci, cj)
между ними, а также граница В длины
маршрута обхода городов.
Вопрос: Существует ли маршрут,
проходящий через все города из C,
длина которого не превосходит В? Т.е.
существует ли перестановка 
такая, что
(2)
Будем исходить из того очевидного
факта, что задачи распознавания обладают той же сложностью, что и задача
оптимизации (k1); поэтому выводы о
сложности второй задачи применимы и к задачам оптимизации.
Можно представить следующую схему
решения задачи распознавания свойств на примере задачи k2 :
1. Предъявление некоторого
маршрута (стадия угадывания).
2. Проверка: является ли он
решением, т.е. соответствует ли условиям задачи, а по длине – не превосходит B.
Т.е. определение ответа – “да” или “нет” (стадия проверки).
Очевидно, что процедуру проверки
можно представить алгоритмом полиномиальной
временной сложности. Стадия же угадывания порождает экспоненциальную
сложность. Такие алгоритмы, состоящие из указанных двух стадий, называют недетерминированными.
Отсюда – класс NP определяется
как класс всех задач типа распознавания, которые могут быть решены
недетерминированными (N – nondeterministic) алгоритмами за полиномиальное (P – polinomial)
время.
Тогда все алгоритмы класса P можно считать подмножеством множества NP, или детерминированными алгоритмами. Тогда
гипотетическая картина класса NP-сложных задач может быть представлена таким
образом:
4. Соотношение между классами P и NP
Очевидно, что всякую задачу, которая может быть разрешена за полиномиальное время на детерминированной машине Тьюринга (ДМТ), можно рассматривать как частный случай НМТ, в которой отсутствует стадия угадывания, а стадия проверки совпадает с ДМТ. Следовательно, справедливо включение P в NP.
К настоящему времени не удалось доказать ни одного из более сильных утверждений: P = NP или P входит в NP. Вопрос о соотношении классов P и NP поставлен более тридцати лет назад. Большинство специалистов полагают, что верно строгое включение P в NP.
В самом деле, интуитивно класс P можно представить себе как класс задач, которые можно быстро решить, а класс NP – как класс задач, решение которых может быть быстро проверено. Ясно, что решить задачу намного труднее, чем проверить готовое решение. Поэтому наверняка в классе NP имеются задачи, которые нельзя решить за полиномиальное время.
Более серьезной причиной полагать, что P ≠ NP, это существование NP-полных задач. Для того, чтобы доказать, что P ≠ NP необходимо научиться получать нижние оценки сложности любого алгоритма, предназначенного для решения некоторой задачи из класса NP. Поэтому проблему соотношения классов P и NP называют проблемой нижних оценок.
Вопрос о соотношении классов P ≠ NP не праздный. На карту поставлено не только машинное время. Так, в криптографии существует раздел о шифровании с открытым ключом. Здесь намеренно используют задачи экспоненциальной сложности, которые не позволяют выполнить дешифрование информации за разумное время. Если вдруг P = NP, то возникает возможность существования для этих задач полиномиальных алгоритмов. Но тогда многие секреты перестанут быть секретными.
5. NP-полные задачи
Для некоторых задач класса P = NP было обнаружено удивительное свойство. Оказалось, что некоторые из них универсальны в том смысле, что построение полиномиального алгоритма для любой такой задачи влечет за собой возможность построения такого же алгоритма для всех остальных задач класса NP. Такие задачи называют NP-полными.
Для понимания этого свойства требуется определить понятие полиномиальной сводимости одной задачи к другой. Пусть заданны две массовые задачи z1, z2 принадлежащие классу NP. Говорят, что задача z1 полиномиально сводится к задаче z2, если:
ü для любой частной задачи из z1 можно за полиномиальное время построить соответствующую ей частную задачу из z2;
ü решение построенной частной задачи из z2 за полиномиальное время может быть преобразовано в решение соответствующей частной задачи из z1.
Массовую задачу z называют NP-полной, если любая задача из этого класса полиномиально сводится к решению задачи z.
Таким образом, теперь ясно, что разработка полиномиального алгоритма любой NP-полной задачи практически означает возможность построения такого алгоритма для любой задачи класса NP, т. е. справедливость равенства P = NP.
Для доказательства NP-полноты некоторой задачи, нет необходимости сводить к ней каждую задачу класса NP. Достаточно установить ее принадлежность к классу NP и показать, что к ней сводится какая-либо известная NP-полная задача. Чтобы воспользоваться этой схемой, надо иметь в распоряжении хотя бы одну NP-полную задачу.
Методы, используемые при доказательстве NP-полноты конкретных задач, развиваются очень быстро.
В настоящее время часто применяются три основных метода: сужение задачи, локальная замена и построение компоненты.
Доказательство методом сужения NP-полноты задачи z1, которая принадлежит классу NP заключается в установление того, что задача z1 включает в качестве частного случая известную NP-полную задачу z2.
Доказательство двумя другими методами достаточно нетривиальны, и поэтому здесь у нас нет возможности их рассмотреть и проиллюстрировать.
В заключение следует отметить, что теория NP-полноты, помимо теоретического, представляет и чисто практический интерес. Доказав, что задача NP-полна, разработчик алгоритмов получает достаточное основания, чтобы отказаться от поиска эффективного и точного решения.
В настоящее время для решения NP-полных задач используются в основном различного рода приближенные алгоритмы, основанные на эвристиках и вероятностных механизмах.
Контрольные
вопросы.
1.
Постановка задачи.
2.
Сложность задачи.
3.
Полиномиально
разрешимые задачи.
4.
Переборные задачи.
5.
Распознавательные
задачи.
6.
Эффективность
алгоритма.
7.
Класс сложности Р.
8.
Класс сложности NP.
9.
Соотношение между
классами Р и NP.
10.
NP-полные задачи.