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

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

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

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

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

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

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

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

п

8

9

10

11

12

13

п

40320

362880

3628800

39916800

479001600

6227020800

і (сек.)

0,05468

0,1679

1,539

18,566

240,078

1440,3

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

Эта зависимость приближена эмпирической формулой Г = ?>(-20,65+2,15«) _ еХр(_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. Вершины второго яруса указывают части маршрутов, которые можно проложить из городов первого яруса. В вершинах последнего, третьего яруса указаны полные маршруты объезда городов, т.е. полные перестановки. Дерево изображено на рис. 5.3.

Согласно этому дереву детерминированный алгоритм формировал бы и оценивал маршруты последовательно. Например, он бы последовательно строил самую левую ветвь, т.е. сформировал бы маршрут 1—2—3—4, и оценил его. Затем вернулся бы в вершину Мп и достроил вершины Л/,^, Л/1243, т-е построил бы маршрут 1—2—4—3, и оценил его. Потом бы вернулся в корневую вершину дерева и построил бы маршрут 1—3—2—4 и т. д. Всего бы он сформировал шесть ветвей, возвращаясь при этом на необходимый ярус дерева. По определению, недетерминированный алгоритм, находясь в состоянии Л/,, одновременно сформирует три вершины дерева Л/|2, Мп, Мн. Находясь в этом состоянии, т. е. на ярусе 1, ОН одновременно сформирует шесть вершин М|23, Л/,24, Л/,32, Л/,34, Л/,42, Мш. Находясь затем на ярусе 2, недетерминированный алгоритм одновременно сформирует вершины последне-

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

Рис. 5.3. Дерево маршрутов в задаче коммивояжера для четырех городов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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