快速多体重力算法？

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坐标(它是2维)超过一定数量的物体之间的关系,这是由它们的质量乘积决定的？对不起,如果这听起来像是在漫无边际,但是我能做些什么才能让它更快？我宁愿保持任意精确,但如果有一些解决方案能够以一点精度降低这个问题的复杂性,我会有兴趣听到它.

谢谢.

Answer 1

看看这个问题.您可以将对象划分为网格,并使用这样的事实:可以将许多遥远的对象视为单个对象以获得良好的近似.单元格的质量等于它包含的对象质量的总和.细胞的质心可以被视为细胞本身的中心,或者更准确地说是它所包含的物体的重心.在一般情况下,我认为这给你O(ñ日志ñ)的性能,而不是O(ñ ²),因为你仍然需要计算每一个重力ñ对象,但每个对象只能交互单独与附近.

假设你用r ²  =  x ²  +  y ²计算距离,然后用F  = G m ₁ m ₂  /  r ²计算力,你根本不需要执行平方根.如果确实需要实际距离,则可以使用快速平方根.您也可以使用定点算术.