14

2D の 3 点の場合:

P1(x1,y1), 
P2(x2,y2), 
P3(x3,y3)

P(x,y)マンハッタン距離の最大値となる点を見つける必要があります

max(dist(P,P1), 
    dist(P,P2), 
    dist(P,P3))

最小限になります。

アルゴリズムに関するアイデアはありますか?

私は本当に正確なアルゴリズムを好むでしょう。

4

2 に答える 2

15

この問題には正確で非反復的なアルゴリズムがあります。Knoothe が指摘したように、マンハッタン距離はチェビシェフ距離と回転的に等価であり、P は極端な座標の平均としてチェビシェフ距離に対して自明に計算可能です。

マンハッタン距離 x 内で P から到達可能な点は、P の周りに菱形を形成します。したがって、すべての点を囲む最小の菱形を見つける必要があり、その中心は P になります。

座標系を 45 度回転すると、ひし形は正方形になります。したがって、この問題は、点を囲む最小の四角形を見つけることに還元できます。

最小の囲み正方形の中心は、最小の囲み長方形の中心として見つけることができます (これは、座標の最大値と最小値として自明に計算されます)。最小の四角形の短辺に沿って中心を移動しても、最小の四角形を囲むことができるため、最小の四角形は無数にあります。私たちの目的のために、中心が囲んでいる長方形と一致するものを単純に使用できます。

したがって、アルゴリズム形式では次のようになります。

  1. x' = x/sqrt(2) - y/sqrt(2)、y' = x/sqrt(2) + y/sqrt(2) を割り当てて、座標系を回転およびスケーリングします。
  2. x'_c = (max(x'_i) + min(x'_i))/2、y'_c = (max(y'_i) + min(y'_i))/2 を計算します。
  3. x_c = x'_c/sqrt(2) + y'_c/sqrt(2)、y_c = - x'_c/sqrt(2) + y'_c/sqrt(2) で逆回転

次に、x_c と y_c は P の座標を与えます。

于 2013-03-11T20:23:17.817 に答える
4

おおよその解で問題ない場合は、単純な最適化アルゴリズムを試すことができます。Python での例を次に示します。

import random
def opt(*points):
    best, dist = (0, 0), 99999999
    for i in range(10000):
        new = best[0] + random.gauss(0, .5), best[1] + random.gauss(0, .5)
        dist_new = max(abs(new[0] - qx) + abs(new[1] - qy) for qx, qy in points)
        if dist_new < dist:
            best, dist = new, dist_new
            print new, dist_new
    return best, dist

説明: ポイント (0, 0) またはその他の任意のポイントから開始し、新しいポイントと以前の最良のポイントを維持するたびに数千回変更します。徐々に、これは最適に近づきます。

マンハッタンの最大距離を最小化する場合、単純に 3 点の平均または中央値を選択したり、x と y を個別に解いたりしても機能しないことに注意してください。反例: ポイント (0,0)、(0,20)、(10,10)、または (0,0)、(0,1)、(0,100) を考えてみましょう。最も離れたポイントの平均を選択すると、最初の例では (10,5) になり、中央値を取ると、2 番目の例では (0,1) になり、どちらも最大マンハッタンが高くなります。最適よりも距離。

更新:によって指摘されているように、 x と y を個別に解決し、最も離れた点の平均をとることは実際には機能するように見えます。

于 2013-03-11T19:46:39.263 に答える