Нахождение ближайшей пары точек: рандомизированный метод - Рандомизированные алгоритмы

В главе 5 метод “разделяй и властвуй” использовался для разработки алгоритма нахождения ближайшей пары точек на плоскости за время O(n log n). Сейчас вы увидите, как на основе рандомизации создать другой алгоритм для этой задачи на базе структуры данных словаря. Мы покажем, что этот алгоритм выполняется за ожидаемое время O(n) плюс O(n) ожидаемых операций со словарем.

Есть несколько причин, по которым время выполнения алгоритма удобно представлять именно так — с отдельным учетом операций со словарем. В разделе 13.6 было показано, что словари имеют очень эффективную реализацию на базе хеширования, поэтому абстрагирование операций со словарем позволяет рассматривать хеширование как своего рода “черный ящик”, с которым общее время выполнения алгоритма определяется гарантиями быстродействия, предоставленными процедурой хеширования. Было показано, что при правильном выборе процедуры хеширования (более мощной и более сложной, чем описанная в разделе 13.6) можно обеспечить выполнение операций со словарем за линейное время, в результате чего общее время выполнения также станет равно O(n). Таким образом, рандомизированное решение приводит к улучшению по сравнению с временем выполнения алгоритма “разделяй и властвуй”, приведенного выше. Идеи, приводящие к этой границе O(n), кратко описаны в конце раздела.

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

Задача

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

Воспользуемся той же записью, которая уже применялась в предшествующем обсуждении задачи о ближайшей паре. Множество точек обозначается P = {p₁, ..., p_n}, точка p_i имеет координаты (x_i, у_i); для двух точек p_i, p_j ∈ P метрика d(p_i, p_j) обозначает стандартное евклидово расстояние между ними. Требуется найти пару точек p_i, p_j, минимизирующую d(p_i, p_j).

Для упрощения анализа будем считать, что все точки лежат в границах единичного квадрата: 0 ≤ x_i, y_i ≤ 1 для всех i = 1, ..., n. Никакой потери общности при этом нет: за линейное время координаты x и у всех точек можно масштабировать так, чтобы они размещались в единичном квадрате, а затем сместить их так, чтобы левый нижний угол квадрата совпадал с началом координат.

Разработка алгоритма

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

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

Для простоты будем считать, что точки в случайном порядке обозначаются р₁, ..., р_n. Работа алгоритма разделена на этапы; на каждом этапе ближайшая пара остается неизменной. Первый этап начинается с присваивания δ = С(р₁, р₂) — расстояния между первыми двумя точками. На этом этапе алгоритм либо убеждается в том, что δ действительно является расстоянием между ближайшей парой точек, либо находит пару точек р_i, р_j на расстоянии d(р_i, р_j) < δ. Во время этого этапа в порядок р₁, р₂, ..., р_n последовательно добавляются точки. Этап завершается при достижении такой точки р_i, что для некоторого j < i выполняется d(р_i, р_j) < δ. Тогда δ становится ближайшим расстоянием, найденным к текущему моменту, для следующего этапа: δ = min_j:_j<_i<d(р_i, р_j).

Количество этапов зависит от случайного порядка. Если нам повезет и р₁, р₂ образуют ближайшую пару точек, то хватит одного этапа. Также количество этапов может достигнуть n - 2, если добавление новой точки всегда приводит к увеличению минимального расстояния. Мы покажем, что ожидаемое время выполнения алгоритма лежит в пределах постоянного множителя от времени, необходимого в первом (счастливом) случае, когда исходное значение δ оказывается наименьшим расстоянием.

Проверка предлагаемого расстояния

Основная часть алгоритма — метод, который проверяет, остается ли текущая пара точек с расстоянием δ ближайшей парой при добавлении новой точки, и если нет — находит новую ближайшую пару.

Проверка реализуется делением единичного квадрата (область, в пределах которой лежат точки) на подквадраты, стороны которых имеют длину δ/2, как показано на рис. 13.2. Всего будет N²подквадратов, где N = [1/(2δ)]: для 0 ≤ s ≤ N - 1 и 1 ≤ t ≤ N - 1 подквадрат S_st определяется по формуле

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

Рис. 13.2. Разбиение квадрата на подквадраты δ/2. Точкаp находится в подквадрате S_st

(13.26) Если две точки p и q принадлежат одному подквадрату S_st, то d(p, q) < δ.

Доказательство. Если точки p и q находятся в одном подквадрате, то обе координаты двух точек отличаются не более чем на δ/2, а следовательно, как и требуется. ■

Подквадраты S_st и S_s'_t' называются близкими, если (Обратите внимание: каждый подквадрат близок к самому себе.)

(13.27) Если для двух точек p, q ∈ P выполняется d(p, q) < δ, то подквадраты, содержащие эти точки, являются близкими.

Доказательство. Рассмотрим две точки p, q ∈ P, принадлежащие подквадратам, которые не являются близкими; будем считать, что p ∈ S_st и q ∈ S_s'_t', где одна из пар s, s' или t, t' отличается более чем на 2. Следовательно, в одной из соответствующих координат х или у значения p и q отличаются не менее чем на δ, поэтому условие d(p, q) < δ выполняться не может. ■

Обратите внимание: для любого подквадрата S_st множество подквадратов, близких к нему, образует вокруг него сетку 5 х 5. Из этого следует, что у S_st может быть не более 25 близких подквадратов, включая сам подквадрат S_st. (Если S_st прилегает к ребру единичного квадрата, содержащему входные точки, их будет меньше 25.)

Утверждения (13.26) и (13.27) подсказывают базовую структуру алгоритма. Предположим, в какой-то точке алгоритма случайная последовательность точек была частично обработана вплоть до P' ⊆ P и минимальное расстояние между точками в P' равно δ. Для каждой из точек в P' сохраняется содержащий ее подквадрат.

Затем при рассмотрении следующей точки p мы определяем, какому из подквадратов S_st она принадлежит. Если p приведет к изменению минимального расстояния, должна существовать некоторая более ранняя точка р' ∈ P' на расстоянии менее δ от нее; следовательно, из (13.27) следует, что точка р' должна принадлежать одному из 25 квадратов вокруг квадрата S, содержащего р. Соответственно мы просто проверяем каждый из 25 квадратов, содержит ли он точку в P'; для каждой точки из P', найденной при этом, вычисляется расстояние от нее до р. Согласно (13.26), каждый из этих подквадратов содержит не более одной точки из P', поэтому это потребует не более чем постоянного количества вычислений расстояния. (Кстати, похожая идея использовалась в критической точке алгоритма “разделяй и властвуй” (5.10) из главы 5.)

Структура данных для хранения подквадратов

Высокоуровневое описание алгоритма зависит от возможности назвать подквадрат S_st и быстро определить, какие точки P содержатся в нем (если они есть). Словарь — наиболее естественная структура данных для реализации таких операций. Универсальное множество U возможных элементов представляет собой множество всех подквадратов, а множество S, хранимое в структуре данных, состоит из подквадратов с точками из множества P', встречавшимися до настоящего момента. А конкретно, для каждой точки р' ∈ Р' в словаре хранится подквадрат, содержащий ее, вместе с индексом р'. Заметим, что N² = [1/(2δ)]² в общем случае намного больше количества точек n. Таким образом, данная ситуация напоминает ту, что была описана в разделе 13.6 для хеширования: универсальное множество возможных элементов (множество всех подквадратов) намного больше количества индексируемых элементов (подквадраты, содержащие входные точки, которые уже встречались).

Затем, при рассмотрении следующей точки р в случайном порядке, определяется содержащий ее подквадрат S_st и выполняется операция Lookup для каждого из 25 подквадратов, близких к S_st. Для всех точек, обнаруженных этими операциями Lookup, вычисляется расстояние до р. Если ни одно из этих расстояний не меньше δ, то ближайшее расстояние не изменяется; мы вставляем S_st (вместе c р) в словарь и переходим к следующей точке.

Но если будет найдена точка р', для которой δ' = d(р, р') < δ, то ближайшую пару необходимо обновить. Обновление приводит к весьма масштабным последствиям: так как расстояние ближайшей пары уменьшилось с δ до δ', вся коллекция подквадратов вместе с поддерживающим ее словарем становится бесполезной — ведь она приносит пользу только в том случае, если минимальное расстояние равно δ. Соответственно мы вызываем MakeDictionary для создания нового, пустого словаря, в котором хранятся подквадраты с длиной стороны δ'/2. Для каждой точки, встреченной до настоящего момента, мы определяем содержащий ее подквадрат (в новом наборе подквадратов), после чего вставляем этот подквадрат в словарь. После того как это будет сделано, можно переходить к вставке следующей точки в случайном порядке.

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

Итак, мы полностью разобрали принцип работы алгоритма.

Анализ алгоритма

Даже сейчас можно кое-что сказать об общем времени выполнения алгоритма. Чтобы рассмотреть новую точку p_i, необходимо выполнить постоянное количество операций Lookup и постоянное количество вычислений расстояния. Более того, даже если бы ближайшую пару пришлось обновлять при каждой итерации, всего пришлось бы выполнить n операций MakeDictionary.

Недостающим ингредиентом является общая ожидаемая стоимость выполнения алгоритма, обусловленная повторными вставками в новые словари при обновлении ближайшей пары. Этот вопрос будет рассмотрен ниже, а пока сформулируем ту информацию, которой владеем на данный момент.

(13.28) Алгоритм корректно поддерживает информацию ближайшей пары и выполняет не более O(n) вычислений расстояния, O(n) операций Lookup и O(n) операций MakeDictionary.

В завершение анализа определим границу ожидаемого количества операций Insert. Попытка найти хорошую границу для общего ожидаемого количества операций Insert на первый взгляд создает немало проблем: обновление ближайшей пары в итерации i приведет к i вставкам, и каждое обновление будет обходиться недешево при больших i. Несмотря на это, мы продемонстрируем удивительный факт: ожидаемое количество вставок равно всего O(n). Это объясняется тем, что наряду с ростом стоимости обновлений сама вероятность таких обновлений снижается соответствующим образом.

Пусть X — случайная переменная, определяющая количество выполняемых операций Insert; значение этой случайной переменной определяется случайным порядком, выбранным изначально. Нас интересует граница E[X], и как обычно в подобных ситуациях, X будет полезно разбить на сумму более простых случайных переменных. При этом случайная переменная X_i равна 1, если i-я точка в случайном порядке приводит к изменению минимального расстояния, и 0 в противном случае.

Используя случайные переменные X_i, можно записать простую формулу для общего количества операций Insert. Каждая точка вставляется один раз при первом обнаружении; i точек придется вставить заново, если минимальное расстояние изменяется в итерации i. Это позволяет сделать следующее утверждение:

(13.29) Общее количество операций Insert, выполняемых алгоритмом, равно

Ограничим вероятность Pr[X_i = 1] того, что рассмотрение i-й точки приводит к изменению минимального расстояния.

(13.30) Рr[X_i = 1] ≤ 2/i.

Доказательство. Рассмотрим первые i точек p₁, p₂, ..., p_i в случайном порядке. Предположим, минимальное расстояние между этими точками достигается для p и q. Теперь точка р_i может привести к уменьшению минимального расстояния только в том случае, если p_i = p или p_i = q. Так как первые i точек следуют в случайном порядке, все они с равной вероятностью могут оказаться последними, так что вероятность того, что последней точкой окажется p или q, равна 2/i. ■

Заметим, что 2/i в (13.30) является только верхней границей, потому что среди первых i точек может встретиться несколько пар, определяющих одно наименьшее расстояние. Из (13.29) и (13.30) следует, что общее количество операций Insert ограничивается выражением

Объединяя это выражение с (13.28), получаем следующую границу для времени выполнения алгоритма:

(13.31) Ожидаемое время выполнения рандомизированного алгоритма нахождения ближайшей пары составляет O(n) плюс O(n) операций со словарем.

Достижение линейного ожидаемого времени выполнения

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

Для реализации словаря будет использоваться универсальная схема хеширования наподобие описанной в разделе 13.6. После того как алгоритм применит схему хеширования, случайность используется в нем двумя разными способами: во-первых, добавляемые точки располагаются в случайном порядке; во-вторых, для каждого нового минимального расстояния δ рандомизация применяется для создания новой хеш-таблицы с использованием универсальной схемы хеширования.

При вставке новой точки р_i алгоритм использует операцию хеш-таблицы Lookup для нахождения всех узлов в 25 подквадратах, близких к р_i. Однако если в хеш-таблице присутствуют коллизии, то эти 25 операций могут потребовать проверки много более чем 25 узлов. Утверждение (13.23) из раздела 13.6 показывает, что каждая операция Lookup требует проверки O(1) ранее вставленных точек (в ожидании). Интуитивно понятно, что выполнение в ожидании O(n) операций с хеш-таблицей, в каждой из которых задействована проверка в ожидании O(1) элементов, приведет к ожидаемому общему времени выполнения O(n). Чтобы точно выразить это интуитивное представление, необходимо внимательно проследить за тем, как взаимодействуют эти два источника случайности.

(13.32) Допустим, рандомизированный алгоритм нахождения ближайшей пары был реализован с применением универсальной схемы хеширования. В ожидании общее количество точек, рассматриваемых во время операций Lookup, имеет границу O(n).

Доказательство. Из (13.31) мы знаем, что ожидаемое количество операций Lookup равно O(n), а из (13.23) — что каждая из этих операций требует рассмотрения в ожидании всего O(1) точек. Чтобы сделать вывод о том, что ожидаемое количество рассматриваемых точек равно O(n), мы проанализируем связь между этими двумя источниками случайности.

Пусть X — случайная переменная для обозначения количества операций Lookup, выполненных алгоритмом. Случайный порядок σ, выбранный алгоритмом, полностью определяет последовательность значений минимального расстояния, рассматриваемую алгоритмом, и последовательность выполняемых операций со словарем. В результате выбор σ определяет значение X; обозначим это значение Х(σ), а E_σ — событие выбора алгоритмом случайного порядка с. Заметим, что условное ожидание E[X | E_σ] равно Х(σ). Кроме того, из (13.31) известно, что E[Х] ≤ с₀nдля некоторой константы с₀.

Теперь рассмотрим эту последовательность операций Lookup для фиксированного порядка σ. Для i = 1, ..., Х(σ) обозначим Y_i количество точек, которые должны быть проверены при выполнении -х операций Lookup, а именно количество ранее вставленных точек, образующих коллизию с элементом словаря, задействованным в текущей операции Lookup. Нам хотелось бы ограничить ожидаемое значение с ожиданием как по случайному выбору σ, так и по случайному выбору хеш-функции.

Из (13.23) известно, что E[Y_i | E_σ] = O(1) для всех с и всех значений i. Полезно иметь возможность ссылаться на константу в выражении O(1), поэтому мы будем говорить, что E[Y_i | E_σ] ≤ с₁ для всех σ и всех значений i. Суммируя по всем i и используя линейность ожидания, получаем В итоге получаем:

Так как мы знаем, что E[X] не более c₀n, общее ожидаемое количество рассматриваемых точек не превышает c₀c₁n = O(n), что доказывает утверждение. ■

Вооружившись этим утверждением, мы сможем использовать универсальные хеш-функции из раздела 13.6 в алгоритме нахождения ближайшей пары. В ожидании алгоритм будет рассматривать O(n) точек в ходе операций Lookup. Потребуется создать несколько хеш-таблиц (новая таблица создается при каждом изменении минимального расстояния) и вычислить O(n) значений хеш-функции. Все хеш-таблицы создаются с одним размером, простым числом p ≥ n. Мы можем выбрать одно простое число и использовать одну таблицу на протяжении всей работы алгоритма. В этом случае для времени выполнения будет получена следующая граница.

(13.33) В ожидании алгоритм использует для нахождения ближайшей пары точек O(n) вычислений хеш-функции и дополнительное время O(n).

Обратите внимание на отличие этого утверждения от (13.31). Тогда каждая операция со словарем считалась одним атомарным шагом; здесь, напротив, операции со словарем концептуально открыты, чтобы учесть время, связанное с коллизиями в хеш-таблицах и вычислениями хеш-функции.

Наконец, рассмотрим время, необходимое для O(n) вычислений хеш-функции. Сколько времени займет вычисление значения универсальной хеш-функции h? Класс универсальных хеш-функций, разработанных в разделе 13.6, разбивает числа универсального множества U на r ≈ log N/ log n меньших чисел с размером O(log n) каждое и затем использует O(r) арифметических операций с меньшими числами для вычисления значения хеш-функции. Итак, в вычислении хеша для одной точки задействовано O(log N/ log n) умножений чисел с размером log n. В сумме получаем O(n log N/ log n) арифметических операций в ходе выполнения алгоритма — больше величины O(n), на которую мы рассчитывали.

На самом деле количество арифметических операций можно уменьшить до O(n) при использовании более сложного класса хеш-функций. Существуют другие классы универсальных хеш-функций, для которых вычисление значения хеш-функции выполняется за O(1) арифметических операций (хотя эти операции выполняются с большими числами — целыми с размером приблизительно log N). Этот класс улучшенных хеш-функций также создает одну дополнительную сложность в данном случае: схеме хеширования необходимо простое число, превышающее размер универсального множества (вместо размера множества точек). А в этом приложении универсальное множество растет в обратной зависимости от минимального расстояния δ, и в частности возрастает каждый раз, когда обнаруживается новое, меньшее минимальное расстояние. В таких точках приходится искать новое простое число и создавать новую хеш-таблицу. И хотя мы не будем вдаваться в подробности, с этими трудностями можно справиться и привести алгоритм к ожидаемому времени выполнения O(n).