19

赏金

这个问题提出了几个问题。赏金将用于从整体上解决它们的答案。

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

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

有一组 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 库 似乎无法处理移动物体。

4

7 回答 7

10

统计学中一种非常简单且非常快速的方法是使用随机线性投影。这些可以帮助您快速确定集群和邻居。通过更多的预测，您可以获得更高的准确性（我相信解决您关于错误的问题）。

本文对几种方法进行了广泛的定量分析，包括与 RLP 相关的新方法 (DPES)。

本文讨论了 RLP 的使用，包括即使在移动点的情况下也能保持距离。

本文介绍了用于运动规划的 RLP，并详细介绍了几种启发式方法。

RLP 方法是：

  1. 非常快
  2. 导致可调整精度和速度的近似值
  3. 距离和角度保持（可证明）
  4. 轻松缩放到大尺寸和大#s的对象
  5. 对降维有用
  6. 导致紧凑的投影（例如，可以投影到分层二进制分区中）
  7. 灵活：您可以投影到您认为对您有好处的任何空间 - 通常是 R^d，但也可以投影到 2^d（即维度 d 的二进制空间），但仅会降低给定的准确度 #的预测。
  8. 统计有趣

嵌入到低维空间后，相邻计算非常容易，因为在相同区域中合并的投影（如果将投影合并到网格中）很可能在原始空间中很接近。

尽管原始数据的维数很小（甚至 10 也很小），但快速投影到预选网格中的能力对于识别和计算邻居非常有用。

最后，您只需更新其位置（或相对位置，如果您正在对数据进行居中和缩放）已更改的那些对象。

对于相关作品，请查看 Johnson-Lindenstrauss 引理。

于 2011-08-05T18:36:51.943 回答
4

您是否尝试过使用四叉树？

也就是说，递归地将“世界”划分为一个图，每个图有四个子节点。然后，树可以快速检查哪些对象位于世界的特定方格内，并丢弃其余对象。一种非常有效的剔除技术，通常用于提高游戏中碰撞检测的性能。

如果这是 3D，则将其扩展为八叉树。

于 2011-07-29T11:25:48.360 回答
4

这是一个简单的反例，表明您的朋友的朋友算法有时会错过邻居：从许多（至少超过 3*N）等间距的演员组成的长直线开始，然后逐渐将线弯曲成圆形。如果这条线足够长，其中的参与者将不会检测到他们所在社区的局部变化；尤其是最后的演员见面时不会注意到。

编辑：实际上，我想到了一个更简单的反例：取两个独立的紧凑集群，每个集群包含 N 个或更多参与者，并将它们发送到彼此的碰撞过程中。

于 2011-07-29T11:28:39.650 回答
3

我有一些看起来有点像解决方案的东西。

在每个“重新计算”步骤中，它需要一个线性时间，我想这不像你recompute_nearest (Actor A)对每个演员那样是一个问题。

让我们进入正题：这个想法是针对每个演员，在计算之前添加一定数量的随机朋友recompute_nearest (Actor A)。这个数字不应该太小，否则你永远不会发现错误。它不应该太大，否则由于计算邻居的邻居是二次的，它的计算成本太高。

但是“不太小”或“不太大”是什么意思呢？我们将从一个演员 A 开始，看看他的邻居列表将如何更新。假设对于每个点，您添加p原始 K 个演员的百分比。然后，如果另一个点 B 接近 A 但不是朋友的朋友，我们应该通过“随机朋友”这个东西“快速”添加他。在每次迭代中，都有(1-p)机会不选择他。

快速计算表明，如果您想在 90% 的情况下在 10 次或更少的迭代中发现这一点，您将需要p=20%. 这是非常昂贵的。

...

然而，一切都没有丢失！我想说的第一点是，如果错误倾向于“一起”，那么性能会显着提高！想象一下最初相距很远的两个 blob（人们聊天、星团等）如果这些 blob 碰撞，朋友的朋友永远不会看到有问题。但是，使用我的算法，如果您发现一个错误，并正确调整您的邻居列表，那么朋友之友算法将纠正所有剩余的错误。

如果您有K=1.000两个仅包含 1% 点的小斑点，并且您希望以 99% 的确定性在 10 次或更少的迭代中发现，您可以计算出您只需要p=1%! （K 越大，p 必须越小！）嗯，这假设一些点“一起”。

我还有另一个优化：调整随机点的数量和质量。简单地说，应该给快的演员比慢的演员更多的随机朋友。你应该随机选择这些朋友喜欢其他快速演员。我无法量化它，但你可以猜到它为什么会提高性能！

关于您的问题的一个小编辑：“当演员很快时我该怎么办”？你可以用你给自己发现错误的步数来转换演员的速度。我的意思是，如果你可以考虑到每个演员的朋友圈都围绕着他。那个理论圈对应他的好友列表。如果大多数演员不能在 10 次迭代中完全穿过这个圆圈，但可以在 15 次内完成，那么您应该考虑给自己 10 次迭代来发现问题。如果您的演员速度如此之快，以至于他们可以分 3 步穿过这个“圆圈”，那么，好吧……这个算法不适合您（我想尝试保留邻居列表而不在每一步都重新计算它是虚幻的）

从根本上说，保持邻居列表表明存在某种结构（即两次迭代之间大致相同）。速度恰恰相反，快速的演员意味着你没有结构。对于速度非常快的演员，保留邻居列表可能是个坏主意。

有关 blob 的技术细节。

您有两个包含每个s%演员（大小sK）的 blob（例如 s = 1%）

你给自己一个误差范围e%（例子是1%）和n步骤（例子是10）

那么 p 有一个上限：p <= [log(1-e^(1/n))]/[s*K²*log(1-s)]

我的例子的真正价值是p <= 0.989%！

p = [log(1-e^(1/n))]/[s*K²*log(1-s)]如果 s 小而 K 大，你就有了。如果不是这样，p 会小很多！

于 2011-07-29T13:31:44.643 回答
1

我会尝试什么。

  1. 覆盖树作为做 kNN 的基础数据结构。特点：不需要欧几里得度量，线性空间使用，kNN/Insert/Remove 在数据的内在维数固定的情况下都是 O(log n)。非特征：运动。

  2. 为了处理移动的对象，周期性地，对于每个对象，移除它的旧位置，插入它的新位置，然后找到 kNN。

如果我们将对象的周期设置为与速度成反比，那么我们知道覆盖树与现实之间的最大差异受一个常数的限制。

于 2011-09-17T13:45:10.207 回答
0

KD 树允许您在一个点的固定半径内有效地搜索。如果一个点的所有邻居都在d1单位内，并且任何点与上一次测量的最大位移为d2，那么您只需在该点的d1+d2单位内进行搜索。

如果您正在处理 Minkowski 距离，那么您可以使用David Mount 的 ANN 库。不过，我不确定是否有一个库可以采用任意距离函数。

于 2011-07-29T12:03:38.717 回答
0

当一个 Actor 在给定时间步长内移动的距离超过到其最远已知邻居的距离时，重新采样所有邻居。

另一个触发条件：当 Actor 自上次重新采样后移动的距离超过与已知最远邻居的距离时，重新采样。

此处进行简单优化，如果存在分层空间索引，则搜索包含 a) 半径等于跳跃大小的球体和 b) 至少 N 个 Actor 的节点。

于 2011-07-29T13:44:09.233 回答