Рубрики

Ближайшая пара точек с использованием алгоритма «разделяй и властвуй»

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

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

Алгоритм
Ниже приведены подробные шаги алгоритма O (n (Logn) ^ 2).
Ввод: массив из n точек P []
Выход: Наименьшее расстояние между двумя точками в данном массиве.

На этапе предварительной обработки входной массив сортируется в соответствии с координатами x.

1) Найти среднюю точку в отсортированном массиве, мы можем взять P [n / 2] в качестве средней точки.

2) Разделите данный массив на две половины. Первый подмассив содержит точки от P [0] до P [n / 2]. Второй подмассив содержит точки от P [n / 2 + 1] до P [n-1].

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

4) Из вышеуказанных 3 шагов мы получаем верхнюю границу d минимального расстояния. Теперь нам нужно рассмотреть пары так, чтобы одна точка в паре была от левой половины, а другая — от правой. Рассмотрим вертикальную линию, проходящую через P [n / 2], и найдите все точки, координата x которых ближе, чем d к средней вертикальной линии. Создайте массив полос [] из всех таких точек.

5) Сортируйте массив полос [] по координатам y. Этот шаг O (nLogn). Его можно оптимизировать до O (n) путем рекурсивной сортировки и слияния.

6) Найдите наименьшее расстояние в полосе []. Это сложно. На первый взгляд это кажется шагом O (n ^ 2), но на самом деле это O (n). Геометрически можно доказать, что для каждой точки в полосе нам нужно проверять не более 7 точек после нее (обратите внимание, что полоса сортируется по координате Y). Смотрите это для дополнительного анализа.

7) Наконец, верните минимум d и расстояние, рассчитанное на предыдущем шаге (шаг 6)

Реализация
Ниже приведена реализация C / C ++ вышеупомянутого алгоритма.

C ++

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

  
#include <bits/stdc++.h>

using namespace std;

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

class Point 

    public:

    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

  

    qsort(strip, size, sizeof(Point), compareY); 

  

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

    // между координатами 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; 

  
// Рекурсивная функция для поиска
// наименьшее расстояние. Массив P содержит
// все точки отсортированы по координате х

float closestUtil(Point P[], int n) 

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

    if (n <= 3) 

        return bruteForce(P, n); 

  

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

    int mid = n/2; 

    Point midPoint = P[mid]; 

  

    // Рассмотрим прохождение вертикальной линии

    // через среднюю точку вычисляем

    // наименьшее расстояние дл слева

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

    float dl = closestUtil(P, mid); 

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

  

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

    float d = min(dl, dr); 

  

    // Создаем массив полос [], который содержит

    // точки близко (ближе чем d)

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

    Point strip[n]; 

    int j = 0; 

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

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

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

  

    // Находим ближайшие точки в полосе.

    // Возвращаем минимум d и ближайший

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

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

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

float closest(Point P[], int n) 

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

  

    // Используем рекурсивную функцию closestUtil ()

    // найти наименьшее расстояние

    return closestUtil(P, 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; 

  
// Это код, предоставленный rathbhupendra

С

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

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

  
// Структура для представления точки в 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

  

    qsort(strip, size, sizeof(Point), compareY); 

  

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

    // между координатами 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;

}

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

float closestUtil(Point P[], int n)

{

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

    if (n <= 3)

        return bruteForce(P, n);

  

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

    int mid = n/2;

    Point midPoint = P[mid];

  

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

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

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

    float dl = closestUtil(P, mid);

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

  

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

    float d = min(dl, dr);

  

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

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

    Point strip[n];

    int j = 0;

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

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

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

  

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

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

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

}

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

float closest(Point P[], int n)

{

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

  

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

    return closestUtil(P, n);

}

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

int main()

{

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

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

    printf("The smallest distance is %f ", closest(P, n));

    return 0;

}


Выход:

The smallest distance is 1.414214

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

Примечания
1) временная сложность может быть улучшена до O (nLogn) путем оптимизации шага 5 вышеприведенного алгоритма. Скоро мы обсудим оптимизированное решение в отдельном посте.
2) Код находит наименьшее расстояние. Его можно легко изменить, чтобы найти точки с наименьшим расстоянием.
3) Код использует быструю сортировку, которая в худшем случае может быть O (n ^ 2). Чтобы иметь верхнюю границу как O (n (Logn) ^ 2), можно использовать алгоритм сортировки O (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

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

Ближайшая пара точек с использованием алгоритма «разделяй и властвуй»

0.00 (0%) 0 votes