3

我试图将二叉树拆分为 k 个类似大小的部分（通过删除 k-1 个边）。有没有解决这个问题的有效算法？或者它是NP难的？任何指向论文、问题定义等的指针？

-- 评估分区质量的一个合理指标可能是最大和最小分区之间的大小差距；另一个指标可能是使最小的分区具有尽可能多的顶点。

4

2 回答 2

3

这是一个多项式确定性解决方案：

  1. 让我们假设树是有根的并且有两个固定值：MIN和MAX- 一个组件的最小和最大允许大小。

  2. 然后可以使用动态编程来检查是否存在分区，使得每个组件大小介于MIN和之间MAX：

  3. 让我们假设当且f(node, cuts_count, current_count)仅true当有一种方法可以精确cuts_count切割node' 的子树，以便current_count顶点连接到 ，node从而条件 2) 成立。

  4. 叶子的基本情况是：（f(leaf, 1, 0)从父节点到叶子的边切割）true当且仅当MIN <= 1and MAX >= 1 f(leaf, 0, 1)（不切割它）总是true（它适用于andfalse的所有其他值）。 cuts_countcurrent_count

  5. 要计算fa node（不是叶子），可以使用以下算法：

    //Combine all possible children states.
for cuts_left in 0..k
    for cuts_right in 0..k
         for cnt_left in 0..left_subtree_size
            for cnt_right in 0..right_subtree_size
                if f(left_child, cuts_left, cnt_left) is true and
                   f(right_child, cuts_right, cnt_right) is true and then
                      f(node, cuts_left + cuts_right, cnt_left + cnt_right + 1) = true
//Cut an edge from this node to its parent.
for cuts in 0..k-1
    for cnt in 0..node's_subtree_size
       if f(node, cuts, node's_subtree_size) is true and MIN <= cnt <= MAX: 
           f(node, cuts + 1, 0) = true

    该伪代码所做的是结合节点子节点的所有可能状态来计算该节点的所有可达状态（第一组 for 循环），然后通过切割该节点与其父节点之间的边（第二一堆 for 循环）（状态意味着(node, cuts_count, current_count)元组。我称之为可达 if f(state)is true）。
    对于具有两个孩子的节点就是这种情况，具有一个孩子的情况可以以类似的方式进行处理。

  6. 最后，如果f(root, k, 0)是true则有可能找到对条件 2) 进行分层的分区，否则不可能。我们需要“假装”我们在这里进行了切割，因为当我们计算根时（以避免极端情况），k我们还切割了从根到其父级的假想边（此边和此父级实际上不存在）。f

  7. 该算法的空间复杂度（对于固定MIN和MAX）为O(n^2 * k)（n为节点数），时间复杂度为O(k^2 * n^2)。看起来复杂度实际上是O(k^2 * n^3)，但实际上并非如此，因为节点左右子树中的顶点数的乘积恰好是节点对的数量，因此它们的最小共同祖先就是该节点。但是节点对的总数是O(n^2)（并且每一对只有一个最不共同的祖先）。因此，所有节点上左右子树大小的乘积之和为O(n^2)。

  8. 人们可以简单地尝试所有可能的MIN价值观MAX并选择最好的，但可以做得更快。关键的观察是，如果 和 有解，和MIN总是MAX有解。因此，可以迭代（不同值）的所有可能值并应用二进制搜索来找到给出有效解决方案的最小值（迭代）。所以总的时间复杂度是。但是，如果您想最大化（而不是最小化和之间的差异），您可以简单地使用此算法并忽略任何地方的值（通过将其值设置为）。然后没有二进制搜索MINMAX + 1MINn / kMAXlog nO(n^2 * k^2 * n / k * log n) = O(n^3 * k * log n)MINMAXMINMAXnMAX将是必需的，但可以进行二进制搜索MIN并获得O(n^2 * k^2 * log n)解决方案。

  9. 要重建分区本身，可以从f(root, k, 0)我们用来计算的步骤开始并应用f，但这次是相反的方向（从根到叶）。也可以保存有关如何获取每个状态的值的信息（结合了哪些子状态或边缘被切割之前的状态是什么）（并在初始计算期间适当更新f），然后重建分区使用这些数据（如果我对这一步的解释似乎不是很清楚，阅读一篇关于动态编程的文章并重建答案可能会有所帮助）。

因此，在二叉树上存在这个问题的多项式解决方案（即使对于任意图来说它是 NP 难的）。

于 2014-07-29T20:32:48.590 回答
3

我可以建议非常快速的解决方案，以使最小的部分具有尽可能多的顶点度量。

假设我们猜测最小部分的大小 S 并想要检查它是否正确。首先我想说几句：

  1. 如果树的总大小大于 S，则至少有一个子树大于 S，并且该子树的所有子树都较小。（检查两个最大的就足够了。）

  2. 如果有某种方法可以拆分树，其中最小部分的大小 >= S，并且我们有子树 T，其所有子树都小于 S，那么我们可以允许 T 内的边不被删除。（因为任何这样的删除都会创建一个小于 S 的分区）

  3. 如果有某种方法可以拆分树，其中最小部分的大小 >= S，并且我们有一些大小 >= S 的子树 T，内部没有删除的边但不是部分之一，我们可以用其他方式拆分树子树 T 将是一个部分本身，所有部分都不会小于 S。（只需将一些额外的顶点从原始部分移动到任何其他部分，其他部分不会变小。）

所以这里有一个算法来检查我们是否可以将树分成不小于 S 的 k 个部分。

  1. 找到所有合适的顶点（大小> = S的子树的根和两个孩子的大小< S）并将它们添加到列表中。当子树大于 S 时，您可以从根开始并遍历所有顶点。

  2. 当列表不为空且零件数量较少时，K 从列表中取出一个顶点并将其从树上切断。比更新父顶点的子树的大小，如果其中一个变得合适，则添加到列表中。您甚至不需要更新所有的父顶点，只有在您首先发现哪个新的子树大小大于 S 时，父顶点尚不适合添加到列表中，可以稍后更新。

  3. 您可能需要重新构造树以恢复分配给顶点的原始子树大小。

现在我们可以使用二分法。我们可以将上限确定为 Smax = n/k 并且可以从等式 (2*Smin- 1)*(K - 1) + Smin = N 中检索到下限，如果我们用两个大小为 Smin - 1 个的子子树，我们将剩下大小为 Smin 的部分。Smin = (n + k -1)/(2*k - 1) 现在我们可以检查 S = (Smax + Smin)/2 如果我们设法使用上述方法构造分区，则 S 小于或等于它的最大值可能的值，构造分区中的最小部分也可能大于 S，如果我们失败，我们可以为其设置新的下限而不是 S，如果 S 大于可能。

一次检查的时间复杂度是 k 乘以每次更新的父节点数量，对于平衡良好的树，更新节点的数量是恒定的（我们将使用前面解释的技巧并且不会更新所有父节点），仍然不大于 (n /k) 在最坏的情况下最终不平衡的树。搜索合适的顶点具有非常相似的行为（搜索时传递的所有顶点将在稍后更新。）。

n/k 和 (n + k -1)/(2*k - 1) 之间的差异与 n/k 成正比。

所以我们有时间复杂度 O(k * log(n/k)) 如果我们有预先计算的子树大小，O(n) 如果子树大小没有预先计算，最坏的情况是 O(n * log(n/k))案子。

这种方法可能会导致最后一个零件相当大的情况，但我想一旦你得到建议的方法，你就可以找出一些改进来最小化它。

于 2014-08-01T23:54:49.717 回答