Bounty
这个问题提出了几个问题。赏金将用于全面解决这些问题的答案。
这是我一直在玩的一个问题。
NOTE我对以下解决方案特别感兴趣不基于欧几里得空间。
有一组 Actor 形成大小为 K 的人群。距离d(ActorA,ActorB)对于任何两个参与者来说，都很容易计算（解决方案应该适用于“距离”的各种定义），并且我们可以使用多种已建立的算法中的任何一种来找到任何给定参与者的 N 个最近邻居的集合。
这个邻居集在第一时刻是正确的，但是演员们总是在移动我想为每个 Actor 维护 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 适当大时，这种方法表现得相当好。它在小错误后收敛，满足第一个标准，但是
- 我没有好的方法来检测大错误，
- 我没有对错误的大小和频率进行定量描述，
- 它在实践中收敛，但我不能prove永远都会如此。
您能在以下几点方面提供帮助吗？
另外，您是否知道任何表现良好的替代方法
- 当人群快速流动时，
- when some演员动作迅速，
- 当 N 较小时，
- 当有的地方人流稀疏，有的地方人流稠密时，
- 或者使用特定的空间索引算法？
我目前正在研究的扩展是在邻居快速移动的情况下将朋友的朋友概括为朋友的朋友的朋友。我怀疑这不能很好地扩展，并且在不量化错误的情况下很难得出正确的参数。
我欢迎所有建议！这是一个有趣的小问题:-)
迄今为止值得注意的建议
Fexvez：随机抽取额外邻居，样本大小取决于代理的速度。从即将进入的区域进行采样可能也会有所帮助。
当代理重新采样邻居speed*delta_time超过了到已知最远邻居的距离。
维持德劳内三角剖分 http://en.wikipedia.org/wiki/Delaunay_triangulation这是最近邻图的超集。仅占one最近的邻居。
大卫·芒特人工神经网络库 http://www.cs.umd.edu/~mount/ANN/ 似乎无法处理moving bodies.
