算法设计与分析——递归与分治策略——最接近点对问题

水深无声 2022-11-12 02:44 147阅读 0赞

【问题描述】  
最近对问题要求在包含有n个点的集合S中，找出距离最近的两个点。设 p1(x1,y1)，p2(x2,y2)，……，pn(xn,yn)是平面的n个点。  
![在这里插入图片描述][20210322134313504.png]

严格地将，最近点对可能不止一对，此例输出一对即可。

【基本算法思想】  
暴力法：  
在蛮力法实现最近点对问题中，将问题简化：距离最近的点对可能多于一对，找出一对即可，另外只考虑二维平面中的情况。此处考虑到  
直接用公式计算其距离（欧几里得距离）：  
![在这里插入图片描述][20210322134435400.png]

通过遍历所有点集，计算出每一个点对的距离，计算出最近的距离并输出。避免同一对点计算两次，只考虑i<j的点对(pi,pj)。  
其主要循环的步骤就是求出平方值，执行的次数为：

![在这里插入图片描述][20210322134500242.png]

分治法:  
在利用分治法思想解决此问题时，首先考虑将最近对问题进行分治，设计其分治策略。将集合S分成两个子集S1和S2，根据  
平衡子问题原则，每个子集中的点数大致都为n/2。这样分治后，最近点对将会出现三种情况：在S1中，在S2中或者最近  
点对分别在集合S1和S2中。利用递归分析法分别计算前两种情况，第三种方法另外分析。求解出三类子情况后，  
再合并三类情况，比较分析后输出三者中最小的距离。

***复杂度分析***: 在分治算法中，当求解n个点的集合的最近点对时，对于上述三类情况中的前两者可由递归算得，  
而分析可得第三类情况的时间代价 ，合并后问题求解的总的时间按复杂度可由下列公式来：

![在这里插入图片描述][20210322134516683.png]

//分治法求解最近点对问题(C++)
    #include<stdio.h>
    #include<math.h>
    #include<string.h>
    #include<algorithm>
    #include<iostream>
    using namespace std;
    struct point{
                   //点结构
        double x,y;
    };
    double Distance(point a,point b){
        
        return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y));
    }
    bool cmp(point a,point b){
                  //按y升排序辅助函数
        return a.y<b.y;
    }
    bool cmp2(point a,point b){
                  //按x升排序辅助函数
        return a.x<b.x;
    }
    double closestPoint(point s[],int low,int high,point rec[]){
        
        double d1,d2,d3,d;
        int mid,i,j,index;
        double x1,y1,x2,y2;         //记录点对的位置
        point P[high-low+1],temp1[2],temp2[2],temp3[2];         //辅助空间
        if(high-low==1){
                     //两个点的情况
            rec[0].x=s[low].x;rec[0].y=s[low].y;
            rec[1].x=s[high].x;rec[1].y=s[high].y;
            return Distance(s[low],s[high]);
            }
        if(high-low==2){
                    //三个点的情况
            d1=Distance(s[low],s[low+1]);
            d2=Distance(s[low+1],s[high]);
            d3=Distance(s[low],s[high]);
            if((d1<d2)&&(d1<d3)){
        
                rec[0].x=s[low].x;rec[0].y=s[low].y;
                rec[1].x=s[low+1].x;rec[1].y=s[low+1].y;
                return d1;
            }
            else if(d2<d3){
        
                rec[0].x=s[low+1].x;rec[0].y=s[low+1].y;
                rec[1].x=s[high].x;rec[1].y=s[high].y;
                return d2;
            }
            else {
        
                rec[0].x=s[low].x;rec[0].y=s[low].y;
                rec[1].x=s[high].x;rec[1].y=s[high].y;
                return d3;
            }
        }
        mid=(low+high)/2;       //其他情况递归
        d1=closestPoint(s,low,mid,rec);
        temp1[0]=rec[0];
        temp1[1]=rec[1];
        d2=closestPoint(s,mid+1,high,rec);
        temp2[0]=rec[0];
        temp2[1]=rec[1];
        if(d1<d2){
        
            d=d1;
            rec[0]=temp1[0];
            rec[1]=temp1[1];
        }
        else {
        
            d=d2;
            rec[0]=temp2[0];
            rec[1]=temp2[1];
        }
        index=0;
        for(i=mid;(i>=low)&&((s[mid].x-s[i].x)<d);i--)      //点集合p1
            P[index++]=s[i];
        for(i=mid+1;(i<=high)&&((s[i].x-s[mid].x)<d);i++)      //点集合p2
            P[index++]=s[i];
        sort(P,P+index,cmp);                    //升序排列
        for(i=0;i<index;i++){
        
            for(j=j+1;j<index;i++){
        
                if((P[j].y-P[i].y)>=d)
                    break;
                else {
        
                    d3=Distance(P[i],P[j]);
                    if(d3<d){
        
                        rec[0].x=P[i].x;rec[0].y=P[i].y;
                        rec[1].x=P[j].x;rec[1].y=P[j].y;
                        d=d3;
                    }
                }
            }
        }
        return d;
    }
    int main(){
        
        point p[10];            //设定点的集合
        int n;
        double minDist;
        cout<<"输入点的个数：\n";      //输入点的个数
        cin>>n;
        cout<<"输入点集:（x,y）\n";
        for(int i=0;i<n;i++)
            cin>>p[i].x>>p[i].y;
        sort(p,p+n,cmp2);      //对输入的点先排序
        point index[2];
        minDist=closestPoint(p,0,n-1,index);
        cout<<"最小距离点对为：("<<index[0].x<<","<<index[0].y<<"),("<<index[1].x<<","<<index[1].y<<")\n";
        cout<<"最小距离为：\n"<<minDist;      //输出点对的最小问题
        return 0;
    }

————————————————  
版权声明：本文为CSDN博主「fanleehao」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/qq\_28666193/article/details/53351482

[20210322134313504.png]: /images/20221022/15242dbbac7040aca77320b15413620e.png
[20210322134435400.png]: /images/20221022/46383c3742cb4b999a7e3141a12b8cb7.png
[20210322134500242.png]: /images/20221022/8057800adcbd458cb175c91c2d98fe71.png
[20210322134516683.png]: /images/20221022/1a45f0061c664e92b23b3aed3429d4aa.png