0

I 2セットのk次元ベクトル。ここで、kは約500で、ベクトルの数は通常これより少なくなります。2つのセット間の（任意に定義された）最小距離を計算したいと思います。素朴なアプローチはこれです：

(loop for a in set1
      for b in set2
      minimizing (distance a b))

ただし、これにはO（n²*距離）の計算が必要です。これを行うより速い方法はありますか？

4

3 に答える 3

1

距離が任意の場合、O(n^2) よりもうまくいくとは思いません (考えられる距離をそれぞれ調べる必要があります!)。与えられた距離関数に対して、関数のプロパティを利用できるかもしれませんが、O(n^2) よりも優れた距離関数で機能する一般的なアルゴリズムはありません (つまり、 o(n^2) :注意小ああ）。

データが動的で、異なる時点で最も近い点のペアを取得し続ける必要がある場合、任意の距離関数については、エプスタインによる次の論文がおそらく役立ちます (最も近い点のペアをすばやく見つけるための特別な更新操作があります)。 :

上記の 1 セット アルゴリズムを 2 セット アルゴリズムに適合させることができます (たとえば、同じセットのポイント間の距離を無限大に定義することにより)。

ユークリッド型 (L^p) 距離の場合、既知の O(nlogn) 時間アルゴリズムがあり、特定のポイント セットで機能します (つまり、特別な更新アルゴリズムは必要ありません)。

もちろん、L^p は 1 セット用ですが、2 セット用に調整できる場合もあります。

距離関数を指定すると、私たちがあなたを助けるのがより簡単になるかもしれません.

それが役に立てば幸い。幸運を！

于 2010-06-06T18:07:32.757 に答える
0

ベクトルの成分がスカラーである場合、中程度のk = 500の場合、O（n²）アプローチはおそらく可能な限り高速であると思います。distance²を最小化することで計算を簡素化できます。また、distance（A_i、B_i）= distance（B_i、A_i）なので、比較するのは1回だけにしてください（500²ではなく、500！/（500-2）！のペアしかありません）。

代わりに、コンポーネントがm次元のベクトルAおよびBである場合、ベクトルAのコンポーネントをRツリーまたはkdツリーに格納し、ベクトルBのすべてのコンポーネントを反復処理して、最も近いパートナーを見つけることにより、最も近いペアを見つけることができます。 Aから---これはO（n）になります。big-Oはn->無限大を表すため、ツリーにはかなり高価な定数項が含まれる可能性があることを忘れないでください（つまり、このアプローチは、大きなkの場合、またはベクトルAが常に同じである場合にのみ意味があります）。

于 2010-06-06T14:35:50.617 に答える
0

2 組の座標をSpatial Index、たとえばKD-tree に入れます。

次に、これら 2 つのインデックスの交点を計算します。

于 2010-06-06T18:21:17.163 に答える