【算法设计与分析】分治法（最近点对问题）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【算法设计与分析】分治法（最近点对问题）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

实验目的

实验内容与结果

蛮力法求解

分治法求解

实验总结

实验目的

（1）掌握分治法思想。

（2）学会最近点对问题求解方法。

实验内容与结果

蛮力法求解

算法过程：

遍历n个点与剩余n-1个点之间的距离，在计算点对距离时不断更新最短距离的值，遍历完所有点对后即可求得最短点对距离。

伪代码：

最近点对算法,算法设计与分析,算法,机器学习,数据结构

复杂度分析：

需要对n(n-1)/2个点对进行遍历来求得最小点对距离，最好情况、最坏情况和平均情况的时间复杂度都为O(n²)。

测试算法运行时间：

随机生成N个点的平面坐标，将每个点的x和y坐标值限制在1-100的范围内，分别对N = 100000-1000000统计算法运行时间，并比较理论效率与实测效率的差异。

理论效率计算：

T实测 = k * n实测²

T理论 = k * n理论²

T理论 = T实测 * (n理论/n实测)²

最终结果如下：(理论效率以N=100000为基准)

N	100000	200000	300000	400000	500000
实测效率/s	79.076	316.686	709.958	1258.56	1972.48
理论效率/s	79.076	316.304	711.684	1265.216	1976.9
N	600000	700000	800000	900000	1000000
实测效率/s	2848.37	4214.7	5090.44	6665.26	8409.58
理论效率/s	2846.736	3874.724	5060.864	6405.156	7907.6

最近点对算法,算法设计与分析,算法,机器学习,数据结构

分治法求解

算法过程：

算法每一次递归调用的输入为点集S以及数组X和Y，X和Y数组中分别包含S中所有点的x和y坐标。在划分开始前，对数组X和Y中的点排序，使其x和y坐标值单调递增。

检查是否有| S | <= 3成立，如果有，则采用暴力方法求解：对所有点对进行检查，并返回最近点对距离。

最近点对算法,算法设计与分析,算法,机器学习,数据结构

对应代码如下：

if (end == start){
        return DBL_MAX;
    }//递归出口（只含一个点时）
    if (end - start == 1){
        return getDistance(p[end],p[start]);
    }//只含两个点时 直接返回两点距离
    if (end - start == 2){
        return brutalSort(p,3);
    }//含三个点时 直接用蛮力法求解

如果| S | > 3，则递归调用如下分治模式。

分解：在分治开始前，已经对X和Y数组进行递增排序，此时取中间点将点集划分为左区域SL和右区域SR，SL中所有点都在中线上或是在中线的左侧，SR中所有点都在中线上或是在中线的右侧。此时要想以最快的方法尽可能均匀平分，可采用效率较高的快速排序和合并排序算法，时间复杂度为O(nlogn)。

最近点对算法,算法设计与分析,算法,机器学习,数据结构

解决：划分后进行两次递归调用，一次找出SL中的最近点对距离dL，另一次找出SR中的最近点对距离dR。令SL和SR返回的最近点对距离分别为dL和dR，并且取d = min(dL,dR)。

最近点对算法,算法设计与分析,算法,机器学习,数据结构

对应代码如下：

double d = DBL_MAX;
    int mid = start + (end - start) / 2;
    double d1 = divide(p,n,start,mid);//递归得到左半区的最近点对距离
    double d2 = divide(p,n,mid + 1,end);//递归得到右半区的最近点对距离
    d = min(d1,d2);

合并：考虑最近点对有可能是上述某次递归调用找出的距离为d的点对，也有可能是SL中的一个点与SR中的一个点形成的点对。寻找是否存在距离小于d的一个点对，一个点位于SL中，另一个位于SR中。若存在这样一个点对，则其中两个点与直线L的距离都必须在d的范围内。

最近点对算法,算法设计与分析,算法,机器学习,数据结构

同时这两点在垂直方向上的距离也应小于d。因此可以限制该点对的范围在2d*d的方框内。

最近点对算法,算法设计与分析,算法,机器学习,数据结构

建立一个数组Y’，它是边界区域Y中的点按照y坐标值排序后得到的点集，Y’可划分为Y’L和Y’R左右两个集合。沿y轴方向找出最短距离，通过排序的贪心策略更容易实现。

对应代码如下：

Point* y = new Point[n];//对应Y'
    int pos = 0;
    Point* yl = new Point[n];//对应Y'L
    int posl = 0;
    Point* yr = new Point[n];//对应Y'R
    int posr = 0;
    for (int i = start; i <= end; i++){
        if (fabs(p[i].x - p[mid].x) <= d){
            y[pos++] = p[i];
            if (p[mid].x - p[i].x <= d){
                yl[posl++] = p[i];
            } else if (p[i].x - p[mid].x <= d){
                yr[posr++] = p[i];
            }
        }
    }
    sort(y,y + pos, cmpy);

对于Y’L中的每一点，检查Y’R中的点与它的距离，更新所获得的最近距离。

部分蛮力：遍历一点在Y’L中，另一点在Y’R中的所有点对距离，并返回得到的最小点对距离。此方法的时间复杂度为O(n²)，不符合线性效率，故舍弃。

一趟查询：考察合理范围内的左半边d*d正方形，因为Y’L中所有点之间至少相距距离d，所以该正方形内至多有4个点满足该条件。类似地，Y’R中也有4个点满足该条件。因此，Y’中至多有8个点可能位于该d*2d范围内。（直线上的点可能属于Y’L也可能属于Y’R，因此直线上至多有4个点）。因此，只需要查询Y’L中每个点随后的6个点，即可达到线性效率并计算出合法区域内的最小点对距离。

最近点对算法,算法设计与分析,算法,机器学习,数据结构

对应代码如下：

for (int i = 0; i < pos - 6; ++i) {
        for (int j = i + 1; j <= i + 6 && y[j].y - y[i].y <= d; ++j) {
            double dis = getDistance(p[i],p[j]);
            if (dis < d){
                d = dis;
            }
        }
    }

程序正确性验证：

对同一组数据分别进行蛮力法和分治法进行求解，运行结果如下:

最近点对算法,算法设计与分析,算法,机器学习,数据结构

返回值为最近点对距离，两方法求得结果相同，程序正确性得证。

时间复杂度分析：

在该算法中，最坏情况、最好情况和平均情况的时间复杂度都为O(nlogn)

测试算法运行时间：

随机生成N个点的平面坐标，将每个点的x和y坐标值限制在1-100的范围内，分别对N = 100000-1000000统计算法运行时间，并比较理论效率与实测效率的差异。

理论效率计算：

T实测 = k * n实测logn实测

T理论 = k * n理论logn理论

T理论 = T实测 * n理论logn理论 / n实测logn实测

最终结果如下：(理论效率以N=100000为基准)

N	100000	200000	300000	400000	500000
实测效率/s	1.088	3.458	5.778	6.484	9.971
理论效率/s	1.088	2.307	3.575	4.876	6.2
N	600000	700000	800000	900000	1000000
实测效率/s	10.723	11.093	11.532	14.897	18.473
理论效率/s	7.544	8.903	10.276	11.660	13.056