algorithm - 最も近い範囲を照会する

Question

AとBの2つのセットがあります。これらのセットはN次元の点で構成され、順序付けられています（N <10）。BのAに​​最も近い部分を見つける必要があります。最も近い部分がB1であるとしましょう。B1のポイントの数はAと同じである必要があり、B1のすべてのポイントからAまでの距離の合計は最小である必要があります。

kdツリーを確認しました。セット内で最も近い点を見つけるのに役立つだけです。では、最も近い範囲をすばやく見つけるためのアルゴリズムはありますか？

ありがとう。

Answer 1

ここでは、最近傍アルゴリズムの単純な拡張であるn最近傍検索アルゴリズムが必要なだけだと思います。セット A の各ポイントに対してこれを実行し、合計を最小化します。

このアルゴリズムについては、この記事(「kd-trees の入門チュートリアル」) で説明されています。複数の最近傍への拡張については簡単に述べただけですが、非常に明確に説明する必要があります。修正アルゴリズムの実装に成功した記事です。

C# での参照実装は、ここからアクセスできます。これには、コメントが付けられ、関連する単体テストが含まれています。選択した命令型言語に簡単に適応できるはずです。