PL 
EnglishDomyślny
Українська🌌 Barnes–Hut N-body
Algorytm Barnes–Hut przybliża symulację grawitacyjną N-body w czasie O(n log n) dzięki drzewu czwórkowemu i kryterium dokładności θ. Zobacz, jak drzewo dostosowuje się do skupisk, a liczba obliczeń siły spada w porównaniu z naiwnym O(n²).
O algorytmie N-ciał Barnesa-Huta
Grawitacyjny problem N ciał — obliczenie siły działającej na każdą cząstkę od wszystkich pozostałych — naiwnie wymaga O(n²) obliczeń na krok czasowy, co staje się nieakceptowalnie kosztowne dla dużych n. Algorytm Barnesa-Huta (1986) redukuje to do O(n log n), rekurencyjnie dzieląc przestrzeń na quadtree (w 2D) lub octree (w 3D) i traktując skupiska odległych ciał jako pojedynczy środek masy, gdy stosunek s/d (rozmiar komórki s do odległości d) spada poniżej progowego kąta θ. Jest to podstawa nowoczesnych kodów formowania galaktyk, takich jak GADGET, i jest wykorzystywana w każdej kosmologicznej symulacji formowania struktur we Wszechświecie.
Ta symulacja pozwala zmieniać liczbę ciał N (do 2000), kąt otwarcia θ (0 = dokładny, 1,5 = bardzo przybliżony), grawitacyjne wygładzanie ε oraz krok czasowy dt spośród czterech ustawień początkowych: obłok gazu, dwie zderzające się galaktyki, masa centralna + obłok oraz pierścień. Włączenie nakładki quadtree pokazuje, które komórki są przybliżane (cyjan), a które przeszukiwane rekurencyjnie (róż) dla podświetlonego ciała, natychmiast uwidaczniając kompromis między szybkością a dokładnością.
Najczęściej zadawane pytania
Czym jest problem N ciał?
Grawitacyjny problem N ciał pyta: mając N mas punktowych o znanych początkowych pozycjach i prędkościach, obliczyć ich przyszłe pozycje pod wpływem wzajemnej grawitacji Newtona F = Gm₁m₂/r². Dla N = 2 rozwiązaniem jest przekrój stożkowy (orbita Keplera); dla N ≥ 3 nie istnieje ogólne rozwiązanie w postaci zamkniętej i wymagane jest całkowanie numeryczne. Każdy krok czasowy naiwnie kosztuje O(n²) obliczeń siły, co czyni duże symulacje — modelujące miliony gwiazd — niewykonalnymi bez algorytmu przybliżającego.
Jak działa quadtree Barnesa-Huta?
W każdym kroku czasowym algorytm wstawia wszystkie ciała do quadtree — rekurencyjnego podziału przestrzeni 2D na cztery równe kwadraty. Aby obliczyć siłę działającą na ciało i, drzewo jest przeszukiwane od korzenia: jeśli komórka węzła jest „wystarczająco daleko” (s/d < θ, gdzie s to szerokość komórki, a d to odległość do i), cała komórka jest przybliżana przez jej całkowitą masę i środek masy. W przeciwnym razie węzeł jest otwierany, a jego dzieci są sprawdzane. Redukuje to typową liczbę interakcji z O(n) na ciało do O(log n).
Co kontroluje kąt otwarcia θ?
θ (theta) to kluczowy parametr dokładności/szybkości. Przy θ = 0 każda komórka jest zawsze otwierana niezależnie od odległości, odtwarzając dokładną sumę bezpośrednią O(n²). Przy θ = 0,5 (typowa wartość produkcyjna) algorytm jest dokładny w około 95% w porównaniu z sumowaniem bezpośrednim, działając przy tym z grubsza 30–100× szybciej dla n = 1000. Przy θ = 1,5 szybkość jest maksymalna, ale struktura odległych galaktyk jest zauważalnie rozmyta. Symulacja wyświetla współczynnik przyspieszenia na żywo, dzięki czemu możesz obserwować ten kompromis bezpośrednio.
Czym jest grawitacyjne wygładzanie (ε)?
Grawitacyjne wygładzanie zastępuje prawo siły 1/r² wyrażeniem 1/(r² + ε²), co zapobiega dążeniu siły do nieskończoności, gdy dwa ciała zbliżą się bardzo do siebie. Bez wygładzania bliskie spotkania wymagałyby nieskończenie małego kroku czasowego dla dokładnego całkowania, powodując awarię symulacji lub generowanie bezsensownych prędkości „procy grawitacyjnej”. Długość wygładzania ε jest zwykle ustawiana jako ułamek średniej odległości międzycząsteczkowej; w rzeczywistych symulacjach kosmologicznych wynosi około 1 kpc dla cząstek ciemnej materii.
Dlaczego algorytm Barnesa-Huta ma złożoność O(n log n)?
Quadtree ma O(n) węzłów i głębokość O(log n). Dla każdego z n ciał przeszukiwanie drzewa odwiedza średnio O(log n) węzłów, zanim wystarczająca liczba komórek spełni kryterium θ. Pomnożenie daje O(n log n) obliczeń siły na krok. Budowa samego drzewa również kosztuje O(n log n). W praktyce czynniki stałe są małe, a dla n = 10 000 przyspieszenie względem O(n²) wynosi około 100–1000-krotności.
Co dzieje się podczas ustawień zderzenia dwóch galaktyk?
Gdy dwie galaktyki przechodzą przez siebie, siły pływowe zdzierają gwiazdy z zewnętrznych krawędzi i wyrzucają je w długie „ogony pływowe” i mostki rozciągające się na miliony lat świetlnych. Proces jest sterowany niemal wyłącznie przez grawitację; dyski gwiazdowe przechodzą przez siebie w dużej mierze bez przeszkód, ponieważ gwiazdy są tak rozproszone. Droga Mleczna i galaktyka Andromedy są na kursie kolizyjnym i oczekuje się, że połączą się za około 4,5 miliarda lat, tworząc podobną strukturę ogona pływowego widoczną w tym ustawieniu.
Jak przyspieszenie wypada w porównaniu z naiwnym O(n²) w praktyce?
Symulacja wyświetla liczbę obliczeń Barnesa-Huta obok naiwnych n(n–1)/2 porównań wymaganych do sumowania bezpośredniego. Dla n = 500 i θ = 0,7 Barnes-Hut typowo oblicza około 3000–5000 par sił na ciało na krok zamiast 499, dając przyspieszenie 50–100×. Wraz ze wzrostem n przewaga narasta: przy n = 2000 metoda naiwna potrzebuje niemal 2 milionów obliczeń par na krok, podczas gdy Barnes-Hut potrzebuje jedynie około 20 000.
Czym są energia kinetyczna i potencjalna i dlaczego się wahają?
Energia kinetyczna KE = Σ ½mᵢvᵢ², a grawitacyjna energia potencjalna PE = –Σᵢ≠ⱼ Gmᵢmⱼ/rᵢⱼ (sumowana po wszystkich parach). W prawdziwej symulacji zachowawczej energia całkowita E = KE + PE powinna być stała, ale całkowanie numeryczne wprowadza błędy. Zastosowany tu integrator leapfrog (Verlet) jest symplektyczny, co oznacza, że zachowuje zmodyfikowany hamiltonian i utrzymuje bardzo mały długoterminowy dryf energii. Obserwowane wahania są częściowo prawdziwymi wymianami fizycznymi (np. ciało na ekscentrycznej orbicie zamienia KE na PE), a częściowo błędem obcięcia numerycznego wynikającym ze skończonego dt.
Czym jest podświetlenie „wrażliwości na warunki początkowe”?
Gdy zaznaczysz „Podświetl zejście θ dla wybranego ciała”, kliknięcie ciała pokazuje, które komórki quadtree są dla niego przybliżane, a które przeszukiwane rekurencyjnie. Ta sama komórka quadtree może być traktowana różnie dla ciał w różnych pozycjach, co ilustruje, że Barnes-Hut jest algorytmem adaptacyjnym. Aby zobaczyć chaos w rzeczywistych trajektoriach N ciał, użyj porównania dwóch trajektorii w powiązanych symulacjach: nawet perturbacja Δ = 10⁻⁵ warunków początkowych prowadzi do wykładniczo rozbieżnych ścieżek, co pokazuje, że problem N ciał jest ogólnie chaotyczny.
Czy algorytm Barnesa-Huta jest wykorzystywany w prawdziwych kodach astrofizycznych?
Tak — rodzina kodów GADGET (Springel 2001, 2005) używa hierarchicznego drzewa bardzo podobnego do Barnesa-Huta i była wykorzystywana do symulowania Millennium Simulation (10 miliardów cząstek) oraz symulacji formowania galaktyk IllustrisTNG. Nowoczesne kody często łączą Barnesa-Huta z metodami szybkiego multipolu (FMM), technikami particle-mesh (PM) lub równoległością GPU, by symulować do 10¹² cząstek. Algorytm jest wykorzystywany również poza astrofizyką, w dynamice molekularnej, symulacjach płynów i renderowaniu gęstych układów cząstek.
Co oznacza „środek masy” w kontekście quadtree?
Każdy węzeł wewnętrzny quadtree przechowuje całkowitą masę M = Σmᵢ oraz ważoną masą średnią pozycję r_cm = Σmᵢrᵢ / M wszystkich ciał w tej komórce. Gdy odległa komórka jest przybliżana, siła grawitacyjna działająca na ciało i jest obliczana tak, jakby cała masa tej komórki była skupiona w r_cm. To przybliżenie jednobiegunowe jest dokładne w pierwszym rzędzie s/d; wyższego rzędu rozwinięcia multipolowe (kwadrupol, oktupol) można uwzględnić dla lepszej dokładności kosztem większego zapotrzebowania na pamięć i obliczenia.