编程实现最近点对算法(暴力与分治对比)

题目要求

1. 随机生成1000/10000个随机坐标点
2. 比较Brute-force法和分治法的计算效率

   算法分析

   算法主要的思想为分治方法
3. 情况1：点数小于等于二时：直接计算，求该两点之间的距离。
4. 情况2：集合中有三个点：两两比较，求三个点中的最近的两个点距离。
5. 情况3：点数大于三时：首先划分集合S为SL和SR，使得SL中的每一个点位于SR中每一个点的左边，并且SL和SR中点数相同。分别在SL和SR中解决最近点对问题，得到DL和DR，分别表示SL和SR中的最近点对的距离。令d=min(DL,DR)。如果S中的最近点对(P1,P2)。P1、P2两点一个在SL和一个在SR中，那么P1和P2一定在以L为中心的间隙内，以L-d和L+d为界。
   

算法流程

如果在SL中的点P和在SR中的点Q成为最近点对，那么P和Q的距离必定小于d。因此对间隙中的每一个点，在合并步骤中，只需要检验yp+d和yp-d内的点即可。
步骤1：根据点的y值和x值对S中的点排序。
步骤2：找出中线L将S划分为SL和SR
步骤3：将步骤2递归的应用解决SL和SR的最近点对问题，并令d=min(dL,dR)。
步骤4：将L-dL+d内的点以y值排序，对于每一个点(x1,y1)找出y值在y1-dy1+d内的接下来的7个点，计算距离为d’。如果d’小于d，令d=d’，最后的d值就是答案。

核心代码

// brute-force 算法求解最近点对问题
double getClosePoints(int n, points a[], int &point1, int &point2)
{
    double dist;
    double minDist = 10000;
    for (int i = 0; i <= n - 1; i++)
    {
        for (int j = i + 1; j <= n - 1; j++)
        {
            dist = (a[i].x - a[j].x) * (a[i].x - a[j].x) + (a[i].y - a[j].y) * (a[i].y - a[j].y);
            if (dist < minDist)
            {
                minDist = dist;
                point1 = i;
                point2 = j;
            }
        }
    }

// 分治法求解最近点对问题

//求出最近点对记录，并将两点记录再point1,point2中
double closePoints(points point[], int length, points &point1, points &point2)
{
    int i = 0;
    int k = 0;
    int j = 0;
    double minDist;                            // 纪录最小点距离
    double dist1, dist2;                       // 记录两个子集中的距离
    points point11, point12, point21, point22; // 保存分割后两个子集中最小点对

    if (length < 2)
        return nodistances;
    if (length == 2)
    {
        point1 = point[0];
        point2 = point[1];
        minDist = getDistances(point[0], point[1]);
    }
    else
    {
        // 开辟两个子集
        points *p1 = new points[length];
        points *p2 = new points[length];

        //调用algorithm库中的sort函数对points进行排序，CmpX为自定义的排序规则
        sort(point, point + length, cmpX);
        float mid = point[(length - 1) / 2].x; //排完序后的中间下标值，即中位数

        for (int i = 0; i < length / 2; i++)
            p1[i] = point[i];
        for (int j = 0, i = length / 2; i < length; i++)
            p2[j++] = point[i];

        dist1 = closePoints(p1, length / 2, point1, point2);          //分治求解左半部分子集的最近点
        dist2 = closePoints(p2, length - length / 2, point1, point2); //分治求解右半部分子集的最近点

        if (dist1 < dist2)
        {
            minDist = dist1;
            point1 = point11;
            point2 = point12;
        }
        else
        {
            minDist = dist2;
            point1 = point21;
            point2 = point22;
        }

        //求解跨分割线并在δ×2δ区间内的最近点对
        points *p3 = new points[length];
        for (i = 0, k = 0; i < length; i++)
        {
            if (abs(point[i].x - mid) <= minDist)
            {
                p3[k++] = point[i];
            }
        }

        for (i = 0; i < k; i++)
        {
            //只需与有序的领接的的7个点进行比较
            for (j = i + 1; j <= i + 7 && j < k; j++)
            {
                if (getDistances(p3[i], p3[j]) < minDist)
                {
                    //如果跨分割线的两点距离小于已知最小距离，则记录该距离
                    minDist = getDistances(p3[i], p3[j]);
                    point1 = p3[i];
                    point2 = p3[j];
                }
            }
        }
    }

    return minDist;
}

实验分析

蛮力法的思想分析

遍历点集中的所有点，算出所有点与其他点的距离，比较得出点集中距离最短的两点的距离，并将两点记录下来。
时间复杂度：T(n) =an² + bn + c

分治法求最近点对问题的思想分析

1. 采用分治法寻找最近点对时，相较于寻找一维的最近点来说，二维的最近点对寻找要困难许多，难点在于分界线周围的点的处理，即跨分治区域的点的比较。
2. 可证明，处理δ*2δ区间内的点时，只需处理与当前点递增相连的7个点即可。因此可以大大减少开销，提高算法效率，改进算法时间复杂度。
3. 可对点对进行预排序，即在第一次递归调用前，对所有的点进行排序。预排序使运行时间增加了O(nlogn)，但这样一来，除递归调用外，递归过程的每一步仅需线性时间。因此算法的整个时间复杂度为O(nlogn)。
   

赏

谢谢你请我吃糖果