最小頂點覆蓋
最小頂點覆蓋是一個經典的圖形問題。比方說，在一個城市，我們有幾條連線幾個點的道路。讓我們使用邊和使用節點的點來表示道路。我們來看兩個示例圖：
https://i.stack.imgur.com/7n7bv.jpg
我們想在某些方面設定守望者。守望者可以保護連線到該點的所有道路。問題是，覆蓋所有道路所需的最小守望人員是多少？如果我們在節點 A ， B ， H ， I 和 J 設定守望者，我們可以覆蓋所有道路。
https://i.stack.imgur.com/ADM8O.jpg
這是我們的最佳解決方案。我們至少需要 5 名守望者才能守護整個城市。怎麼判斷這個？
首先，我們需要理解這是一個 NP 難問題，即問題沒有多項式時間解決方案。但是如果圖形是樹，那意味著如果它有 （n-1）個節點，其中 n 是邊數，並且圖中沒有迴圈，我們可以使用動態程式設計來解決它。
https://i.stack.imgur.com/YvGHM.jpg
要構建 DP 解決方案，我們需要遵循兩個策略：
- 如果節點中沒有守望者，則連線到它的所有節點都必須有守望者，否則所有道路都不會被覆蓋。如果 U 和 v 連線和 U 沒有任何守望者，那麼 v 必須有一個守望者。
- 如果節點中有守望者，則與其連線的不同節點可能有也可能沒有守望者。這意味著沒有必要有一個守望者，但它可能是有益的。如果 U 和 v 連線和 U 有守望，我們會檢查，發現其上是對我們有利的：
- 在 v 。中設定守望者
- 不在 v 中設定守望者。
讓我們定義一個遞迴函式，其中 state 是我們當前的節點，是否有守望者。這裡：
F(u,1) = Currently we're in 'u' node and there is a watchman in this node.
F(u,0) = Currently we're in 'u' node and there is no watchman in this node.
該函式將返回剩餘節點中的守望者數量。
我們來看一個示例樹：
https://i.stack.imgur.com/rka2p.jpg
我們可以很容易地說，如果我們不把守望者放在節點 A 上，我們就必須把守望者放在節點 B ， C 和 D 上。我們可以推斷：
F(A,0) = F(B,1) + F(C,1) + F(D,1) + 0
如果我們不將守望者放在節點 **A 中，**它會返回所需的守望人數。我們最後新增了 0 ，因為我們沒有在當前節點中設定任何守望者。
現在 F(A,1) 意味著，我們在節點 A 中設定了守望者。為此，我們可以在所有連線的節點中設定看門人，也可以不設定。我們將為我們提供最少數量的守望者。
F(A,1) = min(F(B,0), F(B,1) + min(F(C,0), F(C,1)) + min(F(D,0), F(D,1)) + 1
我們通過設定而不是在每個節點上設定守望者並獲取最佳值來檢查。
我們必須要注意的一件事是，一旦我們進入子節點，我們將永遠不會回顧父節點。從上面的例子中，我們去 B 從A，因此父[B] = A。因此，我們將不會再回到一個從B。
為了確定基本情況，我們可以注意到，如果從一個節點，我們不能去任何其他新節點，如果我們當前節點中有一個守望者，我們將返回 **1，**如果我們當前沒有守望者，則返回 0 節點。
最好有一個樹的鄰接列表。讓列表用 edge 表示。我們將有一個陣列 dp [n] [2] ，其中 n 表示儲存計算值的節點數，並用 -1 初始化它。我們還將有一個 parent [n] 陣列來表示節點之間的父子關係。我們的虛擬碼看起來像：
Procedure f(u, isGuarded):
if edge[u].size is equal to 0 //node doesn't have any new edge
Return isGuarded
else if dp[u][isGuarded] is not equal to -1 //already calculated
Return dp[u][isGuarded]
end if
sum := 0
for i from i to edge[u].size
v := edge[u][i]
if v is not equal to parent[u] //not a parent
parent[v] := u
if isGuarded equals to 0 //not guarded, must set a watchman
sum := sum + f(v,1)
else //guarded, check both
sum := sum + min(f(v,1), f(v,0)
end if
end if
end for
dp[u][isGuarded] := sum + isGuarded
Return dp[u][isGuarded]
如果我們將節點 A 表示為 root，我們將通過：min(f(A,1), f(A,0)) 呼叫該函式。這意味著我們還將檢查在根節點中設定 watchman 是否最佳。這是我們的 DP 解決方案。使用最大匹配演算法或 max-flow 也可以解決此問題。