首页 > 编程语言 >算法设计与分析：实验二 分治法——最近点对问题

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

时间：2024-08-30 16:23:42浏览次数：13  
标签：right 递归 分治 算法 mindist 实验 left

实验内容：

  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. 底层处理加上限界优化后的分治算法最快，因为它综合了底层处理和限界优化，避免了不必要的递归调用，并通过优化点集的处理方式进一步降低了时间复杂度，从而提高了算法的效率。

 

标签：right,递归,分治,算法,mindist,实验,left
From： https://blog.csdn.net/gyeolhada/article/details/141714125

相关文章

  • sha-256算法，生成固定长度的字符串
    SHA-256（安全哈希算法256位）是一种广泛使用的加密哈希函数，它会将输入的任意大小的数据转换为固定长度的256位（32字节）哈希值。SHA-256是SHA-2系列算法的一部分，由美国国家安全局（NSA）设计，并由美国国家标准与技术研究院（NIST）发布。SHA-256的主要特点包括：固定长度输出：无论输入数据的......
  • Java中的并发控制算法：如何实现高效的锁机制与无锁编程
    Java中的并发控制算法：如何实现高效的锁机制与无锁编程大家好，我是微赚淘客系统3.0的小编，是个冬天不穿秋裤，天冷也要风度的程序猿！在多线程环境中，如何保证数据的正确性和一致性是个重要的问题。为了解决这个问题，Java提供了多种并发控制算法，主要包括锁机制和无锁编程。本文将介......
  • 基于协同过滤算法的电影推荐系统的设计与实现(论文+源码)_kaic
    摘 要现在观看电影已逐渐成为人们日常生活中最常见的一种娱乐方式，人们通常会在周末或在休息、吃饭时间不由自主地在各种视频软件中搜索当前火热的影视节目。但是现在的视频软件电影推荐功能不够完善，所以需要开发出一套系统来使用户只需要简单操作就能找到喜爱的影片。针对这......
  • C#学习笔记本--第三篇（排序算法之归并排序）
    一、基本原理：//归并=递归+合并//数组分左右 //左右元素相比较//满足条件放入新数组//一侧用完放对面//递归不停分分完在排序//排序结束往上走边走边合并//走到头顶出结果//归并排序分为两部分//1.基本排序规则//2.递归平分数组//递归平分数组：//不停地分割......
  • 一次失败的实验 - 无限注意力，我们为什么坚持实验
    总结:随着我们增加内存压缩次数的次数，Infini-attention的性能会变得越来越差。据我们所知，ringattention、YaRN和ropescaling这三种方法仍是将预训练模型拓展更长上下文的最佳方式。引言:语言模型的上下文长度也是除模型性能之外的重要属性之一。自in-contextlearning(......
  • js逆向之常用算法
     [Python]encode&decodefromurllibimportparse#url进行编码与解码url='你好啊'url_encode=parse.quote(url)print('url编码后:',url_encode)url_decode=parse.unquote(url_encode)print('url解码后:',url_decode)url_encode......
  • Java中的分布式一致性与共识算法
    在分布式系统中，节点之间必须就某些值达成一致。但由于网络的不可靠性、节点故障以及其他不可预测因素，实现一致性变得极为复杂。共识算法应运而生，旨在解决这一难题。本文将深入探讨两种主要的共识算法——Paxos和Raft，解释其原理，并提供Java代码示例。此外，我们还将对比它们的优缺......
  • 分享丨【题单】贪心算法（基本贪心策略/反悔/区间/字典序/数学/思维/构造）
    作者：灵茶山艾府链接：https://leetcode.cn/circle/discuss/g6KTKL/一、贪心策略有两种基本贪心策略：从最小/最大开始贪心，优先考虑最小/最大的数，从小到大/从大到小贪心。在此基础上，衍生出了反悔贪心。从最左/最右开始贪心，思考第一个数/最后一个数的贪心策略，把n个数的原问题转......
  • 求两点间最短路的Dijkstra算法及其matlab程序详解
    #################本文为学习《图论算法及其MATLAB实现》的学习笔记#################设源点为u0u_{0}u0​,目标......
  • 【3.4】贪心算法-解按要求补齐数组
    一、问题        给定一个已排序的正整数数组nums，和一个正整数n。从[1,n]区间内选取任意个数字补充到nums中，使得[1,n]区间内的任何数字都可以用nums中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99