c# - 如何有效地计算力（胡克定律）？

Question

我正在尝试优化力导向图。到目前为止，我已经使用朴素的 O(n ² ) 方法实现了它。它只能处理大约 1000 个节点，这对于我的需求来说太少了。

熟悉该算法的人都知道它有两个主要组成部分：库仑定律形式的节点之间的排斥和使用胡克定律沿边缘的弹簧状吸引力，这两个组成部分都涉及节点之间的成对计算。

Barnes-Hut 算法很好地适用于前者，它将排斥分量变为 O(n log n)。但是，我无法为弹簧组件找到类似的东西。我考虑了以下几点：

1. 根据位置将节点划分为重叠的 bin，并仅在同一 bin 中的节点之间执行成对计算。但是，这可能并非在所有情况下都有效，特别是因为节点的初始配置是随机的，并且连接的节点可能在任何地方。我可以更改生成节点的方式，但除非它们都在同一个 bin 中，否则它仍然会产生不正确的结果。

2. 分别存储边缘并遍历它们以计算弹簧力。现在这对我来说似乎是最有希望的方法。

有没有更好的方法我没有考虑过？如果这很重要，我正在使用 C#，如果在并行循环中抛出它是微不足道的，那就太好了。

Answer 1

我觉得您给出的第二个选项应该在边数方面具有线性复杂性。只需遍历它们并不断更新各自 2 个节点上的合力。

编辑：对不起，我之前认为每个节点都通过弹簧连接到每个其他节点。

Answer 2

如果我对你的理解正确，你有 O(n log n) 的斥力分量和吸引力分量是稀疏的：对于每个节点，你平均有 k << n 个类似弹簧的吸引力。如果是这样，您可以通过将吸引力存储在邻接列表而不是邻接矩阵中来处理 O(n * k) 中的吸引力分量。

Answer 3

最后，我实现了我在第二个案例中描述的内容，并且效果很好。我维护并迭代了每个节点的邻居集合，这使得整个加速例程可以很容易地并行化（与 Barnes-Hut 一起）。总体时间复杂度为 O(max(n log n, k))，其中 k 是边的总数。我的 C# 实现以可接受的性能水平处理大约 100000 个节点和 150000 个边。