算法分析:求最近点对问题(c++)

1、 准备部分:
对于最近点问题,需要将问题代码化,所以要先创建一个点类,来使得计算使用时候更加方面,
class Points //点类 { public: float x; float y; };
因为会多次计算距离,需要一个计算两点之间距离的函数。
float Distance(Points p1,Points p2)//求两点距离函数 { return sqrt((p1.x-p2.x)*(p1.x-p2
.x)+(p1.y-p2.y)*(p1.y-p2.y)); } 但这里改进将开根号放在外面可以使得计算量减少。 float Distance(Points
p1,Points p2)//求两点距离函数 { return (p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y);
}
2、 穷举法
算法思想:
遍历每个个点,将每个点与另外其他所有个点求距离,然后找到最短的那根距离,同时保留点对返回。

实现代码:

遍历每个点,使用两个循环,每次求和,第i个只用和第i+1到n的数去比较,因为前面的数已经比较过,不必重复计算。一开始最小值为无穷大,计算出来的距离一个个比较,如果比最小值小,就将其的值替换,保存点对。
for (int i=0; i<length-1; i++) { for(int j=i+1; j<length; j++) { float temp =
Distance(p[i],p[j]);if (temp < min_dis) { min_dis = temp; a = p[i]; b = p[j]; }
} }
3、 分治法
函数名:
float merge_distance(Points* po,int len,Points &a,Points &b)
参数:
po排好序的点集,len为点的数量,a保存第一个点,b保存第二点。

算法思想及代码解释:
把二维先看成一维数组,按照x轴将所有点排序。
代码实现:
sort(p, p+length, CmpX); //排序 min_dis = merge_distance(p, length, a, b);
//调用函数
点数较少情形。

代码实现:
if(len < 2) return na_n;//无穷大 if(len == 2) { a = po[0]; b = po[1]; dis =
Distance(po[0],po[1]); }
点数|S|>3时,将平面点集S分割成为大小大致相等的两个子集SL和SR,选取一个垂直线mid作为分割直线。

代码实现:
else //len>=3 { Points *p1 = new Points[len/2+1]; //左边点 Points *p2 = new
Points[len/2+1]; //右边点 float mid = po[(len-1)/2].x; int i=0, j=0, k1=0, k2=0;
for(i=0; i<len/2; i++) //得到左边点 p1[i] = po[j++]; //得到右边点 for(i=0; i<len/2; i++)
p2[i] = po[j++]; d1 = merge_distance(p1,len/2, a1, b1);//左边递归 d2 =
merge_distance(p2,len-len/2, a2, b2);//右边递归
使用两个递归调用分别找到两边各自区域中最短距离,为d1、d2,d=min{d1,d2}

代码实现:
if (d1 < d2) { dis = d1; a = a1; b = b1; } else { dis = d2; a = a2; b = b2; }
再考虑跨界区域之间点的距离,按照上面得到的d,在中线两边画出2d的区域,因为超过这个区域,左边到右边点必然超出d的距离,为了减少计算,先对x轴切割。

代码实现:
Points *p3 = new Points[len/2]; //d区左边 Points *p4 = new Points[len-len/2];
//d区友边 for(i=0, k1=0; i<len/2; i++) //x轴左边切割 if((mid - po[i].x) <= dis)
p3[k1++] = po[i];for(i=0, k2=0; i<(len-len/2); i++) //x周右边切割 if((po[i].x - mid)
>= dis) p4[k2++] = po[i];
为了更加减少计算,在遍历左边d内的所有点的时候,对面d内的点处理,将其y轴切割,也按d来划出d*2d的区域。因为超出这个区域也不可能比d小。

代码实现:
for(i=0; i<k1; i++) { for(j=0; j<k2; j++) { if( abs(p3[i].y - p4[j].y) < dis)
//y轴切割 { float temp = Distance(p3[i],p4[j]); if(temp < dis) { dis = temp; a =
p3[i]; b = p4[j]; } } } }
完整全部代码展示(进行过优化),将计算距离的开根号,拿到最外面
#include <iostream> #include <time.h> #include <cmath> #include <sys/timeb.h >
#include <windows.h> #include <limits> #include <algorithm> #define Example_num
2 using namespace std; class Points //点类 { public: float x; float y; }; bool
CmpX(Points a, Points b) {return a.x < b.x; } class Handles { public: int
length;float min_dis; float na_n; double p_time; Points *p; Handles(){} Handles(
int n) { na_n = numeric_limits<float>::max(); min_dis = na_n; length = n; p =
new Points[length]; set_points(); } void set_points() { struct timeb timeSeed;
ftime(&timeSeed); srand(timeSeed.time *1000 + timeSeed.millitm); for(int i=0;
i<length; i++) { p[i].x = rand()/10.00000000; p[i].y = rand()/10.00000000; } }
float Distance(Points p1,Points p2) { return
((p1.x-p2.x)*(p1.x-p2.x)+(p1.y-p2.y)*(p1.y-p2.y)); }float exhaustion_Distance()
{ Points a,b; LARGE_INTEGER li, freq; QueryPerformanceCounter(&li);long long
p_start = li.QuadPart; QueryPerformanceFrequency(&freq);for (int i=0; i<length-1
; i++) {for(int j=i+1; j<length; j++) { float temp = Distance(p[i],p[j]); if
(temp < min_dis) { min_dis = temp; a = p[i]; b = p[j];/*if (min_dis ==0)
cout<<p[i].x<<' '<<p[i].y<<' '<<p[j].x<<' '<<p[j].y<<endl;*/ } } }
QueryPerformanceCounter(&li);long long p_end = li.QuadPart; p_time = (p_end -
p_start)*1000./freq.QuadPart; cout<<"最短距离为"<<sqrt(min_dis)<<' '; cout<<'('
<<a.x<<','<<a.y<<')'<<','<<'('<<b.x<<','<<b.y<<')'<<' '; cout<<p_time<<"ms"<<' '
<<endl;return min_dis; } float merge_dis() { Points a,b; LARGE_INTEGER li,
freq; QueryPerformanceCounter(&li);long long p_start = li.QuadPart;
QueryPerformanceFrequency(&freq);//计算时间 sort(p, p+length, CmpX); //排序 min_dis =
merge_distance(p, length, a, b);//调用函数 QueryPerformanceCounter(&li); long long
p_end = li.QuadPart; p_time = (p_end - p_start)*1000./freq.QuadPart; cout<<
"最小距离为"<<sqrt(min_dis)<<' '; cout<<'('<<a.x<<','<<a.y<<')'<<','<<'('<<b.x<<','
<<b.y<<')'<<' '; cout<<p_time<<"ms"<<' '<<endl; } float merge_distance(Points*
po,int len,Points &a,Points &b) { float dis; float d1,d2; Points a1,b1,a2,b2; if
(len <2) return na_n; //只有一个点无穷大 if(len == 2) //两个点直接计算 { a = po[0]; b = po[1];
dis = Distance(po[0],po[1]); } else //len>=3 { Points *p1 = new Points[len/2+1];
//左边点 Points *p2 = new Points[len/2+1]; //右边点 float mid = po[(len-1)/2].x; int
i=0, j=0, k1=0, k2=0; for(i=0; i<len/2; i++) //得到左边点 p1[i] = po[j++]; //得到右边点
for(i=0; i<len/2; i++) p2[i] = po[j++]; d1 = merge_distance(p1, len/2, a1, b1);
//左边递归 d2 = merge_distance(p2, len-len/2, a2, b2);//右边递归 if (d1 < d2) { dis =
d1; a = a1; b = b1; }else { dis = d2; a = a2; b = b2; } Points *p3 = new
Points[len/2]; //d区左边 Points *p4 = new Points[len-len/2]; //d区友边 for(i=0, k1=0;
i<len/2; i++) //x轴左边切割 if((mid - p[i].x) <= dis) p3[k1++] = po[i]; for(i=0, k2=0
; i<(len-len/2); i++) //x周右边切割 if((po[i].x - mid) <= dis) p4[k2++] = po[i]; for
(i=0; i<k1; i++) { for(j=0; j<k2; j++) { if( abs(p3[i].y - p4[j].y) < dis)//y轴切割
{float temp = Distance(p3[i],p4[j]); if(temp < dis) { dis = temp; a = p3[i]; b
= p4[j]; } } } }delete []p1; delete []p2; delete []p3; delete []p4; } return
dis; } ~Handles() {delete []p; } }; int main() { int x = 0; bool key = true;
while(x<2) { int n = 10; if(key) {cout<<"穷举法"<<endl;cout<<"样本大小:"
<<Example_num<<endl;}else {cout<<"分治法"<<endl;cout<<"样本大小:"<<Example_num<<endl;}
for(int i=0; i<4; i++) { double time_ave = 0; n = n*10; cout<<"规模为"<<n<<endl;
for(int k=0; k<Example_num; k++) { Handles h(n); if (key)
h.exhaustion_Distance();else h.merge_dis(); time_ave += h.p_time; } cout<<
"平均时间为"<<time_ave/Example_num<<"ms"<<endl; cout<<endl; } x++; key = false; } cin
>>x;return 0; }

技术
©2019-2020 Toolsou All rights reserved,
年薪20万属于什么水平?答案让人扎心!连 CEO 都不香了?这些互联网大佬接连辞任一文揭秘阿里、腾讯、百度的薪资职级百度、阿里、腾讯内部岗位级别和薪资结构,附带求职建议!可怕的不是堕落,而是清楚自己在堕落用C++跟你聊聊“原型模式” (复制/拷贝构造函数)关于keras使用fit_generator中遇到StopIteration惹什么猫都别惹熊猫!「功夫熊猫」20年对人类拿下4血C语言程序设计课程设计 之《学生成绩管理系统》Unity 场景异步加载(加载界面的实现)