Barnes-Hut Algorithm

释义 Definition

Barnes-Hut 算法：一种用于加速 N 体问题（如引力或库仑力相互作用）计算的近似算法。它通过把远处的一组粒子用“整体”（质量中心/多极近似）来近似，并用 树结构（2D 常用四叉树 quadtree，3D 常用八叉树 octree）组织空间，将计算复杂度通常从 \(O(N^2)\) 降到约 \(O(N\log N)\)。常见于天体物理模拟、粒子系统与大规模物理仿真。（该术语也可泛指“Barnes-Hut 树算法/树码 treecode”。）

发音 Pronunciation (IPA)

/ˈbɑːrnz hʌt ˈælɡəˌrɪðəm/

例句 Examples

We used the Barnes-Hut algorithm to speed up the gravity simulation.
我们使用 Barnes-Hut 算法来加速引力模拟。

By tuning the opening angle parameter, the Barnes-Hut algorithm balances accuracy and performance in large N-body systems.
通过调整开角参数，Barnes-Hut 算法能在大型 N 体系统中平衡精度与性能。

词源 Etymology

“Barnes-Hut”来自提出该方法的两位研究者 Josh Barnes 与 Piet Hut 的姓氏；该算法最早以树结构近似远距离相互作用而闻名，属于计算物理与计算天体物理中经典的 treecode（树码） 方法之一。

相关词 Related Words

• N-Body Problem
• Quadtree
• Octree
• Treecode
• Fast Multipole Method
• Gravitational Simulation
• Approximation

文学与典籍 Literary Works

• Barnes, J. & Hut, P. (1986). A hierarchical O(N log N) force-calculation algorithm. Nature（提出并系统阐述 Barnes-Hut 算法的经典论文）
• Springel, V. (2005). The cosmological simulation code GADGET-2. Monthly Notices of the Royal Astronomical Society（讨论树算法/相关思想在宇宙学 N 体模拟代码中的应用）
• Hockney, R. W. & Eastwood, J. W. Computer Simulation Using Particles（粒子模拟经典教材，涉及 N 体计算加速与相关方法）
• Dehnen, W. & Read, J. I. (2011). N-body simulations of gravitational dynamics. European Physical Journal Plus（综述 N 体方法，常包含 Barnes-Hut 等树算法的讨论）