» » »

=7. Методика декомпозиции (Определение. Алгоритмы и задачи: сортировка слиянием, бинарный поиск, быстрая сортировка, задача о паре двух ближайших точек, задача о выпуклой оболочке)

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

Он же - метод «разделяй и властвуй»:
  • Экземпляр задачи разбивается на несколько меньших экземпляров той же задачи, в идеале — одинакового размера.

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

  • При необходимости решение исходной задачи находится путем комбинации решений меньших экземпляров.

Метод декомпозиции идеально подходит для параллельных вычислений. 

Рекуррентное уравнение декомпозиции

  • В общем случае экземпляр задачи размера n может быть разделен на несколько экземпляров размером n/b, а из которых требуется решить.

  • Обобщенное рекуррентное уравнение декомпозиции:

  • для упрощения принято, что размер n равен степени b.

  • Порядок роста зависит от a, b и f.

Основная теорема декомпозиции

  • Можно указать класс эффективности алгоритма, не решая само рекуррентное уравнение.

  • Этот подход позволяет установить порядок роста решения, не определяя неизвестные множители.

Сортировка слиянием

Алгоритм был пред­ло­жен Джо­ном фон Ней­ма­ном в 1945 го­ду.

Это устойчивый ал­го­ритм, использующий O(n) дополнительной памяти и O(n \log(n)) времени.

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

Бинарный поиск

Двоичный (бинарный) поиск (также известен как метод деления пополам и дихотомия) — классический алгоритм поиска элемента в отсортированном массиве (векторе), использующий дробление массива на половины.
Берем отсортированный массив, смотрим в середину, если не нашли там число, в зависимости от того, что в середине — ищем это число этим же методом либо в левой части, либо в правой, откидывая средний элемент. Для функций также, просто берем не массив, а функцию.

Быстрая сортировка

В отличие от сортировки слиянием, которая разделяет элементы массива в соответствии с иx положением в массиве, быстрая сортировка разделяет элементы массива в соответствии с их значениями. 

Описание алгоритма

  • Выбираем опорный элемент

  • Выполняем перестановку элементов для получения разбиения, когда все элементы до некоторой позиции s не превышают элемента A [s], а элементы после позиции s не меньше него.

  • Очевидно, что после разбиения A [s] находится в окончательной позиции, и мы можем сортировать два подмассива элементов до и после A [s] независимо (тем же или другим методом)

Эффективность быстрой сортировки

  • Наилучший случай: все разбиения оказываются посередине соответствующих подмассивов

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

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

Cavg = 2 n ln n = 1,38 n log2 n

Нахождение пары ближайших точек

Построим алгоритм по общей схеме алгоритмов разделяй-и-властвуй: алгоритм оформляем в виде рекурсивной функции, которой передаётся множество точек; эта рекурсивная функция разбивает это множество пополам, вызывает себя рекурсивно от каждой половины, а затем выполняет какие-то операции по объединению ответов. Операция объединения заключается в обнаружении случаев, когда одна точка оптимального решения попала в одну половину, а другая точка — в другую (в этом случае рекурсивные вызовы от каждой из половинок отдельно обнаружить эту пару, конечно, не смогут). Основная сложность, как всегда, заключается в эффективной реализации этой стадии объединения. Если рекурсивной функции передаётся множество из n точек, то стадия объединения должна работать не более, чем O(n), тогда асимптотика всего алгоритма T(n) будет находиться из уравнения:

T(n)

Решением этого уравнения, как известно, является T(n).

Итак, перейдём к построению алгоритма. Чтобы в будущем прийти к эффективной реализации стадии объединения, разбивать множество точек на два будем согласно их x-координатам: фактически мы проводим некоторую вертикальную прямую, разбивающую множество точек на два подмножества примерно одинаковых размеров. Такое разбиение удобно произвести следующим образом: отсортируем точки стандартно как пары чисел, т.е.:

p_i

Тогда возьмём среднюю после сортировки точку p_m (m), и все точки до неё и саму p_m отнесём к первой половине, а все точки после неё — ко второй половине:

A_1
A_2

Теперь, вызвавшись рекурсивно от каждого из множеств A_1 и A_2, мы найдём ответы h_1 и h_2 для каждой из половинок. Возьмём лучший из них: h.

Теперь нам надо произвести стадию объединения, т.е. попытаться обнаружить такие пары точек, расстояние между которыми меньше h, причём одна точка лежит в A_1, а другая — в A_2. Очевидно, что для этого достаточно рассматривать только те точки, которые отстоят от вертикальной прямой раздела не расстояние, меньшее h, т.е. множество B рассматриваемых на этой стадии точек равно:

B

Для каждой точки из множества B надо попытаться найти точки, находящиеся к ней ближе, чем h. Например, достаточно рассматривать только те точки, координата y которых отличается не более чем на h. Более того, не имеет смысла рассматривать те точки, у которых y-координата больше y-координаты текущей точки. Таким образом, для каждой точки p_i определим множество рассматриваемых точек C(p_i) следующим образом:

C(p_i)

Если мы отсортируем точки множества B по y-координате, то находить C(p_i) будет очень легко: это несколько точек подряд до точки p_i.

Итак, в новых обозначениях стадия объединения выглядит следующим образом: построить множество B, отсортировать в нём точки по y-координате, затем для каждой точки p_iрассмотреть все точки p_j, и каждой пары (p_i,p_j) посчитать расстояние и сравнить с текущим наилучшим расстоянием.

На первый взгляд, это по-прежнему неоптимальный алгоритм: кажется, что размеры множеств C(p_i) будут порядка n, и требуемая асимптотика никак не получится. Однако, как это ни удивительно, можно доказать, что размер каждого из множеств C(p_i) есть величина O(1), т.е. не превосходит некоторой малой константы вне зависимости от самих точек. Доказательство этого факта приведено в следующем разделе.

Наконец, обратим внимание на сортировки, которых вышеописанный алгоритм содержит сразу две: сначала сортировка по парам (x,y), а затем сортировка элементов множества B по y. На самом деле, от обеих этих сортировок внутри рекурсивной функции можно избавиться (иначе бы мы не достигли оценки O(n) для стадии объединения, и общая асимптотика алгоритма получилась бы O(n). От первой сортировки избавиться легко — достаточно предварительно, до запуска рекурсии, выполнить эту сортировку: ведь внутри рекурсии сами элементы не меняются, поэтому нет никакой необходимости выполнять сортировку заново. Со второй сортировкой чуть сложнее, выполнить её предварительно не получится. Зато, вспомнив сортировку слиянием (merge sort), которая тоже работает по принципу разделяй-и-властвуй, можно просто встроить эту сортировку в нашу рекурсию. Пусть рекурсия, принимая какое-то множество точек (как мы помним, упорядоченное по парам (x,y)) возвращает это же множество, но отсортированное уже по координате y. Для этого достаточно просто выполнить слияние (за O(n)) двух результатов, возвращённых рекурсивными вызовами. Тем самым получится отсортированное по y множество.

Чтобы показать, что вышеописанный алгоритм действительно выполняется за O(n, нам осталось доказать следующий факт: |C(p_i)|.

Итак, пусть мы рассматриваем какую-то точку p_i; напомним, что множество C(p_i) — это множество точек, y-координата которых лежит в отрезке [y_i-h;, а, кроме того, по координате x и сама точка p_i, и все точки множества C(p_i) лежат в полосе шириной 2h. Иными словами, рассматриваемые нами точки p_i и C(p_i) лежат в прямоугольнике размера 2h.

Наша задача — оценить максимальное количество точек, которое может лежать в этом прямоугольнике 2h; тем самым мы оценим и максимальный размер множества C(p_i). При этом при оценке надо не забывать, что могут встречаться повторяющиеся точки.

Вспомним, что h получалось как минимум из двух результатов рекурсивных вызовов — от множеств A_1 и A_2, причём A_1 содержит точки слева от линии раздела и частично на ней, A_2 — оставшиеся точки линии раздела и точки справа от неё. Для любой пары точек из A_1, равно как и из A_2, расстояние не может оказаться меньше h — иначе бы это означало некорректность работы рекурсивной функции.

Для оценки максимального количества точек в прямоугольнике 2h разобьём его на два квадрата h, к первому квадрату отнесём все точки C(p_i), а ко второму — все остальные, т.е. C(p_i). Из приведённых выше соображений следует, что в каждом из этих квадратов расстояние между любыми двумя точками не менее h.

Покажем, что в каждом квадрате не более четырёх точек. Например, это можно сделать следующим образом: разобьём квадрат на 4 подквадрата со сторонами h/2. Тогда в каждом из этих подквадратов не может быть больше одной точки (т.к. даже диагональ равна h, что меньше h). Следовательно, во всём квадрате не может быть более 4 точек.

Итак, мы доказали, что в прямоугольнике 2h не может быть больше 4 точек, а, следовательно, размер множества C(p_i) не может превосходить 7, что и требовалось доказать.

Задача о выпуклой оболочке

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

Выпуклая

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

два важных преимущества:

  • Время работы всегда O(nlogn)
  • Легко распараллеливается: множество точек делится на N частей, выпуклые оболочки которых вычисляются независимо, а затем быстро сливаются.

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.