树的最小权重顶点覆盖

Question

存在一个处理树的现有问题，其中顶点的权重是它的度数，但我对顶点可以具有任意权重的情况感兴趣。

这不是功课，但它是在算法设计手册，这我目前正在读的问题之一; 一个答案集给出了解决方案

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

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

作为回应阿里的回答：所以假设我有这个图，顶点由Aetc. 和括号中的权重给出：

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

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

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

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

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

Answer 1

它实际上并没有什么令人困惑的意思，它只是动态编程，你似乎几乎理解了所有的算法。如果我想说得更清楚的话，我必须说：

1. 首先在图上执行 DFS 并找到叶子。
2. 按照算法的规定，为每个叶子分配值。
3. 现在从叶子开始，并通过该公式为每个叶子父代分配值。
4. 开始为已经有值的节点的父节点分配值，直到到达图形的根。

就是这样，通过在算法中回溯，这意味着您将值分配给其子节点已经具有值的每个节点。正如我上面所说，这种解决问题的方法称为动态规划。

编辑只是为了解释您对问题的更改。正如你所看到的，你有下面的图表，答案显然是 B，E，但你认为这个算法只给你 B，但你错了，这个算法给你 B 和 E。

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

score[D][false] = 0; score[D][true] = 4
score[C][false] = 0; score[C][true] = 2
score[B][false] = 6 this means we use C and D; score[B][true] = 3 this means we use B
score[E][false] = 0; score[E][true] = 1
score[A][false] = 4 This means we use B and E; score[A][true] = 12 this means we use B and A.

你选择 4，所以你必须使用 B 和 E。如果只是 B，你的答案就是 3。但如果你找到正确的答案，你的答案就是 4 = 3 + 1 = B + E。

同样当 E = 1000 时

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

答案是 B 和 A 是 100% 正确的，因为仅仅因为不想选择相邻节点而使用 E 是错误的。通过这个算法你会发现答案是A和B，只要检查一下你也可以找到它。假设这涵盖：

C D A = 15
C D E = 1006
A B = 12

虽然前两个答案没有相邻节点，但它们比最后一个有相邻节点的答案大。所以最好用A和B进行掩护。