Метод декомпозиции (Метод «разделяй и властвуй»), страница 3

Пример. Задача о паре ближайших точек. Пусть множество S состоит из n точек на плоскости. Требуется найти две точки, расстояние между которыми минимально. Точки можно разделить на два подмножества S1 и S2, состоящие из n/2 точек каждое, проведя вертикальную линию x=c так, чтобы слева и справа от нее оказалось по n/2 точек (одни из способов поиска значения константы с состоит в использовании медианы координат x точек). Следуя методу декомпозиции можно рекурсивно найти пары ближайших точек в левом подмножестве S1 и в правом подмножестве S2.

Метод декомпозиции

Пусть d1 и d2 – наименьшие расстояния между парами точек в подмножествах S1 и S2, соответственно. Обозначим d = min{d1,d2}. К сожалению, d не обязательно представляет собой наименьшее расстояние между парами точек в S, поскольку пара точек с минимальным расстоянием между ними может лежать по разные стороны от разделяющей линии. Таким образом, этап комбинирования должен включать рассмотрение таких точек. Очевидно, что можно ограничиться рассмотрением точек, попадающих в вертикальную полосу шириной 2d, поскольку расстояние между любыми двумя парами точек по разные стороны от разделяющей линии < d.

Метод декомпозиции

Пусть C1 и C2 – подмножества точек в левой и правой части полосы, соответственно. Теперь для каждой точки P из C1 мы должны рассмотреть точки в C2, которые могут оказаться от точки P на расстоянии, меньшем d. Совершенно очевидно, что координаты y таких точек не могут выходить за пределы интервала [y - d, y + d]. Наиболее важным является то, что таких точек может быть не более шести, поскольку любая пара точек в C2 находится как минимум на расстоянии d друг от друга. Второе важное наблюдение заключается в том, что можно поддерживать списки точек в C1 и C2 отсортированными в порядке возрастания их координат y.

Метод декомпозиции

Кроме того, такой порядок можно поддерживать не путем пересортировки точек при каждой итерации, а слиянием двух ранее отсортированных списков. Можно рассматривать точки C1, в то время как указатель в список C2 будет выполнять осцилляции в пределах отрезка 2d, выбирая шесть кандидатов, для которых будут вычисляться расстояния до текущей точки P из списка C1. Время M(n), необходимое для «слияния» решений меньших подзадач, равно O(n). В результате рекуррентное соотношение для времени работы T(n) описанного алгоритма над n предварительно отсортированными точками имеет вид:

Метод декомпозиции

T(n) = 2*T(n/2) + M(n) Применяя Основную теорему, получаем (a=2, b=2, d=1), что T(n) Є Θ(n*log2n). Возможная необходимость предварительной сортировки точек не меняет класс эффективности алгоритма, поскольку может быть выполнена за время О(n*log2n). Мы получили алгоритм с наивысшим классом эффективности для данной задачи, т.к. можно доказать, что любой алгоритм для ее решения принадлежит к Ω(n*log2n). Можно показать, что метод грубой силы имеет сложность Θ(n²).

Метод декомпозиции

Пример. Поиск выпуклой оболочки. Выпуклая оболочка множества точек S представляет собой наименьшее выпуклое множество, содержащее S. Теорема. Выпуклая оболочка произвольного множества S, состоящего из n>2 точек (не лежащих на одной прямой), представляет собой выпуклый многоугольник с вершинами в некоторых точках S. Отрезок, соединяющий две точки Pi и Pj множества, состоящего из n точек, является частью границы выпуклой оболочки тогда и только тогда, когда все прочие точки лежат по одну сторону от прямой, проходящей через эти две точки.

Метод декомпозиции

Проверка каждой пары точек дает список из отрезков, которые составляют границу выпуклой оболочки. Эффективность данного алгоритма равна О(n³): для каждой из n*(n-1)/2 различных пар точек понадобится найти знаки выражений a*x+b*y+c для n-2 точек. Пусть множество из n точек отсортировано в возрастающем порядке по координате x, а в случае совпадения координаты x – в возрастающем порядке по координате y. Крайние точки должны принадлежать множеству вершин выпуклой оболочки. Прямая, соединяющая эти точки, делит множество точек на два подмножества S1 и S2.

Метод декомпозиции

Алгоритм быстрой оболочки, основанных на методе декомпозиции, имеет ту же эффективность, что и алгоритм быстрой сортировки: Θ(n*log2n) в среднем, и Θ(n²) – в наихудшем случае. Хотя это и выше эффективности алгоритма, основанного на грубой силе, имеются алгоритмы, имеющие сложность Θ(n*log2n) в наихудщем случае.