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

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

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

Для простоты будем считать, что точки в случайном порядке обозначаются pp ..., pn. Работа алгоритма разделена на этапы; на каждом этапе ближайшая пара остается неизменной. Первый этап начинается с присваивания δ = d(pv p2) — рас- стояния между первыми двумя точками. На этом этапе алгоритм либо убеждается в том, что δ действительно является расстоянием между ближайшей парой точек, либо находит пару точек р ,, р_ на расстоянии d(р ,, р) < δ. Во время этого этапа в порядокрt2, ...,рn последовательно добавляются точки. Этап завершается при достижении такой точки р ., что для некоторого j < i выполняется d(р ,, р) < δ. Тогда δ становится ближайшим расстоянием, найденным к текущему моменту, для сле- дующего этапа: δ = min :.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. Разработка анкеты