gpt4 book ai didi

algorithm - 将不平衡树转换为生成树

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:45:08 25 4
gpt4 key购买 nike

<分区>

如何将不平衡的树转换为(平衡的)生成树?假设我有一棵树(在不同节点有不同(不一定不同)数量的 child )。我想以这样的方式操作树,使其成为 k 元生成树。

允许对树进行各种迭代。限制是我们不能只在一个地方收集所有节点,然后从中生成一棵生成树(这是一种简单的方法)。相反,必须从给定的树创建生成树。也就是说,子节点可以与父节点(以及祖父节点,如果需要)交换信息(例如,它拥有的子节点的数量和子节点的 ID),并且父节点决定在其子节点之间移动节点(按顺序平衡树)。

您可能已经理解我正在尝试在并行计算环境中执行此操作。其中,一个节点只知道其父节点的 ID、其子节点以及每个子树中以其子节点为根节点的节点数。

(当我们试图平衡树时, parent 和 child 会改变)。关于如何解决这个问题的任何提示?


回复为什么这个问题很重要/值得考虑的评论 - 毕竟琐碎的方法是可扩展的:

  1. 从理论上讲,开发一种使用小于 O(N) 空间(用于平凡方法)的算法来构建生成树具有挑战性。

  2. 大规模考虑替代解决方案很有趣。

  3. 就数字而言:N=100,000(这在当今的 super 计算机中很常见,在即将到来的 BG/Q 中 N 将达到 1000,000)。在简单的方法中,所涉及的步骤是 a) all-reduce b) O(N) 以构建生成树和 c) 最后是一对多广播。

另一种分布式方法可能不会带来太大改进,但出于好奇,它可能值得一试。

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com