2

我正在编写一个程序来模拟 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 坐标（它是二维的）超过一定数量的物体之间的关系，由它们的质量的乘积决定？抱歉，如果这听起来像我在漫无边际，但我能做些什么来加快速度吗？我宁愿保持任意精确，但如果有解决方案可以降低这个问题的复杂性，但会以一点精确为代价，我很想听听。

谢谢。

4

3 回答 3

7

看看这个问题。您可以将对象划分为网格，并利用可以将许多遥远对象视为单个对象的事实进行良好的近似。一个细胞的质量等于它所包含的物体的质量之和。一个细胞的质心可以被视为细胞本身的中心，或者更准确地说是它所包含的物体的重心。在平均情况下，我认为这会给你 O( n log n ) 的性能，而不是 O( n 2 )，因为你仍然需要计算n 个对象中每一个的重力，但每个对象只与那些单独交互附近。

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

于 2011-11-13T21:49:34.803 回答
3

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

有一些聚类算法相当快，诀窍是不要在每个滴答声中都运行聚类算法。而是每隔 C 滴答 (C>1) 运行一次。

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

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

你将不得不摆弄：

  • 使用哪种聚类算法：有些更快，有些更准确。有些是确定性的，有些不是。
  • 多久运行一次聚类算法：少跑会更快，多跑会更准确。
  • 集群的大小：大多数集群算法允许您输入集群的大小。您允许的集群越大，输出越快但精度越低。

所以这将是一场速度与准确性的博弈，但至少通过这种方式，您将能够牺牲一点准确性来获得一些速度的提升——按照您目前的方法，您根本无法真正调整任何东西。

于 2011-11-13T21:49:22.573 回答
1

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

于 2011-11-13T21:57:56.233 回答