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 座標 (2 次元) が質量の積によって決まる特定の量を超えるオブジェクト間の関係を無視することによってでしょうか? とりとめのないように聞こえる場合は申し訳ありませんが、これを高速化するためにできることはありますか? 任意の精度を維持したいのですが、少し精度を犠牲にしてこの問題の複雑さを軽減できる解決策がある場合は、それを聞いてみたいと思います。

ありがとう。

4

3 に答える 3

7

この質問を見てください。オブジェクトをグリッドに分割し、多くの遠くのオブジェクトを 1 つのオブジェクトとして扱うことができるという事実を利用して、適切な近似を行うことができます。セルの質量は、セルに含まれるオブジェクトの質量の合計に等しくなります。セルの質量の中心は、セル自体の中心、またはより正確にはセルに含まれるオブジェクトの重心として扱うことができます。平均的なケースでは、これにより O( n 2 )ではなくO( n log n ) のパフォーマンスが得られると思います。これは、 n 個のオブジェクトのそれぞれにかかる重力を計算する必要がありますが、各オブジェクトはそれらと個別にしか相互作用しないためです。近所の。

r 2  =  x 2  +  y 2で距離を計算し、 F  = G m 1 m 2  /  r 2で力を計算すると仮定すると、平方根を実行する必要はまったくありません。実際の距離が必要な場合は、高速逆平方根を使用できます。固定小数点演算も使用できます。

于 2011-11-13T21:49:34.803 に答える
3

損失を伴う適切なアプローチの 1 つは、クラスタリング アルゴリズムを実行してボディをまとめてクラスタリングすることです。

かなり高速なクラスタリング アルゴリズムがいくつかありますが、コツは、ティックごとにクラスタリング アルゴリズムを実行しないことです。代わりに、C ティック (C>1) ごとに実行します。

次に、クラスターごとにクラスター内のすべてのボディ間の力を計算し、クラスターごとにクラスター間の力を計算します。

これは損失が大きくなりますが、良いアプローチだと思います。

あなたはいじる必要があります：

  • どのクラスタリング アルゴリズムを使用するか: 高速なものもあれば、より正確なものもあります。決定論的なものもあれば、そうでないものもあります。
  • クラスタリング アルゴリズムを実行する頻度: 少ないほど高速になり、多いほど正確になります。
  • クラスターを作成するための小ささ/大きさ: ほとんどのクラスタリング アルゴリズムでは、クラスターのサイズに関する入力が可能です。クラスターを大きくするほど、出力は速くなりますが、精度は低下します。

したがって、これは速度と精度のゲームになりますが、少なくともこの方法では、速度を向上させるために精度を少し犠牲にすることができます。現在のアプローチでは、実際に微調整できるものはまったくありません。

于 2011-11-13T21:49:22.573 に答える
1

精度の低いバージョンの平方根を試してみることをお勧めします。おそらく、完全な倍精度は必要ありません。特に、座標系の大きさのオーダーが通常同じである場合は、切り捨てられたテイラー級数を使用して、効率をあまり犠牲にすることなく、平方根演算をかなり迅速に推定できます。

于 2011-11-13T21:57:56.233 に答える