バウンティ
この質問は、いくつかの問題を引き起こします。報奨金は、全体的に対処する回答に送られます。
これが私が遊んできた問題です。
注私は、ユークリッド空間に基づかないソリューションに特に興味があります。
サイズ K の群集を形成するアクタのセットがあります。距離d(ActorA,ActorB)は任意の 2 つのアクタについて簡単に計算できます (「距離」のさまざまな定義に対してソリューションが機能するはずです)。数多くの確立されたアルゴリズムのいずれか。
この隣接セットは最初は正しいですが、アクタは常に移動しているため、各アクタの N 個の最近傍の展開リストを維持したいと考えています。私が興味を持っているのは、完全解よりも効率的な近似解です。
- エラーが導入された後、ソリューションは正確に収束する必要があります。
- エラーが大きくなりすぎた場合は、完全な再計算を実行しても問題ありませんが、これらのエラーの検出は安価です。
これまでのところ、友人の友人アルゴリズムを使用してきました。
recompute_nearest (Actor A)
{
Actor f_o_f [N*N];
for each Actor n in A.neighbours
append n to f_o_f if n != A and n not in f_o_f
Distance distances [N*N];
for 0 <= i < f_o_f.size
distances [i] = distance (A, f_o_f [i])
sort (f_o_f, distances)
A .neighbours = first N from f_o_f
}
これは、群集の動きが遅く、N が適切に大きい場合に、適切に機能します。小さな誤差の後に収束し、最初の基準を満たしますが、
- 大きなエラーを検出する良い方法がありません。
- エラーのサイズと頻度の定量的な説明はありませんが、
- 実際には収束しますが、常に収束することを証明することはできません。
これらの点について何かお手伝いできますか？
また、うまく機能する代替アプローチを知っていますか
- 群衆の動きが速いとき、
- 一部のアクターの動きが速い場合、
- N が小さい場合、
- ある場所では群衆がまばらで、別の場所では密集している場合、
- または特定の空間索引付けアルゴリズムを使用しますか?
私が現在取り組んでいる拡張機能は、友人の友人を一般化して、隣人の動きが速い場合に友人の友人の友人を取ることです。これはうまくスケーリングできず、エラーを定量化せずに適切なパラメーターを導き出すのは難しいと思います。
私はすべての提案を歓迎します！それは楽しい小さな問題です:-)
これまでの注目すべき提案
Fexvez: エージェントの速度に応じて、ランダムな余分な隣人をサンプリングします。サンプル サイズ。移動しようとしているエリアからサンプリングすることもおそらく役立つでしょう。
エージェントspeed*delta_timeが既知の最も遠い隣人までの距離を超えると、隣人を再サンプリングします。
最近傍グラフのスーパーセットであるDelaunay 三角形分割を維持します。1 つの最近傍のみを考慮します。
David Mount のANN ライブラリは、 移動体を処理していないようです。