algorithm - 树的最小权重顶点覆盖

Question

有一个 existing question处理顶点权重为其度数的树，但我对顶点可以具有任意权重的情况感兴趣。

这不是家庭作业，但它是我正在阅读的算法设计手册中的问题之一；答案集给出的解决方案为

1. 执行 DFS，在每一步更新 Score[v][include]，其中 v 是一个顶点，include 为真或假；
2. 如果 v 是叶子，设置 Score[v][false] = 0，Score[v][true] = w_v，其中 w_v 是顶点v的权重。
3. 在 DFS 期间，当从节点 v 的最后一个子节点向上移动时，更新 Score[v][include]:Score[v][false] = Score[c][true] 和 Score[v][true] = w_v + Sum for c in children(v ) 的最小值(分数[c][真]; 分数[c][假])
4. 通过回溯 Score 提取实际覆盖。

但是，我实际上无法将其转化为有效的东西。 (作为对评论的回应:到目前为止我尝试的是绘制一些带有权重的小图并在纸上运行算法，直到第四步，其中“提取实际封面”部分不透明。)

作为回应 Ali 的回答:所以假设我有这个图，顶点由 A 等给出，权重在后面的括号中:

A(9)---B(3)---C(2)
\\
E(1) D(4)


正确答案显然是 {B,E}。

通过这个算法，我们会像这样设置值:

• 得分[D][false] = 0; 得分[D][true] = 4
• 得分[C][false] = 0; 得分[C][true] = 2
• 分数[B][false] = 6; 得分[B][true] = 3
• 得分[E][false] = 0; 得分[E][true] = 1
• 得分[A][false] = 4; 得分[A][true] = 12

好的，所以，我的问题基本上是，现在什么？做简单的事情并遍历 score 向量并确定本地最便宜的东西是行不通的；您最终只会包含 B。根据父级决定和交替也行不通:考虑 E 的权重为 1000 的情况；现在正确答案是 {A,B}，而且它们是相邻的。也许这不应该令人困惑，但坦率地说，我很困惑。

Answer 1

没有完成(或需要)实际的回溯。该解决方案使用动态规划来避免回溯，因为这会花费指数时间。我的猜测是“回溯分数”意味着分数包含您通过回溯获得的部分结果。

树的覆盖顶点允许包含交替和相邻的顶点。它不允许排除两个相邻的顶点，因为它必须包含所有边。

以递归计算Score的方式给出答案。不包括顶点的成本是包括其子节点的成本。然而，包含一个顶点的成本是成本较低的，包含它的子节点或不包含它们的成本，因为这两种情况都是允许的。

正如您的解决方案所建议的那样，它可以在单次通过后顺序使用 DFS 完成。诀窍是如果分数表明必须包含一个顶点，则包含一个顶点，如果必须排除它，则包含它的子节点，否则我们将排除两个相邻的顶点。

这是一些伪代码:

find_cover_vertex_of_minimum_weight(v)
  find_cover_vertex_of_minimum_weight(left children of v)
  find_cover_vertex_of_minimum_weight(right children of v)
  Score[v][false] = Sum for c in children(v) of Score[c][true]
  Score[v][true] = v weight + Sum for c in children(v) of min(Score[c][true]; Score[c][false])
  if Score[v][true] < Score[v][false] then
    add v to cover vertex tree
  else
    for c in children(v)
      add c to cover vertex tree