2

互いに相互作用する宇宙の n 個の粒子のシステムをコンピューターでシミュレートするには、次の大まかなアルゴリズムを使用できます。

for interval where dt=10ms
  for each particle a in universe
    for each particle b in universe
      interact(a,b,dt)
  for each particle a in universe
    integrate(a,dt)

これは重く、interactティックごとに n^2 回呼び出すため、多くのパーティクルをシミュレートすることはできません。ただし、ほとんどの場合、近くにある粒子はあまり強く相互作用しません。アイデアは、この事実を利用して、各ノードが粒子であり、各接続がそれらの距離であるグラフを作成することです。近くにある粒子は、遠くにある粒子よりも頻繁に相互作用します。例えば、

for interval where dt=10ms
  for each particle a in universe
    for each particle b where 0m <= distance to a < 10m
      interact(a,b,dt)
for interval where dt=20ms
  for each particle a in universe
    for each particle b where 10m <= distance to a < 20m
      interact(a,b,dt)
for interval where dt=40ms
  fro each particle a in universe
    for each particle a in b where 20m <= distance to a < 40m
      interact(a,b,dt)
(...etc)
for interval where dt=10ms
  for each particle a in universe
    integrate(a,dt)

粒子は主に近くにある粒子と相互作用するため、これは明らかに優れています。遠くにあるパーティクルが近づくと、より頻繁に更新が開始されます。

距離の関数で 2 つの粒子間の最適なリフレッシュ レートを計算するには、この背後にある数学を知る必要があります。したがって、私の質問は、ここで説明しているものの正式な名前は何ですか?

4

3 に答える 3

3

O(n^2)各ステップでペアワイズ相互作用の完全なセットを計算するコストを克服するために、この種のN 体シミュレーションは、多くの場合、Barnes-Hutアプローチを使用して実装されます。これは、あなたが説明したマルチ解像度のアイデアのタイプと精神的に似ています。

Barnes-Hut はO(n*log(n))、階層空間分割戦略に基づく完全なペアワイズ相互作用項の効率的な ( ) 近似です。粒子のセットは、高さ の空間インデックス ツリーであるoctree (図の四分木) に挿入されます。子へのポインターを含むことに加えて、ツリーの各レベルのノードには、子粒子のセットの重心も含まれます。ツリー ノードは、実際には、さまざまな空間解像度でひとまとめにされた「超粒子」です。R^2O(log(n))

特定のパーティクルに作用する力を計算するとき、ツリーはルートからトラバースされ、各ノードで、その子へのトラバースを続行するか、またはその重心に基づいて近似的な「集中」寄与を取得するかが決定されます。子供。通常、この決定は問題の粒子からの質量中心の距離に基づいて行われます。質量中心が「十分に離れている」場合、トラバーサルは終了し、「集中」近似が行われます。

この戦略により、完全な (そして高価な) ペアワイズ相互作用が「短い」粒子距離でのみ計算され、距離が増加するにつれて近似の「集中」相互作用が使用されることが保証されます。

最先端の N 体アルゴリズムは、システム内の各粒子の個々の (そして可変の) 時間ステップも組み込んで、効率を高めていますが、これは非常に複雑になり始めています!

お役に立てれば。

于 2013-06-30T04:22:45.153 に答える
1

時間ステップ シミュレーションを行っており、ローカリゼーションと呼ばれるパフォーマンスを向上させるヒューリスティックを使用しています。

于 2013-06-30T03:45:14.513 に答える
0

あなたが説明する一般的なアルゴリズムはN-body シミュレーションです。

あなたが説明したヒューリスティックに普遍的な名前があるとは思いません。

于 2013-06-30T00:08:09.660 に答える