(x,y) 座標で定義されたグラフ上に一連の N ポイントと、それらのペアワイズ距離を含むテーブルがあります。たとえば、closeness[5][9] == 4 の場合、ノード 9 はノード 5 に対して 4 番目に近い項目です。
これを行う明白な方法は、インデックスのリストを生成し、すべての i (1->n) に対して d[i][j] < d[i][k] に基づいてそれらをソートし、知識によってテーブルを変換することです。 sorted[5][4] == 9 は、closeness[5][9] == 4 を意味します。
これには O(n² log n) の時間が必要です。もっと効率的な方法がありそうな気がします。何か案は？
わかりました、私はこれを試してみるつもりです。
背景知識について: この問題は、k 最近傍に多少関連しています。ペアごとの距離をどのように生成したかはわかりませんが、kd ツリーはこの種の問題を解決するのに非常に優れています。
ここで、kd ツリーを使用しても、少しは役に立ちます (すべてのポイントを並べ替えるのではなく、必要なものだけをクエリします): O(N log N) 時間でツリーを構築し、必要な K 個の最も近いポイントに対してクエリするには、それぞれに O(log N) 時間がかかります。最後に、O(N log N) + O(NK log N) を見ています。
さて、実際のヒューリスティックな部分です。これはデータによって異なります。それらが接近しているか離れているかを確認したい場合があります。ただし、飛行機をビンに分割する分割統治法を試すこともできます。最も近いポイントを見つける必要がある場合は、作業しているポイントが属するビンを見つけてから、隣接するビンのみを操作し、より多くのポイントが必要なときに隣接するビンをさらに探索します。
うまくいけば、これが役に立ちます。