樹的最小尺寸頂點覆蓋：動態規劃配方

我想了解如何制定一個樹的最小尺寸頂點覆蓋作爲動態規劃問題，並遇到一些麻煩的問題。對我來說，涉及深度優先搜索的非動態規劃公式會產生最直觀的意義。基本上，這涉及到爲葉節點（包括其最小尺寸頂點封面中的父節點）執行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

樹的最小尺寸頂點覆蓋：動態規劃配方

回答

相關問題