首页 > 专题系列 > 经典问题 > 最接近点对问题[分治]
2014
04-15

最接近点对问题[分治]

问题描述

给定平面S上n个点,找其中的一对点,使得在n(n-1)/2 个点对中,该点对的距离最小。

这个问题出现在许多应用中。例如,在空中交通管制,您可能要监视飞机以免靠得太近而发生碰撞事故。两点间p和q的距离的公式:

分析

暴力的解决方法是O(n^2),计算每个点对间的距离,返回最小值。我们可以使用分治的策略降低复杂度。下面讨论的算法复杂度为 O(n (Logn)^2)

算法思路:

  1) n较小时直接求 (n=2).                                                         
  2) 将S上的n个点分成大致相等的2个子集S1和S2    
  3) 分别求S1和S2中的最接近点对
 4) 求一点在S1、另一点在S2中的最近点对
  5) 从上述三对点中找距离最近的一对.

仔细分析上面的过程,只有第4步有些困难,其它几个步骤只要递归下去就行了。看下面这个图,我们把点分成了左右两部分S1和S2,并且分别求得了最小距离为dl,dr。 令 d = min(dl,dr):

divide_points_new1

接下来要考虑的就是 两个端点分别在左右两部分中的点对。已经知道最小距离不会超过d。我们在拆分两部分的时候把 P [N/2] 作为中间点。做一条过P的垂直线,并找到所有距离垂直线距离在d以内的点,把这些点放在数组strip[] 中,如下图所示。其它点就可以不用考虑了。

strip_closesr1

接下来计算strip[]中的最小距离点对。按照y坐标排序,这一步需要O(nLogn)的复杂度,其实可以 通过递归和归并优化到O(n)。由于已经排序,我们可以再O(n)内找到最小距离点对d3(这里其实需要一些几何知识来证明,参考:http://people.csail.mit.edu/indyk/6.838-old/handouts/lec17.pdf)。

C语言实现:

// 分治法解决最小点对问题
#include <stdio.h>
#include <float.h>
#include <stdlib.h>
#include <math.h>
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)
               );
}

// 暴力方法找到最小的点对
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就是min(dl,dr) 这个是上限。
//就是上面的第4步。找出 strip[] 数组中的最小点对。看似复杂度O(n^2)
//实际上O(n),因为内层循环最多执行6次。
float stripClosest(Point strip[], int size, float d)
{
    float min = d; 
    qsort(strip, size, sizeof(Point), compareY); 
    // 可以证明这个循环最多执行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;
}

//递归的计算最小点对
float closestUtil(Point P[], int n)
{
    // 如果点较少,用暴力解决
    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++;

    // 找出strip 数组中的最小点对
    return min(d, stripClosest(strip, j, d) );
}

float closest(Point P[], int n)
{
    qsort(P, n, sizeof(Point), compareX);
    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

时间复杂度

在上面分成两部分后,需要找到 strip[] 数组,需要的时间为O(n),排序strip[]的时间为 O(nLogn),在strip[] 在找到最小点对的时间为 O(n)。

总时间 T(n) =  2T(n/2) + O(n) + O(nLogn) + O(n)

T(n) = 2T(n/2) + O(nLogn)
T(n) = T(n x Logn x Logn)

即复杂度为  O(n (Logn)^2)

参考:http://www.geeksforgeeks.org/closest-pair-of-points/


  1. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  2. Often We don’t set up on weblogs, but I would like to condition that this established up really forced me individually to do this! considerably outstanding publish

  3. 学算法中的数据结构学到一定程度会乐此不疲的,比如其中的2-3树,类似的红黑树,我甚至可以自己写个逻辑文件系统结构来。