logo标签列表

所有距离其他给定点的曼哈顿距离最小的点 [优化]

algorithmoptimization
9
这里的问题是找到所有整数点的集合，使得给定点集上所有曼哈顿距离的总和最小！
例如：
假设有一个给定的点集{ P1, P2, P3...Pn }。
基本问题是找到一个点X，它在所有点 { P1, P2, P3... Pn } 上的距离之和最小。
即 |P1-X| + |P2-X| + .... + |Pn-X| = D，其中D是所有X中最小的。
更进一步，可能会有多个X值满足上述条件。即可能会有多个X可以产生相同的D值。因此，我们需要找到所有这样的X。
任何人都可以想到的一种基本方法是找到输入的中位数，然后暴力枚举坐标，这在这篇文章中有提到。
但是这种方法的问题是：如果中位数给出两个非常远的值，那么我们最终会尝试暴力枚举所有点，这将永远无法在给定时间内运行。
因此，是否有其他方法可以在点之间非常远的情况下获得结果（其中中位数给出的范围为10^9级别）？
@BlueRaja-DannyPflughoeft floor(mean)不能给你最小距离。拿[0,99,100,101]为例。floor(mean) = ceiling(mean) = 75，但是最接近的点是99和100。 - soulcheck
@soulcheck：啊，你说得对，使用平均值实际上会最小化平方和。 - BlueRaja - Danny Pflughoeft
4个回答
11

您可以分别考虑X和Y，因为它们独立于彼此地增加距离。这将问题简化为，在一条线上给定n个点的情况下，找到一个与其他点的距离之和最小的点。很简单：介于两个中位数之间（包括中位数）的任何点都将满足此要求。

证明：如果我们有偶数个点，则会有两个中位数。处于两个中位数之间的点将具有n/2个点在左侧和n/2个点在右侧，并且与这些点的总距离之和为S。

如果我们将其向左移动一个点，则S将增加n/2 （因为我们正在远离最右边的点）并减少n/2 （因为我们正在靠近最左边的点），因此总体上S保持不变。直到我们触及最左边的中位数点时，这仍然是正确的。当我们向最左边的中位数点左移一个点时，现在我们有(n/2 + 1)个点在右侧，(n/2 - 1)个点在左侧，因此S增加了两个。继续向左移动只会进一步增加S。
按照同样的逻辑，右侧最右边的点也具有更高的S。

如果我们有奇数个点，则只有一个中位数。按照与上面相同的逻辑，我们可以证明它具有最低的S值。

2
讲解得非常好，对我理解解决方案有很大帮助。谢谢您！ :) - iwc2010005
3
如果中位数给出的区间大约是10^9，那么该区间内的每个点都与其他任何点一样好。因此，根据您后面想要对这些点做什么，您可以返回范围或枚举该范围内的点。没有其他方法。显然，在二维中，您将获得一个边界矩形，在三维中，将获得一个边界长方体等等。结果始终是为每个维度获得的范围的笛卡尔积，因此您可以将这些范围的列表作为结果返回。
你的回答很有说服力。这意味着在点数为奇数的情况下，最小距离处始终会有一个单独的点。如果我只想计算最小距离处的点数，在点数为奇数的情况下，它总是1，在偶数情况下，它是由中位数给定的间隔的乘积。对吗？ - iwc2010005
@LoginTest 只是为了明确。如果点数为奇数，则在每个维度中您将获得单个中位数。因此，如果点数为奇数，则只有一个“最接近”的点。 - soulcheck
1

由于曼哈顿距离中每个分量都是独立的，因此您也可以单独考虑它们。最佳答案是（中位数(x)，中位数(y)）。您需要在该点周围寻找整数解。

注意：我在回答时没有仔细阅读您的问题。我的答案仍然正确，但您可能已经知道了这个解决方案。

0

是的，我也认为对于在网格上的N个点中的奇数个点，只会有一个点（即中位数）其到所有其他点的曼哈顿距离之和最小。

对于偶数值的N，情况会有所不同。

据我所知，如果两个集合X = {1,2} 和 Y= {3,4} ，它们的笛卡尔积将始终为4。

即 X × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}。这是我目前理解的内容。

对于偶数个值，我们总是取"中间两个"值作为中位数。从X中取2个值，并从Y中取2个值将始终返回4个点的笛卡尔积。

如果我错了，请纠正我。

你对中位数的事情是正确的，但是对笛卡尔积的事情是错误的。实际上，X和Y可以有很大的范围，因此更多的点将满足条件，而不仅仅是所有情况下的4个点。 点的数量将是(|x1-x2+1|*|y1-y2+1|)，其中{x1,x2}是X轴坐标的中位数，{y1,y2}是Y轴坐标的中位数。 - iwc2010005
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接