За границами полиномиального времени

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

Предположим, для некоторого графа нужно найти независимое множество максимального размера (вместо того, чтобы проверять сам факт существования при заданном количестве узлов). До настоящего времени не известны никакие алгоритмы, обеспечивающие заметный выигрыш по сравнению с поиском методом «грубой силы», который в данном случае выглядит так:

Для каждого подмножества узлов S

Проверить, образует ли S независимое множество Если S является независимым множеством, размер которого превышает размер наибольшего из найденных ранее Сохранить размер S как текущий максимум Конец Если Конец цикла

Этот алгоритм очень похож на алгоритм «грубой силы» для независимых множеств из к узлов, однако на этот раз перебор ведется по всем подмножествам графа. Общее количество подмножеств n-элементного множества равно 2n, по- этому внешний цикл алгоритма будет выполнен в 2n итерациях при переборе всех этих подмножеств. Внутри цикла перебираются все пары из множества S, которое может содержать до n узлов, так что каждая итерация цикла выполняется за максимальное время O(n2). Перемножая эти два значения, мы получаем время выполнения O(n22n).

Как видите, граница 2n естественным образом возникает в алгоритмах поиска, которые должны рассматривать все возможные подмножества. Похоже, в задаче поиска независимого множества такая (или по крайней мере близкая) неэффектив- ность неизбежна; но важно помнить, что пространство поиска с размером 2n встре-

чается во многих задачах, и достаточно часто удается найти высокоэффективный алгоритм с полиномиальным временем выполнения. Например, алгоритм поиска методом «грубой силы» для задачи интервального планирования, упоминавшейся в главе 1, очень похож на представленный выше: мы опробуем все подмножества интервалов и находим наибольшее подмножество без перекрытий. Однако в задаче интервального планирования, в отличие от задачи поиска независимого множества, оптимальное решение может быть найдено за время O(n log n) (см.

главу 4). Такого рода дихотомия часто встречается при изучении алгоритмов: два алгоритма имеют внешне похожие пространства поиска, но в одном случае алгоритм поиска методом «грубой силы» удается обойти, а в другом нет.

Функция n! растет еще быстрее, чем 2n, поэтому в качестве границы произво- дительности алгоритма она выглядит еще более угрожающе. Пространства поиска размера n! обычно встречаются по одной из двух причин. Во-первых, n! — количе- ство комбинаций из n элементов с n другими элементами, например количество воз- можных идеальных паросочетаний n мужчин с n женщинами в задаче поиска устой- чивых паросочетаний. У первого мужчины может быть n вариантов пары; после исключения выбранного варианта для второго мужчины остается n - 1 вариантов; после исключения этих двух вариантов для третьего остается n - 2 вариантов, и т. д. Перемножая все эти количества вариантов, получаем n(n - 1) (n - 2) ... (2)(1) = n!

Несмотря на огромное количество возможных решений, нам удалось решить задачу устойчивых паросочетаний за O(n2) итераций алгоритма с предложениями. В главе 7 аналогичное явление встретится нам в контексте задачи двудольных паросочетаний, о которой говорилось ранее; если на каждой стороне двудольного графа находятся n узлов, существуют n! возможных комбинаций. Однако до- статочно хитроумный алгоритм поиска позволит найти наибольшее двудольное паросочетание за время O(n3).

Функция n! также встречается в задачах, в которых пространство поиска со- стоит из всех способов упорядочения n элементов. Типичным представителем этого направления является задача коммивояжера: имеется множество из n городов и расстояния между всеми парами, как выглядит самый короткий маршрут с по- сещением всех городов? Предполагается, что коммивояжер начинает и заканчивает поездку в первом городе, так что суть задачи сводится к неявному поиску по всем вариантам упорядочения остальных n - 1 городов, что ведет к пространству поиска размером (n - 1)!. В главе 8 будет показано, что задача коммивояжера, как и задача независимых множеств, относится к классу ЖР-полных задач; как предполагается, она не имеет эффективного решения.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме За границами полиномиального времени:

  1. Управление временем «Нам некогда делать это как следует - у нас хватает времени лишь на то, чтобы потом все переделывать».
  2. Линия времени "во времени"
  3. Я-ГРАНИЦА
  4. Границы эго
  5. Границы
  6. § 7. Смежные права и их границы
  7. Часть I. Границы Ума
  8. § 5. Границы исключительных авторских прав
  9. Царство без границ
  10. Нарушение границы