最近点对的高效算法

‘壹’ 求最近点对的分治算法采用了哪些措施降低时间复杂性

动态规划与分治策略都是将一个问题分解成为若干子问题，动态规划和分治相比，则有一个非常有用的性质，就是 动态规划中使用的子问题有大部分都是相同的（重叠子问题），这样我就可以通过记录每个子问题的答案使得 每个子问题 不被重复计算

‘贰’ 杭电acm1007，超时了，求更快的算法

n^2必然超时，这是一个很经典的分治问题，时间复杂度O(NlogN)。

首先按x轴排序，把点集分成左右两半，那么最近点对只有三种可能：都在左边，都在右边，一左一右。对于前两种情况可以递归下去，然后现在我们来找一左一右的最近点对。这道题的精华就在此，只需要在开始按y轴排序一次然后扫描一遍就可以找出来。

网上找一下“最近点对”，有很多题解。因为这道题思考起来确实有难度，你若不懂我把QQ给你详细讲。。

‘叁’ 关于最近点对算法

你可以去csdn上找博文介绍，有详细的介绍，在这里说不清楚

‘肆’ C语言课设，最近点对问题，求大神用分治法做出来，图片是具体要求，谢谢😜

#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<time.h>

typedefstruct
{
doublex;
doubley;
}Building;

//创建所有建筑的坐标
Building*creatCoordinate(intiBuilNum)
{
inti,j;
doublex,y;
srand((int)time(NULL));
Building*bBuil=(Building*)malloc(sizeof(Building)*iBuilNum);
for(i=0;i<iBuilNum;i++)
{
x=(rand()%10000)*0.01;
y=(rand()%10000)*0.01;
for(j=0;j<i;j++)
{
if(x==bBuil[j].x&&y==bBuil[j].y)
{
i--;
continue;
}
}
bBuil[i].x=x;
bBuil[i].y=y;
}

returnbBuil;
}

//求两点间的距离
doublegetDis(BuildingbA,BuildingbB)
{
doubledDifferenceX=bA.x-bB.x;
doubledDifferenceY=bA.y-bB.y;
returnsqrt(dDifferenceX*dDifferenceX+dDifferenceY*dDifferenceY);
}

//求所有点间的距离
double*getAllDis(Building*abCoordinate,intiBuilNum,intiDisNum,int*aiMinIndex)
{
inti,j,k;
doubledMin=1000.0;
double*adDis=(double*)malloc(sizeof(double)*iDisNum);
for(i=iBuilNum-1,k=0;i>0;i--)
{
for(j=i;j>0;j--)
{
//printf("%d%d
",iBuilNum-i-1,iBuilNum-j);
adDis[k]=getDis(abCoordinate[iBuilNum-i-1],abCoordinate[iBuilNum-j]);
//截取最小距离
if(adDis[k]<dMin)
{
dMin=adDis[k];
//截取最小距离相应坐标数组的下标
aiMinIndex[0]=iBuilNum-i-1;
aiMinIndex[1]=iBuilNum-j;
}
k++;
}
}

returnadDis;
}

intmain(void)
{
intiBuilNum,iDisNum=0,aiMinIndex[2],i;
printf("%s
","请输入建筑物数量：");
scanf("%d",&iBuilNum);
for(i=1;i<iBuilNum;i++)
iDisNum+=i;

Building*abCoordinate=creatCoordinate(iBuilNum);
double*adDis=getAllDis(abCoordinate,iBuilNum,iDisNum,aiMinIndex);

//输出所有坐标
printf("%s
","所有建筑物的坐标为：");
for(i=0;i<iBuilNum;i++)
printf("x:%0.2lfy:%0.2lf
",abCoordinate[i].x,abCoordinate[i].y);

//输出距离最近两个点的坐标
printf("%s
","距离最近两个建筑物的坐标为：");
printf("x:%0.2lfy:%0.2lf
",abCoordinate[aiMinIndex[0]].x,abCoordinate[aiMinIndex[0]].y);
printf("x:%0.2lfy:%0.2lf
",abCoordinate[aiMinIndex[1]].x,abCoordinate[aiMinIndex[1]].y);

//输出距离最近两个点的距离
printf("%s
","距离最近两个建筑物的距离为：");
printf("%0.2lf
",getDis(abCoordinate[aiMinIndex[0]],abCoordinate[aiMinIndex[1]]));

//输出所有距离
//printf("%s
","所有建筑物的距离为：");
//for(i=0;i<iDisNum;i++)
//printf("%0.2lf
",adDis[i]);

free(abCoordinate);
free(adDis);

return0;
}

‘伍’ 最近点对问题

#include<stdio.h>
#include<math.h>
void main()
{
int n,i,j,k=0;
float a[5000],b[5000],c[5000],min;
printf("请输入点的数目：");
scanf("%d",&n);
printf("请输入点的坐标：");
for(i=0;i<n;i++)
scanf("%f%f",&a[i],&b[i]);
min=(a[0]-a[1])*(a[0]-a[1])+(b[0]-b[1])*(b[0]-b[1]);
for(j=0;j<n-1;j++)
for(i=j+1;i<n;i++)
{
c[k]=(a[j]-a[i])*(a[j]-a[i])+(b[j]-b[i])*(b[j]-b[i]);
c[k]=sqrt(c[k]);
if(c[k]<min)
{min=c[k];}
k++;
}
min=(int)(min*100)+0.5;
min=min/100;//四舍五入
printf("%.2f\n",min);
}

‘陆’ 已知点求与已知点集中的最近点的算法

可以用四叉树（二维）或者八叉树（三维）来对点分组，把空间分块，计算每块的中心点坐标即为树的中间结点，与其距离小于组半径的即为其组内的叶节点。已知点所在的组可以根据要求再缩短半径细分，直到点的数量达到要求。

八叉树参考：http://en.wikipedia.org/wiki/Octree

‘柒’ java找出距离最近的点对怎么把点从文件导入我的TXT文件写入了很多点，放在FindNearestPoints同一目录

思路: 1 . 为了符合面对对象编程的需要, 为了少写二维数组, 点坐标,可以封装成一个Point对象

classPoint{
	doublex;//点对象的属性:x坐标
	doubley;//点对象的属性:y坐标
	//点坐标创建时,需要传入2个参数,一个x坐标,一个y坐标
	publicPoint(doublex,doubley){
		this.x=x;//把传入的x坐标赋值给属性x
		this.y=y;//把传入的y坐标赋值给属性y
	}
	publicStringtoString(){//重写Object类的toString方法
		return"("+x+","+y+")";//方便我们需要打印输出时,得到字符串
	}
}

参考代码

importjava.io.BufferedReader;
importjava.io.FileReader;
importjava.io.IOException;

classPoint{
	doublex;
	doubley;
	
	publicPoint(doublex,doubley){
		this.x=x;
		this.y=y;
	}
	publicStringtoString(){
		return"("+x+","+y+")";
	}
}
publicclassFindNearestPoints{
//文本格式点的x,y坐标用逗号隔开,每个点之间用空格隔开,具体如下
//6,57.1,3.54.2,3.89,67.5,3.44.1,3.9
	publicstaticvoidmain(String[]args){
		Point[]ps=null;
		try{
			BufferedReaderbr=newBufferedReader(newFileReader("d:\FineNearestPoints.txt"));
			StringBuffersbf=newStringBuffer();
			Stringstr=null;
			while((str=br.readLine())!=null){
				sbf.append(str.trim());
			}
			br.close();//流用完要关闭
			Strings=sbf.toString();
			String[]ss=s.split("");//用空格,把字符串切割出来,每个字符串都包含一个点比如"6,5"
			ps=newPoint[ss.length];
			for(inti=0;i<ss.length;i++){
				String[]temp=ss[i].split(",");//用逗号把字符串切割成两部分,比如"6""5"
				doublex=Double.parseDouble(temp[0]);//字符串"6"-->解析成数字6
				doubley=Double.parseDouble(temp[1]);
				Pointp=newPoint(x,y);//创建点对象
				ps[i]=p;//把点存入数组
			}
		}catch(IOExceptione){
			e.printStackTrace();
		}
		doublemindis=distance(ps[0],ps[1]);//假定第一个和第二个坐标最近
		Point[]p2={ps[0],ps[1]};
		for(inti=1;i<ps.length;i++){
			for(intj=i+1;j<ps.length;j++){//为了让点不和自身的距离比较,所以j=i+1
				if(distance(ps[i],ps[j])<mindis){//如果比假设的最近距离还要近,那么暂时他们就最近
					mindis=distance(ps[i],ps[j]);
					p2[0]=ps[i];
					p2[1]=ps[j];
				}
			}
		}
		System.out.println("最近的点距离为:"+mindis);
		System.out.println("最近的点对是:"+p2[0]+"<=>"+p2[1]);
	}
	publicstaticdoubledistance(doublex1,doubley1,doublex2,doubley2){
		returnMath.sqrt((x2-x1)*(x2-x1)+(y2-y1)*(y2-y1));
	}
	
	publicstaticdoubledistance(Pointp1,Pointp2){
		returndistance(p1.x,p1.y,p2.x,p2.y);
		//returnMath.sqrt((p2.x-p1.x)*(p2.x-p1.x)+(p2.y-p1.y)*(p2.y-p1.y));
	}
}

最近的点距离为:0.14142135623730995
最近的点对是:(4.2,3.8)<=>(4.1,3.9)

‘捌’ ZJU2107最近点对

最接近的点或者x坐标相邻，或者y坐标相邻，只要排两次序，取相邻两点距离即可得到答案，复杂度为(2nlogn+2n)

var a:array[1..100000] of longint;
b:array[1..100000,1..2] of real;
q,w:real;
i,j,k,l,o,p,n,m:longint;

procere sortx(l,r:longint);
var i,j,k:longint;
o,p:real;
begin
i:=l;j:=r;o:=b[a[(i+j) div 2],1];p:=b[a[(i+j) div 2],2];
while i<=j do
begin
while (b[a[i],1]<o) or ((b[a[i],1]=o) and (b[a[i],2]<p)) do inc(i);
while (b[a[j],1]>o) or ((b[a[j],1]=o) and (b[a[j],2]>p)) do dec(j);
if i<=j then begin
k:=a[i];a[i]:=a[j];a[j]:=k;
inc(i);dec(j);
end;
end;
if i<r then sortx(i,r);
if l<j then sortx(l,j);
end;

procere sorty(l,r:longint);
var i,j:longint;
o,p:real;
begin
i:=l;j:=r;o:=b[a[(i+j) div 2],1];p:=b[a[(i+j) div 2],2];
while i<=j do
begin
while (b[a[i],2]<p) or ((b[a[i],2]=p) and (b[a[i],1]<o)) do inc(i);
while (b[a[j],2]>p) or ((b[a[j],2]=p) and (b[a[j],1]>o)) do dec(j);
if i<=j then begin
k:=a[i];a[i]:=a[j];a[j]:=k;
inc(i);dec(j);
end;
end;
if i<r then sorty(i,r);
if l<j then sorty(l,j);
end;

begin
read(n);
while n>0 do
begin
for i:=1 to n do begin a[i]:=i;read(b[i,1],b[i,2]);end;
q:=maxlongint;
sortx(1,n);
for i:=1 to n-1 do
begin
w:=sqrt((b[a[i+1],1]-b[a[i],1])*(b[a[i+1],1]-b[a[i],1])+(b[a[i+1],2]-b[a[i],2])*(b[a[i+1],2]-b[a[i],2]))/2;
if q>w then q:=w;
end;
sorty(1,n);
for i:=1 to n-1 do
begin
w:=sqrt((b[a[i+1],1]-b[a[i],1])*(b[a[i+1],1]-b[a[i],1])+(b[a[i+1],2]-b[a[i],2])*(b[a[i+1],2]-b[a[i],2]))/2;
if q>w then q:=w;
end;
writeln(q:0:2);
read(n);
end;
end.

‘玖’ 高分求算法：寻找与特定对象距离最近的对象

用现在的ID,X,Y三个元素来找最近点的话无论什么办法,都至少要与每个点进行一次距离的判断,比较X或者Y也好,计算距离(当然这个距离是不用开平方的,与其他所有点的距离都不开平方也能比较相对的距离长短)也好,所以如果只有这三个元素的话,其实再怎么改也不会有太大的优化的。

最好还是添加一些辅助信息，比较常用的就是以划分网格的方法，将所有点分派在不同的网格中，然后以网格为基础找最近点，这样的话就要加一个网格的结构（以空间换时间），里面存放的就是属于这个网格的点的ID，通过编号规则可以很快的找最近的网格，然后再找里面的点，这样可以提高点查找速度。

呵呵,不好意思,没想清楚就写了:P,改一下,改一下,再加一步就好了

1.给点添加一个所属网格的信息:
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
}
2.构造一个点链表,这是为了减少空间和方便处理而加的,后面的算法里会感觉到用处
(为每个点对象建立一个点链表节点)
Class I
{
public A *pAObject; //指向一个点对象
publci I *pNextA; //指向下一个
}
3.构件一个网格信息结构
Class G
{
public int ID; //网格编号
public I *pAObjects; //指向一个点链表(至于这个是带头节点还是不带头节点的都一样啦)
//这里用链表比较好
//第一,因为点可移动,那么点对象个数可以随意,可以发挥链表的扩展性
//第二,不需要取中间节点,也就没有用到数组的长处
}
4.构建网格,比如以1000为长度(长度可以自己定义,关键是平衡空间和速度关系),建立正方形的网格,那么(0,0)到(1000000,1000000)就是有1000*1000个网格(在给网格编号的时候最好有规律,那么就能通过List或者其他数组容器的下标来获得网格信息)
5.添加点的时候,先判断属于哪个网格,然后在点信息中添加网格编号,同时构建对应的点链表节点,并添加到所属网格的链表中
6.最后就是查询点了,首先获得出发点中的所属网格信息,看这个网格中是否有其他点:有,则一个个的判断距离(距离的平方),那么最近点一定在这些点里面(如果点还是太多,那么就考虑缩小网格的范围);没有,那就找所属网格周边8个网格中是否有点,有,则再找最近点,没有就再往外扩(如果感觉网格太多,可以加大网格的范围)
7.以找到的最近点到出发点的距离为基准,看看出发点到周边网格在这个距离内会接触到的(没有在6中遍历过的)有几个网格,把这些网格中的点再查看有没有更近的就行了

注:
1.如果还要优化就是加大网格的层次,可以用多层网格,这就会更复杂一点
2.在网格信息结构(G)中,因为点会移动,那么删点链表节点会有一个查找过程,如果觉得这个慢,那么就在点对象结构体中加一个所属点链表的指针:
class I;
Class A
{
public int ID;
public int X;
public int Y;
publci int Index;//所属网格编号
publci I *pI;
}
....

呵呵，看了lipai006的回答，想了下似乎也是可以实现的，只要多花点内存就可以达到比较好的速度了，而且也不需要真的从X坐标出发这样慢慢的以扇形扩展了啦，通过做一些辅助结构，就直接可以从出发点的X坐标出发，找同X不同Y中Y坐标与出发点最近的就行啦，循环结束条件就是X的扩展距离已经大于当前最小距离，因为再往外也肯定比当前最小距离大了。这个方法也就是要更复杂一些的辅助结构做索引，添加点的时候也要多做些事情，而且实现上的代码相对网格方法复杂一些，但查找速度应该比网格会快一点，因为毕竟是直接找点去了，其实网格方法就是把一批点的X，Y坐标看成是一样的，这样先过滤一批而已，是个速度与复杂度的折中。

xx_lzj:划分区域的目的就是为了使每个区域内的点不能太多，根据我的结构，每个区域有没有点，一个bool判断就够了，不会存在太稀疏影响效率的事情，不过最坏的情况的确会退化到遍历整个点空间，所以这个方法的时间复杂度仍然是O(n)。
你的方法其实和lipai006说的原理是差不多的（如果我对你们链表结构的猜想准确的话），无非就是通过X,Y坐标形成一个二维双向链表，在形成这个链表的过程会比网格相对复杂一点，而且也不是像你想的只要判断8个点就够的，当只有一个点在中间，其他点分布成以这个点为圆心的圆周上时，按照贴主的要求，难道只有8个最近点吗？？在这个情况下，你的最坏复杂度还是O(n)，但就如我说过的，这个方法的平均时间复杂度在参数上是会比网格的低一点，但是算法本身的代码复杂度上会高一点，而且在插入点的过程中的时间消耗会大一点而已。我觉得这是一个整体的过程，不能为了查找的快速牺牲太多其他的时间。
*************
xx_lzj:不好意思，你的链表我还有些不明白的地方:1.二维双向链表每个节点有4个指针，你能否把这4个指针如何获得的说一下，最好不要取边界线上的点，取中间的一个点进行介绍。2.对于初始化和修改点坐标的时候，现有数据如果是链表结构（不是数组），如何能不依靠其他辅助数据进行折半查找？3.修改某个点坐标之后，根据你的链表结构，我感觉不是删除、插入节点这么简单的，能不能具体点说明。