算法设计与分析：实验二 分治法——最近点对问题

2024-08-30 13:44
文章标签 算法 分析 设计 问题 实验 分治 最近

本文主要是介绍算法设计与分析：实验二 分治法——最近点对问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

实验内容：

  1. 对于平面上给定的N个点，给出所有点对的最短距离，即，输入是平面上的N个点，输出是N点中具有最短距离的两点。
  2. 要求随机生成N个点的平面坐标，应用蛮力法编程计算出所有点对的最短距离。
  3. 要求随机生成N个点的平面坐标，应用分治法编程计算出所有点对的最短距离。
  4. 分别对N=100000—1000000，统计算法运行时间，比较理论效率与实测效率的差异，同时对蛮力法和分治法的算法效率进行分析和比较。

1.暴力枚举算法

（1）主要思路：枚举点集中所有可能形成的点对，且设置全局变量最小距离mindist,然后计算每个点对之间的距离并与mindist进行比较，如果比mindist还小，就对mindist进行更新，同时对最近点对的两个点也进行更新。

（2）时间复杂度：点集中有n个点，可能形成的点对有O(n^2)的规模，即需要两层for循环，需要一一进行枚举，因此时间复杂度为O(n^2)。

（3）伪代码：

暴力枚举算法O(n^2)

Function Brute_n2(left,right)

  For i=left to right

    For j=i+1 to right

      If dist(a[i],a[j]) < mindist

        mindist=dist(a[i],a[j])

        ansX1=a[i].id

        ansX2=a[j].id

        ansP[0]=a[i]

        ansP[1]=a[j]

（4）算法过程：

方格内的数字表示两点之间的距离，红色表示目前更新到的最短距离，蓝色表示最短距离的两个点。

随机生成10个点：points = [(943, 5798), (9838, 8020), (5975, 5678), (5814, 8662),

(2067, 7698),(5009, 2238), (4297, 5729), (8897, 378), (2003, 1453), (2317, 194)]

0

1

2

3

4

5

6

7

8

9

0

0

9168.33

5033.43

5650.59

2207.57

5404.25

3354.71

9625.1

4472.43

5769.98

1

0

4517.49

4074.89

7777.67

7533.31

5995.95

7699.72

10233.1

10854.1

2

0

2988.34

4399.19

3573.06

1678.77

6052.11

5798.91

6592.06

3

0

3869.02

6474.24

3302.09

8839.09

8154.35

9161.66

4

0

6202.17

2974.87

10011.6

6245.33

7508.16

5

0

3562.87

4310.01

3106.81

3380.06

6

0

7056.43

4852.49

5878.49

7

0

6977.31

6582.57

8

0

1297.57

9

0

如上表所示，mindist =1297.57，ansX1=8，ansX2=9，即第8个点和第9个点为最近点对，最短距离为1297.57。

2.分治算法

（1）主要思路：

用分治算法求解最近点对的问题分为三个阶段：排序、递归、合并，其中核心是我们的递归函数。以下是它们的主要思路：

  1. 合并（Merge） 函数：用于合并两个已经排序好的子数组。在这里，按照点的纵坐标进行归并排序，合并得到排好序的数组。至于为什么选择归并排序而不是快速排序（实测数据证明下文有），主要是因为归并排序是一种稳定的排序算法，它能够保持相同元素的相对顺序在排序前后不变，快速排序虽然在平均情况下具有较好的性能，但它是一种不稳定的排序算法，元素的相对顺序可能会被改变，这在合并阶段可能会导致不正确的结果。
  1. 入口（Divided_nlogn） 函数：用于初始化并调用递归函数。首先对整个点集按照横坐标进行排序，然后调用递归函数进行分治求解。
  2. 递归（Recur） 函数：用于分治地处理问题。首先判断当前区间是否只有一个点，如果是则返回。然后，找到当前区间的中间点，将问题分成两个部分，第一部分是求出子问题即左半部分left点集的最近点对和右半部分right点集的最近点对；第二部分是求出横跨左右两个点集的点形成的最近点对。这样就实现了找到点集left-right所有可能形成的最近点对。

（2）时间复杂度：

总时间复杂度为排序阶段的时间复杂度加上递归合并阶段的时间复杂度，即O(nlogn)+O(nlogn)，最后结果为O(nlogn)。

（3）伪代码：

分治算法O(nlogn)

  1. Function Merge(left,mid,right) // 合并函数即归并排序
  2.   Temp[right-left+1]
  3.   li = left, ri = mid+1, ii = 0
  4.   While li<=mid and ri<=r
  5.     If a[li].y<a[ri].y // 按照点的纵坐标从小到大
  6.       Temp[ii++] = a[li++]
  7.     Else
  8.       Temp[ii++] = a[ri++]
  9.   While li<=mid
  10.     Temp[ii++] = a[li++]
  11.   While ri<=right
  12.     Temp[ii++] = a[ri++]
  13.   For i=left to right //合并后的子序列进行更新
  14.     a[i] = Temp[i-left]
  15. // 递归函数
  16. Function Recur(left,right)
  17.   If left == right //当前区间只包含一个点
  18.     Return //不需要再继续递归，直接返回
  19.   mid = (left+right)/2 //找到区间的中间点
  20.   midx = a[mid].x
  21.   Recur(left,mid) //左半部分进行递归处理
  22.   Recur(mid+1,right) //右半部分进行递归处理
  23.   Merge(left,mid,right)
  24.   Temp[right-left+1] //存储跨越左右两个子集可能贡献答案的点
  25.   Tempsize = 0
  26.   For i=left to right
  27.     If abs(a[i].x – midx) < mindist //选择当前点与中线midx横坐标小于mindist
  28.       For j=Tempsize-1 to 0 desc
  29.         If a[i].y-Temp[j].y>=mindist
  30.           Break //如果大于则跳出循环，因为之后的点不可能满足距离小于mindist
  31.         UpdateAns(a[i],Temp[j]) //小于则贡献答案，更新
  32.       Temp[Tempsize++] = a[i] // 将满足的点放入temp临时数组中
  33.  // 分治算法入口函数
  34. Function Divided_nlogn(left,right)
  35.   Sort(a from left to right by a.x) //按照横坐标从小到大排序
  36.   Recur(left,right) // 开始递归处理

（4）算法过程：

最近点对的线段用红色实线绘制，中间线用蓝色实线绘制，当前处理区间边界线Left和Right用两条红色虚线表示，midx - mindist 和 midx + mindist用两条蓝色虚线表示。用黄色线段表示当前处理的点对。

随机生成10个点：points = [(943, 5798), (9838, 8020), (5975, 5678), (5814, 8662),

(2067, 7698),(5009, 2238), (4297, 5729), (8897, 378), (2003, 1453), (2317, 194)]

分治算法过程（以更新最近点对的图为例）

Left=943

Mid=943

Right=2003

Dist=4472.429

最近点对信息：

P1:(943,5798)

P2:(2003,1453)

Mindist=4472.43

Left=943

Mid=2003

Right=2067

Dist=2207.572

最近点对信息：

P1:(2067,7698)

P2:(943,5798)

Mindist=2207.57

Left=943

Mid=2067

Right=4297

Dist=1297.566

最近点对信息：

P1:(2003,1453)

P2:(2317,194)

Mindist=1297.57

Left=943

Mid=4297

Right=9838

Dist=0.000

最近点对信息：

P1:(2003,1453)

P2:(2317,194)

Mindist=1297.57

需要注意的是，当没有找到最近点对的时候p1-p2=--，且p1和p2的距离dist=0.000。上述只以更新最近点对时的图为例，完整过程在动图展示中。最终得到的最近点对为P1(2003,1453)和P2(2317,194)，最近点对距离Mindist=1297.57。

3.分治算法优化

（1）底层处理：

  1. 考虑“底层处理”，在算法递归到底层时，当集合中的点数量减少到一个较小的阈值（三个点）时，不再进行继续的递归分割，而是直接使用暴力方法O(n^2)求解最近点对。
  2. 具体而言，当分治算法递归到底层时，可能会剩下很少的点。在这种情况下，继续递归下去可能会增加额外的开销，因为递归的开销在剩下的点很少时可能会占据相当大的比例。在点数量较少时，暴力方法的计算开销相对较小，而不会明显影响算法的性能。这种优化策略可以减少递归调用的次数，降低算法的时间复杂度，提高算法的执行效率。
  3. 伪代码如下：

分治算法-底层优化处理

  1. Function Recur_dicen(left,right)
  2.   If left == right //当前区间只包含一个点
  3.     Return //不需要再继续递归，直接返回
  4.   // 底层优化
  5.   If (right-left+1)<=3
  6.     Brute_n2(left,right)
  7.     Return
  8.   mid = (left+right)/2 //找到区间的中间点
  9.   midx = a[mid].x
  10.   Recur_dicen(left,mid) //左半部分进行递归处理
  11.   Recur_dicen(mid+1,right) //右半部分进行递归处理
  12.   Merge(left,mid,right)
  13.   Temp[right-left+1] //存储跨越左右两个子集可能贡献答案的点
  14.   Tempsize = 0
  15.   For i=left to right
  16.     If abs(a[i].x – midx) < mindist //选择当前点与中线midx横坐标小于mindist
  17.       For j=Tempsize-1 to 0 desc
  18.         If a[i].y-Temp[j].y>=mindist
  19.           Break //如果大于则跳出循环，因为之后的点不可能满足距离小于mindist
  20.         UpdateAns(a[i],t[j]) //小于则贡献答案，更新
  21.       Temp[Tempsize++] = a[i] // 将满足的点放入temp临时数组中
  22. Function Divided_nlogn_xianjie(left,right)
  23.   Sort(a from left to right by a.x) //按照横坐标从小到大排序
  24.   Recur_xianjie(left,right) // 开始递归处理

（2）限界优化：

  1. 考虑在跨点集处理中的第三步对S(pi)进行限界优化处理。
  2. 在处理点集S(pi)时，通过确定中值线midx，将点集分为左右两部分S1(pi)和S2(pi)，然后在处理S2(pi)时，只需要考虑纵坐标最大的两个点，而不需要考虑全部点，从而限制了搜索空间，提高了算法的效率。这种处理方式被称为限界优化，或者说边界优化的一种形式。
  3. 处理思路：以midx直线为中值，将点集S(pi)分成左右两个部分S1(pi)和S2(pi)，现假设已有pi在左半部分点集S1(pi)中，猜想如果点集S2(pi)存在点pj，使得pi和pj的距离可以更新答案。那么pj一定是点集S2(pi)里纵坐标最大的点或纵坐标次大的点。样本要逐个遍历点集S2(pi)中的点（最多四个点），就可以变成只需要遍历S2(pi)中的前两个点（纵坐标最大的两个点）。
  4. 伪代码如下：

分治算法-限界优化处理

  1. Function Recur_xianjie(left,right)
  2.   If left == right //当前区间只包含一个点
  3.     Return //不需要再继续递归，直接返回
  4.   mid = (left+right)/2 //找到区间的中间点
  5.   midx = a[mid].x
  6.   Recur_xianjie(left,mid) //左半部分进行递归处理
  7.   Recur_xianjie(mid+1,right) //右半部分进行递归处理
  8.   Merge(left,mid,right)
  9.   Temp[right-left+1] //存储跨越左右两个子集可能贡献答案的点
  10.   Tempsize = 0
  11.   For i=left to right
  12.     If abs(a[i].x – midx) < mindist //选择当前点与中线midx横坐标小于mindist
  13.       For j=Tempsize-1 to max(0, Tempsize-2) desc //限界优化
  14.         If a[i].y-Temp[j].y>=mindist
  15.           Break //如果大于则跳出循环，因为之后的点不可能满足距离小于mindist
  16.         UpdateAns(a[i],t[j]) //小于则贡献答案，更新
  17.       Temp[Tempsize++] = a[i] // 将满足的点放入temp临时数组中
  18.   
  19. Function Divided_nlogn_xianjie(left,right)
  20.   Sort(a from left to right by a.x) //按照横坐标从小到大排序
  21.   Recur_xianjie(left,right) // 开始递归处理

实验结果及分析：

1.暴力枚举算法O(n^2)：

可以看出，暴力枚举算法O(n^2)的实际运行时间曲线略低于预测运行时间曲线，但总体来说两条曲线是比较贴合的，即实际性能与预测性能相差不大。

2.分治算法O(nlogn)：

可以看出，分治算法O(nlogn)的实际运行时间曲线和预测运行时间曲线几乎是完全贴合，即预测效果是不错的，预测性能与实际性能几乎一致。

3.O(n^2)与O(nlogn)对比：

根据上面暴力法和分治法的效率分析，我们易知暴力法和分治法的时间效率相差很大，而且暴力法在数据规模很大时，运行时间非常慢，因此为了方便比较，以二者的预测运行时间来进行对比，同时把时间取对数。下图数据和图表的时间表示均已取过对数。

得到两种算法的差距非常明显，分治法的运行效率明显比暴力法的运行效率优越。

4.分治算法合并阶段使用快速排序和归并排序性能对比：

一开始当n的规模较小时，二者的差距不算大，但是随着n的规模增大，使用归并排序的算法性能明显优于使用快速排序的算法性能。当n=1000000时，使用快速排序所需要的运行时间已经是使用归并排序的运行时间的2倍了。我们知道归并排序的时间复杂度稳定在 O(nlogn) 级别，而快速排序在最坏情况下可能会达到 O(n^2)，所以这使得归并排序在处理大规模数据时更具优势。

5.分治算法优化性能对比：

由图可知，普通的分治算法最慢，只有限界优化后的分治算法略快一点，只有底层处理后的分治算法快得多一些，底层处理加上限界优化后的分治算法最快。

  1. 普通的分治算法最慢，因为它在任何情况下都会继续递归地划分问题，导致递归调用过多，增加时间复杂度。
  2. 限界优化后的分治算法略快一点，但不是很多，因为优化点集时，点集本来最多也才4个，优化后最多2个，数量差距不是很大，但由于减少遍历次数，也一定程度上优化了算法效率。
  3. 底层处理后的分治算法略快一些，因为当问题规模较小时，它不再进行进一步的递归划分，而是直接使用暴力方法解决，减少了递归调用次数。
  4. 底层处理加上限界优化后的分治算法最快，因为它综合了底层处理和限界优化，避免了不必要的递归调用，并通过优化点集的处理方式进一步降低了时间复杂度，从而提高了算法的效率。

 

这篇关于算法设计与分析：实验二 分治法——最近点对问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1120983。

相关文章

不懂推荐算法也能设计推荐系统

不懂推荐算法也能设计推荐系统

本文以商业化应用推荐为例，告诉我们不懂推荐算法的产品，也能从产品侧出发， 设计出一款不错的推荐系统。 相信很多新手产品，看到算法二字，多是懵圈的。 什么排序算法、最短路径等都是相对传统的算法（注：传统是指科班出身的产品都会接触过）。但对于推荐算法，多数产品对着网上搜到的资源，都会无从下手。特别当某些推荐算法 和 “AI”扯上关系后，更是加大了理解的难度。 但，不了解推荐算法，就无法做推荐系
阅读更多...
好题——hdu2522（小数问题：求1/n的第一个循环节）

好题——hdu2522（小数问题：求1/n的第一个循环节）

好喜欢这题，第一次做小数问题，一开始真心没思路，然后参考了网上的一些资料。 知识点***********************************无限不循环小数即无理数，不能写作两整数之比*****************************（一开始没想到，小学没学好） 此题1/n肯定是一个有限循环小数，了解这些后就能做此题了。 按照除法的机制，用一个函数表示出来就可以了，代码如下
阅读更多...
hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

hdu1043（八数码问题，广搜 + hash（实现状态压缩） ）

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu
阅读更多...
康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应） 公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）； 典型应用： 计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第
阅读更多...
性能分析之MySQL索引实战案例

性能分析之MySQL索引实战案例

文章目录 一、前言二、准备三、MySQL索引优化四、MySQL 索引知识回顾五、总结 一、前言 在上一讲性能工具之 JProfiler 简单登录案例分析实战中已经发现SQL没有建立索引问题，本文将一起从代码层去分析为什么没有建立索引？ 开源ERP项目地址：https://gitee.com/jishenghua/JSH_ERP 二、准备 打开IDEA找到登录请求资源路径位置
阅读更多...
csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

csu 1446 Problem J Modified LCS （扩展欧几里得算法的简单应用）

这是一道扩展欧几里得算法的简单应用题，这题是在湖南多校训练赛中队友ac的一道题，在比赛之后请教了队友，然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意：把题意转变下就变成了：求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点：求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个
阅读更多...
综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

综合安防管理平台LntonAIServer视频监控汇聚抖动检测算法优势

LntonAIServer视频质量诊断功能中的抖动检测是一个专门针对视频稳定性进行分析的功能。抖动通常是指视频帧之间的不必要运动，这种运动可能是由于摄像机的移动、传输中的错误或编解码问题导致的。抖动检测对于确保视频内容的平滑性和观看体验至关重要。 优势 1. 提高图像质量 - 清晰度提升：减少抖动，提高图像的清晰度和细节表现力，使得监控画面更加真实可信。 - 细节增强：在低光条件下，抖
阅读更多...
【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

【数据结构】——原来排序算法搞懂这些就行，轻松拿捏

前言：快速排序的实现最重要的是找基准值，下面让我们来了解如何实现找基准值 基准值的注释：在快排的过程中，每一次我们要取一个元素作为枢纽值，以这个数字来将序列划分为两部分。 在此我们采用三数取中法，也就是取左端、中间、右端三个数，然后进行排序，将中间数作为枢纽值。 快速排序实现主框架： //快速排序 void QuickSort(int* arr, int left, int rig
阅读更多...
poj1330（LCA最近公共祖先）

poj1330（LCA最近公共祖先）

题意：求最近公共祖先 思路：之前学习了树链剖分，然后我就用树链剖分的一小部分知识就可以解这个题目了，记录每个结点的fa和depth。然后查找时，每次将depth大的结点往上走直到x = y。 代码如下： #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstring>
阅读更多...
购买磨轮平衡机时应该注意什么问题和技巧

购买磨轮平衡机时应该注意什么问题和技巧

在购买磨轮平衡机时，您应该注意以下几个关键点： 平衡精度 平衡精度是衡量平衡机性能的核心指标，直接影响到不平衡量的检测与校准的准确性，从而决定磨轮的振动和噪声水平。高精度的平衡机能显著减少振动和噪声，提高磨削加工的精度。 转速范围 宽广的转速范围意味着平衡机能够处理更多种类的磨轮，适应不同的工作条件和规格要求。 振动监测能力 振动监测能力是评估平衡机性能的重要因素。通过传感器实时监
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2