David Eisenstat
2020-11-28 22:54:56
我不知道如何分析该算法，也没有引文，但似乎可行。
选择一个出发中心。你当前的近似值应该可以很好地解决此问题。
计算从当前中心到S的最短路径树。
修剪树，以便所有叶子都属于S并计算其中心。
如果此中心比根中心好，请返回到步骤2。
关于该算法，我可以真正声明的两个形式属性是：它总是终止，并且永远不会比起始中心差（因为如果树的中心不是根，那么它必须是比根更好的中心，因为缺少的边缘可以改善它，但不能改善根部）。
为了有效地计算树的中心，请在每个节点的所有后代中以最大距离标记每个节点（在线性时间内，通过按后顺序访问这些节点）。然后通过带有最大标签的子项下降到树中，只要它能改善半径。孩子的子树中的所有内容都将随着孩子的父边缘的长度而变得更近。其他一切都将以相同的数量增长。
热门帖子
热门github
1
2
3
5
6
7
8
11
13
14
15
Mamba is a new state space model architecture showing promising performance on information-dense data such as language modeling, where previous subquadratic models fall short of Transformers. It is based on the line of progress on structured state space models, with an efficient hardware-aware design and implementation in the spirit of FlashAttention.
(翻译：Mamba 是一种新的状态空间模型架构，在信息密集型数据（例如语言建模）上显示出良好的性能，而之前的二次模型在 Transformers 方面存在不足。它基于结构化状态空间模型的进展，并本着FlashAttention的精神进行高效的硬件感知设计和实现。)
简洁，好用。它的边缘数量不会比二次方更糟：如果将每个顶点作为潜在中心进行测试，就会发生这种情况，但是我很难想象这种情况。我可以想象（但没有尝试给出一个例子）它可能会陷入局部最小值，但是我认为我不必为此担心。
我还没有时间进行测试，但是我现在就接受它，因为它最简单，应该可以完成工作。尝试过此方法后，我将进行更新。
原来我正确地放置了复选标记。即使我将k设置为低至3，该算法也会在运行时方面优于您的其他建议。在输出质量方面，我需要将k = 36设置为从另一种算法中获得更好的结果，这时运行时间要超过10倍。
@Thomas感谢您的更新。这对我来说并不奇怪，因为另一点是最坏情况的保证，但通常输入数据与对抗性数据相差甚远。
@Thomas是的，我的意思是古怪。如前所述，我们最初计算每个子树的高度。然后随着下降，我们得到当前的候选中心v以及从v到不在v的子树中的节点的最大距离（最初为零）。v的离心率是v的高度和非子树的最大值。一旦确定了高度最大的v的子w，我们将分两步更新max非子树。首先，对于v的每个子x，其中x≠w，我们将max非子树更新为max（max non-subtree，length（vx）+ height（x））。然后，我们将最大非子树的长度增加（vw）。