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

最小スパニング ツリーは、他のすべてのポイントへの最短距離ツリーを計算できます。

于 2013-10-13T19:46:36.637 に答える