C++ 中查找 N 个坐标对之间的最大曼哈顿距离

计算几何这个庞大的领域，是算法与空间信息交汇的区域，它提出了一个有趣的问题：找出 N 个随机选择的坐标点对中，任意两个不同点对之间的最大曼哈顿距离。这个问题看似简单，实则是一个相当复杂的谜题，其中蕴含着一个等待被探索的复杂性和实用性世界。

最初，曼哈顿距离，也被称为 L1 距离或出租车距离，用于衡量两个地点之间的距离，其方式是通过网格状的街道进行 traversal，类似于在曼哈顿的街道上漫游。与定义为两个地点之间直线距离的欧几里得距离不同，曼哈顿距离在网格的思维框架内表达距离，就像出租车司机在城市街区中行驶一样。最常见的实际应用包括电路设计、图像处理、城市规划、交通和物流，这些例子自然地来自于其特殊的功能。

• 一个 2D 城市景观的插图，每个点代表一个特定的位置。要解决的问题是，在给定的 N 个坐标中，找出给定点集中任意两点之间的最大曼哈顿距离。归根结底，我们试图在城市中找到两点之间最快（最短）的出租车行程，使用一张包含城市街区（街道）的地图，而出租车必须在这些街道上行驶。
• 如果需要一个插图，可以想象一张描绘大都市结构中一组点的地图。通过确定每对地点之间的距离并找到遇到的最大值，我们正在寻找城市边界内的最长旅程。简而言之，这里的距离意味着我们超出给定区域的散布程度，并决定了空间的分布。
• 这不仅仅是一个理论游戏，这关系到人们的生活和人类的未来。最大曼哈顿距离到几个地点的可用性，使得城市规划负责人更容易规划更有效的紧急响应路线和交通系统。这个原理是交通行业中经常使用的规则之一，它允许快速交付并减少连接配送中心和客户的距离。另一个应用是，在数据科学和机器学习中，当考虑地理分析、聚类算法和模式识别任务时，曼哈顿距离具有重要意义。
• 尽管这个问题可能有一个看似简单的解决方案，但它在计算方面产生了严重的影响。虽然对于初学者来说它可能看起来足够简单，但当处理大量数据时，该方法注定会很快遇到瓶颈。这种方式无法有效地处理大量数据，因为它具有二次时间复杂度，因此非常慢。这要求开发更复杂的算法。
• 我们可以将最大曼哈顿距离作为参考，这个距离总是在由给定坐标构成的边界框的两个相对极端角点之间存在的，并在此基础上进行最优方法。如果我们不进行大量的成对比较，而是首先找到这些最优点并计算它们的距离，我们就可以在此类问题中找到更有效的方法。这个问题可能看起来容易解决，但实际上它是一个要求兼顾效率和简洁性的绝佳案例。问题解决范式是一个连接数据结构、算法和演绎逻辑的多维网络，从而提高了对计算几何的理解水平。

在本文中，我们将探讨该问题的一些重要特征，包括最优解和暴力解法、C++ 实现和复杂度分析，以及另一个改进。我们将通过深入研究每个组成部分的细节，来揭示在 N 个坐标中寻找最大曼哈顿距离的复杂性。

暴力破解法

暴力解法是判断力最差但最简单的犯罪侦破策略之一。它包括发现 N 个地点之间任意两点之间的最大曼哈顿距离。第二种方法，简单地说，就是通过计算每两点之间的平均距离来计算最大距离的暴力计算。虽然乍一看很简单，但考虑到数据的大小，很快就会发现这种方法受到很多限制，再次反映了更复杂算法的必要性。

暴力解法的基本思想很简单：我们需要通过计算曼哈顿距离来找出每两点之间的总距离，以便给出任意两点之间的最大距离。这意味着必须计算每对点，并且要执行所有可能的组合的每次迭代，并记录到目前为止发现的最大距离。

让我们更详细地研究一下这个策略的工作原理。

• 成对比较： 首先，为了实现暴力解法，数据集中的每个点都与其他点进行比较以找到匹配项。这需要通过嵌套循环来完成整个过程：外循环迭代每个点，内循环迭代剩余的点。因此，对于 N 个点，会产生 N*(N-1) 次成对比较。
• 计算曼哈顿距离： 两个给定点之间的曼哈顿距离的计算公式为 |x1 - x2| + |y1 - y2|，其中 (x1, y1) 和 (x2, y2) 是城市中两个点的坐标。基本算术运算符用于此计算，以连续处理每对点。
• 最大距离跟踪： 当出现一个更长的距离时，随着成对相似度的持续进行，到该点的已打包曼哈顿距离将更新。
• 暴力解法的缺点是效率低下，但该方法易于理解或实现。该算法的时间复杂度为 O(N^2)，其中 N 是点的数量。考虑到计算机工作量随着输入量的增长而呈二次方增长，因此对于成千上万甚至更多的点，这种指数级时间复杂度的算法是不可行的。

现在让我们用两个点分配的例子来展示一下使用暴力解法时可能遇到的困难。在处理一个额外的点时，而不是从“逐对”比较开始，会导致计算时间呈近指数级增长。在实际操作中，当速度和规模是优先事项时，暴力解法很快就会被认为效率低下。

尽管暴力解法存在明显的误导，但它仍然是走向更好解决方案的初步但粗略的途径。在这里，我们还将看到其清晰、透明且在某种程度上简单的结构的原因，因为它是理解问题域和寻找一些可能优化方案的完美起点。欣赏距离计算和成对接触的基础可以帮助人们加深对与几何问题相关的计算问题的理解。

优化方法

使用暴力解法计算 N 个点的最大曼哈顿距离是可行的，但在应用于海量数据集时效率低下。我们选择一种最优方法，该方法利用了问题域内的数据知识来克服这个缺点，并提供更高的计算效率。

一个关键的发现构成了最优策略的基础：任意两点之间的最短曼哈顿距离由包含给定点的边界框的角点决定。通过确定极值点的位置并计算它们之间的距离，我们可以节省大量的成对比较成本。这将加快处理速度。

现在让我们更详细地研究一下优化方法的工作原理。

• 计算边界框： 优化解决方案的第一步是识别并捕获练习中提供的每个点周围的小范围。最小的矩形，无论其在二维平面上的方向如何，只要所有点都包含在内，就被视为边界框。我们确定所有地点中最小和最大的 x 和 y 坐标，以获得一个边界矩形。
• 识别极值点： 现在，在创建了边界框之后，我们可以确定最远点所在的角点，并将每个点与一个角点关联起来。边界框的边缘由这些极值点表示，这些极值点对于查找最大曼哈顿距离至关重要。我们关注最左边和最右边的 x 坐标（最小值和最大值），以及最底边和最顶边的 y 坐标（最小值和最大值）。
• 计算曼哈顿距离： 接下来，我们找到 x 和 y 坐标最极端的极值点，然后确定它们之间的曼哈顿距离。对于这项任务，即在给定坐标的曼哈顿距离的此种情况下，找到被给定坐标覆盖的两个不同位置之间的最长路程距离，必须考虑这两者距离中的较大者。

暴力解法实现

输出

Maximum Manhattan distance using brute force approach: 13 

说明

• C++ 代码采用暴力方法，给定一组 N 个坐标，计算最大曼哈顿距离。
• 使用曼哈顿距离函数计算两点之间的曼哈顿距离，公式为 dist(p1, p2) = abs(p1.first - p2.first) + abs(p1.second - p2.second)。该函数以两点 p1 和 p2 作为输入，这两点由表示每个点 x 和 y 坐标的数字对表示。
• maxManhattanDistanceBruteForce 方法使用一对嵌套循环遍历给定点集中的每对点。通过曼哈顿距离函数，算法计算每对点的估计距离，并在计算出的距离大于当前有效距离时更新 maxDist 变量。
• 在初始化点数组时，声明了一个 vector 数据结构，其中每个点由一对整数表示。在二维空间中，这些点随机选择其 x、y 和 r 坐标。
• 随后，通过调用 maxManhattanDistanceBruteForce 函数（该函数接收 points 向量作为输入）来实现暴力方法来计算最大曼哈顿距离。最终，maxDistBruteForceVariable 将包含结果。
• 最后，cout 将在控制台上显示通过暴力方法获得的最大曼哈顿距离。

优化方法实现

输出

Maximum Manhattan distance using the optimized approach: 9 

说明

• 在此示例中，C++ 算法查找给定 N 个坐标之间唯一点对的最大曼哈顿距离。优化算法的关键组成部分是 maximManhattanDistanceOptimized 函数。它以一个向量作为输入，该向量是表示点位置的二维数字对。minX、maxX、minY 和 maxY 变量都用极端值初始化，以存储函数中的最小和最大 x 和 y 坐标。
• 之后，该函数利用基于范围的循环遍历 points 向量中的每个点。它通过将当前点的坐标与现有点的坐标进行比较来修改最小和最大坐标。循环结束后，给定的坐标将转换为包含这些点的边界框的极端位置，由 minX、maxX、minY 和 maxY 表示。
• 首先，它定义了外边界，确定了它们之间两点之间的最大曼哈顿距离。它通过分别考虑 x 轴和 y 轴上的最大间隔，然后将每个间隔相减来实现这一点。此值代表任何给定点之间最远曼哈顿距离。
• Vector 是在 main 函数中初始化的点的名称，其坐标是以数字对形式的数组。二维宇宙只给这些行星随机坐标。
• 因此，将加载并执行 maxManhattanDistanceOptimized 函数，其输入为 points 向量，以计算最大曼哈顿距离。maxDistOptimized 变量将作为结果。
• 最佳方法输出最大曼哈顿投影，该投影通过 cout 路由到控制台。

复杂度分析

暴力破解法

暴力解法是一种直接的方法，需要消耗计算时间来查找 N 个点之间的最大曼哈顿距离。该方法通过两个嵌套循环来实现。它连续地为每对点执行一个循环。这导致了高时间复杂度。N 对应于多面体中的点数，外层循环包含 0 到 N-1 的值，而内层循环包含 i+1 到 N-1。因此，总共产生了大约 N*(N-1)/2 次循环。曼哈顿距离涉及简单的数学运算，这些运算被认为是常数时间，并且在每次迭代中花费相同的时间。因此，该算法的时间复杂度为 O(N^2)。

就空间复杂度而言，在应用暴力解法时，由 N 个点组成的数据源数据集必须存储在空间中。用于存储数据集的空间与其中点的数量相同（O(N））;数字对被用来表示每个点。我接下来要探讨的是暴力解法的 O(N) 空间复杂度特性，它不需要使用任何额外的数据结构或递归调用。通常，暴力解法在计算上并不高效，因为它的时间复杂度为 O(n^2)，它比线性增长得更快，具体取决于数据库中的项目数量。

优化方法

有效方法不同于暴力解法，它旨在快速定位最大矩形坐标，这是计算最大曼哈顿距离的第一步。最优方法的时序复杂度是其处理大量数据的效率的度量。为了获取极值坐标，maxManhattanDistanceOptimized 函数只遍历一次给定的数据集点。由于每个点都被完全检查了一次，因此该方法不再具有线性时间复杂度，但确定极值坐标仍需要 O(N) 的时间。在确定极值坐标之后，需要进行快速重复活动，例如基本的数学计算，以计算最快的曼哈顿距离。总之，决定优化方案整体时间复杂度的因素是线性时间复杂度所执行的具体操作，这意味着也实现了 O(N) 的时间复杂度。

在信息复杂度方面，精确方法和优化算法都需要存储输入数据集。O(N) 表示需要 N 个点的大小。此外，该操作独立地保留其扩展区域，作为存储和计算短期变量以及极值的位置。因此，压缩方法的内存量也保持为O(N)。总的来说，与暴力解法相比，优化技术在效率和可扩展性方面具有几个显著优势，是处理大型数据集和实际工作目的的更优选解决方案。

结论

总之，对 N 个位置的最大曼哈顿距离的分析提供了一些创新的几何计算视角。通过研究优化和暴力解法示例，我们了解了算法的复杂性和可扩展性。它是与其他方法相比最简单的方法，但由于算法具有平方“时间复杂度”，因此对于大型数据集来说毫无用处。然而，更有效的方法，它依赖于算法本身通过逻辑基础来解决问题，从而实现线性时间复杂度，是另一个方面。

对复杂性分析概念的调查表明了算法设计在解决当今我们面临的问题中的重要性。对于计算机图形、物流优化和城市规划领域的工作来说，高水平的空间分析算法至关重要。通过找到解决特定问题的最优方案，科学家和设计师可以促进新技术和创新的发展。

然而，计算几何不仅仅是距离因子的研究。它包含了各种问题，例如网格的构建、空间的索引、凸包和 Voronoi 图。每个主题都有其独特的问题，可以使用算法分析来解决。