精华内容
下载资源
问答
  • 最近点对问题分治法
    千次阅读
    2021-12-10 20:10:36

    分治法适用情景

    • 该问题的规模缩小到一定的程度就可以容易地解决
    • (前提) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质
    • (关键) 利用该问题分解出的子问题的解可以合并为该问题的解;
    • (效率) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题

    使用分治法 (Divide and Conquer) 解题步骤

    Step1:Devide——将要解决的问题划分成若干规模较小的同类问题
    Step2:Conquer——当子问题划分得足够小时,用较简单的方法解决 (递归)
    Step3:Combine——将子问题的解逐层合并构成原问题的解

    最接近点对问题

    问题描述

    二维平面上的n个点中,找出最接近的一对点

    问题背景

    在应用中,常用诸如点、圆等简单的几何对象代表现实世界中的实体。在涉及这些几何对象的问题中,常需要了解其邻域中其他几何对象(最接近)的信息。例如,在空中交通控制问题中,若将飞机作为空间中移动的一个点来看待,则具有最大碰撞危险的2架飞机,就是这个空间中最接近的一对点。这类问题是计算几何学中研究的基本问题之一

    问题分析

    已知集合S中有n个点,使用分治法的思想就是将S进行拆分,分为2部分求最近点对。算法每次选择一条垂线L,将S拆分左右两部分为SL和SR,( L一般取点集S中所有

    更多相关内容
  • C++的课程作业,一个简单的最近点对程序,用dev就能直接运行,老师应该不会太仔细检查,糊弄一下肯定没事的,不过最好能自己看懂就是了
  • 3. 要求随机生成N个的平面坐标,应用分治法编程计算出所有点对的最短距离。4. 分别N=100100010000100000,统计算法运行时间,比较理论效率与实测效率的差异,同时蛮力法和分治法的算法效率进行分析和比较。5. ...
  • 1. 对于平面上给定的N个,给出所有点对的最短距离,即,输入是平面上的N个,输出是N点中具有最短距离的两。2. 要求随机生成N个的...3. 要求随机生成N个的平面坐标,应用分治法编程计算出所有点对的最短距离。
  • 分治法——最近对问题

    千次阅读 2022-03-18 15:50:02
    最近对问题 令P为笛卡儿平面上n>1个构成的集合。简单起见,假设集合中的每个都不一样。我们还假设这些是按照其x轴坐标升序排列的。(如果不是这样,可以事先用类似合并排序这样的高效算法其排序。)为了...

    最近对问题

    令P为笛卡儿平面上n>1个点构成的集合。简单起见,假设集合中的每个点都不一样。我们还假设这些点是按照其x轴坐标升序排列的。(如果不是这样,可以事先用类似合并排序这样的高效算法对其排序。)为了更加方便,我们还可以按照点的y轴坐标在另一个列表中进行升序排列,并将这个列表示为Q。
    当2≤n≤3时,问题就可以通过蛮力算法求解。当n>3时,可以利用点集在x轴方向上的中位数m,在该处作一条垂线,将点集分成大小分别为 ⌈ n / 2 ⌉ 和 ⌊ n / 2 ⌋ \lceil n/2 \rceil 和\lfloor n/2 \rfloor n/2n/2的两个子集 P l 和 P r P_l和P_r PlPr。即使得其中⌈n/2⌉个点位于线的左边或线上,⌊n/2⌋个点位于线的右边或线上。然后就可以通过递归求解子问题 P l 和 P r P_l和P_r PlPr来得到最近点对问题的解。其中 d l 和 d r d_l和d_r dldr分别表示在 P l 和 P r P_l和P_r PlPr中的最近对距离,并定义d=min{ d l , d r d_l,d_r dl,dr}。但请注意,d不一定是所有点对的最小距离,因为距离最近的两个点可能分别位于分界线的两侧。因此,在合并较小子问题的解时,需要检查是否存在这样的点。显然,我们可以只关注以分割带为对称的、宽度为2d的垂直带中的点,因为任何其他点对的距离都至少为d,如下图。
    在这里插入图片描述

    设S是来自Q,位于分割线2d宽度范围内的垂直带的点的列表。由于Q的特点,因此S是按照y轴坐标升序排列的。我们扫描该列表,当遇到更近的点对时,更新目前为止的最小距离 d m i n d_{min} dmin。初始情况下 d m i n d_{min} dmin=d,但接下来 d m i n d_{min} dmin≤d。设p(x,y)为列表中的点。如果另一个点p’(x’,y’)和p点的距离小于d,那么在列表S中,p’点一定位于p点后面,并且两点在y轴上的距离一定要小于d。在几何上,这也就意味着p’点一定包含在下图的矩形内。该算法的主要原理利用了以下事实:矩形内一般只能够包含少量候选点,因为在矩形每一边(左半边和右半边)内,点与点的距离至少为d
    在这里插入图片描述
    其实很容易证明,在矩形中满足条件的点(包括P在内)的总数不超过8个,更细致的研究表明这个数不会大于6。也就是说,在移动到下一个点之前,算法最多只需要考虑列表S中点p后面的5个点。

    伪代码

    EfficientClosePair(P,Q)
    	//使用分治算法来求解最近对问题
    	//输入:数组P中存储了平面n>=2个点,并且这些点按照x轴坐标升序排列
    	//		数组Q存储了与P相同的点,只是它是按照这点的y轴坐标升序排列
    	//输出:最近点对之间的欧几里得距离
    	if n <= 3
    		返回由蛮力算法求出的最小距离
    	elseP的前⌈n/2⌉个点复制到PlQ的前⌈n/2⌉个点复制到QlP中余下的⌊n/2⌋个点复制到PrQ中余下的⌊n/2⌋个点复制到Qr
    		dl <- EfficientClosePair(Pl,Ql)
    		dr <- EfficientClosePair(Pr,Qr)
    		d <- min{dl,dr}
    		m <- P[⌈n/2-1].x
    		将Q中所有[x-m|<d的点复制到数组S[0..num-1]
    		dminsq <- d的平方
    		for i<-0 to num-2 do
    			k <- i+1
    			while k<=num-1 and (S[k].y-S[i].y)的平方 < dminsq
    				dminsq < min((S[k].x-S[i].x)^2+(S[k].y-S[i].y)^2),dminsq)
    				k <- k+1
    		return sqrt(dminsq)
    

    Java代码实现

    package com.算法.分治法;
    
    import java.util.ArrayList;
    import java.util.Comparator;
    import java.util.List;
    
    /**
     * @Author Lanh
     **/
    public class 最近对问题 {
        public static void main(String[] args) {
            int[][] matrix = {{12,5},{23,1},{3,27},{65,4},{2,5}};
            List<Node> P = new ArrayList<>();
            for (int[] ints : matrix) P.add(new Node(ints[0], ints[1]));
            List<Node> Q = new ArrayList<>(P);
            P.sort(Comparator.comparingInt(o -> o.x));
            Q.sort(Comparator.comparingInt(o -> o.y));
            double d = ClosestPoints(P, Q);
            System.out.println("最近距离:"+d);
    
        }
    
        public static double ClosestPoints(List<Node> P,List<Node> Q){
            if (P.size()<=3){
                int n = P.size();
                double d = Double.MAX_VALUE;
                for (int i=0;i<n;i++){
                    int x1 = P.get(i).x;
                    int y1 = P.get(i).y;
                    for (int j=i+1;j<n;j++){
                        int x2 = P.get(j).x;
                        int y2 = P.get(j).y;
                        d = Math.min(d,Math.pow(x1-x2,2)+Math.pow(y1-y2,2));
                    }
                }
                return d;
            }else {
                List<Node> pl = P.subList(0,P.size()/2+1);
                List<Node> pr = P.subList(P.size()/2+1, P.size());
                List<Node> ql = Q.subList(0, Q.size()/2+1);
                List<Node> qr = Q.subList(Q.size()/2+1, P.size());
                double d = Math.min(ClosestPoints(pl,ql),ClosestPoints(pr,qr));
                int m = P.get(P.size()/2).x;
                List<Node> S = new ArrayList<>();
                for (Node node : Q) {
                    if (node.x - m < d) S.add(node);
                }
                double dminsq = Math.pow(d,2);
                for (int i=0;i<S.size()-1;i++){
                    int k=i+1;
                    while (k<S.size()&&Math.pow((S.get(k).y-S.get(i).y),2)<dminsq){
                        dminsq=Math.min(Math.pow((S.get(k).y-S.get(i).y),2)+Math.pow((S.get(k).x-S.get(i).x),2),dminsq);
                        k++;
                    }
                }
                return Math.sqrt(dminsq);
            }
        }
    
        static class Node{
            int x;int y;
            Node(int x,int y){
                this.x = x;
                this.y = y;
            }
    
            @Override
            public String toString() {
                return "Node{" +
                        "x=" + x +
                        ", y=" + y +
                        '}';
            }
        }
    }
    
    

    测试

    测试用例:{{12,5},{23,1},{3,27},{65,4},{2,5}}
    测试结果:
    在这里插入图片描述

    展开全文
  • 问题描述 对于平面上给定的N个,给出所有点对的最短距离,即,输入是平面上的N个,输出是N点中具有最短距离的两。...分治法 问题分割策略:排序,取中位数 如果像快速排序,分割的策略与数据...

    问题描述

    对于平面上给定的N个点,给出所有点对的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。

    暴力法

    暴力法的思路相对简单,即枚举所有可能的配对情况,然后一一比对,找到距离最小的点,一共有 Cn2 种组合,也就是 n*(n-1)/2种,总的时间复杂度是O(n^2),因为时间开销过于昂贵,我们寻求别的方法

    分治法

    问题分割策略:排序,取中位数

    如果像快速排序,分割的策略与数据有关,那么算法便会退化,不能达到稳定的O(nlogn)

    但是如果效仿归并排序,每次选取中点(中位数)进行分割,那么可以使得递归树的深度稳定的控制在log(n)

    这里对点做预处理,按照x升序,x相同则y升序排序,这样我们每次选取中间下标的点,都能尽量地将点分割成几何上的两半

    在这里插入图片描述

    子问题存在分析:

    问题是选取两个点,p1,p2,使得他们距离最短,子问题存在于以下空间

    • p1 p2 同时位于左边点集
    • p1 p2 同时位于右边点集
    • p1 p2 一个在左侧一个在右侧

    对于子问题1和2,我们可以通过递归直接解决,难点就在于解决子问题3,即两点在两边的情况

    子问题3求解 缩小空间:

    想起来归并是要【合并】的,如何有效利用递归得到的答案呢?
    注意这里如果要一一配对找两边点求距离,那么合并效率还是O(n^2)

    递归得到两边点子集的最近点对距离,取最小值d,我们可以借此距离d来缩小我们查找的空间

    从中间点向外扩散,如果点与中间点的x左边之差,大于d,那么这个点及其往后的点,都不可能是最优的答案,缩小了查找空间

    在这里插入图片描述
    缩小查找空间,其实是不稳定的,可能查找空间和原来一样,所以我们不能暴力枚举查找空间内的点,下面引入一个结论,来帮助我们快速查找

    结论:点目标出没区域确定

    结论:对于左边区域的每一点p,要想在右边区域找到一点p’使得 pp’距离<=d,这样的点p’必定存在于【以p的y坐标为中心,上下延展d形成的d*2d的子矩形中】

    证明:
    假设极限情况,p在左右边线上,以p为中心半径为d画圆,半圆区域内,都是距p的距离小于d的,半圆是矩形的真子集,故目标点一定存在于矩形中

    而且因为右侧的点具有稀疏性,即两两之间距离大于等于d, d*2d的矩形区域,矩形区域内最多存在6个点(如果圆形区域则是四个)

    在这里插入图片描述
    我们遍历左边区域的所有点,划分出d*2d的矩形区域,然后检查6个点,更新答案即可,可是如何用短时间找到d*2d的矩形区域? 想到矩形区域的划分和y有关,那么应该是利用y坐标的特性了!

    y的划分

    对左右的子区域的所有点按照y升序排序(左右分开排序,不是混合在一起),在指针i升序遍历左边的所有点的时候,设置指针h在右边的点中向后查找,找到第一个不矮于iy坐标d高度的点h(即hi点高度差小于d),从h往后找6个点即可

    (因为点y坐标递增,那么对应的矩形区域,下边界也递增,那么上一次找过的下界点(h指针),就不用再从头开始找了,直接在上一次的基础上找就行了)
    在这里插入图片描述

    合并代价O(n)的证明

    因为左右点集都是升序,这表明,i++之后,下一个i点的d*2d矩形的下边界一定会提升,而h指针随着做出更新即可,因为i点矩形的下边界是递增的,h指针不走回头路

    h指针最多从0增加到右边区域点的个数,最多n/2次,所以遍历左边点集,h迭代的次数,均摊到每一次i迭代,就是均摊一次,O(1),而查找矩形区域总共是6个点,也是常数时间可以完成,所以总的复杂度仍然是O(n)

    分治法的改进:

    因为每次递归之后,还要对左右按d划分的区域排序,总复杂度是O(2*n/2log(n/2)), 即合并代价,不是线性效率,总体复杂度超过O(nlong(n))

    那么如何优化呢?
    效仿归并排序,每次二分递归之后,我们对数组归并,因为递归排好了左右子区间,这样归并后,数组就是对y有序的了,不用消耗额外的时间再排序了,可以使合并子问题的代价变为O(n)级别

    代码

    代码的前半部分是一些帮助函数,后面两个函数才是分治法和归并分治法的代码

    #include <bits/stdc++.h>
    
    using namespace std;
    
    typedef struct p
    {
    	int x, y;
    	p(){}
    	p(int X, int Y):x(X),y(Y){}	
    }p;
    
    /*
    浮点最小函数,防止默认min的int形参截断 
    */
    double lfmin(double a, double b)
    {
    	return (a<b)?(a):(b);
    }
    
    /*
    比较函数,排序用,x升序,x相同则y升序
    param p1 : 第一个点
    param p2 : 第二个点 
    return   : p1 前于 p2 ? 
    */
    bool cmpx(const p& p1, const p& p2)
    {
    	if(p1.x==p2.x) return p1.y<p2.y;
    	return p1.x<p2.x;
    }
    
    /*
    比较函数,排序用,则y升序,归并用 
    param p1 : 第一个点
    param p2 : 第二个点 
    return   : p1 前于 p2 ? 
    */
    bool cmpy(const p& p1, const p& p2)
    {
    	return p1.y<p2.y;
    }
    
    /*
    求解两点欧氏距离 
    param p1 : 第一个点
    param p2 : 第二个点 
    return   : 距离,浮点数 
    */
    double dis(const p& p1, const p& p2)
    {
    	return sqrt((double)(p1.x-p2.x)*(p1.x-p2.x)+(double)(p1.y-p2.y)*(p1.y-p2.y));
    }
    
    /*
    求两点水平距离 
    param p1 : 第一个点
    param p2 : 第二个点 
    return   : 水平距离,浮点数 
    */
    double disX(const p& p1, const p& p2)
    {
    	double ans = (double)p1.x - (double)p2.x;
    	if(ans<0) return ans*-1;
    	return ans;
    }
    
    /*
    暴力求解最近点对
    param points : 点的数组
    return       : 最近点对距离 
    */ 
    double cp(vector<p>& points)
    {
    	double ans = (double)INT_MAX;
    	for(int i=0; i<points.size(); i++)
    		for(int j=i+1; j<points.size(); j++)
    			ans = lfmin(ans, dis(points[i], points[j]));
    	return ans;
    }
    
    /*
    分治求解最近点对,复杂度O(nlog(n)log(n)) 
    param points : 点的数组
    param l      : 点数组左端点
    param r      : 点数组右端点 
    return       : 最近点对距离 
    explain      : 区间[l, r]左闭右闭 
    */ 
    double cp(vector<p>& points, int l, int r)
    {
    	if(l>=r) return (double)INT_MAX;
    	if(l+1==r) return dis(points[l], points[r]);
    	int mid=(l+r)/2, le=mid, ri=mid, h=0;
    	double d=lfmin(cp(points, l, mid), cp(points, mid+1, r)), ans=d;
    	vector<p> ll, rr;
    	while(le>=l && disX(points[mid], points[le])<=d) ll.push_back(points[le]), le--;
    	while(ri<=r && disX(points[mid], points[ri])<=d) rr.push_back(points[ri]), ri++;
    	sort(ll.begin(), ll.end(), cmpy), sort(rr.begin(), rr.end(), cmpy);
    	for(int i=0; i<ll.size(); i++)
    	{
    		while(h<rr.size() && rr[h].y+d<ll[i].y) h++; h=min((int)rr.size(), h);
    		for(int j=h; j<min((int)rr.size(), h+6); j++)
    			if(!eqfunc()(ll[i], rr[j])) ans=lfmin(ans, dis(ll[i], rr[j])); 
    	}
    	return lfmin(ans, d);
    }
    
    /*
    分治+归并求解最近点对,复杂度O(nlog(n)) 
    param points : 点的数组
    param l      : 点数组左端点
    param r      : 点数组右端点 
    return       : 最近点对距离 
    explain      : 区间[l, r]左闭右闭 
    */ 
    double cpm(vector<p>& points, int l, int r)
    {
    	if(l>=r) return (double)INT_MAX;
    	if(l+1==r) 
    	{
    		if(cmpy(points[r], points[l])) swap(points[l], points[r]);
    		return dis(points[l], points[r]);
    	}
    	int mid=(l+r)/2, le=mid, ri=mid, h=0;
    	p midp = points[mid];
    	double d=lfmin(cpm(points, l, mid), cpm(points, mid+1, r)), ans=d;
    	inplace_merge(points.begin()+l, points.begin()+mid+1, points.begin()+r+1, cmpy);
    	vector<p> ll, rr;
    	for(int i=l; i<=r; i++)
    	{
    		if(midp.x>=points[i].x && disX(midp, points[i])<=d) ll.push_back(points[i]);
    		if(midp.x<=points[i].x && disX(midp, points[i])<=d) rr.push_back(points[i]);
    	}
    	for(int i=0; i<ll.size(); i++)
    	{
    		while(h<rr.size() && rr[h].y+d<ll[i].y) h++; h=min((int)rr.size(), h);
    		for(int j=h; j<min((int)rr.size(), h+6); j++)
    			if(!eqfunc()(ll[i], rr[j])) ans=lfmin(ans, dis(ll[i], rr[j])); 
    	}
    	return lfmin(ans, d);
    }
    
    
    展开全文
  • 我们可以先从一维的寻找最近点寻找思路: 伪代码: NearestPointPairDim1(A[0,...,n-1]) { if (n = 1) return INF; if (n = 2) return d(A[0],A[1]); d1 = NearestPointDim1(A[0,...,(n/2)-1]); d2 = ...

    在一个平面当中分布着n个点。现在我们知道这n个点的坐标,要求找出这n个点当中距离最近的两个点的间距。

    我们可以先从一维的寻找最近点寻找思路:
    伪代码:

    NearestPointPairDim1(A[0,...,n-1]) {
        if (n = 1) 
            return INF;
        if (n = 2)
            return d(A[0],A[1]);
        d1 = NearestPointDim1(A[0,...,(n/2)-1]);
        d2 = NearestPointDim1(A[n/2,...,n-1]);
        d3 = d(A[(n/2)-1,n/2]);
        return min(d1,d2,d3);
    }
    

    既然一维可以用分治法解决,那二维当然也是可以。
    点集合 { ( x i , y i ) } i = 1 N \{(x_i,y_i)\}_{i=1}^N {(xi,yi)}i=1N
    算法思想:
      将点集合内的点按 x x x坐标排序,然后按照中点进行划分,从而我们只要求出左边部分的最近点对,右边部分的最近点对,以及一个点在左边一个点在右边的最近点对,最后再取最小距离的就是总体的最近点对。
      通过递归我们可以求左边部分的最近点对的距离 D 1 D_1 D1和右边部分的最近点对的距离 D 2 D_2 D2,我们取 D = m i n ( D 1 , D 2 ) D=min(D_1,D_2) D=min(D1,D2),现在我们来考虑一个点在左边一个点在右边的最近点对这种情况:

      像图片中的这种情况,如果要与左边的 p p p点构成最近点对,则只要在虚线框的部分找就可以,那么虚线框里的点数会不会等于 N 2 \frac{N}{2} 2N,答案是不会的。
    在这里插入图片描述
      我们来看这张图,如果要在长方形里(包括边框)里放七个点,根据鸽巢原理,那么一定可以找得到两点 A A A B B B,使得 ∣ A B ∣ < D |AB|<D AB<D,所以要使得虚线框能够形成,那么虚线框里的点不能够多于7个。也就是说对于点 p p p,我们在中线右侧最多只能找出6个点来构成最短点对。
      然后接下来我们就要来找着六个点,对已经按x坐标排好序的点,从中线往左寻找在 D D D范围内的点在数组中的下标 L L L,从中线往右寻找在 D D D范围内的点在数组中的下标 R R R,然后计算 p t s [ L ] pts[L] pts[L] p t s [ R ] pts[R] pts[R]之间中是否存在比 D D D距离更小的最近点对。

    #include<vector>
    #include<map>
    #include<math.h>
    #include<iostream>
    #include <unordered_map>
    #include<algorithm>
    using namespace std;
    #define INF 0x7fffffff
    #define goleft true
    #define goright false
    int getDist(pair<int,int> A, pair<int,int> B) {
        return (A.first - B.first)*(A.first - B.first) + (A.second - B.second)*(A.second - B.second);
    }
    int getPos(int left,int right,vector<pair<int,int>>& vec,int D,bool GOLeft) {
        if(GOLeft){
            for (int i = right-1; i>=left; --i){
                int xdist = abs(vec[right].first - vec[i].first);
                if(xdist<D)
                    return i;
            }
        }
        else {
            for (int i = left+1; i<=right; ++i){
                int xdist = abs(vec[right].first - vec[i].first);
                if(xdist<D)
                    return i;
            }        
        }
        return -1;
    }
    vector<int> divide (vector<pair<int,int>>& vec, int left, int right) {
        if(left == right) {
            vector<int> res = {INF, -1, -1};
            return res;
        }
        if(left == right - 1) {
            vector<int> res = {getDist(vec[left], vec[right]), left, right};
            return res;
        }
        vector<int> d1= divide(vec, left, ((right+left) / 2) - 1);
        vector<int> d2= divide(vec, (right+left) / 2, right);
        int d = 0;
        int point1;
        int point2;
        if(d1[0]>d2[0]){
            d = d2[0];
            point1 = d2[1]; 
            point2 = d2[2];
        }
        else {
            d = d1[0];
            point1 = d1[1]; 
            point2 = d1[2];
        }
        int l = getPos(left, (right + left) / 2, vec, d, goleft);
        int r = getPos((right + left) / 2, right, vec, d, goright);
        for (int i = l; i < (right + left) / 2;++i){
            if(l==-1||r==-1)
                break;
            int count = 0;
            for (int j = (right + left) / 2; j <=r;++j) {
                int temp = getDist(vec[i], vec[j]);
                if(count>7)
                    break;
                ++count;
                if(temp < d){
                    d = temp;
                    point1 = i; 
                    point2 = j;
                }
            }
        }
        vector<int> dPoint = {d, point1, point2};
        return dPoint;
    }
    
    int main() {
        // int n;
        // cin >> n;
        // int x, y;
        // vector<pair<int,int>> point;
        // for (int i = 0; i < n; ++i) {
        //     cin >> x >> y;
        //     point.push_back(make_pair(x,y));
        // }
        vector<int> xpts = {0, 1,  5, 12, 17, 21, 24, 6, 19, 3, 9, 15, 7, 11, 6, 16};
        vector<int> ypts = {4, 9, 11, 12, 12,  9,  7, 0,  1, 8, 9,  8, 6,  6, 2,  2};
        vector<pair<int, int>> pts;
        for (int i = 0; i < xpts.size(); ++i) {
            pts.push_back(make_pair(xpts[i], ypts[i]));
        }
        sort(pts.begin(), pts.end());
        for(auto p:pts){
            cout << p.first << "," << p.second << endl;
        } 
        vector<int> d = divide(pts, 0, pts.size() - 1);
        cout << d[0] << endl;
        cout << pts[d[1]].first << "," <<pts[d[1]].second<< endl;
        cout << pts[d[2]].first << "," << pts[d[2]].second << endl;
        system("pause");
        return 0;
    }
    

    杭电1007

    Have you ever played quoit in a playground? Quoit is a game in which flat rings are pitched at some toys, with all the toys encircled awarded.
    In the field of Cyberground, the position of each toy is fixed, and the ring is carefully designed so it can only encircle one toy at a time. On the other hand, to make the game look more attractive, the ring is designed to have the largest radius. Given a configuration of the field, you are supposed to find the radius of such a ring.
    Assume that all the toys are points on a plane. A point is encircled by the ring if the distance between the point and the center of the ring is strictly less than the radius of the ring. If two toys are placed at the same point, the radius of the ring is considered to be 0.

    展开全文
  • 问题描述: 方法一:蛮力算法:倘若在n个点中进行两两遍历对比,就要比较n*(n-1)/2次,时间复杂度...于是可以先简化我们的问题,那么如何用分治的方法去考虑一维的情形: 用中位数,那么可不可以用平均数呢? ...
  • 给定平面S上n个,找其中的一对,使得在n个组成的 所有点对中,该点对间的距离最小。 假设所讨论的是以标准笛卡儿坐标形式(x, y)给出的。因 此,在两个Pi =(xi , yi )和Pj =(xj , yj )之间的距离是标准的...
  • 算法设计与分析 实验二 分治法求解最近点对问题

    千次阅读 多人点赞 2021-06-07 01:06:36
    分治法求解最近点对问题一、实验目的与要求1、实验基本要求:2、实验亮点:二、实验内容与方法三、实验步骤与过程(一)一些准备工作1、实验流程2、数据生成与去除重复点(二)暴力穷举法1、算法描述2、时间复杂度...
  • 3. 要求随机生成N个的平面坐标,应用分治法编程计算出所有点对的最短距离。 4. 分别N=100,1000,10000,100000,统计算法运行时间,比较理论效率与实测效率的差异,同时蛮力法和分治法的算法效率进行分析和比较...
  • 分治法最近点对

    2013-10-27 22:17:36
    资源位分治法最近点对,包含几种算法,以及图形界面,是一套完整的工程。全部为java实现。
  • 讲解分治法最近点对问题的思想与算法实现。 利用分治法最近点对与归并排序的结构上的相同,将时间复杂度降到真正意义上的O(nlogn)而不是O(nlognlogn)。 1. 预处理:创建结构体Node附带属性x,y表示在平面...
  • (2)学会最近点对问题求解方法。 二、内容: 对于平面上给定的N个点,给出所有点的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。 要求随机生成N个点的平面坐标,应用蛮力编程计算出...
  • 分治法最近点对.cpp

    2020-04-08 19:55:39
    对于短路的你,希望算法代码给你一个新的思路,代码的讲解利于你更好的对于题目的详细解释同时学会方法,利于自身的创新
  • 分治法最近点对问题,要求:1. 对于平面上给定的N个点,给出所有点的最短距离,即,输入是平面上的N个点,输出是N点中具有最短距离的两点。 2. 要求随机生成N个点的平面坐标,应用蛮力法编程计算出所有点的...
  • 分治法解决最近点对问题:python实现
  • 分治法详解二维最近点对问题

    千次阅读 多人点赞 2020-04-14 16:47:31
    算法设计与分析——分治法:详解二维最近点对问题1 前言2 问题描述3 分治法4 暴力求解4.1 算法思路4.2 时间复杂度分析4.3 代码实现5 分治法求解5.1 算法思路5.1.1 数据预处理5.1.2 划分中轴线5.1.3 求半边最小距离...
  • 【算法设计与分析】分治法最近点对问题

    千次阅读 多人点赞 2018-10-15 17:26:32
    说明:这是武汉理工大学计算机学院【算法设计与分析】课程的第一次实验第三题:分治法最近点对问题 >>点击查看WUTer计算机专业实验汇总 谨记:纸上得来终觉浅,绝知此事要躬行。 一、问题描述 设,,…...
  • 分治法最近点对 分治法 分治法将一个难以直接解决的大问题划分成一些规模较小的子问题,分别求解各个子问题,再合并子问题的解得到原问题的解。 一般来说,分治法的求解过程由以下三个阶段组成: 划分:把规模为n的...
  • 对于最近点对问题,采取了暴力破解与分治法解决
  • 最接近点对-分治法-C++实现

    千次阅读 2020-01-11 18:39:36
    本实验使用了分治法的算法思想,所谓分治,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。...
  • 分别用暴力法和分治法 求解最近点对问题 C++代码 网盘链接
  • 本资源为文档类型,内有相关代码,题目是用分治法解平面最近点对问题,希望有帮助!
  • c语言 分治法求解最近点对问题

    千次阅读 2018-10-22 21:13:33
    最近对问题(二维平面上的点),编程实现用分治法求解。 最近点对算法: double cpair2(S) {  n=|S|;  if (n &lt; 2) return 0; 1)、m=S中各点x坐标的中位数;  //构造S1和S2;  S1={p∈S|x(p)&...
  • 分治法最近点对的程序用分治法最近点对的程序用分治法最近点对的程序用分治法最近点对的程序用分治法最近点对的程序
  • 这是算法作业,最近点对问题,采用分治策略。资源内包括全部代码,和exe文件。以文件形式读入所有点的位置,文件在Debug文件夹内和exe文件放在一起。
  • 分治法求解最近点对问题

    千次阅读 2020-03-28 21:32:49
    一、求解最近点对问题问题描述】给定平面S上n个点...(1)蛮力求解最近点对问题 double ClosestPoints(vector<Point> a,int leftindex,int rightindex) { int i,j; double d,mindist =INF; for (i=le...
  • 分别用暴力和递归方法实现了最近点对的计算,并且带有图形界面!

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 71,982
精华内容 28,792
关键字:

最近点对问题分治法