1.4. Алгоритмы и сложность

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

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

С практической точки зрения наиболее важным параметром является время решения задачи. Реально временная мера сложности алгоритма зависит от модели вычислительного устройства, от набора команд, от скорости их выполнения. Однако можно не фиксировать конкретное вычислительное устройство, а сравнивать алгоритмы по времени работы на гипотетическом устройстве, в котором каждая элементарная операция требует одну единицу времени. С учетом этого соглашения трудоёмкость (время) работы алгоритма будем оценивать необходимым для получения результата числом элементарных операций (как функции от размера входа алгоритма).

В каком же случае можно признать, что некоторая задача решена с практической точки зрения, то есть для нее построен алгоритм, «быстро» работающий на практике? Пусть на вычислительном устройстве, работающем со скоростью 10⁷ элементарных операций в секунду, решается ряд задач. Ниже указан максимальный размер входа (n) задач, допускающих решение за один день:

Трудоёмкость алгоритма	n	n2	2 n	n!
Значение n, при котором задача может быть решена за один день	1012	104	40	14

Для сравнения приведём данные о времени работы алгоритмов разной трудоемкости, если фиксирован объем входа (время выполнения одной операции принято равным одной миллисекунде):

Трудоёмкость алгоритма	Размер входа задачи
	20	50	100	200	500	1000
1000n	0,02 c	0,05 с	0,1 с	0,2 с	0,5 с	1 с
10 n3	0,08 c	1 с	10 с	60 с	0,35 ч	2,7 ч
2 n/3	110-4 c	0,1 с	2,7 ч	3104 веков	-	-
2n	1 c	35 лет	3104 веков	-	-	-
3n	0,96 ч	2109 веков	-	-	-	-

Приведенные данные позволяют естественным образом разделить алгоритмы на приемлемые с практической точки зрения (эффективные), у которых трудоемкость оценивается степенной функцией, и неэффективные алгоритмы с экспоненциальной оценкой трудоёмкости алгоритма. Такое разделение алгоритмов на «хорошие» и «плохие» подтверждается на практике: если для задачи удаётся предложить алгоритм со степенной (полиномиальной) оценкой трудоёмкости, то, как правило, удаётся получить (после серии улучшений) оценку не выше O(n³) , что позволяет успешно использовать такой алгоритм для реально возникающих значений параметров, в то время, как экспоненциальные алгоритмы не справляются с ними из-за «астрономического» объёма вычислений. Среди специалистов по сложности алгоритмов принят тезис, что понятие полиномиального алгоритма является формальным уточнением понятия приемлемого на практике алгоритма.

Дадим более строгое определение понятия временной сложности алгоритма.

Входные данные для любой задачи представляются словом в некотором алфавите. Например, в задаче построения эйлерова цикла граф G=(V,E) можно задать матрицей смежности, которая представляется двоичным вектором длины V². Размером входа задачи называется длина кода ее входных данных. Размер входа зависит от способа кодирования.

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

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

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

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

Каждая дискретная задача оптимизации П представляет последовательность П=(З1, З2, …,ЗМ ) индивидуальных задач, возникающих из П при конкретном выборе объектов и числовых параметров, фигурирующих в постановке задачи. Для каждой индивидуальной задачи З определена совокупность R допустимых решений r этой задачи. Каждому r поставлено в соответствие значение целевой функции l(r), как правило, целое. Например, задача коммивояжера – совокупность индивидуальных задач нахождения гамильтонова цикла минимальной суммарной длины в конкретном графе G, ребрам которого приписаны веса – длины этих рёбер.

Каждой задаче З можно поставить в соответствие предикат Р(З,l), принимающий значение 1 тогда и только тогда, когда для индивидуальной задачи З существует решение r , обладающее свойством l(r)≤l (в случае задачи минимизации). Например, для задачи коммивояжера предикат Р(З,l) =1 тогда и только тогда, когда в задаче З найдется гамильтонов цикл, суммарная длина которого не превышает l.

Задачу вычисления значений предиката Р(З,l) также называют задачей в форме распознавания. В теории сложности алгоритмов, где основной вопрос – вопрос о существовании полиномиальных алгоритмов решения тех или иных задач, исследуются только задачи в форме распознавания.

Наряду с описанным предикатом Р(З,l) с каждой экстремальной задачей свяжем предикат удостоверения q(З, l , r ), который принимает значение 1 тогда и только тогда, когда r является решением индивидуальной задачи З, причем выполнено l(r)≤l (или l(r)≥l в случае максимизации).

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

NP- полные задачи. Соотношение между классами Р и NP имеет в теории сложности алгоритмов фундаментальное значение. Учитывая, что Р включено в NP, необходимо решить, совпадают ли эти классы? В настоящее время общепринятым является убеждение в том, что эти классы не совпадают. Известно множество проблем П, не поддающихся полиномиальным алгоритмам. Основным приемом при исследовании алгоритмов является идея сводимости проблем.

Говорят, что проблема П1 сводится к проблеме П2, если алгоритм решения проблемы П2 может быть использован и для решения проблемы П1. Важность введенного понятия в том, что, если проблема П1 сводима к проблеме П2, и П2 относится к классу Р, то П1 также относится к классу Р. Опираясь на это понятие рассмотрим «самые трудные» задачи в классе NP.

Задача П NP называется NP – полной, если к ней сводится любая задача из класса NP. Если установлено, что некоторая задача является NP – полной, то такая задача становится кандидатом на звание неподдающейся эффективным алгоритмам задачи. Примерами таких задач являются задачи об упаковке в контейнеры, о рюкзаке, о покрытии таблиц, задача коммивояжера. Все эти задачи относятся к классу NP-полных.

Подходы к решению NP – полных задач. Задачи, относящиеся к классу NP – полных, трудно решить эффективно и точно. Тем не менее, известны удовлетворительные подходы к решению NP – полных задач.

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

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

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

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