最小曼哈顿距离的算法

Question

我希望找到一组点中曼哈顿距离/直角距离之和最小的点（即该点与集合中每个点之间的直角距离之和应该最小）。得出的点可以是给定集合中的某个点（但不一定如此）。如果存在多个与最小距离相同的点，则希望检索所有这些点。

换句话说，我有一个网格，其中标记了某些交点。我想找到最靠近所有标记交点的交点。也就是说，我需要找到一点，使得所有点到该点的距离之和最小。

- user1045047

---

这是作业吗？如果是，我们应该添加那个标签。另外，你是否被给予一个点列表以从中选择答案？ - Jonathan M

那么你的问题是什么？我认为这不是一个真正的问题。 - moooeeeep

你是在问：我有一个网格，某些交叉点已标记。我想找到一个交叉点，它离所有标记的交叉点最近。吗？ - Jonathan M

这是一个经典问题。请参阅马丁·加德纳(Martin Gardner)的书《啊哈！洞察力》中的“女友问题”。 - Tyler Durden

@TylerDurden 那里提出的解决方案是否与我提出的类似？如果不是，您可以添加另一个答案作为参考。如果您这样做，请@我以便我收到通知 :) - Boris Strandjev

Answer 1

曼哈顿距离的独特之处在于距离本身由两个独立的部分组成：x和y坐标上的距离。因此，您可以解决两个简单的任务并将它们的结果合并以获得所需的结果。

我所说的任务是：给定一条线上的点，找到使所有点到该点的绝对距离之和最小的点。如果有多个，请找出所有这些点（顺便说一句，它们总是转化为一个单段，这很容易证明）。该段由集合的（可能是两个）中位数点确定。中位数是指左右两侧的点数相等的点。如果点数是偶数，则没有这样的点，并选择两个方向上差为1的点来形成该段。

这里我添加了几个解决这个简单任务的示例：

如果线上的点像这样：

-4 | | | 0 | 2 3 4
             ^

解决方案只是一个点，它是2。

如果线上的点是这样的：

-4 | | | 0 | 2 3
         ^---^

整个区间 [0, 2] 是这个问题的解。

你需要分别针对 x 和 y 坐标解决这个任务，然后将结果合并以获得最小距离点的矩形。

---

示例

现在给出一个初始任务的解决示例。

假设你想要找到到集合 (0, 6), (1, 3), (3, 5), (3, 3), (4, 7), (2, 4) 中与点最小曼哈顿距离的点。

你需要分别解决两个简单任务：

对于 x：

0 1 2 3 3 4
    ^-^

这里的解决方案是段落 [2, 3]（注意这里有重复的点3，我可能没有用最直观的方式表示）。

对于y：

3 3 4 5 6 7
    ^-^

这里的解决方案是段落[4, 5]。

最终，我们得到了初始任务的解决方案公式为矩形：

 2 <= x <= 3; 4 <= y <= 5 

---

复杂度

由于很多人对这篇文章感兴趣，我决定将其改进一下。

让我们谈谈复杂度。

任务的复杂度实际上与解决更简单任务的复杂度相同（因为正如已经讨论过的那样，解决方案实际上包括解决两个更简单的任务）。许多人会通过排序然后选择中位数来解决它。然而，这将导致O(nlog n)的复杂度，其中n是输入集合中点的数量。

如果使用更好的查找第k个元素算法（C++ STL中实现示例），可以提高效率。该算法基本上遵循与qsort相同的方法。运行时间为O(n)。即使在两个中位数点的情况下，它仍将保持线性（需要两次运行相同的算法），因此算法的总复杂度变为O(n)。很明显，只要输入本身具有所述的复杂度，就无法更快地解决任务。

- Boris Strandjev

---

谢谢提供的示例，帮了我很多忙。 - user1045047

为什么中位数是这个问题的解决方案？ - milo

运行时间不是O(n)，而是平均情况下的O(n)。 - Yola

@dh16 在我找到的解决方案中，所有点到目标集合中所有点的曼哈顿距离之和相等。当然，在选择矩形的不同点时，目标集合中单个点的曼哈顿距离可能会发生变化。 - Boris Strandjev

@BorisStrandjev 非常感谢。 - dh16