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

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

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

Этот алгоритм очень похож на алгоритм «грубой силы» для независимых множеств из k узлов, однако на этот раз перебор ведется по всем подмножествам графа. Общее количество подмножеств n-элементного множества равно 2n, поэтому внешний цикл алгоритма будет выполнен в 2n итерациях при переборе всех этих подмножеств.

Как видите, граница 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) итераций алгоритма с предложениями.

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

Функция n! также встречается в задачах, в которых пространство поиска состоит из всех способов упорядочения n элементов.

Типичным представителем этого направления является задача коммивояжера: имеется множество из n городов и расстояния между всеми парами, как выглядит самый короткий маршрут с посещением всех городов?

Предполагается, что коммивояжер начинает и заканчивает поездку в первом городе, так что суть задачи сводится к неявному поиску по всем вариантам упорядочения остальных n – 1 городов, что ведет к пространству поиска размером (n − 1)!.