algorithm - 此处介绍的粒子模拟数据结构/算法的正式名称是什么？

Question

要让计算机模拟宇宙中相互作用的 n 个粒子系统，可以使用以下粗略算法:

for interval where dt=10ms
  for each particle a in universe
    for each particle b in universe
      interact(a,b,dt)
  for each particle a in universe
    integrate(a,dt)

它很重，每个刻度调用 interact n^2 次 - 因此，模拟许多粒子是不可行的。但是，大多数时候，靠近的粒子相互作用不那么强烈。这个想法是利用这个事实，创建一个图形，其中每个节点都是一个粒子，每个连接都是它们的距离。近距离的粒子比远距离的粒子更频繁地相互作用。例如，

for interval where dt=10ms
  for each particle a in universe
    for each particle b where 0m <= distance to a < 10m
      interact(a,b,dt)
for interval where dt=20ms
  for each particle a in universe
    for each particle b where 10m <= distance to a < 20m
      interact(a,b,dt)
for interval where dt=40ms
  fro each particle a in universe
    for each particle a in b where 20m <= distance to a < 40m
      interact(a,b,dt)
(...etc)
for interval where dt=10ms
  for each particle a in universe
    integrate(a,dt)   

这显然更好，因为粒子主要与附近的粒子相互作用。当远处的粒子靠近时，它会开始更频繁地刷新。

我需要知道这背后的数学原理，以便根据距离计算 2 个粒子之间的最佳刷新率。因此，我的问题是，我在这里描述的内容的正式名称是什么？

Answer 1

为了克服在每一步计算全套成对交互的 O(n^2) 成本，N-body这种模拟通常使用 Barnes-Hut 来实现方法。这在本质上类似于您所描述的多分辨率想法类型。

Barnes-Hut 是基于分层空间分区策略的完整成对交互项的高效 (O(n*log(n))) 近似。这组粒子被插入到 octree 中。 (R^2 中的四叉树)，这是一棵高度为 O(log(n)) 的空间索引树。除了包含指向其子节点的指针外，树的每个级别的节点还包含其子粒子集的质心 - 树节点实际上是各种空间分辨率下的集总“超粒子”。

当计算作用在特定粒子上的力时，树从根开始遍历，并且在每个节点处决定是继续遍历它的子节点，还是只根据粒子的中心取近似的“集总”贡献大量的 child 。通常，此决定是根据质心与所讨论粒子的距离做出的 - 如果质心“距离足够远”，则遍历终止并采用“集总”近似。

此策略确保仅在“短”粒子距离处计算完整(且昂贵)的成对相互作用，随着距离的增加使用近似的“集总”相互作用。

最先进的 N 体算法还为系统中的每个粒子合并了单独的(和可变的)时间步长以获得额外的效率，但这开始变得非常复杂!

希望这对您有所帮助。