最近对问题?
设p1=(x1,y1), p2(x2,y2), ....,pn=(xn,yn)是平面上n个点构成的集合S,最近对问题就是找出集合S中距离最近的点对。
两种算法思想:
1. 蛮力法:顾名思义,利用正常的思维,使用强硬的方式求解出结果。
2. 分治法:分治,分而治之,把大问题分解为小问题,主要有三个过程:划分、求解子问题、合并。
直接上代码:
蛮力法求解最近对问题:
#include "iostream"
#include "math.h"
#include "time.h"
#include "stdlib.h"
using namespace std;
struct P
{
int x;
int y;
};
double ClosePoints(int n,P a[],int &index1,int &index2)
{
double d;
double Dist=10000;
for (int i=0;i<n-1;i++)
{
for (int j=i+1;j<=n-1;j++)
{
d=(a[i].x-a[j].x)*(a[i].x-a[j].x)+(a[i].y-a[j].y)*(a[i].y-a[j].y);
if(d<=Dist)
{
Dist=d;
index1=i;
index2=j;
}
}
} return Dist;
}
void main (void)
{
clock_t start,end;
int g;
int s,e;
P a[10000];
for (int i=1;i<4;i++)
{
cout<<"输入坐标的个数(10000以内)";
cin>>g;
srand(time(NULL));
for (int r=0;r<g;r++)
{
a[r].x=rand()%(g-123);
a[r].y=rand()%(g-1234);
}
start=clock();
double w=ClosePoints(g,a,s,e);
end=clock();
cout<<"最近的两个点是:P1("<<a[s].x<<","<<a[s].y<<") P2("<<a[e].x<<","<<a[e].y<<")"<<endl; cout<<"距离是:"<<sqrt(w)<<endl;
cout<<"蛮力法求最近对用时:"<<(double)(end-start)/CLOCKS_PER_SEC<<"ms"<<endl;
cout<<"============================================================="<<endl;
}
}
分治法求解最近对问题:
#include<iostream>
#include "cstdio"
#include "cstring"
#include "math.h"
#include "time.h"
#include "stdlib.h"
#include "algorithm"
using namespace std;
#define eps 1e-8
#define N 10000
//定义一个保存坐标的结构体
struct point
{
double x,y;
};
point node[N * 2];
point d[N];
point c[N];
point b[N];
int cmp(point a, point b) //比较两点之间的y值
{
return a.y < b.y;
}
int cmp1(point a, point b)
{
if(a.x != b.x)
return a.x < b.x;
return a.y < b.y;
}
double min(double a, double b) //求a和b两者较小值
{
return a > b? b:a;
}
double dx(double x1, double x2)
{
if((x1 - x2) > eps && (x1 - x2) < eps)
{
return 0;
}
else if(x1 > x2)
{
return x1 - x2;
}
else if(x1 < x2)
{
return x2 - x1;
}
}
double ds(point a, point b) //求两点之间的距离
{
return sqrt((a.x - b.x) * (a.x - b.x) + (a.y - b.y) * (a.y - b.y));
}
/**
* 最近对问题
* 三种情况:
* 1.在子集S1中
* 2.在自己S2中
* 3.最近的两个点分别在子集S1和S2中
*/
double closestPoints(point node[], int n)
{
int i, j;
int Dist = 99999; //无穷大数
if(n < 2) //只有一个点,不存在最近对
return 0;
int m = (n - 1) / 2; //m是各个坐标的中位数
for(i = m + 1; i < n; i++)
{
b[i].x = node[i].x;
b[i].y = node[i].y;
}
//划分为两个子问题,递归求解子问题
double d1 = closestPoints(node, m + 1); //得到S1中的最近距离d1
double d2 = closestPoints(b, n - m - 1); //得到S2中的最近距离d2
double dm = min(d1, d2); //求得d1与d2两者之间较小值
int f,p; //记录点的个数
p = 0;
for(i = 0; i <= m; i++) //找出S1中与x=m的距离小于dm的所有点,保存在结构体c当中
{
if(dx(node[i].x,node[m].x) < dm)
{
c[p].x = node[i].x;
c[p].y = node[i].y;
p++;
}
}
f=0;
for(i = m + 1; i < n; i++) //找出S2中与x=m的距离小于dm的所有点,保存在结构题d当中
{
if(dx(node[i].x, node[m].x) < dm)
{
d[f].x = node[i].x;
d[f].y = node[i].y;
f++;
}
}
sort(c, c+p,cmp); //按照y轴的坐标值升序排列
sort(d, d+f,cmp);
double ret = Dist;
for(i = 0; i < p; i++) //遍历比较分别在S1和S2中两点之间的距离
{
for(j = 0; j < f; j++)
{
double ans = ds(c[i], d[j]);
ret = min(ret, ans); //得出最近对距离
}
}
return min(ret, dm); //返回第三种情形与前两种情形较小值
}
int main(void)
{
int n,i;
for(int w=0;w<6;w++)
{
cout<<"输入坐标的数目:"<<endl;
cin>>n;
srand((unsigned)time(NULL));
for(i=0;i<n;i++)
{
node[i].x=rand()/(double)(RAND_MAX/10000);
node[i].y=rand()/(double)(RAND_MAX/10000);
}
sort(node,node+n,cmp);
clock_t start,end;
start=clock();
closestPoints(node,n); //系统调用十次分治法函数。
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
closestPoints(node,n);
end=clock();
cout<<"分治法求最近对用时为"<<double(end-start)/CLOCKS_PER_SEC<<"ms"<<endl;
cout<<"==========================================================="<<endl;
}
system("pause");
return 0;
}
分享到:
相关推荐
算法设计--蛮力法&&分治法求最近对问题(C++实现).rar
算法设计实验报告,包括:分治法和蛮力法求最近对问题的基本思想、时间复杂度分析,C++实现代码,两种算法运行时间的比较,运行结果截图,实验心得。
这是一个解决最近点对问题的很好的范例!
蛮力法、分治法和动态规划法设计最大子段和问题的算法,一、试分别利用蛮力法、分治法和动态规划法求解最大子段和问题,要求写出C/C++程序实现和算法的效率分析。程序运行结果要同时给出最大子段和的值以及由哪个子段...
算法设计与分析--求最大子段和问题(蛮力法、分治法、动态规划法) C++实现.rar
主要是对 1 - 8章 以及 第10章中的课后习题进行代码解答,主要包括的章节有第1章概论、第2章递归算法设计技术、第3章分治法、第4章蛮力法、第5章回溯法、第6章分支限界法、第7章贪心法、第8章动态规划以及第10章计算...
算法设计与分析 汉诺塔 分治法 1、采用分治法的思想,编写程序解决汉诺塔问题Hanio(n,A...3、分别采用二路归并(分治法)、快速排序(分治法)和选择排序(蛮力法),对序列{23,13,49,6,31,19,28}进行升序排列。
算法设计实验报告,包括:蛮力法、分治法和减治法求最大子段和问题各自的基本思想、时间复杂度分析,C++实现代码,三种算法运行时间的比较,运行截图,实验心得。
第2章介绍常用数学工具,第3章从算法的观点介绍了NP完全理论,从第4章~第12章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术。课程中所配算法均给出...
C++最近点对问题,蛮力算法和分治算法,分治法:遵循分治思路方法利用递归求出左子集和右子集最近点对然后再对两子集的间点对进步分析比较最后求出整个点集最近点对
这个文档里包含了算法设计与分析-C++语言描述(电子工业出版社出版)课程里需要做的典型实验题的源代码及实现,包括找零钱问题,0-1背包问题,比赛日程问题,找作案人问题,求数字排列问题等等,均是运用几种常用...
本算法是用C++实现最大子段和问题,包括蛮力法,分治法和动态规划法的实现及时间效率的对比
语言:C++ 问题:最近点对问题 方法:蛮力法和分治法 包括两种算法效率的比较,测试以通过
第2章介绍常用数学工具,第3章从算法的观点介绍了NP完全理论,从第4章~第12章分别介绍了蛮力法、分治法、减治法、动态规划法、贪心法、回溯法、分支限界法、概率算法和近似算法等算法设计技术。课程中所配算法均给出...
分别用分治法、蛮力法、减治法实现了a的n次方,并进行了三种算法的时间性能比较,测试数据可以用1的n次方
最大子段和/三种方法/c++语言/(内有报告) 蛮力法,动态规划法,分治法。 可比较时间,随机输入数据......
文件给出了四种方式求解子序列的最大和,并给出了具体的代码实现。对于深入探讨算法和程序性能非常有帮助。