树的最小尺寸顶点覆盖：动态规划配方

我想了解如何制定一个树的最小尺寸顶点覆盖作为动态规划问题，并遇到一些麻烦的问题。对我来说，涉及深度优先搜索的非动态规划公式会产生最直观的意义。基本上，这涉及到为叶节点（包括其最小尺寸顶点封面中的父节点）执行DFS，并重复执行根目录。伪代码是这样的：树的最小尺寸顶点覆盖：动态规划配方

// DFS based solution 
find_minimum_vertex_cover_dfs(root) { 
    // leaf nodes aren't in minimum size vertex cover 
    if (root == NULL || isLeafNode(root)) { 
     return; 
    } 

    for (each child node of root) { 
     find_minimum_vertex_cover_dfs(child node); 
     // child isn't in minimum size vertex cover so need to cover edge 
     // from current root to child by including current root 
     if (!isInMinCover(child node)) { 
      include root in minimum vertex cover; 
     } 
    } 
}

动态规划制定，我从here得到如下：

DynamicVC(root): 
    for each child c: 
     Best[c][0], Best[c][1] = DynamicVC(c) 

    withoutRoot = sum over all c of Best[c][1] 
    withRoot = 1 + sum over all c of min(Best[c][0], Best[c][1]) 

    return (withoutRoot, withRoot)

我想我明白了子问题是计算的最小尺寸顶点覆盖的想法在每个顶点处植入的子树包括封面中的该顶点，并且将该顶点从封面中排除。我有两个问题：

对我来说，利用叶节点永远不会处于最小顶点覆盖并因此使用基于DFS的解决方案这一事实似乎是最自然的。为什么会使用动态编程解决方案解决这个问题？
我习惯于从下往上迭代地构建动态编程矩阵，而没有实际使用递归。然而，在这种情况下，因为我需要首先计算叶子节点的解决方案，使用递归从树叶节点构建动态编程矩阵，这对我来说似乎是最直观的。对我来说，这似乎很奇怪，因为我所做过的所有动态编程问题都避免了这一点。我在这里错过了什么吗？

编辑：当我想到它时，可能会让我感到困惑的是，在这种情况下，递归地在树上做DFS是我更熟悉的。我一直在做一些动态编程问题，但这是第一个涉及树/图遍历的问题，在其他问题中，我可以使用一些循环来计算更大和更大的子问题。我想我可以通过使用一个显式堆栈并以这种方式进行树遍历而不是通过递归来使动态编程版本更加熟悉。那有意义吗？

来源

2016-08-24 Mike Sweeney

1：没有真正充分的理由。它只是起作用，所以为什么不使用它。对我来说，你展示的DP解决方案比递归更直观。

2：动态规划是关于子问题的递归解决方案的记忆。使用DP算法通常需要先定义一个递归，然后向其添加记忆。递归解决方案可以自动转换为DP：只需创建类型为(subproblem id -> result)的全局散列表，并在递归调用开始时检查散列映射是否已经包含给定子问题的结果，如果是，则立即返回，否则计算它并将其放入哈希映射中。这种方法通常会像您提到的自下而上的方法一样快。

来源

2016-08-24 09:43:36 piotrekg2

树的最小尺寸顶点覆盖：动态规划配方

回答

相关问题