likes
comments
collection
share

分治法（三）：最近点对问题｜算法设计与分析

作者站长头像
站长
· 阅读数 24

本系列分治法重点内容一览：

  1. 详解当求解子问题与划分+合并子问题时间复杂度相同时，分治法的整体复杂度
  2. 详解最短点对问题为什么可以做到线性的时间复杂度，包括鸽舍原理等。

【问题描述】

给定平面S上n个点,找其中的一对点,使得在n个点组成的所有点对中,该点对间的距离最小。

蛮力法求解

分别计算每一对点之间的距离,然后找出距离最小的那一对。

T(n)=O(n2)T(n)=O(n^2 )T(n)=O(n2)

应用分治法求解

分治策略

T(n)=2T(n2)+O(n)=O(nlog⁡2n)T(n) =2T(\frac{n}{2})+O(n)= O(n\log_2n)T(n)=2T(2n​)+O(n)=O(nlog2​n)

【分治法的求解过程】

  1. 划分 将集合S分成两个大小基本相等的子集S1S_1S1​和S2S_2 S2​
  2. 求解子问题 递归地求解两个子问题
  3. 合并问题的解 可能出现三种情况
  • (1)组成S的最近点对的2个点都在S1S_1S1​中
  • (2)组成S的最近点对的2个点都在S2S_2S2​中
  • (3)组成S的最近点对的2个点分别在S1S_1S1​和S2S_2S2​中

比较三种情况下最近点对,取三者之中较小者为原问题的解。

【求解最近点对的分治算法】

预排序:把S 中的点分别按x-坐标值和y-坐标值排序。

为什么要预排序

1. 如果S 中包含的点少于4个(n<4),则采用蛮力法直接求解。

可以直接求解

2. 划分

计算 SSS 中各点 x-坐标的中位数 mmm ；

用垂线 L:x=mL: x=mL:x=m 把 SSS 划分成两个大小相等的子集合 S1S_1S1​和 S2S_2S2​ ， S1S_1S1​ 中的点在 LLL 左边, S2S_2S2​ 中的点在 LLL 右边。

分治法（三）：最近点对问题｜算法设计与分析

3. 求解子问题

递归地在 S1S_1S1​ 和S2 S_2S2​ 中找出最近点对 (p1,p2)\left(p_1,p_2\right)(p1​,p2​) 和 (q1,q2)\left(q_1, q_2\right)(q1​,q2​) ，设其距离分别为 d1\mathrm{d}_1d1​ 和 d2\mathrm{d}_2d2​

4. 合并解

(1) d=min⁡{d1,d2}d=\min \left\{d_1, d_2\right\}d=min{d1​,d2​}

(2) 在L两侧查找距离小于 ddd的点对(p,q),p∈S1,q∈S2(p, q), p \in S_{1}, q \in S_2(p,q),p∈S1​,q∈S2​，设其距离为d3d_3d3​ ；

(3) 如果找到，则 (p,q)(p, q) (p,q)是SSS中最近点对，否则 (p1,p2)\left(p_1, p_2\right)(p1​,p2​) 和(q1,q2) \left(q_1, q_2\right)(q1​,q2​) 中距离较小者为SSS中最近点对。

(p,q)(p,q)(p,q)的搜索方法及其搜索时间：

搜索范围缩小到以L为中心、宽度为2d的临界区内

对于点p∈Pp∈Pp∈P,需要考察QQQ中的各个点和点ppp之间的距离是否小于ddd,显然,QQQ 中这样点的yyy轴坐标一定位于区间[y−d,y+d][y-d, y+d][y−d,y+d]之间,即这样的点一定落在一个d×2dd×2dd×2d 的矩形区域内。而且,根据鸽舍原理可知这样的点不会超过6个。

为什么不超过6个？

如图所示，将在实线框起来的d×2dd \times 2dd×2d矩形区域中找两个子集之间的点的距离，点ppp对于另一个子集 点的距离

分治法（三）：最近点对问题｜算法设计与分析

为什么将 2d边三等分，因为当x2x_2x2​相同时，p(x1,y1)p(x_1,y_1)p(x1​,y1​)会 与点 (x2,y1)(x_2,y_1)(x2​,y1​)距离最近，分治的思想则是将该部分的子问题在纵轴上划分为三块区域，横轴可以划分为两个区域，最终得到6个矩形，作为新的子问题。

为什么它的时间复杂度是线性的？ppp最多和6个点的距离进行比较？

由于鸽舍原理，如果这块d×2dd \times 2dd×2d矩形区域中超过6个点，比如7个点，那么至少其中一块d2×2d3\frac{d}{2} \times \frac{2d}{3}2d​×32d​的矩形区域中至少有两个或多个点

设这两个点为u,vu,vu,v这样的话 ∣∣uv∣∣=(xu−xv)2+(yu−yv)2≤2536d2=56d||uv|| = \sqrt{(x_u-x_v)^2+(y_u-y_v)^2} \leq \sqrt{\frac{25}{36}d^2} = \frac{5}{6}d∣∣uv∣∣=(xu​−xv​)2+(yu​−yv​)2​≤3625​d2​=65​d

当∣∣uv∣∣=56d||uv|| = \frac{5}{6}d∣∣uv∣∣=65​d时，u,vu,vu,v距离最大，也即uvuvuv为对角线两端点，此时该距离必然比d要小，这与d=min⁡(d1,d2)d=\min(d_1,d_2)d=min(d1​,d2​)定义不符，产生了矛盾（两点处于同一子集，其最短距离为d1d_1d1​或d2d_2d2​)。

因此得出结论:在该d×2dd \times 2dd×2d矩形区域内最多只有6个点，也就是说p只需要最多和6个点的距离进行比较即可，这就让该种情况求解子问题的时间复杂度降到了线性。

临界区内所有点构成点集RRR,将其按照yyy坐标排序,对RRR中的每个点rir_iri​依次考察其后的点rjr_jrj​(最多只要考察紧随其后的7个点),因此,合并步骤可以在线性时间内完成。

//搜索d_3的线性时间实现过程
for(i = 0; i < size(R); i++) 
    for(j = i + 1; j < size(R); j++) 
        if(|y(r_i) - y(r_j)| >= d) 
            break;//继续处理$r_{i+1}$ 
        else 
        if(distance(r_i,r_j) < d) 
            d_3 = distance(r_i,r_j);

为什么只需要和紧随其后的7个点进行比较就可以？

根据上面鸽舍原理，每个d2×2d3\frac{d}{2} \times \frac{2d}{3}2d​×32d​的矩形区域中最多有一个点，两个子集中最多有12个点，而上下相邻的两块，左边最多有4个点，右边最多有4个点，所以最多共8个点（一个点和紧随其后的7个点），后面的4个点其实是无需进行比较的，因为距离必然超过前7个点。

故而，合并的时间复杂度也可以在线性时间内解决。

【伪代码实现】

double closestPoints(S){
    n=|S| 
    if(n < 4)  
        采用蛮力法直接求解，返回求得的最近点对值;
    m = S中各点x坐标的中位数;
    构造S_1和S_2, 其中S_1={x \in S|x \leq m},S_2={x\in S | x > m}; 
        d_1=closestPoints(S_1);
        d_2=closestPoints(S_2); 
        d = min{d_1,d_2); 
    设距离垂直分割线$L$的距离为$d$的区域为临界区;
    构造临界区内所有点组成的集合R(R中的点按照y坐标值有序)；
    for(i = 0; i < size(R); i++)  //size(R)表示集合R中点的个数
        for(j = i+1; j < size(R); j++) 
            if(|y(r_i) - y(r_j)| >= d) 
            break;  //继续处理$r_{i+1}$ 
        else 
        if(distance(r_i,r_j) < d) 
            d_3 = distance(r_i,r_j);
    return min{d,d3}

【时间复杂度分析】

  1. 划分阶段需要O(n)时间
  2. 求解子问题阶段需要2T(n/2)时间
  3. 合并解阶段需要O(n)时间
    • 递归方程
      • T(n)=O(1)n<2T(n) = O(1) \quad \quad \quad \quad \quad \quad n < 2T(n)=O(1)n<2
      • T(n)=2T(n/2)+O(n)n≥2T(n) = 2T(n/2) + O(n) \quad n \geq 2T(n)=2T(n/2)+O(n)n≥2
    • 用主方法求解T(n)
      • T(n)=O(nlog⁡2n)T(n) = O(n\log_2n)T(n)=O(nlog2​n)

【参考资料】

转载自:https://juejin.cn/post/7230071785160343611
评论
请登录