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

Начнем с определения некоторых обозначений. Имеется множество точек P = {pv ...,

pn}, в котором точка p. имеет координаты (x, у); для двух точек p ,, p. р стандартное

евклидово расстояние между ними будет обозначаться d(p , p.).

Наша цель — найти

i.

пару точекp,p, минимизирующую d(p,p).

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

Будет полезно рассмотреть одномерную версию этой задачи — она намного проще, а результаты показательны. Как найти ближайшую пару точек на прямой? Нужно сначала отсортировать точки за время O(n log n), а затем перебрать отсо- ртированный список с вычислением расстояния от каждой точки до следующей. Понятно, что одно из этих расстояний должно быть минимальным.

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

Вместо этого будет применена стратегия в стиле «разделяй и властвуй», ис- пользованная в сортировке слиянием: мы находим ближайшую пару среди точек в «левой половине» P и ближайшую пару среди точек в «правой половине» P, после чего эта информация используется для получения общего решения за линейное время. Если разработать алгоритм с такой структурой, то решение базового рекур- рентного отношения из (5.1) обеспечит время выполнения O(n log n).

Сложности возникают в последней, «объединяющей» фазе алгоритма: ни один из рекурсивных вызовов не рассматривает расстояния между точкой из левой и точкой из правой половины; всего таких расстояний Ω(n2), но мы должны найти наименьшее из них за время O(n) после завершения рекурсивных вызовов. Если это удастся сделать, то решение будет завершено: результатом становится меньшее из значений, вычисленных в ходе рекурсивных вызовов, и минимального рассто- яния между точками из левой и правой половин.

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

Еще по теме Разработка алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Разработка Плана
  13. 2.7. Разработка анкеты
  14. 6. Разработка перспектив
  15. Разработка и принятие Основного закона