快速多体重力算法？

Question

我正在编写一个程序来模拟 n 体重力系统，其精度是任意的，具体取决于我在每一步之间采取的“时间”步长有多小。目前，它对于最多 500 个物体运行速度非常快，但之后它会变得非常慢，因为它必须运行一个算法来确定每次迭代中每对物体之间施加的力。其复杂度为 n(n+1)/2 = O(n^2)，因此它很快就会变得非常糟糕也就不足为奇了。我想成本最高的操作是通过求平方根来确定每对之间的距离。那么，在伪代码中，这就是我的算法当前运行的方式：

for (i = 1 to number of bodies - 1) {
  for (j = i to number of bodies) {
   (determining the force between the two objects i and j,
    whose most costly operation is a square root)
  }
}

那么，有什么方法可以优化它吗？有什么奇特的算法可以重用过去迭代中使用的距离并进行快速修改吗？有没有什么有损的方法可以减少这个问题？也许通过忽略 x 或 y 坐标（二维）超过一定量（由其质量的乘积确定）的物体之间的关系？抱歉，如果这听起来像是我在胡言乱语，但是我可以做些什么来加快速度吗？我宁愿保持它任意精确，但如果有解决方案可以以牺牲一点精度为代价来降低这个问题的复杂性，我会有兴趣听到它。

谢谢。

Answer 1

看看这个问题。您可以将对象划分为网格，并利用许多远处对象可以被视为单个对象的事实来获得良好的近似值。细胞的质量等于其所含物体的质量之和。细胞的质心可以被视为细胞本身的中心，或更准确地说是 barycenter< /a> 它包含的对象。在平均情况下，我认为这会给你 O(n log n) 性能，而不是 O(n^{2），因为您仍然需要计算每个 n 个对象上的重力，但每个对象仅与附近的对象单独相互作用。}

假设您使用 r² = x²+  计算距离y²，然后计算力F = Gm₁m₂ /  ;r²，根本不需要执行平方根。如果您确实需要实际距离，可以使用快速平方根反比。您还可以使用定点算术。

Answer 2

一种好的有损方法是运行聚类算法将物体聚类在一起。

有一些聚类算法相当快，诀窍是不要每次都运行聚类算法。相反，每隔 C 个周期运行一次（C>1）。

然后对于每个簇，计算簇中所有物体之间的力，然后对于每个簇计算簇之间的力。

这会有损失，但我认为这是一个很好的方法。

您必须摆弄：

• 使用哪种聚类算法：有些更快，有些更准确。有些是确定性的，有些则不是。
• 运行聚类算法的频率：运行次数越少会更快，运行次数越多会更准确。
• 集群的大小：大多数集群算法允许您输入有关集群大小的一些信息。允许的簇越大，输出就会越快，但准确性会降低。

因此，这将是一场速度与准确性的游戏，但至少这样您将能够牺牲一点准确性来获得一些速度增益 - 使用您当前的方法，您没有什么可以真正调整的全部。

Answer 3

您可能想尝试不太精确的平方根版本。您可能不需要完整的双精度。特别是如果坐标系的数量级通常相同，那么您可以使用截断的泰勒级数来快速估计平方根运算，而不会放弃太多的效率。

Answer 4

对于 n 体问题，有一个非常好的近似方法，速度更快（对于朴素算法，O(n log n) vs O(n²)），称为 巴恩斯小屋。空间被细分为分层网格，在计算远距离质量的力贡献时，可以将多个质量视为一个。有一个精度参数可以根据您愿意为计算速度牺牲精度的程度进行调整。