2

对于计算机来模拟宇宙中的 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)

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

I need to know the math behind this, in order to calculate the optimal refresh rate between 2 particles in function of distance. Thus, my question is, what is the formal name of what I am describing here?

4

3 回答 3

3

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

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

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

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

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

希望这可以帮助。

于 2013-06-30T04:22:45.153 回答
1

You're doing time-step simulation, and using a performance enhancing heuristic called localization.

于 2013-06-30T03:45:14.513 回答
0

您描述的一般算法是N 体模拟。

我认为您描述的启发式方法没有通用名称。

于 2013-06-30T00:08:09.660 回答