1

我想运行 Barnes Hut N 体模拟（维基百科文章）。我知道八叉树的单个节点将占用多少内存，但我无法弄清楚对于给定数量的粒子，最坏的内存使用情况是什么。简而言之，我想知道对于给定数量的粒子，八叉树中可能存在多少个节点。我需要知道这一点才能知道为八叉树分配多少内存。

编辑：

哦，如果有人想给我代码而不是仅仅和解释，我正在用 C 语言编写。

我有这个，这比最坏的情况还要糟糕。但它保证至少分配足够的内存。我希望有人能给我一些内存效率更高的东西。

int KBH_worstcase(int particles)
{ // returns number of nodes required to store a number of particles in a worst case scenario
    int worst;
    unsigned int n;
    worst=1;
    n=1;
    while(n<particles)
    {
        n=n<<3;
        worst+=n;
    }
    return worst;
}
4

2 回答 2

2

我不确定是否存在这样一个合适的标准。八叉树考虑了在模拟过程中可能发生变化的粒子分布。所以树的有效深度不能只依赖于粒子的数量。

一种虚假的解决方案可能是定义树深度（或节点数）的界限。在这种情况下，您可以将更多粒子组合在一个单元格（八叉树的叶子）中，然后退回到身体-身体相互作用。但是，如果您想对树结构进行更多控制，那么在必要时能够分配新节点可能会更好。

于 2012-09-03T17:53:11.233 回答
0

实际上，四叉树（或三维的八叉树）所需的节点数上限不受粒子总数的对数限制。

通常，节点中的空间被划分为四个相等的象限。考虑与根节点的边界框相比，两个粒子彼此非常接近的情况。在这里很容易看出，在到达单个粒子的节点之前，需要创建很多内部节点。见下图。

在此处输入图像描述

许多内部节点 - 只有两点

二维的上限应该是（我的头顶）

log4 w/m

其中 w 是根节点边界框​​的大小，m 是任意两个粒子之间的最短距离。

但是，计算任意两点之间的最短距离具有 O(n^2) 复杂性，这是您希望避免的。

您可以改为修改算法以仅将树构建到最大深度 d。这会将内存消耗限制为 4^(d+1)-1 个节点。

您还需要小心处理与多个粒子的节点之间的交互，例如退回到朴素的 O(n^2) 算法。

于 2015-03-29T20:06:03.047 回答