最近點對的高效演算法

『壹』 求最近點對的分治演算法採用了哪些措施降低時間復雜性

動態規劃與分治策略都是將一個問題分解成為若乾子問題，動態規劃和分治相比，則有一個非常有用的性質，就是 動態規劃中使用的子問題有大部分都是相同的（重疊子問題），這樣我就可以通過記錄每個子問題的答案使得 每個子問題 不被重復計算

『貳』 杭電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.修改某個點坐標之後，根據你的鏈表結構，我感覺不是刪除、插入節點這么簡單的，能不能具體點說明。