本节介绍了使用分治法查找最接近的点对的有效算法。给定一组点，最近对问题是找到彼此最接近的两个点。如下图所示，绘制一条线来连接最近对动画中两个最近的点。
案例研究：查找最近对，提出了一种用于查找最近点对的强力算法。该算法计算所有点对之间的距离并找到距离最小的点。显然，该算法需要 O(n^2) 时间。我们能设计一个更高效的算法吗？
我们将使用一种名为分而治之的方法来解决这个问题。该方法将问题划分为子问题，求解子问题，然后组合子问题的解以获得整个问题的解。与动态规划方法不同，分而治之方法中的子问题不重叠。子问题就像原问题一样，但规模较小，因此可以应用递归来解决问题。事实上，所有递归问题的解决方案都遵循分而治之的方法。
以下步骤描述了如何使用分而治之的方法解决最近对问题。
选择排序需要 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中文网其他相关文章！
