別のセットから一組の中で最も遠い点を見つける

Question

私の目標は、in this questionというアルゴリズムをより効率的に実装することです。

RGB空間の例ではN空間、3空間、2空間の場合は 1空間 の解は距離計算でのみ異なります）を考慮してください。第2セットの最も近い隣から最も遠い第1セットのポイントをどのように見つけますか？

1スペースの例では、セットA：{2,4,6,8}とB：{1,3,5}が与えられると、答えは 8となります。 5はAの他のすべてのメンバーがBの最寄りの隣からちょうど1単位離れているのに対し、1つのスペースはあまり単純化されていません。寸法。

ソース質問の解決策は、1セット（すべてのR、G、B、ここで512> = R + G + B> = 256、R％4 = 0およびG％4 = 0およびB％4 = 0）を他のセット（colorTable）のすべてのポイントに適用します。この質問のために、最初のセットは、2番目のセットのようなストアド・リストとして反復されるのではなく、プログラムで詳述されることを無視してください。

Answer 1

まず、すべての要素の最も近い隣をもう一方の集合で見つける必要があります。

これを効率的に行うには、アルゴリズムnearest neighborが必要です。個人的には私はkd-treeを実装しています。なぜなら私は過去にアルゴリズムクラスでそれをやったからです。それはかなり簡単でした。別の実行可能な代替案はR-treeです。

最小のセットの要素ごとにこれを1回行います。 （最小のものから大きいものに1つの要素を追加し、最も近いものを見つけるためにアルゴリズムを実行してください）

これから、各要素の最近隣のリストを取得できるはずです。

最近接のペアを見つけている間に、高速追加メソッドと高速getMaxメソッド（たとえば、heap、Euclidean distanceでソートされている）を持つソートされたデータ構造にそれらを保持します。

次に、完了したら単純にヒープに最大値を問い合わせます。

次のように、このための実行時間が故障：

N =小さいセットのサイズ
Mより大きいセット

• N * O（M + 1ログ）すべてのための=サイズをkd-tree最近隣チェック。
• ヒープに追加する前のユークリッド距離を計算するためのN * O（1）。
• ヒープにペアを追加するためのN * O（log N）。だから、最後に全体のアルゴリズムはO D

（N * Mを記録）：

O（1）が最終的な答えを取得します。

各ペアの順序を気にしない場合は、今まで見つかった最大値を保持するだけで、少しの時間とスペースを節約できます。

※免責事項：これは非常に多くのディメンションを使用しないことと、要素がほとんどランダムな分布に従うことを前提としています。

Answer 2

EDIT：これはnlog（n）を意味し、nは両方のセットのサイズの合計です。私はあなたが

この

Struct Item { 
    int value 
    int setid 
} 

（1）最大距離= 0
（2）読むのすべてのような構造を使用して、この（擬似コード）のような何かを行うことができ、1スペースのセットで

（3）構造体のItem-> valueフィールドでポインタの配列を並べ替えます。
（5）配列を歩くこの距離が最大距離よりも大きい場合、この距離に
チェック（SetIDsが異なる）場合 をSETID>アイテム - > SETIDが前のアイテム - と異なっているかどうかのチェック、最後に始まるように設定MaxDistance場合

戻ります最大距離。

Answer 3

最も明白なアプローチは、あなたが比較的迅速に検索できるように、1つのセットにツリー構造を構築することです。そのためにはkd-treeまたはそれに類するものがおそらく適切でしょう。

これを実行すると、他のセットのすべてのポイントを歩き、最初のセットで最も近いネイバーを見つけるためにツリーを使用して、移動しながら最大値を記録します。

ツリーを構築するにはnlog（n）、1回の検索ではlog（n）を使用して、すべてをnlog（n）で実行する必要があります。

Answer 4

物事をより効率的にするには、ピジョンホールアルゴリズムを使用することを検討してください。リファレンスセット（あなたのcolorTable）内のポイントをn空間の位置でグループ化してください。これにより、すべての点を反復する必要なしに、最も近い隣を効率的に見つけることができます。

たとえば、2空間で作業していた場合は、平面を5 x 5グリッドに分割し、25個の正方形に25点のグループを割り当てます。

3つのスペースでは、キューブを5 x 5 x 5のグリッドに分割して、それぞれにポイントセットを持つ125個のキューブを与えます。

次に、点nをテストするために、nを含む正方形/立方体/群を見つけ、それらの点までの距離をテストします。ポイントnがグループ内の最も近い隣のポイントよりもエッジに近い場合、隣接するグループからポイントをテストする必要があります。集合Bの各点について

Answer 5

、各最近傍までの距離を見つけるために設定A.

その最近傍までの距離を見つけ、あなたは、限り、次元数が合理的であるようkd-treeを使用することができあまりにも多くのポイントがありませんし、あなたは多くのクエリを行うでしょう - そうでなければ、価値のあるツリーを構築するには高価になります。

Answer 6

私は疑問を誤解しているかもしれませんが、1つのデータセット内のすべての座標の符号を逆にする（つまり、1つの座標セットに-1を掛ける）のが最も簡単です。 （これは最も遠い隣人だろう）？ k = 1で好きなknnアルゴリズムを使うことができます。