0

假设我们在网格p上有随机点。M-by-M我们想在网格上找到一个到所有点的曼哈顿距离总和最小的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;
}
4

3 回答 3

3

我认为您正在寻找的点是中位数 X 和中位数 Y：X 和 Y 在它们之前有尽可能多的点 - 分别在 X 和 Y 维度中 - 和它们之后一样）。

此时，向左或向右移动不会减少总距离，因为左侧和右侧的连接数相同。上下 Y 也是如此。

这是由于曼哈顿距离的定义有些奇特，实际上可以在X和Y中分别计算曼哈顿距离的总和，然后相加。

编辑：中位数很容易计算，只需列出 X 的所有值，对其进行排序，然后选择列表中间的那个。Y也一样。

于 2013-10-13T19:45:10.917 回答
0

正如 jdv-Jan de Vaan 所说，以下代码有效：

    Arrays.sort(point , new Comparator<int[]>(){
        @Override
        public int compare(int[] arg0, int[] arg1) {
            return Double.compare(arg0[0], arg1[0]);
        }
    });
    int median_x = point[point.length/2][0];
    Arrays.sort(point , new Comparator<int[]>(){
        @Override
        public int compare(int[] arg0, int[] arg1) {
            return Double.compare(arg0[1], arg1[1]);
        }
    });
    int median_y = point[point.length/2][1];
    int min_distance = 0;
    for (int i = 0 ; i < point.length ; i++){
        min_distance += Math.abs(point[i][0] - median_x) + Math.abs(point[i][1] - median_y);
    }
    System.out.println(min_distance);
    System.out.println(median_x + " : " + median_y);
于 2013-10-13T19:59:58.827 回答
0

最小生成树可以计算到所有其他点的最短距离树。

于 2013-10-13T19:46:36.637 回答