我希望找到距离一组点的曼哈顿距离/直线距离的最小总和的点(即该点与该组中每个点之间的直线距离之和应该最小).结果点可以是给定集合中的一个点(不一定).如果存在多个具有相同最小距离的点,我希望检索所有这些点.
换一种说法:
我有一个标有某些交叉点的网格.我想找到最接近所有标记交叉点的交叉点.也就是说,我需要找到一个点,使得距离所有点的距离之和最小.
Bor*_*jev 34
关于曼哈坦距离的一个很酷的事情是距离本身包含两个独立的部分:x和y坐标上的距离.因此,您可以解决两个更简单的任务并合并它们的结果以获得所需的结果.
我所说的任务是:给定一条线上的点.找到最小化到所有点的绝对距离之和的线上的点.如果有很多人找到所有这些(顺便说一句,他们总是变成一个容易证明的单一部分).该段由该组的(可能两个)点中位数确定.中位数是指与左侧和右侧具有相同点数的点.如果点数是奇数,则没有这样的点,并且您选择在两个方向上具有差异1的点以形成该段.
在这里,我添加了这个简单任务的解决方案示例:
如果线上的点是这样的:
-4 | | | 0 | 2 3 4
^
解决方案只是一个点而已2.
如果线上的点是这样的:
-4 | | | 0 | 2 3
^---^
整个段[0,2]是问题的解决方案.
您可以单独为x和y坐标解决此任务,然后合并结果以获得最小距离点的矩形.
现在是初始任务解决方案的一个例子.
想象一下,你想要找到与该集合的Manhatan距离最小的点 (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).很明显,只要输入本身具有上述复杂性,任务就无法更快地解决.