4

コーメンの著書「アルゴリズムの紹介」の第9 章に郵便局の場所の問題があります。

重み w1,w2,....wn を持つ n 個の点 p1,p2,...pn が与えられます。合計 wi*d(pi,p) を最小化するポイント p (入力ポイントの 1 つとは限りません) を見つけます。ここで、d(a,b) = ポイント a、b 間の距離です。

同じ の解決策を見ると、加重中央値がこの問題の最良の解決策であることがわかります。

しかし、実際のコーディング部分と使用法について、いくつかの根本的な疑問があります。

  • すべての要素の重みが等しい場合、重み付けされた中央値を見つけるために、すべての重みの合計が 1/2 未満になる点を見つけます。ここを拡張するには？

  • 重みとしてさまざまな家に配達される手紙の数を言う実際のシナリオが与えられ、郵便局の場所を見つけることによって移動距離を最小限に抑えたいと考えています。 ）、実際にどうやってそれを行うのでしょうか？

誰かが私の疑問を解消し、問題を理解するのを手伝ってくれませんか.

編集 ：

私も非常によく似た問題について考えていました:長方形のグリッド(2d)があり、さまざまな場所にさまざまな数の人々がいて、すべてが1点で会いたいと思っています(間違いなく整数座標を持つ必要があります)。上記の問題と、それをどのように解決しますか?

4

2 に答える 2

4

それでも、重みの合計が1/2になるポイントが必要です。任意のポイントを選択し、そこから1ポイントを左に移動するか、1ポイントを右に移動する方がよいかを検討します。左に1ポイント移動すると、左側のすべてのポイントまでの距離が1つ短くなり、右側のすべてのポイントまでの距離が1つ長くなります。これで勝つか負けるかは、左側の重みの合計と右側の重みの合計によって異なります。重みの合計が1/2にならない場合は、重みが1/2を超える方向に移動することで改善できるため、別の重みを選択しても改善できないポイントは、重みが1/2のポイントのみです。 -または、より正確には、両側の重みが両方とも<=1/2になるポイント。

1/2が正解であるためには、重みの合計を1にする必要があります。したがって、文字の数である重みから始める場合は、それらを文字の総数で割って、合計を1にする必要があります。もちろん、このペナルティ関数は、配信される文字ごとに個別に移動する必要がない限り、実際には意味がありませんが、それを無視することになっていると思います。

編集

複数の次元の場合、距離の加重和を直接最小化するという問題を解決することになります。ウィキペディアでは、これについてhttp://en.wikipedia.org/wiki/Geometric_medianで説明しています。重みを考慮に入れたいのですが、それでも問題はそれほど複雑にはなりません。それを行う1つの方法は、http：//en.wikipedia.org/wiki/Iteratively_reweighted_least_squaresです。残念ながら、それは、検出したソリューションがグリッドポイント上にあること、またはソリューションに最も近いグリッドポイントが最適なグリッドポイントになることを保証するものではありません。おそらくそれほど悪くはないでしょうが、考えられるすべての場合に最適なグリッドポイントを見つけるのは難しいかもしれません。

于 2012-07-21T19:26:45.313 に答える
-1

編集：この答えは間違っています。コメントを参照してください

あなたが探しているのは重心と呼ばれるものです（TMHO加重中央値は1次元の重心です）。

最初の質問がわかりませんでした。詳細を教えてください。

あなたの例では、この位置にリンクされているオフィスごとの文字数で重み付けされた平均位置を計算します。これにより、x_center = sum(x_i * w_i) / sum(w_i) および y_center = sum(y_i * w_i) / sum(w_i) が得られます。

それはあなたの問題に正しく答えましたか?

于 2012-07-21T15:19:38.550 に答える