java - 快速多体重力算法？

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

看看this question .您可以将对象划分为网格，并利用许多远处的对象可以被视为单个对象的事实来获得良好的近似值。一个细胞的质量等于它包含的物体质量的总和。细胞的质心可以视为细胞本身的中心，或者更准确地说是 barycenter它包含的对象。在一般情况下，我认为这会给你 O(n log n) 性能，而不是 O(n²)，因为您仍然需要计算 n 个物体中每个物体的重力，但每个物体仅单独与附近的物体相互作用。

假设您计算的距离为 r² = x² + y²，然后用F = Gm₁m₂/r²，您根本不需要计算平方根。如果确实需要实际距离，可以使用 fast inverse square root .您也可以使用 fixed-point arithmetic .