Рубрики

Ближайшая пара очков | O (nlogn) Реализация

Нам дан массив из n точек на плоскости, и задача состоит в том, чтобы найти ближайшую пару точек в массиве. Эта проблема возникает в ряде приложений. Например, при управлении воздушным движением вы можете отслеживать самолеты, которые находятся слишком близко друг к другу, поскольку это может указывать на возможное столкновение. Напомним следующую формулу для расстояния между двумя точками p и q.

Мы обсудили решение «разделяй и властвуй» для этой проблемы. Временная сложность реализации, представленная в предыдущем посте, составляет O (n (Logn) ^ 2). В этом посте мы обсуждаем реализацию со сложностью времени как O (nLogn).

Ниже приведено резюме алгоритма, рассмотренного в предыдущем посте.

1) Сортируем все точки по x координатам.

2) Разделите все точки на две половины.

3) Рекурсивно найти наименьшее расстояние в обоих подмассивах.

4) Возьмите минимум два наименьших расстояния. Пусть минимум будет d.

5) Создайте массив полос [], в котором хранятся все точки, которые находятся на расстоянии не более d от средней линии, разделяющей два набора.

6) Найдите наименьшее расстояние в полосе [].

7) Верните минимум d и наименьшее расстояние, рассчитанное на шаге 6 выше.

Самое замечательное в вышеупомянутом подходе состоит в том, что если массив strip [] отсортирован по координате y, то мы можем найти наименьшее расстояние в strip [] за O (n) время. В реализации, обсуждавшейся в предыдущем посте, strip [] явно сортировалась в каждом рекурсивном вызове, что делало сложность времени O (n (Logn) ^ 2), предполагая, что шаг сортировки занимает время O (nLogn).
В этом посте мы обсудим реализацию, где сложность времени равна O (nLogn). Идея состоит в том, чтобы предварительно отсортировать все точки по y координатам. Пусть отсортированный массив будет Py []. Когда мы делаем рекурсивные вызовы, нам нужно разделить точки Py [] также по вертикальной линии. Мы можем сделать это, просто обработав каждую точку и сравнив ее координату х с координатой х средней линии.

Ниже приведена реализация O (nLogn) в C ++.

// Программа «разделяй и властвуй» на C ++, чтобы найти наименьшее расстояние от
// заданный набор точек.

  
#include <iostream>
#include <float.h>
#include <stdlib.h>
#include <math.h>

using namespace std;

  
// Структура для представления точки в 2D плоскости

struct Point

{

    int x, y;

};

  

  
/ * Следующие две функции необходимы для библиотечной функции qsort ().

   См. Http://www.cplusplus.com/reference/clibrary/cstdlib/qsort/ * /

  
// Нужно отсортировать массив точек по координате X

int compareX(const void* a, const void* b)

{

    Point *p1 = (Point *)a,  *p2 = (Point *)b;

    return (p1->x - p2->x);

}
// Нужно отсортировать массив точек по координате Y

int compareY(const void* a, const void* b)

{

    Point *p1 = (Point *)a,   *p2 = (Point *)b;

    return (p1->y - p2->y);

}

  
// Полезная функция для определения расстояния между двумя точками

float dist(Point p1, Point p2)

{

    return sqrt( (p1.x - p2.x)*(p1.x - p2.x) +

                 (p1.y - p2.y)*(p1.y - p2.y)

               );

}

  
// Метод грубой силы, чтобы вернуть наименьшее расстояние между двумя точками
// в P [] размера n

float bruteForce(Point P[], int n)

{

    float min = FLT_MAX;

    for (int i = 0; i < n; ++i)

        for (int j = i+1; j < n; ++j)

            if (dist(P[i], P[j]) < min)

                min = dist(P[i], P[j]);

    return min;

}

  
// Утилита для поиска минимум двух значений с плавающей запятой

float min(float x, float y)

{

    return (x < y)? x : y;

}

  

  
// Полезная функция для определения расстояния между ближайшими точками
// полоса заданного размера. Все точки в полосе [] отсортированы по
// координата у. Все они имеют верхнюю границу минимального расстояния как d.
// Обратите внимание, что этот метод выглядит как метод O (n ^ 2), но это O (n)
// метод, поскольку внутренний цикл выполняется не более 6 раз

float stripClosest(Point strip[], int size, float d)

{

    float min = d;  // Инициализируем минимальное расстояние как d

  

    // Собираем все точки по одной и пробуем следующие до разницы

    // между координатами y меньше, чем d.

    // Это доказанный факт, что этот цикл выполняется не более 6 раз

    for (int i = 0; i < size; ++i)

        for (int j = i+1; j < size && (strip[j].y - strip[i].y) < min; ++j)

            if (dist(strip[i],strip[j]) < min)

                min = dist(strip[i], strip[j]);

  

    return min;

}

  
// Рекурсивная функция для наименьшего расстояния. Массив Px содержит
// все точки отсортированы по x координатам, а Py содержит все точки
// отсортировано по координатам y

float closestUtil(Point Px[], Point Py[], int n)

{

    // Если есть 2 или 3 очка, то используйте грубую силу

    if (n <= 3)

        return bruteForce(Px, n);

  

    // Найти среднюю точку

    int mid = n/2;

    Point midPoint = Px[mid];

  

  

    // Делим точки в отсортированном по y массиве вокруг вертикальной линии.

    // Предположение: все координаты х различны.

    Point Pyl[mid+1];   // y отсортированные точки слева от вертикальной линии

    Point Pyr[n-mid-1];  // y отсортированные точки справа от вертикальной линии

    int li = 0, ri = 0;  // индексы левого и правого подмассивов

    for (int i = 0; i < n; i++)

    {

      if (Py[i].x <= midPoint.x)

         Pyl[li++] = Py[i];

      else

         Pyr[ri++] = Py[i];

    }

  

    // Рассмотрим вертикальную линию, проходящую через среднюю точку

    // вычисляем наименьшее расстояние dl слева от средней точки и

    // доктор на правой стороне

    float dl = closestUtil(Px, Pyl, mid);

    float dr = closestUtil(Px + mid, Pyr, n-mid);

  

    // Находим меньшее из двух расстояний

    float d = min(dl, dr);

  

    // Построить массив полос [], который содержит точки близко (ближе, чем d)

    // к линии, проходящей через среднюю точку

    Point strip[n];

    int j = 0;

    for (int i = 0; i < n; i++)

        if (abs(Py[i].x - midPoint.x) < d)

            strip[j] = Py[i], j++;

  

    // Находим ближайшие точки в полосе. Вернуть минимум d и ближайший

    // расстояние - полоса []

    return min(d, stripClosest(strip, j, d) );

}

  
// Основная функция, которая находит наименьшее расстояние
// Этот метод в основном использует closestUtil ()

float closest(Point P[], int n)

{

    Point Px[n];

    Point Py[n];

    for (int i = 0; i < n; i++)

    {

        Px[i] = P[i];

        Py[i] = P[i];

    }

  

    qsort(Px, n, sizeof(Point), compareX);

    qsort(Py, n, sizeof(Point), compareY);

  

    // Используем рекурсивную функцию closestUtil (), чтобы найти наименьшее расстояние

    return closestUtil(Px, Py, n);

}

  
// Программа драйвера для проверки вышеуказанных функций

int main()

{

    Point P[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};

    int n = sizeof(P) / sizeof(P[0]);

    cout << "The smallest distance is " << closest(P, n);

    return 0;

}

Выход:

The smallest distance is 1.41421

Сложность по времени: пусть сложность по времени вышеупомянутого алгоритма равна T (n). Предположим, что мы используем алгоритм сортировки O (nLogn). Вышеприведенный алгоритм делит все точки на два набора и рекурсивно вызывает два набора. После деления он находит полосу за O (n) раз. Кроме того, требуется O (n) время, чтобы разделить массив Py вокруг средней вертикальной линии. Наконец находит самые близкие точки в полосе за O (n) времени. Таким образом, T (n) можно выразить следующим образом
T (n) = 2T (n / 2) + O (n) + O (n) + O (n)
T (n) = 2T (n / 2) + O (n)
T (n) = T (nLogn)

Ссылки:
http://www.cs.umd.edu/class/fall2013/cmsc451/Lects/lect10.pdf
http://www.youtube.com/watch?v=vS4Zn1a9KUc
http://www.youtube.com/watch?v=T3T7T8Ym20M
http://en.wikipedia.org/wiki/Closest_pair_of_points_problem

Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой теме

Рекомендуемые посты:

Ближайшая пара очков | O (nlogn) Реализация

0.00 (0%) 0 votes