5

最近傍探索問題のための効率的なアルゴリズムを実装しようとしています。

この種の問題（たとえば、Rツリー、カバーツリーなど）の操作をサポートするいくつかのデータ構造に関するチュートリアルを読みましたが、それらすべてを実装するのは困難です。

また、これらのデータ構造のサンプルソースコードが見つかりません。私はC++を知っており、この言語でこの問題を解決しようとしています。

理想的には、ソースコードを使用してこれらのデータ構造を実装する方法を説明するリンクが必要です。

4

2 に答える 2

14

高速最近傍検索ライブラリにはいくつかの良い選択肢があります。

  • マウントとアリャの作品に基づいているANN 。この作業は、S。AryaとDMMountによる論文に記載されています。「固定次元での近似最近傍クエリ」。Proc。第4回ACM-SIAMシンポジウム。Discrete Algorithms、ページ271–280、1993。

  • マリウス・ムジャ＆カンパニーの研究に基づくFLANN 。コンピュータビジョン理論と応用に関する国際会議（VISAPP ' 09）、2009年。FLANNのコードはgithubで入手できます。

FLANNは場合によってはより高速であるように思われ、変更を迅速に組み込むことができる、他の多くの言語の確実なバインディングを備えたコードのより新しいバージョンです。しっかりとテストされた標準ライブラリが必要な場合は、ANNがおそらく良い選択です。

コメントに応じて編集

これらのライブラリには両方とも、広範なドキュメントと例があります。

ANNのサンプルコードは、マニュアルのセクション2.1.4にあります。

FLANNのサンプルコードは、FLANNリポジトリのexamplesディレクトリにあります（例：/examples/flann_examples.c）。

于 2012-04-06T09:01:54.547 に答える
2

ラインスイープアルゴリズムを試して、最も近いポイントのペアを見つけることができます： http ://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lineSweep 。

于 2012-04-06T09:57:01.167 に答える