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

Алгоритм Барнса-Хата — це ієрархічний метод наближення, який пришвидшує симуляції n тіл — де кожна частинка діє гравітаційною чи електростатичною силою на кожну іншу — з наївної вартості O(n²) до O(n log n). Він рекурсивно поділяє простір на квадродерево (у 2D) або октодерево (у 3D), і коли група віддалених частинок достатньо мала відносно відстані до цільової частинки, вся група трактується як єдина точкова маса в її центрі мас, замість підсумовування кожної частинки окремо. Запропонований Джошем Барнсом і Пітом Хатом 1986 року, алгоритм робить симуляції масштабу галактик і систем із великою кількістю частинок обчислювально здійсненними на звичайному обладнанні, обмінюючи невелику, регульовану частку точності на разюче зменшення обчислень зі зростанням кількості частинок. Те, чи кластер вважається "достатньо далеким" для наближення, контролює поріг кута розкриття θ: менше значення θ вимагає суворішої точності й змушує алгоритм заглиблюватися в дерево, перш ніж наближати, тоді як більше θ наближає агресивніше й працює швидше ціною певної числової похибки. Саме цей регульований компроміс робить алгоритм Барнса-Хата, а не наївне попарне підсумовування, основою більшості симуляцій галактик, зоряних скупчень та електростатики частинок реального часу, яким потрібно масштабуватися за межі кількох тисяч тіл.