使用分治法查找最近的点对

本节介绍了使用分治法查找最接近的点对的有效算法。给定一组点，最近对问题是找到彼此最接近的两个点。如下图所示，绘制一条线来连接最近对动画中两个最近的点。

案例研究：查找最近对，提出了一种用于查找最近点对的强力算法。该算法计算所有点对之间的距离并找到距离最小的点。显然，该算法需要 O(n^2) 时间。我们能设计一个更高效的算法吗？

我们将使用一种名为分而治之的方法来解决这个问题。该方法将问题划分为子问题，求解子问题，然后组合子问题的解以获得整个问题的解。与动态规划方法不同，分而治之方法中的子问题不重叠。子问题就像原问题一样，但规模较小，因此可以应用递归来解决问题。事实上，所有递归问题的解决方案都遵循分而治之的方法。

以下步骤描述了如何使用分而治之的方法解决最近对问题。

• 第 1 步：按 x 坐标升序对点进行排序。对于具有相同 x 坐标的点，按 y 坐标排序。这会产生一个排序的点列表 S。
• 第 2 步：使用排序列表中的中点将 S 分为两个大小相等的子集 S1 和 S2。令中点位于 S1 处。递归地找到 S1 和 S2 中最接近的对。令 d1 和 d2 分别表示两个子集中最近对的距离。
• 第3步：找到S1中的点和S2中的点之间最接近的对，并将它们的距离表示为d3。最接近的一对是距离为 min(d1, d2, d3) 的一对。

选择排序需要 O(n^2) 时间。步骤 1 可以在 O(n log n) 时间内完成。步骤 3 可以在 O(n) 时间内完成。设 d = min(d1, d2)。我们已经知道最近的对距离不能大于 d。要使 S1 中的点和 S2 中的点形成 S 中最接近的对，左边的点必须在 stripL 中，右边的点必须在 stripR 中，如下图所示（ a).

对于stripL中的点p，只需考虑d X 2d矩形内的右点，如下图(b)所示。矩形外的任何右点都不能与 p 形成最接近的对。由于 S2 中最近对的距离大于或等于 d，因此最多可以有 6 个
矩形内的点。因此，对于stripL中的每个点，最多需要考虑stripR中的六个点。

对于stripL中的每个点p，如何定位stripR中对应的d X 2d矩形区域中的点？如果 stripL 和 stripR 中的点按 y 坐标升序排序，则可以有效地完成此操作。令 pointsOrderedOnY 为按 y 坐标升序排序的点列表。 pointsOrderedOnY可以在算法中预先获得。 stripL 和 stripR 可以在步骤 3 中从 pointsOrderedOnY 获取，如下面的代码所示。

对于pointsOrderedOnY 中的每个点p
if (p 在 S1 中且 mid.x – p.x 将 p 附加到 stripL;
else if (p 在 S2 中且 p.x - mid.x 将 p 附加到 stripR;

设stripL和stripR中的点为{p0, p1, ... , pk}和{q0, q1, ... , qt}，如下所示上图(c)。可以使用下面代码中描述的算法找到 stripL 中的点和 stripR 中的点之间最接近的对。

d = min(d1, d2);
 r = 0; // r is the index of a point in stripR
 for (each point p in stripL) {
 // Skip the points in stripR below p.y - d
  while (r < stripR.length && q[r].y <= p.y - d)
  r++;

  let r1 = r;
  while (r1 < stripR.length && |q[r1].y – p.y| <= d) {
 // Check if (p, q[r1]) is a possible closest pair
 if (distance(p, q[r1]) < d) {
 d = distance(p, q[r1]);
 (p, q[r1]) is now the current closest pair;
 }

 r1 = r1 + 1;
 }
}

stripL 中的点按 p0, p1, ... , pk 的顺序考虑。对于 stripL 中的点 p，跳过 stripR 中低于 p.y – d 的点（第 5-6 行）。一旦跳过某个点，就不再考虑该点。 while 循环（第 9-17 行）检查 (p, q[r1]) 是否是可能最接近的对。这样的 q[r1] 对最多有 6 个，因为 stripR 中两点之间的距离不能小于 d。因此，在第 3 步中找到最接近的对的复杂度是 O(n)。

请注意，上述步骤中的步骤 1 仅执行一次以对点进行预排序。假设所有点都已预先排序。令 T(n) 表示该算法的时间复杂度。因此，

因此，可以在 O(n log n) 时间内找到最接近的点对。

以上是使用分治法查找最近的点对的详细内容。更多信息请关注PHP中文网其他相关文章！