1

过去通过网站上的快速搜索，已经有很多关于这个主题的帖子，其中许多都使用了这种动态编程重复：

C(x) = min(1 + sum (C(i) for i in x's children), len(x's children) + sum(C(i) for i in x's sunchildren))

假设树以节点 1 为根，我对节点链 1-2-3-4-5-6 尝试了此算法，以获得以下 C(i)：

| C(1) | C(2) | C(3) | C(4) | C(5) | C(6) |

| 3 | 2 | 2 | 1 | 1 | 1 |

但是，C(1) 的正确答案应该是 2，这是通过标记节点 2 和 5 来实现的。

我决定尝试我自己的方法，详情如下：

int solve(int curr, int height){
    if(dp[curr][height] > -1) return dp[curr][height];
    if(int(children[curr].size()) == 0) return dp[curr][height] = height > 1 ? 1 : 0;
    if(height == 3){
        int ret = 1;
        for(int i = 0; i < int(children[curr].size()); i++){
            int next = children[curr][i];
            ret += solve(next, 1);
        }
        return dp[curr][height] = ret;
    }
    int ret1 = 0; int ret2 = 1;
    if(height == 2){
        for(int i = 0; i < int(children[curr].size()); i++){
            int next = children[curr][i];
            ret1 += solve(next, 3); ret2 += solve(next, 1);
        }
        return dp[curr][height] = min(ret1, ret2);
    }
    for(int i = 0; i < int(children[curr].size()); i++){
        int next = children[curr][i];
        ret1 += solve(next, 2); ret2 += solve(next, 1);
    }
    return dp[curr][height] = min(ret1, ret2);
}

curr是我们所在的当前节点，height是距其上方最近的标记节点的距离。这个想法是，一旦节点的高度 = 3，就必须在该特定路径中标记它。否则，我们现在可以跳过标记它。一个例外是叶子节点，如果没有标记相邻节点，则必须标记它。

有人可以验证我的方法的有效性，并解释为什么第一个算法未能通过链测试吗？

提前致谢！

4

1 回答 1

1

第一个算法确实有效。在最小顶点覆盖中，每条边都必须与至少一个顶点相关。在您的“反例”中，顶点 3 和 4 均未标记，因此边 (3,4) 在集合中没有入射顶点。所以 {2, 5} 不是顶点覆盖。

你的方法根本行不通。首先，我认为您仍然使用错误的最小顶点覆盖定义。我猜，你认为，每个顶点都必须被一个边缘事件触及到一个标记的顶点。

即使你使用了错误的定义，你的方法也行不通。与标记的父顶点距离为 3 的顶点不必标记。看这个例子：

  0
  |
  1
  |
  2
 / \
3   4
    |
    5

在这个例子中，如果顶点 0 被标记，那么顶点 3 和 4 也会被标记，因为它们距顶部的距离为 3。但是没有必要标记顶点 4，相反我们也可以标记顶点 5。显然，这将在此示例中给出相同数量的顶点，但我相信您可以将其扩展到更大的示例，您的方法会失败。

不同定义的解决思路：

我相信贪婪的解决方案是有效的。（还有一个最小顶点覆盖的贪心算法）。从叶子开始向上到中心。只标记需要标记的节点。

您可以使用深度优先搜索和 DP 再次执行此操作。令 dp[v] 为 v 与 v 的子树中标记节点之间的最短距离。要计算 v，首先计算子节点的所有 dp 值，然后决定是否需要标记它。如果任何孩子的 dp[child] = 2，那么您需要标记 v 并将 dp[v] = 0。否则您不必标记它并且 dp[v] = min(dp[children] + 1) . 最后，您可能还需要标记根节点。

注意：我没有测试过这个。

于 2017-07-08T22:21:02.100 回答