Быстрый алгоритм гравитации нескольких тел? - PullRequest
Новая
       30

Быстрый алгоритм гравитации нескольких тел?

2 голосов
/ 14 ноября 2011

Я пишу программу для моделирования гравитационной системы из 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 (в двух измерениях) превышают определенную величину, определяемую произведением их масс?Извините, если это звучит так, как будто я болтаю, но могу ли я что-нибудь сделать, чтобы сделать это быстрее?Я бы предпочел, чтобы это было сколь угодно точным, но если есть решения, которые могут снизить сложность этой проблемы за счет некоторой точности, мне было бы интересно услышать ее.*

Ответы [ 3 ]

7 голосов
/ 14 ноября 2011

Взгляните на этот вопрос .Вы можете разделить ваши объекты на сетку и использовать тот факт, что многие далекие объекты можно рассматривать как один объект для хорошего приближения.Масса клетки равна сумме масс объектов, которые она содержит.Центр масс клетки можно рассматривать как центр самой клетки, или, точнее, барицентр объектов, которые он содержит.В среднем случае, я думаю, это дает вам производительность O ( n log n ), а не O ( n 2 ),потому что вам все еще нужно рассчитать силу тяжести для каждого из n объектов, но каждый объект взаимодействует только индивидуально с теми, кто находится рядом.

Предполагается, что вы вычисляетерасстояние с r 2 = x 2 + y 2 , а затем вычислениесила с F = G м 1 м 2 / r 2 , вам вообще не нужно выполнять квадратный корень.Если вам нужно фактическое расстояние, вы можете использовать быстрый обратный квадратный корень .Вы также можете использовать арифметику с фиксированной точкой .

3 голосов
/ 14 ноября 2011

Одним из подходов с хорошими потерями было бы запустить алгоритм кластеризации для объединения тел.

Существуют некоторые алгоритмы кластеризации, которые достаточно быстрые, и хитрость будет заключаться в том, чтобы не запускать алгоритм кластеризации каждый тик. Вместо этого запускайте его каждые C галочки (C> 1).

Затем для каждого кластера рассчитайте силы между всеми телами в кластере, а затем для каждого кластера рассчитайте силы между кластерами.

Это будет с потерями, но я думаю, что это хороший подход.

Вам придется возиться с:

  • Какой алгоритм кластеризации использовать: некоторые быстрее, другие более точны. Некоторые детерминированы, некоторые нет.
  • как часто запускать алгоритм кластеризации: чем меньше он будет работать, тем больше будет работать больше.
  • как мал / велик сделать кластеры: большинство алгоритмов кластеризации дают вам некоторую информацию о размере кластеров. Чем больше вы позволите кластерам быть, тем быстрее, но менее точным будет результат.

Так что это будет игра скорости против точности, но, по крайней мере, таким образом вы будете в состоянии пожертвовать немного точности для некоторого увеличения скорости - с вашим текущим подходом вы ничего не сможете по-настоящему настроить на всех.

1 голос
/ 14 ноября 2011

Возможно, вы захотите попробовать менее точную версию квадратного корня.Вам, вероятно, не нужна полная двойная точность.Особенно, если порядок вашей системы координат обычно одинаков, то вы можете использовать усеченный ряд Тейлора, чтобы довольно быстро оценить операцию квадратного корня, не теряя слишком много эффективности.

...