使用動態規劃尋找最小邊緣覆蓋的有效方法

Question

給定一個無自循環和平行邊的無向圖。

我的目標是找到minimum edge cover。我開始知道使用bitmask DP可以有效地完成。我嘗試了很多，但無法弄清楚如何定義state of DP。請幫助決定DP狀態。

Answer 1

我沒有實現使用位掩碼，我的動態規劃方法有2個狀態 -

dp[u][hashGuard] // curerntly in u node, this depicts minimum guards required for rest of the nodes encountered later 

轉換功能 -

// In node u, we have no guards, so we must have to put guards on adjacent nodes 
dp[u][0] += dp[v][1] for all adjacent nodes v from u 

// In current node u, we have guard. So we can try to minimize the number of guards by puting guards on adjacent nodes or by not putting 
dp[u][1] += min(dp[v][1], dp[v][0]) for all adjacent nodes v from u 

這裏是我的C++實現 -

// Assuming the graph is a tree. you can transform it for graph by using a visited flag instead of parent array 
#define MAX 100001 

int dp[MAX << 2][2]; 
int parent[MAX]; 
vector <int> adj[MAX]; 

int minVertexCover(int node, bool hasGuard) { 

    if((int)adj[node].size() == 0) return 0; 
    if(dp[node][hasGuard] != -1) return dp[node][hasGuard]; 

    int sum = 0; 
    for(int i = 0; i < (int)adj[node].size(); i++) { 
     int v = adj[node][i]; 
     if(v != parent[node]) { 
      parent[v] = node; 
      if(!hasGuard) { 
       sum += minVertexCover(v, true); 
      } else { 
       sum += min(minVertexCover(v, false), minVertexCover(v, true)); 
      } 
     } 
    } 
    return dp[node][hasGuard] = sum + hasGuard; 
} 

/* 
usage: 
// graph input 
// if node 1 and node 2 connected, then 
// adj[2].push_back(1); 
// adj[1].push_back(2) 

result = min(minVertexCover(1, false), minVertexCover(1, true)); 
if(n > 1) 
    printf("%d\n", result); 
else 
    printf("1\n"); 
*/