4

セット A とセット B の 2 セットのノードがあります。各セットのサイズは 25,000 です。

パーセンテージ (20% としましょう) が与えられます。セット A のノードの 20% がセット B の任意のノードの距離内に収まるような最小距離を見つける必要があります。

解決：

セット B のノードに最も近いセット A の 20% を見つけます。答えは、セット B のノードから最も遠い 20% のノードです。

ブルート フォース ソリューション:

        foreach (Node a in setA)
        {
            a.ShortestDistance = infinity;
            foreach (Node b in setB)
            {
                if (a.DistanceTo(b) < a.ShortestDistance)
                {
                    a.ShortestDistance = a.DistanceTo(b);
                }
            }
        }
        setA.SortByShortestDistance();
        return setA[setA.Size * 0.2];

これは機能しますが、非常に時間がかかります。(O(n^2 + Sort) かな？)

どうすればこれをスピードアップできますか? できればO(n)を打ちたいです。

4

2 に答える 2

1

以下は、速度を向上させる可能性のあるアルゴリズムです:-

  1. あなたの（緯度、経度）ペアを地球の中心を原点とするデカルトの（x、y、z）に変換します
  2. デカルトでの (x,y,z) 間の距離は、球面座標での実際の距離の下限です。
  3. setA と setB の3D ツリーを分離するように構築します。
  4. setA の各ノード a について、setB の 3d ツリーで最近傍を検索します。これは、平均的なケースでは O(logN) です。
  5. 次に、最近傍の距離は、最近傍からの距離になります。
  6. 次に、行ったように setA をソートします。

時間の複雑さ:-

平均的なケースでは: O(n*logn)

最悪の場合： O(n^2)

于 2014-06-25T05:26:39.157 に答える
1

2 つのセットのうち小さい方を選択し、最近傍クエリに応答するための構造を構築することができます。ハーサイン/大円。

これを行った後、最も簡単な方法は、大きなセットのすべてのメンバーを取得し、小さなセットでそれに最も近いものを見つけてから、距離を並べ替えるかhttp://en.wikipedia.org/wiki/Quickselectすることです。 . 最も近いオブジェクトがしきい値の距離よりも遠くにある必要があり、大まかな距離がわかっている場合は、何も検出せずに早期に戻るように検索操作を変更すると、時間を節約できる可能性があります。

事前に 2 つのセットからランダムなサンプルに対して同じ操作を実行することで、大まかなアイデアを得ることができます。推測が少し高すぎる場合は、ソートする最近傍距離がもう少しあります。推測が少し低すぎる場合は、最近隣操作が何も見つからずに早期に返されたポイントに対してのみ、検索操作を繰り返す必要があります。

于 2014-06-25T05:29:15.510 に答える