9

ここでの問題は、与えられた点のセットからすべてのマンハッタン距離にわたって最小の合計を与えるすべての整数点のセットを見つけることです！

例えば：

与えられた点のセット{P1、P2、P3...Pn}を持つことができます

基本的な問題は、点{P1、P2、P3...Pn}からのすべての距離にわたって最小の合計を持つXなどの点を見つけることです。

すなわち|P1-X| + | P2-X | + .... + | Pn-X | = D、ここでDはすべてのXで最小になります。

さらに一歩進むと、上記の条件を満たすXの値が複数存在する可能性があります。つまり、同じ値Dを与える複数のXが可能である可能性があります。したがって、そのようなXをすべて見つける必要があります。

誰もが考えることができる基本的なアプローチの1つは、入力の中央値を見つけてから、この投稿で言及されている座標をブルートフォースすることです。

しかし、そのようなアプローチの問題は、中央値が非常に離れた2つの値を与える場合、特定の時間内に実行されることのないすべてのポイントをブルートフォース攻撃することになります。

それで、ポイントが非常に離れている場合でも結果をもたらす他のアプローチはありますか（中央値は10 ^ 9のオーダーの範囲を与えます）。

4

4 に答える 4

10

XとYは互いに独立して距離を追加するため、別々に考慮することができます。これにより、線上にn個の点が与えられた場合に、他の点までの距離の合計が最小の点を見つけるという質問が減ります。これは単純です。2つの中央値（両端を含む）の間の任意の点がこれを満たします。

証明：ポイントの数が偶数の場合、中央値は2つになります。2つの中央値の間のポイントは、左にn / 2ポイント、右にn / 2ポイント、およびSのそれらのポイントまでの距離の合計になります。

左に1ポイント移動すると、Sはn / 2 （右端のポイントから離れているため）上に移動し、n / 2 （左端のポイントに向かって移動しているため）下に移動します。 ）、したがって全体的なSは同じままです。これは、左端の中央値に達するまで当てはまります。左端の中央値の1つ左に移動すると、（n / 2 + 1）ポイントが右に、（n / 2 --1）が左にポイントするので、Sは2つ上がります。左に進むと、Sがさらに増加するだけです。
同じ論理で、右端の中央値の右側にあるすべてのポイントのSも高くなります。

ポイントの数が奇数の場合、中央値は1つだけです。上記と同じロジックを使用して、Sの値が最も低いことを示すことができます。

于 2012-05-02T20:18:41.577 に答える
3

中央値が10^9のオーダーの間隔を与える場合、その間隔の各ポイントは他のポイントと同じくらい良好です。

したがって、後でそれらのポイントをどのように処理するかに応じて、範囲を返すか、その範囲内のポイントを列挙することができます。それを回避する方法はありません。

明らかに、2次元では長方形が、3次元では直方体などが表示されます。

結果は常に各ディメンションに対して取得された範囲のデカルト積になるため、結果としてそれらの範囲のリストを返すことができます。

于 2012-05-02T19:01:30.510 に答える
1

マンハッタン距離では、各コンポーネントが別々に寄与するため、それらを別々に考慮することもできます。最適な答えは（median（x）、median（y））です。整数解については、この点を見回す必要があります。

注：回答中にあなたの質問を正しく読みませんでした。私の答えはまだ当てはまりますが、おそらくあなたはこの解決策についてすでに知っていたでしょう。

于 2012-05-02T17:29:17.970 に答える
0

はい、グリッド上のN点の数が奇数の場合、他のすべての点からのマンハッタン距離の最小合計となる単一の点（つまり、中央値）のみが存在すると思います。

Nの値が偶数の場合、シナリオは少し異なります。

私によると、2セットX = {1,2} and Y= {3,4}の場合、デカルト積は常に4になります。

すなわちX × Y = {1,2} × {3,4} = {(1,3), (1,4), (2,3), (2,4)}。これは私がこれまでに理解したことです。

偶数の値については、常に「MIDDLETWO」の値をMEDIANとして使用します。Xから2、Yから2を取ると、常に4ポイントのデカルト積が返されます。

私が間違っている場合は私を訂正してください。

于 2012-05-03T07:30:27.790 に答える