蠻力算法最近對(duì)

問(wèn)題描述：
一個(gè)包含n個(gè)點(diǎn)的集合中，找出距離最近的兩個(gè)點(diǎn)。
問(wèn)題分析：
假設(shè)所考慮的點(diǎn)是以標(biāo)準(zhǔn)的笛卡爾坐標(biāo)形式（ x ，y ）給出的，兩個(gè)點(diǎn)pi = （ xi ，yi ）和 pj =（ xj，yj ）之間的距離是標(biāo)準(zhǔn)的歐幾里得距離

顯然求解該問(wèn)題的蠻力算法應(yīng)該是：分別計(jì)算每一對(duì)點(diǎn)之間的距離，然后找出距離最小的那一堆。當(dāng)然為了提高算法的效率，我們并不希望同一對(duì)點(diǎn)計(jì)算兩次距離，所以我們只考慮 i < j 的那些對(duì)（ pi ， pj）。
算法
BruteForceClosePoints( p )
//使用蠻力算法求平面中距離最近的兩個(gè)點(diǎn)
//輸入：一個(gè) n （n >= 2）個(gè)點(diǎn)的列表 p ， p1 = （ x1，y1 ），… pn = ( xn, yn )
//輸出：兩個(gè)最近點(diǎn)的距離
d <-- ∞
for i <–1 to n -1 do
for j <-- i + 1 to n do
d <-- min( d, sqrt( xi - xj )2 + （ yi - yj )2
return d
算法優(yōu)化
該算法的基本操作就是計(jì)算平方根，，整數(shù)的平方根大多是無(wú)理數(shù)，只能對(duì)它們近似求解，而計(jì)算這些近似數(shù)也不是一件輕松的事。實(shí)際上，我們可以避免求平方根，只比較其值的本省。因?yàn)槿绻婚_(kāi)方數(shù)越小，它的平方根也越小，平方根函數(shù)是嚴(yán)格遞增的
核心代碼

void FindClosest(Postion P[], int n){double min = 10000;double d;for(int i = 0; i < n - 1; i++){for(int j = i + 1; j < n; j++){d = (P[i].x - P[j].x)*(P[i].x - P[j].x) + (P[i].y - P[j].y)*(P[i].y - P[j].y);if(d < min){min = d;}}} }

代碼實(shí)現(xiàn)

/*最近對(duì)問(wèn)題*/ #include<stdio.h>struct Postion{double x;double y; }P[100];void BruteForceClosePoints(Postion P[], int n, int *index1, int *index2){double min = 10000;double d;for(int i = 0; i < n - 1; i++){for(int j = i + 1; j < n; j++){d = (P[i].x - P[j].x)*(P[i].x - P[j].x) + (P[i].y - P[j].y)*(P[i].y - P[j].y);if(d < min){min = d;*index1 = i;*index2 = j;}}}printf("第%d個(gè)點(diǎn)到%d個(gè)點(diǎn)距離最短為%lf", *index1 + 1, *index2 + 1, min); }int main(){int n, index1,index2;printf("請(qǐng)輸入點(diǎn)個(gè)數(shù)\n");scanf("%d", &n);for(int i = 0; i < n; i++){printf("請(qǐng)輸入第%d個(gè)點(diǎn)的xy值\n", i+1);scanf("%lf%lf", &P[i].x, &P[i].y);} BruteForceClosePoints(P, n, &index1, &index2); }

運(yùn)行結(jié)果

代碼分析
算法的時(shí)間復(fù)雜度為 C（n）= O（n2）
雖然加快了算法執(zhí)行內(nèi)層循環(huán)的速度，但對(duì)算法運(yùn)行時(shí)間的提升只是微乎其微的，并不能改變其漸進(jìn)效率類(lèi)型。

總結(jié)
寫(xiě)博客是為了一是整理所學(xué)知識(shí)，親生寫(xiě)代碼的經(jīng)驗(yàn)，而是為了總結(jié)經(jīng)典算法，三是督促自己努力，懂得越多，越知道自己知識(shí)的淺薄，四是希望和他人多多交流，有什么不對(duì)的地方大佬們多多指點(diǎn)

總結(jié)

以上是生活随笔為你收集整理的蛮力算法求解最近对的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。