5

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

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

  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] = Sum for c in children(v) of Score[c][true] and Score [v][true] = w v + 子项中 c 的总和 (v) of min(Score[c][true]; Score[c][false])
  4. 通过回溯分数提取实际覆盖。

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

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

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}，并且它们是相邻的。也许这不应该令人困惑，但坦率地说，我很困惑。

4

2 回答 2

3

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

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

答案以递归计算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
于 2019-10-08T04:40:59.117 回答
2

它实际上并不意味着任何令人困惑的事情，它只是动态编程，您似乎几乎了解所有算法。如果我想让它更清楚，我不得不说：

  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做掩护。

于 2014-12-17T07:00:59.483 回答