最近點對問題演算法

A. 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;
}

B. 最近點對問題

#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);
}

C. python如何在眾多的點中找到與特定點最近的點的演算法

首先目測一下查詢大概不止一次所以前面那些統統乘個Q就大爆炸吧。
平民的做法寫個kdtree基本sqrt n復雜度對付10w的數據量應該輕松愉快，動態的話套個替罪羊。
泥垢無聊的話動態v圖歡迎入坑 傳聞是logn的我沒寫過不知道會不會比上面的慢。
啊找到了我記得這個大輪子應該可以很簡單（不如手寫）的解決你的問題
PCL - Point Cloud Library (PCL)
-

單純的替罪羊套kdt放到這種場合可能不大合適……畢竟修改一次可能鎖死整個子樹……（當然可以不用替罪羊，緩存sqrt n個修改，然後每sqrt n個修改暴力重構整個樹，重構完成之前就先用原來的，然後再加上各種奇怪的優化……。）
然後再YY一下，我個人覺得他們可能是這樣乾的，首先把地圖切成一塊一塊的每塊足夠小。然後隨便YY一下按照每個地方人數的多少，取一個合適的am^2范圍內最多有x人，然後只要這個x夠小，查詢的時候只查詢當前用戶所在的區塊和周圍的幾個區塊就好了，然後你就可以用輪子哥那樣的sql查詢啦～
如果還是有問題要麼加伺服器，或者最不濟還可以對這個區塊再維護kdtree。而且這樣修改起來還方便。
至於用戶周圍都沒有人，最近的有人區塊在幾十公里外…

D. 高分求演算法：尋找與特定對象距離最近的對象

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