c++ 問題解決のためのプログラミング一巡り - 与えられた半径の1つの円で最大点数をカバーするアルゴリズム




格子点 個数 (9)

いくつかの点がある平面があるとしましょう。 与えられた半径の円もあります。

最大の可能なポイント数をカバーする円の位置を決定するアルゴリズムが必要です。 もちろん、そのような位置が多数あるため、アルゴリズムはそれらの位置の1つを返す必要があります。
精度は重要ではなく、アルゴリズムは小さなミスをする可能性があります。

ここでは例の写真です:

入力:
int n (n <= 50) - ポイント数。
float x[n]float y[n] - ポイントのX座標とY座標を持つ配列。
float r - 円の半径。

出力:
float cxfloat cy - 円の中心の座標

アルゴリズムのライトニング速度は必要ありませんが、遅すぎるようにしてはいけません。

C ++コードが推奨されますが、必須ではありません。


Answers

これは文献の「ディスクの一部をカバーする問題」です。グーグルグレーディングを開始するのに適しています。 1つの可能な解を扱う論文がありますが、数学的には少し激しいです: http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf : http://www.utdallas.edu/~edsha/papers/bin/ISPAN04_cover.pdf

実際には、これは計算幾何学と呼ばれる領域にあります。これは魅力的ですが、トーンホールドを得るのが難しい場合があります。テーマに関連するさまざまなアルゴリズムについてdeBergが概説しています。


一見すると、私はクワッドツリーソリューションと言うでしょう。

また、与えられたデータのクラスタを作るK-meansという情報視覚化/データマイニング法もある。 目的に合わせて最終的に機能を追加して使用することができます。

K-Meansの基本アルゴリズムは次のとおりです。

  1. クラスタリングされているアイテムによって表される空間にK点を置く - これらの点は初期のグループ重心を表す
  2. それぞれのデータ項目を最も近い重心を持つグループに割り当てる
  3. すべてのアイテムが割り当てられたら、ドットの平均位置を計算してKセントロイドの位置を再計算します
  4. セントロイドが動かなくなるまでステップ2とステップ3を繰り返します。

追加された機能は次のようになります。

  1. Kセントロイドに位置するサークル内の点の数を計算する
  2. あなたに一番合うものを選んでください;)

ソース:
K平均アルゴリズム - LinköpingUniversity
Quadtree - en.wikipedia.org/wiki/Quadtree

wikipediaのクイック検索とソースコード: en.wikipedia.org/wiki/K-means_clustering


提案されたとおり、より良い言葉遣いに編集されました:

基本的な観察:

  • 私は半径が1であると仮定します。何も変化しないからです。
  • 任意の2つの点があれば、それらが存在する単位円は最大でも2つ存在する。
  • あなたの問題の解決策の円があれば、その中にあなたのセットの同じ数のポイントを維持しながら、それがあなたのセットの2つのポイントを含むまでそれを移動することができます。

アルゴリズムは次のとおりです。

  • 各点の対について、それらの距離が<2である場合、それらを通過する2つの単位円C1およびC2を計算する。
  • C1とC2の中であなたのセットのポイントの数を計算する
  • 最大を取る。

精度が重要でなく、アルゴリズムが小さなミスをしているのであれば、私は次のように思います。

点(0,0)に最大値を持ち、半径Rの円の内側の点でのみ有意である関数であるとするf(x,y) = e^{(x^2 + y^2)/ (2 * R^2)}

(x_i,y_i)を点とし、 E_i(x,y) = f(x - x_i, y - y_i)

あなたの問題は、 \sum_i E_i(x,y)最大値を見つけることです。 。

各点から勾配降下を開始することができます。


O(n)近似アルゴリズムとO(n ^ 2 log n)正確(非近似)アルゴリズムの2つのアイデアがあります:

高速近似

ローカリティセンシティブハッシングを使用する。 基本的に、各ポイントをすべての近くのポイントを含むハッシュバケットにハッシュします。 バケットは、近くのポイント間でのみ衝突が発生するように設定されています。類似の名前のハッシュテーブルとは異なり、ここでは衝突が便利です。 バケット内の衝突数を連続してカウントし、そのバケットの中心をサークルの中心として使用します。

私は、これが最初にあなたがそれを聞いたときには、はっきりとした概念ではないことを素早く説明していることを認めます。 類推は、郵便番号が何であるかを人々に尋ね、最も一般的な郵便番号を使用して最も人口の多いサークルを決定することです。 それは完璧ではありませんが、良いヒューリスティックです。

基本的にはポイント数のリニアな時間で、データセットを即座に更新して、ポイントごとに一定の時間内に新しい回答を徐々に得ることができます(n =ポイント数で一定です)。

ローカリティに敏感なハッシュについての一般的な情報、この場合に動作する個人的に好きなバージョンについての情報。

ブルートフォースよりも優れた決定論的アプローチ

アイデアは:各点について、その点に円の端を置き、どの方向に最も多くの点が含まれているかを見るために円を掃引します。 すべての点でこれを行い、グローバル最大値を見つける。

点p周りの掃引は、n log n時間で行うことができます。(a)角度θで円を配置するときに、qを含むように他の点qごとの角度間隔を求めます。 (b)線形時間でpの周りを行進/掃引できるように間隔をソートする。

だから、O(n log n)時間で固定小数点pに触れる最善の円を見つけて、O(n)でそれを掛けてすべての点をチェックします。 合計時間はO(n ^ 2 log n)です。



密度マップをお勧めしますか? xとyの最小値と最大値の境界を求めます。 xとyの範囲の範囲を、サークルの直径に等しい幅を持つビンに分割します。 xとyの各ビン内の点の数を別々に数えます。 最も高いランクのxビンと最も高いランクのビンとの密度マップ上の交差点を見つけてください。

これは、大量のデータセットをすばやく一般化するための非常に高速なアルゴリズムですが、正確性を向上させるために、ビンを小さく小さくしたり、ビンの位置を左右にn回シフトしたり、投票システムを使用して試行の間に最も頻繁に発生する回答を選択します。


単純なものを望むならば、ランダムな位置(x、y)をとり、円の中の点の数を計算し、前の位置と比較してください。 最大限に活用してください。 必要なときにいつでも操作を繰り返します。

なぜ地獄downvote? Monte Carloメソッドについて聞いたことがありますか? 実際には膨大な量の点について、決定論的アルゴリズムは妥当な時間に終了しないことがあります。


エントロピーを使用するには、単一のパスワードのShannonエントロピーを取得するだけでなく、一般的なパスワードのリストの要素として取得する必要があります。 パスワードが他のパスワードと非常によく似ている場合、そのエントロピーは他のパスワードに比べて低くなります。 それが非常にユニークであるならば、それはより高いでしょう。





c++ algorithm circle points