0

チェビシェフ距離の下にある一連の点の重心を見つけようとしています。私が試したケースでは明らかに機能するプログラムを書きましたが、アクセスできないいくつかのエッジケースでは明らかに間違った答えを返します。[メタ リマーク: この宿題にマークを付けたはずですが、タグは廃止されつつあります]

追跡するために、重心は、一連のポイントまでの平均距離が最小のポイントです。2 次元の 2 点 p と q のチェビシェフ距離は、

チェビシェフ距離

また、整数座標を持つ点に制限されています。

これは私のコードです：

sum_x=0; sum_y=0
for p in points:
    sum_x = sum_x + p[0]
    sum_y = sum_y + p[1]
center_x = int(sum_x/N)
center_y = int(sum_y/N)

directions = [(-1,-1),
     (-1,0),
     (-1,1),
     (0,-1),
     (0,0),
     (0,1),
     (1,-1),
     (1,0),
     (1,1)]

distances = [0] * len(directions)
for p in points:
    for i in range(len(directions)):
        distances[i] = distances[i] + max(abs(center_x+directions[i][0]-p[0]),abs(center_y+directions[i][1]-p[1]))

best_direction = min(range(len(directions)), key = lambda i:distances[i])

print "centroid = (", center_x+directions[best_direction][0],",", center_y+directions[best_direction][1],")"

print "total distance = ", distances[best_direction]

これが私の理論的根拠です: チェビシェフ計量は、2 次元で回転するマンハッタン距離と同じです。基本的に、ポイントの通常の平均と同じであるマンハッタンの重心を見つけてから、隣接する積分ポイントを検索して、実際のチェビシェフの重心を取得します。しかし、コードにバグが見つからないようです。

4

1 に答える 1

1

あなたの論理的根拠は、ある点で間違っています。マンハッタンの重心はポイントの平均ではありません。たとえば、点集合 (0, 0) を考えます。(1, 0); (100, 0)。平均は (33.66, 0) ですが、代わりに (1, 0) を選択することでより良い結果が得られた可能性があります。さらにいくつかの例を実行すると、実際の答えが簡単にわかるはずです。

また、Chebyshev metric は Manhattan distance under rotationと同等であると述べていますが、コード内のどこでもポイントを回転させません。これは少なくとも一貫性がないように見えます。代わりに、回転した空間でマンハッタンの重心を計算するべきではありませんか?

于 2012-10-05T02:31:01.473 に答える