Massive Algorithms: Minimum Sum of Manhattan Distance

http://blog.csdn.net/yuanhisn/article/details/46118191

In a city there are N persons. A person can walk only horizontally or vertically. Find a point that minimizes the sum of distances all persons walk to the point.

This is called the manhattan distance since a person can walk only horizontally or vertically, like in the city of Manhattan.

Let's assume this is 1-dimensional. Then for 2 persons, the point can be any point on the line connecting the 2 persons. For 3 persons , the point is the middle person. For 4 persons, the point can be any point between the middle 2 persons. For 5 persons, the point is the middle person. In general, for odd number of persons, it's the person in the middle; for even number of persons, it's any point between the middle 2 persons.

This can be extended to 2-dimensional. The answer is the point (x, y), where x and y are the median points taken independently of all the xi and yi for i = 1 to n. [1][2]

The cool thing about the Manhatan distance is that the distance itself comprises of two independent components: the distance on the x and y coordinate. Thus you can solve two simpler tasks and merge the results from them to obtain the desired results.

Minimum Sum of Manhattan Distance | tech::interview

已知平面上有N个点，找到其中某个点P，使得P到其余所有点的Manhattan距离之和最短并求出这个最短距离。

因为是曼哈顿距离，所以可以把x轴和y轴分离开来计算。

针对x坐标对所有点排序。

求一个数组，每个元素为对应点到其他所有点的在x轴上的距离和。
这一步需要O(n)的算法，具体思路是，记录两个数组，left和right:
left[i] = x[1] + x[2] + ... + x[i-1]
right[i] = x[i+1] + x[i+2] ... + x[n]
然后对每个点
sum[i] = x[i] * i - left[i] + right[i] - (n - 1 - i) * x[i]

针对y坐标重复1和2的计算。

求得每个点在x和y上的1D曼哈顿距离和之后，可以遍历所有点，直接找出最小值。

http://www.jiuzhang.com/problem/30/
初阶：因为采用曼哈顿距离，所以可以分开考虑x坐标和y坐标。将k个点的x坐标排序，可以知道要求的x坐标一定在这k个点的x坐标上，扫描一遍并统计到各个点的x坐标距离和，找到使得距离和最小的x坐标。这一步只需要O(k)的时间复杂度，而不是O(k^2)，怎么优化这里不多赘述。对y坐标做同样的操作，从而得到答案。时间复杂度O(klogk)，排序的复杂度。

进阶：通过初阶的算法得到一个最优位置，如果这个位置与k个点重合，则从这个位置开始进行搜索，将这个点周围的点和对应的距离放入到一个堆里，每次从堆中取出最小距离的点，然后将这个点周围的点放入堆中，直到取出的点不与所给k个点重合。时间复杂度klogk，因为最多从堆中取出k+1个点即可找到一个不与所给k个点重合的点。堆每次操作为logk。

面试官角度：
本题的最优算法较难想到。所以如果公司要求不高，答出O(nm)的方法即可。O(nm)的方法是因为假设我们知道在(x,y)这个位置的距离和为S，那么当(x,y)移动到(x+1,y)和(x,y+1)的时候，我们可以在O(1)的时间更新S。方法是预处理每一行上方/下方有多少个k个点中的点，每一列左侧/右侧有多少个k个点中的点。上面的解答基于nm>>klogk，如果k比较大，则还是O(nm)的方法更好。答题时需要答出对于给定参数不同情况下采用不用算法这一点。

#堆#
#矩阵#
#排序#

map<pair<int,int>,int> mht_sum(const vector<Point>& pts, bool get_x) {


int n = (int)pts.size();

vector<int> left(n), right(n);



int sum = 0;

for(int i = 0; i < n; ++i) {

left[i] = sum;

sum += get_x ? pts[i].x : pts[i].y;

}

sum = 0;

for(int i = n - 1; i >= 0; --i) {

right[i] = sum;

sum += get_x ? pts[i].x : pts[i].y;

}   

map<pair<int,int>,int> ret;

for(int i = 0; i < n; ++i) {

int p = get_x ? pts[i].x : pts[i].y;

ret[{pts[i].x,pts[i].y}] = p * i - left[i] + right[i] - (n-1-i) * p;

}

return ret;

}



int min_mht_dis(vector<Point> pts) {

sort(pts.begin(), pts.end(), [&](const Point& p0, const Point& p1){

return p0.x < p1.x;

});

auto x_sums = mht_sum(pts, true);



sort(pts.begin(), pts.end(), [&](const Point& p0, const Point& p1){

return p0.y < p1.y;

});

auto y_sums = mht_sum(pts, false);



int ret = INT_MAX;

for(int i = 0; i < pts.size(); ++i) {

ret = min(ret, x_sums[{pts[i].x,pts[i].y}] + y_sums[{pts[i].x,pts[i].y}]);

}

return ret;

}

http://www.haodaima.net/art/1630004
曼哈顿距离最小生成树

http://www.jiuzhang.com/problem/30/

初阶：因为采用曼哈顿距离，所以可以分开考虑x坐标和y坐标。将k个点的x坐标排序，可以知道要求的x坐标一定在这k个点的x坐标上，扫描一遍并统计到各个点的x坐标距离和，找到使得距离和最小的x坐标。这一步只需要O(k)的时间复杂度，而不是O(k^2)，怎么优化这里不多赘述。对y坐标做同样的操作，从而得到答案。时间复杂度O(klogk)，排序的复杂度。

进阶：通过初阶的算法得到一个最优位置，如果这个位置与k个点重合，则从这个位置开始进行搜索，将这个点周围的点和对应的距离放入到一个堆里，每次从堆中取出最小距离的点，然后将这个点周围的点放入堆中，直到取出的点不与所给k个点重合。时间复杂度klogk，因为最多从堆中取出k+1个点即可找到一个不与所给k个点重合的点。堆每次操作为logk。

O(nm)的方法是因为假设我们知道在(x,y)这个位置的距离和为S，那么当(x,y)移动到(x+1,y)和(x,y+1)的时候，我们可以在O(1)的时间更新S。方法是预处理每一行上方/下方有多少个k个点中的点，每一列左侧/右侧有多少个k个点中的点。上面的解答基于nm>>klogk，如果k比较大，则还是O(nm)的方法更好。答题时需要答出对于给定参数不同情况下采用不用算法这一点。
http://flexaired.blogspot.com/2013/02/minimum-manhattan-distance.html

http://www.mitbbs.com/article_t/Programming/31346575.html
进阶：如果要求这个点与所给的k个点不重合，该怎么办？

II. Geometric median.
The geometric median of a discrete set of sample points in a Euclidean space is the point minimizing the sum of distances to the sample points [3]. This no longer requires the path be horizontal or vertical.

Despite the simple form, the solution is much more complex than the similar problem of finding the center of mass, which minimizes the sum of the squares of distances of the points to the center. There is no simple formula for the solution.

For 2 points, it's any point on the line connecting the 2 points.

For 3 non-collinear points, the problem is known as Fermat's problem. Solution is in [3]. For 4 co-planar points, the solution is also in [3].

For more points, the solution can be approximated by numerical methods such as the Weiszfeld's algorithm.

References:
[1] Shortest distance travel - common meeting point
[2] Algorithm to find point of minimum total distance from locations
[3] Geometric median

Minimum Sum of Manhattan Distance | tech::interview

Labels

Popular Posts