Классификация алгоритмов по временной сложности

Применение порядковых оценок определения сложности алгоритмов, с одной стороны, и исследование возможностей решения различных задач на современных ЭВМ — с другой позволили по характеристике время решения задачи выделить два класса алгоритмов: полиномиальные и экспоненциальные. К классу полиномиальных алгоритмов относят те из них, для которых функция /(п) при п —> со растет не быстрее, чем некоторый полином (многочлен) от п. Если же указанная функция растет быстрее, алгоритм относят к классу экспоненциальных алгоритмов. Например, алгоритм с функцией /(л) = 100л3 + п2 +10 — полиномиальный. Алгоритмы, для которых /(л) = 2"+л2, /(л) = е2",

/(л) = л! — экспоненциальные.

В сравнении с экспоненциальными алгоритмами алгоритмы с полиномиальным ростом сложности вычислений характеризи-руются рядом положительных свойств. Во-первых, при увеличении размера задачи л время счета по этим алгоритмам растет значительно медленнее, чем по экспоненциальным, даже в том случае, когда для малых л полиномиальный алгоритм затрачивает больше времени, чем экспоненциальный. Во-вторых, полиномиальные алгоритмы лучше используют технологии производства ЭВМ, направленные на повышение их производительности. Так, если удается увеличить производительность ЭВМ, например, в 10 раз, размер задач, решаемых полиномиальным алгоритмом, увеличивается в 1 <10 раз. Для экспоненциального алгоритма возможно увеличение размера решаемых задач не в к раз, а лишь на некоторую величину [4].

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

Перечисленные качества позволяют считать полиномиальные алгоритмы эффективными.

В противоположность этому экспоненциальные алгоритмы называют неэффективными и прежде всего потому, что даже при высокой производительности современных ЭВМ они не справляются с решением задач требуемых размеров в заданное время. В подтверждение сказанному в табл. 1.1 приведена табличная зависимость процессорного времени генерации п перестановок на персональном компьютере модели 1ВМ РС Репйит (III) с тактовой частотой центрального процессора 877 МГц.

Таблица 1.1. Табличная зависимость 7 = /(я!)

п

8

9

10

11

12

13

п

40 320

362 880

3 628 800

39 916 800

479 001 600

6 227 020 800

6 С

0,05468

0,1679

1,539

18,566

240,078

1440,3

Эта зависимость приближена эмпирической формулой / = = е<-2065+215,,> = ехр (-20,65 + 2,15л), указывающей на то, что, с одной стороны, она носит экспоненциальный характер, с другой — уже при п= 12 для генерации всех перестановок указанной ЭВМ требуется три минуты. При л =13 для достижения этой цели компьютер должен затратить примерно 23 минуты, а при л= 14 — немногим меньше 3,5 ч. Такое время перебора вариантов в практических условиях не всегда допустимо.

Все множество задач, решаемых полиномиальными алгоритмами, называют классом Р (полиномиальный). Для определения класса задач, решаемых только экспоненциальными алгоритмами, введено понятие недетерминированного алгоритма. Это воображаемый полиномиальный алгоритм, который в каждом состоянии может выполнять как угодно много альтернативных действий одновременно. Чтобы проиллюстрировать работу такого алгоритма, рассмотрим задачу путешествующего продавца (коммивояжера). Этот продавец имеет товарную базу в одном из городов его региона продаж, например в городе 1, и должен объехать еще три города для того, чтобы продать свои товары и потом вернуться в исходный город 1. Различные порядки объезда городов, скажем, 1—2—3—4 и 1—3—2—4, требуют различного расхода бензина и, следовательно, имеют различную стоимость, что обусловлено различным профилем автомобильных дорог. Продавец должен выбрать такой порядок объезда городов (маршрут), который обеспечит наименьшую его стоимость.

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

Все перестановки, а их 3! = 6, легко построить, используя корневое дерево перебора. В корневой вершине дерева указывается номер исходного города. В вершинах первого яруса отмечаются части маршрутов, которые ведут из города 1 в остальные города 2, 3, 4. Вершины второго яруса указывают части маршрутов, которые можно проложить из городов первого яруса. В вершинах последнего, третьего яруса указаны полные маршруты объезда городов, т. е. полные перестановки. Дерево изображено на рис. 1.2.

Дерево маршрутов в задаче коммивояжера

Рис. 1.2. Дерево маршрутов в задаче коммивояжера

для четырех городов

Согласно этому дереву детерминированный алгоритм формировал бы и оценивал маршруты последовательно. Например, он бы последовательно строил самую левую ветвь, т. е. сформировал бы маршрут 1—2—3—4 и оценил его. Затем вернулся бы в вершину М|2 и достроил вершины М|24, М|242, т. е. построил бы маршрут 1—2—4—3 и оценил его. Потом вернулся бы в корневую вершину дерева и построил маршрут 1—3—2—4 и т. д. Всего бы он сформировал шесть ветвей, возвращаясь при этом на необходимый ярус дерева. По определению недетерминированный алгоритм, находясь в состоянии М,, одновременно сформирует три вершины дерева М12, М13, М|4. Находясь в этом состоянии, т. е. на ярусе 1, он одновременно сформирует шесть вершин М |2з, М124, М132 М134, М142, М143. Находясь затем на 2-м ярусе, недетерминированный алгоритм одновременно сформирует вершины последнего яруса дерева маршрутов. Таким образом, это дерево он мог бы построить за три последовательных шага, так как будто бы строилась одна ветвь, т. е. за полиномиальное время.

В какой-то мере действия недетерминированного алгоритма напоминают работу многопроцессорной ЭВМ с бесконечным числом асинхронно включающихся в работу процессов. Однако никакое физическое устройство пока не может быть построено по этому принципу. Например, только в случае двоичного дерева высотой п на последнем его ярусе будет образовано 2" листьев, что при п = 30 потребует больше миллиарда процессоров для их обработки.

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

Другое толкование понятия «недетерминированный полиномиальный» несколько иное. Оно вытекает из того, что недетерминированность алгоритма подразумевает неопределенность количества шагов предполагаемого двухэтапного способа решения задачи. На первом этапе этого способа за полиномиальное время находится возможное ее решение. На втором этапе тоже за полиномиальное время проверяется, действительно ли это решение рассматриваемой задачи. Хотя каждый из этапов требует полиномиального времени решения, число обращений к ним может оказаться экспоненциальным. Такая задача попадает в класс А!Р, так как для поиска ее необходимого решения требуется просматривать огромное количество побочных решений и нет алгоритма интенсивного отбрасывания заведомо не нужных из них.

Хотя классы задач Р и Л^Р являются различными, любая задача из Р принадлежит множеству ЫР. Это обусловлено тем, что любая задача из класса Р, решаемая детерминированным алгоритмом, может быть представлена как описанный двухэтапный процесс решения: вначале находится любое решение, затем проверка, действительно ли это решение. Причем PczNP, так как для класса А!Р неизвестны детерминированные полиномиальные алгоритмы. Однако это не означает, что такого алгоритма не существует. Пока этот тезис не удалось доказать. Поэтому проблема, равны ли классы Р и NP, является открытой.

В классе задач Л^Р существует подмножество задач, которые принято называть АТ’-полными. Эти задачи обладают особой сложностью решения и отличаются от остальных задач класса АГР тем, что если удастся найти полиномиальный алгоритм решения какой-либо из них, то это будет означать, что все задачи из А могут быть решены полиномиальными алгоритмами.

Выделение класса А^Р-полных задач основано на преобразовании одной задачи в другую.

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

При отнесении некоторой задачи А к классу АР’-полных задач поступают наоборот. К этой задаче А сводят (преобразовывают в нее) некоторую АР^-полную задачу. Тем самым подтверждают, что выбранная АР’-полная задача выражается в терминах А, т. е. А также принадлежит к классу АР’-полных задач.

Таким образом, класс АР>-полных задач — это класс задач из А!Р, которые преобразуются одна в другую. Именно на это опирается утверждение, что если будет найден полиномиальный алгоритм для некоторой АР’-полной задачи, то все другие АР’-полные задачи также могут быть решены с помощью своего полиномиального алгоритма.

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

К настоящему времени большинство задач дискретной математики по показателю «сложность алгоритмов решения» классифицировано, т. е. отнесено к классам Р и А]Р. Кроме задач на поиск наибольшего (наименьшего) значения функций (функционалов), в класс АР*включены так называемые задачи распознавания, решением которых является ответ «да—нет». Эти задачи не труднее в отношении решения, чем экстремальные задачи, однако во многих случаях они оказались более удобными для целей классификации. Особое место среди этих задач занимает задача из раздела математической логики о выполнимости булевой формулы. Обычно она представляется в конъюнктивной нормальной форме (КНФ). Например, как (х, V х2 V х3) л (х, V х2 V х4) л (х3 х4) л х,,

где булевы переменные х,, х2, х3, х4 называются литералами, а дизъюнкции х,, х2, х3, х4 или их отрицания — дизъюнктами.

Булева формула считается выполнимой, если существует некоторый набор литералов такой, что она получает значение «истина». Если же такого набора литералов не существует, формула является невыполнимой. Задача о выполнимости булевой формулы состоит в том, чтобы выяснить, есть ли некоторый набор литералов, для которых значение булевой формулы истинно.

Очевидное решение этой задачи — перебор 2" наборов литералов, построение для каждого набора таблицы истинности функций и выяснение по ней, истинна ли булева формула. Такой алгоритм имеет сложность 0(2"), т. е. он экспоненциальный и, таким образом, неэффективный. Других алгоритмов решения этой задачи нет. Наоборот, доказано, что эта задача принадлежит к классу ./УР-полных задач [4, 5].

Доказательство УУР-полноты задачи о выполнимости булевой формулы в свою очередь послужило основанием не только для классификации других задач, а в большей мере для развития самой логики доказательства УУР-полноты. Она состоит в следующем. Для того чтобы доказать, что некоторая задача УУР-полна, необходимо логически обосновать два положения:

  • 1) задача входит в класс ТУР;
  • 2) задача также трудна по решению, как и известные УУР-полные задачи этого класса.

Весьма часто и успешно для обоснования первого положения используется понятие недетерминированного алгоритма. Если удается показать, что рассматриваемая задача может быть решена недетерминированным алгоритмом за полиномиальное время, то она автоматически входит в класс /УД-задач. Доказательство УУР-трудности задачи осуществляется путем преобразования (полиномиального сведения) некоторой УУР-полной задачи в рассматриваемую задачу. Иными словами, необходимо подобрать наиболее подходящую УУР-полную задачу и представить ее в терминах той задачи, которая нуждается в доказательстве ее ЛТ’-полноты. Подробно с логикой доказательства можно познакомиться по книге [6].

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

 
< Пред   СОДЕРЖАНИЕ     След >