1

有一棵树有 N 个节点和 N-1 条边（使它成为一棵树）。每个节点都有一个权重 W(i)。如何选择一个仍包含原始树根的大小为 K 个节点的子树？我必须这样做，以便最大限度地减少选择此“子树”的“成本”，其中成本定义为保留的所有边的权重之和。

我想我以前做过这样的问题，看起来像 DP/recursion。但是，当每个节点限制为 2 个子节点时，我知道如何处理它。您已经定义了一个函数 cost(n, i)，这意味着从节点 n 开始保持 i 个节点的最小成本。您将在其中一个孩子中从 i = 0 迭代到 n ，并将其余部分交给另一个孩子。但是，由于每个节点可以有无限数量的孩子，有没有办法解决这个问题？

谢谢

4

2 回答 2

2

对于给定的节点，您希望使用其子节点的 cost(n, i) 计算成本(n, i)。从 0..K 开始给孩子编号，你就有了另一个动态程序。在第 j 阶段，您希望仅使用子 0..j 计算出可能的最佳成本集（n，i）。

我一直在考虑编写这样的代码，同时玩弄机器学习（只是为了好玩，我想编写通过安装两个 Weka 分类器而不是一个来查找异常的程序）。这和你的目的一样吗？

于 2012-10-12T19:19:10.670 回答
0

DP 解决方案（可能与 mcdowella 所描述的相似，也可能不同）：

让根节点编号为0。其余节点可以任意编号（但最好的方法是逐级对节点进行编号）。

f(i, j)表示当我们考虑索引大于 i 的所有兄弟节点加上任何子节点（如果适用）时的最小成本，并且我们从有效节点中挑选 j 个节点。

f(i, 0) = 0            // i can be anything, even NOT_FOUND
f(NOT_FOUND, j) = +Inf // j > 0
f(i, j) = min(f(x, j), // Node i not chosen
              min[r = 0 to j - 1] (f(x, j - 1 - r) + f(y, r)) + cost(i))
              // Node i is chosen, then we can pick some elements from 
              // children node, or from untouched sibling nodes + descendants

在哪里

  • x是大于 的最小索引i，并且 nodex和i是兄弟节点
  • y是最小索引，其中节点y是节点 i 的子节点。
  • 如果未找到索引x，则分配 NOT_FOUND 。y

结果将在f(0, K).

于 2012-10-12T20:59:00.433 回答