悬赏
这个问题涉及到几个问题。将会悬赏给一个综合解决这些问题的答案。
这是一个我一直在探索的问题。
注意：我尤其感兴趣的是不基于欧几里得空间的解决方案。
有一组演员组成了大小为K的人群。任意两个演员之间的距离d（ActorA，ActorB）可以轻松计算出来（解决方案应该适用于各种距离的定义），我们可以使用多种已建立的算法找到任何给定演员的N个最近邻的集合。
这个邻居集在第一时间是正确的，但是演员总是在移动，我想要维护每个演员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三角剖分，它是最近邻图的超集。 仅适用于一个最近邻居。
David Mount的ANN库 似乎不能处理移动体。