假设我们在 M-by-M
网格上有 p
个随机点。我们想在网格上找到到所有 p
点的曼哈顿距离之和最小的点。
我的想法:我认为也许通过对所有 x 和 y 求平均值并尝试接近该点的所有 9 个点,我们可能会找到请求的点。但似乎这种方法不起作用:
static void find_center(int p , int M){
int[][] point = new int[p][2]; // initializing p points as random
Random r = new Random();
for (int i = 0 ; i < p ; i++){
point[i][0] = r.nextInt(M);
point[i][1] = r.nextInt(M);
}
//the naive brute force approach to find the real closest point on the grid
int min_distance = Integer.MAX_VALUE;
int[] result = new int[2];
for (int i = 0 ; i < M ; i++){
for (int j = 0 ; j < M ; j++){
int d = 0;
for (int k = 0 ; k < point.length ; k++){
d += Math.abs(i - point[k][0]);
d += Math.abs(j - point[k][1]);
}
if (d < min_distance){
min_distance = d;
result[0] = i;
result[1] = j;
}
}
}
System.out.println(min_distance);
System.out.println(result[0] + " : " + result[1]);
//the other proposed approach
System.out.println("---------");
int x = 0;
int y = 0;
for (int i = 0 ; i < point.length ; i++){
x += point[i][0];
y += point[i][1];
}
x /= point.length;
y /= point.length;
min_distance = Integer.MAX_VALUE;
for (int a : new int[] {-1,0,1}){
for (int b : new int[] {-1,0,1}){
int d = 0;
for (int k = 0 ; k < point.length ; k++){
d += Math.abs(x + a - point[k][0]);
d += Math.abs(y + b - point[k][1]);
}
if (d < min_distance){
min_distance = d;
result[0] = x + a;
result[1] = y + b;
}
}
}
System.out.println(min_distance);
System.out.println(result[0] + " : " + result[1]);
return;
}
最佳答案
我认为您正在寻找的点位于中值 X 和中值 Y:X 和 Y 在它们之前(分别在 X 和 Y 维度中)和之后的点一样多)。
此时,向左或向右移动不会减少总距离,因为左右连接的数量相同。上下 Y 也是如此。
这是由于曼哈顿距离的定义有些特殊,其实你可以分别计算X和Y的曼哈顿距离总和,然后相加。
编辑:中位数很容易计算,只需列出 X 的所有值,对其进行排序,然后选择列表中间的那个。 Y 也一样。
关于algorithm - 寻找二维平面上n个点的几何中心——曼哈顿距离,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19349416/