赏金

这个问题提出了几个问题。赏金将得到一个整体解决他们的答案。

这是我一直在玩的一个问题。

注意 我对 非欧几里得空间的 解决方案特别感兴趣 。

有一组Actor构成一个大小为K的人群。该距离d(ActorA,ActorB)对于任何两个Actor
都很容易计算（解决方案应适用于“距离”的各种定义），我们可以使用任何给定Actor来找到N个最近邻居的集合。许多已建立的算法中的任何一种。

这个邻居集在最初的瞬间是正确的，但是 Actor总是在移动 ，我想为每个Actor保留N个最近邻居的不断变化的列表。我感兴趣的是 近似
解决方案，它比完美解决方案更有效。

1. *引入错误后， *解决方案应收敛到正确性 。
2. 如果错误变得太大，有时可以执行完全重新计算，但是 检测这些错误应该很便宜 。

到目前为止，我一直在使用“ 朋友好友” 算法：

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：对随机额外邻居进行抽样，样本大小取决于Agent的速度。 从将要进入的区域进行采样可能也会有所帮助。

当业务代表speed*delta_time超出到最远已知邻居的距离时，请对邻居进行重新采样。

保持Delaunay三角剖分，它是最近邻图的超集。
仅占 一个 最近的邻居。

David Mount的ANN库 似乎无法处理 移动的 物体。