1

Yahooの機械学習プロフィールでこんな質問がありました。一連のポイント (x,y) 座標が与えられると、O(n) または O(log n ) 時間で最小距離のポイントを見つけるように求められました。明らかに、私は O(n^2) 時間を思い付くことができましたが、より良いアルゴリズムを得るにはほど遠いものでした. 問題文は分割統治を叫んでいたにもかかわらず、私はマージステップの理由を思いつくことができませんでした. また、インターネットでこの質問をグーグル検索したところ、実際には非常に人気があることがわかりましたが、マージステップの理由を理解できませんでした。

誰でもこれで私を助けることができますか?

入力: (x1,y1),(x2,y2),(x3,y3),(x4,y4),(x5,y5)

4

1 に答える 1

5

この問題は、次のように、再帰的な分割統治法を使用して O(n log n) 時間で解決できます。

1. ポイントを x 座標に従って並べ替えます。

2.点のセットを垂直線 x=xmid によって 2 つの等しいサイズのサブセットに分割します。

3.左部分集合と右部分集合で再帰的に問題を解きます。これにより、左側と右側の最小距離 dLmin と dRmin がそれぞれ得られます。

4.1 つの点が分割垂直線の左側にあり、2 番目の点が右側にある点のペアの間で最小距離 dLRmin を見つけます。

5.最終的な答えは、dLmin、dRmin、dLRmin の最小値です。

http://en.wikipedia.org/wiki/Closest_pair_of_points

于 2012-09-05T15:02:27.630 に答える