k 最近傍アルゴリズムのシリアル C/C++ 実装はどこにありますか?
これを持っているライブラリを知っていますか？
openCV を見つけましたが、実装は既に並列化されています。
シリアル実装から始めて、pthreads openMP と MPI で並列化したいと考えています。
ありがとう、
アレックス
27908 次
3 に答える
3
最近傍検索を使用して、KDツリーのC++実装を作成しました。優先キューを追加することで、K最近傍に簡単に拡張できます。
更新： N次元でのk-最近傍探索のサポートを追加しました
于 2012-12-10T21:37:47.133 に答える
1
これを実装する最も簡単な方法は、すべての要素をループして、Kを最も近くに格納することです。（比較するだけです）。これの複雑さはO(n)それほど良くありませんが、前処理は必要ありません。だから今は本当にあなたのアプリケーションに依存します。knnを検索する領域を分割するには、空間インデックスを使用する必要があります。一部のアプリケーションでは、グリッドベースの空間構造で問題ありません（世界を固定ブロックに分割し、最初にクローズブロック内でのみ検索します）。これは、エンティティが均等に分散されている場合に適しています。より良いアプローチは、kd-treeのようないくつかの階層構造を使用することです...それは本当にあなたが必要とするものに依存します
これらのプレゼンテーションの擬似コードの外観を含む詳細については、以下を参照してください。
于 2012-11-21T09:47:36.957 に答える