N体模拟——Barnes-Hut 算法

三体问题可以在知乎这个问题了解一下 https://www.zhihu.com/question/35025389 Barnes-Hut算法是专门针对N体问题的模拟过程设计的一个算法,它可以将一次模拟过程的复杂度变为O(N*logN)。

该算法的基本思想是:通过八叉树将整个空间划分为立方体。对于每个星球,由于距离较近的星球对它的影响较大,距离较远的星球对它的影响较小,因此只需要对它附近的星球进行单独处理,然后将较远的星球的信息压缩在树中的虚拟节点中。这样就可以将每个星球的计算量压缩到O(log N)级别。

Licensed under CC BY-NC-SA 4.0