经典算法:最短点对

简介: 经典算法:最短点对

说明

旧文新发,改了错别字,死链等。尽量保持“原汁原味”。

难点

如何测试。我的解决方式是:a,三种解法,看结果是否一致。b,小数据(100个点),人工排查。第一种方法,暴力法适合小数据。第二种方法:我的改进型。第三种方法:经典方法(分治法)。实验证明1000万数据时,我的算法有优势。

改进

暴力算法,O(n2)。我的改进型要点:先对所有数据按Y排序。只比较y距离小于等于已知最小距离的点对。经典方法:按Y排序,分成两部分,递归调用。合并时只比较距离分界线不超过已知最小距离的点对。

实际证明500万数据以下,我的改进算法明显优于经典算法;1000万数据时,略强于经典算法。

核心源码节选:

double Dis(const CPT& pt1,const CPT& pt2)
{
  return sqrt((double) (pt1.x-pt2.x)*(pt1.x-pt2.x)+(pt1.y-pt2.y)*(pt1.y-pt2.y)+(pt1.z-pt2.z)*(pt1.z-pt2.z) );
}
void InitData(CPT* pts,int iNum)
{
  srand(time(NULL));
  for( int i = 0 ; i < iNum ; i++)
  {
    pts[i].x = rand()%10000;
    pts[i].y = rand()%10000;
    pts[i].z = rand()%10000;
  }
}
double Fun1(CPT* pts,const int iNum)
{
   double dMinDis = 10000*10000 ;
  for(int i = 0 ; i < iNum ; i++ )
    for( int j = i+1 ; j < iNum ; j++ )
    {
      const double d = Dis(pts[i] , pts[j]);
      if( d < dMinDis)
      {
        dMinDis = d ;
      }
    }
    return dMinDis;
}
class CCmpY
{
public:
  bool operator()(const CPT& pt1,const CPT& pt2)
  {
    return pt1.y < pt2.y ;
  }
};
double Fun2(CPT* pts,const int iNum)
{
  std::sort(pts,pts+iNum,CCmpY() );
  double dMinDis = 10000*10000 ;
  for(int i = 0 ; i < iNum ; i++ )
    for( int j = i+1 ; j < iNum ; j++ )
    {
      const double d = Dis(pts[i] , pts[j]);
      if( d < dMinDis)
      {
        dMinDis = d ;
      }
      if( abs(pts[i].y - pts[j].y )> dMinDis )
      {
        break;
      }
    }
    return dMinDis;
}
double Fun3(CPT* pts,const int iNum)
{
  std::sort(pts,pts+iNum,CCmpY() );
  if( iNum < 100 )
  {
    return Fun1(pts,iNum);
  }
  const int iMid = iNum/2 ;
  const double dMin1 = Fun3(pts,iMid);
  const double dMin2 = Fun3(pts+iMid,iNum-iMid);
  double dMinDis = min(dMin1,dMin2) ;
  for(int i = iMid-1 ; i >= 0 ; i-- )//左集合
  {
    if( abs(pts[i].y - pts[iMid].y ) > dMinDis )
    {
      break;
    }
    for( int j = iMid ; j < iNum ; j++ )//右集合
    {
      const double d = Dis(pts[i] , pts[j]);
      if( d < dMinDis)
      {
        dMinDis = d ;
      }
      if( abs(pts[i].y - pts[j].y )> dMinDis )
      {
        break;
      }
    }
  }
    return dMinDis;
}

测试环境

似乎是WinXP VS2005(VC8)

下载

可通过以下链接下载测试数据,exe,源码(VS2005,VC8)

https://download.csdn.net/download/he_zhidan/10887801


相关文章
|
6月前
|
存储 算法 数据管理
【C/C++ 基础算法】 C/C++ 位图算法的使用
【C/C++ 基础算法】 C/C++ 位图算法的使用
113 0
|
存储 算法 索引
数据结构与算法之图论及其相关算法
图的基本介绍 线性表局限于一个直接前驱和一个直接后继的关系,树也只能有一个直接前驱也就是父节点,当我们需要表示多对多的关系时, 这里我们就用到了图。 图是一种数据结构,其中结点可以具有零个或多个相邻元素。两个结点之间的连接称为边。 结点也可以称为顶点。如图: 简单来说,图就是由顶点的有穷非空集合和顶点之间的边组成的集合。通常表示为:G(V,E),其中,G 表示一个图,V 表示顶点的集合,E 表示边的集合。 然后我们说说图中的一些常见概念: 节点(Vertex):图中的基本元素,用于表示某个实体。 边(Edge):连接两个节点的线段,用于表示节点之间的关系。 度(Degree):
55 0
|
6月前
|
算法
基础算法题
基础算法编程题
25 3
|
算法 C++
【基础算法】开平方算法 & C++实现
在数学中,因为很多数的开平方都是无理数,所以我们需要借助数值计算的方式来进行近似值的求解。
323 0
【基础算法】开平方算法 & C++实现
|
算法
【学习挑战赛】经典算法之折半查找
【学习挑战赛】经典算法之折半查找
172 0
|
算法 搜索推荐
【学习挑战赛】经典算法之直接选择排序
【学习挑战赛】经典算法之直接选择排序
56 0
|
算法 搜索推荐
【学习挑战赛】经典算法之直接插入排序
【学习挑战赛】经典算法之直接插入排序
69 0
|
存储 算法 大数据
基础算法-高精度乘法
高精度算法 为什么要使用高精度算法 C++ 每一个变量都有自己的类型,每个类型都有自己的存储长度范围
|
算法 C++
|
算法 C++
【基础算法】分治算法 & C++实现
分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题,这些子问题相互独立且与原问题性质相同。求出子问题的解,就可得到原问题的解。即一种分目标完成程序算法,简单问题可用二分法完成。下面的硬币问题就是分治算法的一种典型算法题。
125 0
【基础算法】分治算法 & C++实现