8

n個のベクトルを保持する配列があると仮定します。これらのベクトル間の最大ユークリッド距離を計算します。最も簡単な（ナイーブ？）アプローチは、配列を反復し、各ベクトルについて、後続のすべてのベクトルとの距離を計算してから、最大値を見つけることです。ただし、このアルゴリズムは大きくなります（n-1）。配列のサイズに関して。

この問題に対する他のより効率的なアプローチはありますか？

ありがとう。

4

4 に答える 4

4

素朴なアルゴリズムの複雑さの計算は不安定です、それはであるはずですO(n(n-1)/2)、それはに減少しO(n^2)ます。2つのベクトル間の距離の計算は次のとおりですO(k)。ここkで、はベクトル内の要素の数です。これでも、以下の複雑さが得られますO(n!)。

于 2012-08-24T11:13:05.320 に答える
3

複雑さは、ブルートフォースアルゴリズムの場合はO（N ^ 2 * K）です（Kはベクトル内の要素の数です）。しかし、点A、B、Cのユークリッド空間では、次のことを知ることで、より良い結果が得られます。

|AB| + |AC| >= |BC|

アルゴリズムは次のようになります。

これまでに見つかった最大距離がでMAXあり、距離がすでに計算されているような|AB| 点がある場合、の計算をスキップできます。C|AC||CB|MAX > |AC|+|CB||AB|

このアルゴリズムの複雑さを判断するのは難しいですが、私の直感はそれが遠くないことを教えてくれますO(N*log(N)*K)

于 2012-08-24T13:17:07.043 に答える
2

この質問は以前にここにありました。2つの最も遠いポイントを見つける方法を参照してください。

そして答えは次のとおりです。ユークリッド空間ではO（n ^ 2）未満で実行できます。http://mukeshiiitm.wordpress.com/2008/05/27/find-the-farthest-pair-of-points/も参照してください

于 2012-08-26T11:28:09.523 に答える
0

したがって、点AとBのペアがあるとします。北極と南極にそれぞれAとBがある超球を考えます。超球に含まれる点Cは、BよりもAから遠くなる可能性がありますか？

さらに、ポイントセットをそれぞれsqrt（N）ポイントを持つsqrt（N）ハイパーボックスに分割するとします。ハイパーボックスの任意のペアについて、それらに含まれる無限のポイントセットの任意の2つのポイント間で可能な最大距離をk時間で計算できます。これは、最も遠いコーナー間の距離を計算するだけです。これよりも優れた候補がすでにある場合は、それらのハイパーボックスからすべてのポイントのペアを破棄できます。

于 2012-08-26T11:50:41.280 に答える