Алгоритм Барнса — Хата

Алгори́тм Ба́рнса — Ха́та, або моде́ль Ба́рнса — Ха́та (англ. Barnes–Hut simulation, TreeCode) — алгоритм для моделювання гравітаційної задачі N тіл у пласких структурах, подібних до галактик чи планетних систем.

Побудова моделі Барнса—Хата для сотні тіл. Межі комірок обведено блакитним.

Принцип роботи

Плаский простір поділяють на чотири прямокутні комірки. Якщо в якійсь із утворених комірок перебуває більше одного тіла, її, у свою чергу, рекурсивно поділяють на чотири комірки. Таким чином утворюється ієрархічна структура — дерево ступеня чотири (чотири-дерево, англ. quad-tree). Деякі з утворених таким чином комірок можуть бути порожніми^[1]. Взаємодію тіл у сусідніх комірках розглядають індивідуально, а тіла у віддалених комірках розглядають як одне велике тіло, розташоване в центрі мас, за рахунок чого досягається значне скорочення обчислень: (замість N*(N-1) обчислень потрібно виконати лише ${\displaystyle O(N\log N)}$)^[2].

Алгоритм застосовують для моделювання динамічних систем, в яких сила, що діє на кожний окремий елемент системи, може бути розрахована як суперпозиція сил від решти елементів, наприклад, при моделюванні поведінки магнітних рідин^[3]. В цьому випадку необхідне розширення методу до тривімирного простору (Евклідового) з використанням дерева октантів.^[4]

Див. також

• Задача двох тіл
• Задача трьох тіл
• Гравітаційна задача N тіл