一棵树的最小重量顶点覆盖率 [英] minimum weight vertex cover of a tree

问题描述

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

There's an existing question dealing with trees where the weight of a vertex is its degree, but I'm interested in the case where the vertices can have arbitrary weights.

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

This isn't homework but it is one of the questions in the algorithm design manual, which I'm currently reading; an answer set gives the solution as

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] =儿童c的总和(v)Score [c] [true]和Score [v] [true] = w _v +儿童c的总和(v )的min(Score [c] [true]; Score [c] [false])
4. 通过回溯得分来提取实际掩护.

1. Perform a DFS, at each step update Score[v][include], where v is a vertex and include is either true or false;
2. If v is a leaf, set Score[v][false] = 0, Score[v][true] = w_v, where w_v is the weight of vertex v.
3. During DFS, when moving up from the last child of the node v, update Score[v][include]: Score[v][false] = Sum for c in children(v) of Score[c][true] and Score[v][true] = w_v + Sum for c in children(v) of min(Score[c][true]; Score[c][false])
4. Extract actual cover by backtracking Score.

但是，我实际上无法将其转换为有用的. (作为对评论的回应:到目前为止，我一直在尝试绘制一些带有权重的小图形，并在纸上遍历该算法，直到第四步为止，在该步骤中，提取实际封面"部分并不透明.)

However, I can't actually translate that into something that works. (In response to the comment: what I've tried so far is drawing some smallish graphs with weights and running through the algorithm on paper, up until step four, where the "extract actual cover" part is not transparent.)

作为对阿里的回答:因此，假设我有这张图，其顶点由A等给出，并且权重在以下位置以括号为单位:

In response Ali's answer: So suppose I have this graph, with the vertices given by A etc. and the weights in parens after:

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

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

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

通过此算法，我们将像这样设置值:

Going through this algorithm, we'd set values like so:

• 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[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}，并且它们是相邻的.也许不应该让人感到困惑，但是坦率地说，我很困惑.

Ok, so, my question is basically, now what? Doing the simple thing and iterating through the score vector and deciding what's cheapest locally doesn't work; you only end up including B. Deciding based on the parent and alternating also doesn't work: consider the case where the weight of E is 1000; now the correct answer is {A,B}, and they're adjacent. Perhaps it is not supposed to be confusing, but frankly, I'm confused.

推荐答案

没有完成(或需要)实际的回溯.该解决方案使用动态编程来避免回溯，因为这将花费大量时间.我的猜测是回溯得分"，这意味着分数"包含您通过回溯可以获得的部分结果.

There's no actual backtracking done (or needed). The solution uses dynamic programming to avoid backtracking, since that'd take exponential time. My guess is "backtracking Score" means the Score contains the partial results you would get by doing backtracking.

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

The cover vertex of a tree allows to include alternated and adjacent vertices. It does not allow to exclude two adjacent vertices, because it must contain all of the edges.

答案以递归计算得分的方式给出.不包含顶点的成本就是包含其子级的成本.但是，包含顶点的成本要便宜得多，因为包含两个子元素都是允许的，所以包含或不包含子元素的成本也较低.

The answer is given in the way the Score is recursively calculated. The cost of not including a vertex, is the cost of including its children. However, the cost of including a vertex is whatever is less costly, the cost of including its children or not including them, because both things are allowed.

正如您的解决方案所建议的那样，可以使用DFS一次完成一次订购.诀窍是，如果Score指出必须包含一个顶点，则包括一个顶点，如果必须排除它，则包括其子对象，否则我们将排除两个相邻的顶点.

As your solution suggests, it can be done with DFS in post-order, in a single pass. The trick is to include a vertex if the Score says it must be included, and include its children if it must be excluded, otherwise we'd be excluding two adjacent vertices.

这是一些伪代码:

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

这篇关于一棵树的最小重量顶点覆盖率的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！