什么是一个很好的算法为获得最低顶盖的一棵树?

StackOverflow https://stackoverflow.com/questions/926847

题

什么是一个很好的算法为获得最低顶盖的一棵树?

输入：

节点的邻国。

输出：

最低数量的顶点。

有帮助吗？

解决方案

我的希望 在这里， 你可以找到更多的相关回答你的问题。

我想我的解决方案，也许你会需要以波兰语，但只要动态程序是在你的一个标签的你可能需要：

  1. 每个u顶点的定义S+(u) 盖子大小的顶点u和S-(u) 盖子没有顶点。
  2. S+(u)=1+Sum(S-(v))对于每个儿童v u.
  3. S-(u)=Sum(max{S-(v)、S+(v)})对于每个儿童v u.
  4. 答案是max(S+(r)，S-(r))，其中r为根的树。

在阅读 此.改变上述算法找到的最大的独立设置的，因为在维基的文章说

一组是独立的，如果并且只有如果其补充是一个顶点盖。

因此，通过改变分钟max我们可以找到的最大独立和通过的恭维的最小的顶点盖，因为这两个问题都是等同的。

其他提示

T(V)是一棵树，这意味着，对于任何叶，任何最小的顶点盖了以包括叶片或顶点相邻的叶子。这为我们提供了下列算法找到S的顶盖：

  1. 找到所有的树叶中的树(BFS或DFS),O(|V|)，在一棵树。
  2. 如果(u)是一个边缘例v叶，加u到顶点的涵盖和修剪(u,v)。这将留下一个森林T_1(V_1,E_1),...,T_n(u_n_的,V_n).
  3. 现在，如果是v_i={v}，这意味|是v_i|=1，则那棵树可以删除，因为所有的边缘射入v都包括在内。这意味着，我们有一个终止的条件递归，这里我们有一个或不折点，我们可以计算 S_i 作为复盖为每 T_i, 和定义S作为所有的顶点，从第2步联盟盖的每 T_i.

现在，所有这一切仍然是验证，如果原来的树上只有一个顶点，我们返回1和永远不会开始递归，和最低限度的顶点盖可以被计算的。

编辑：

实际上，之后考虑这一点，可以通过一个简单的外勤部的变型。

我没有完全阅读这里的答案后才明白，所以我想我会发布一个从的此处

总的想法是，你根树在任意的节点，并要求根是否是在盖或没有。如果是的话，你算算通过递归在其子根的子树的分顶点覆盖。如果不是，那么根本的每个孩子都必须在顶点覆盖，使得该根源及其子之间的每个边缘被覆盖。在这种情况下，你递归根的孙子。

因此，举例来说，如果你有以下三种：

    A
   / \
  B   C
 / \ / \
D  E F  G

请注意，通过检查，你知道最小顶点覆盖是{B, C}。我们会发现这个分盖。

下面我们先从A。

A是在盖

我们向下移动到B和C，和递归的该算法的两个子树。我们不能简单地指出B和C不是盖的，因为即使AB和AC都包括在内，我们不能说我们是否需要B和C是在盖或没有什么。

（想一想下面的树，其中，所述根和它的一个子两者在分盖（{A, D}）

  A
 /|\___
B C    D
      /|\
     E F G

）

A不是在盖

但我们知道，AB和AC必须被覆盖，所以我们要B和C添加到封。由于B和C都在封面上，我们可以递归自己的孩子，而不是递归的B和C（即使我们这样做，它不会给我们任何详细信息）。

“正式”

让C(x)是分钟盖在x根的大小。

然后，

C(x) = min ( 
            1 + sum ( C(i) for i in x's children ),                    // root in cover
            len(x's children) + sum( C(i) for i in x's grandchildren)  // root not in cover
            )

{- Haskell implementation of Artem's algorithm -}

data Tree = Branch [Tree]
    deriving Show

{- first int is the min cover; second int is the min cover that includes the root -}
minVC :: Tree -> (Int, Int)
minVC (Branch subtrees) = let
    costs = map minVC subtrees
    minWithRoot = 1 + sum (map fst costs) in
    (min minWithRoot (sum (map snd costs)), minWithRoot)

我们可以使用基于DFS算法来解决此问题：

DFS(node x)
{

    discovered[x] = true;

    /* Scan the Adjacency list for the node x*/
    while((y = getNextAdj() != NULL)
    {

        if(discovered[y] == false)
        {

            DFS(y);

           /* y is the child of node x*/
           /* If child is not selected as a vertex for minimum selected cover
            then select the parent */ 
           if(y->isSelected == false)
           {
               x->isSelected = true;
           }
        }
   }
}

在叶节点将永远不会被选定为顶点覆盖。

我们需要找到我们需要的选择，使每个节点的最低点覆盖，无论是包括或不包括它。但是，根据每个边的问题（U，V），无论是“U”或“V”的，应在封面，所以我们需要照顾，如果不包括当前顶点那么我们就应该包括它的孩子，如果我们包括当前顶点然后，我们可以或可以不包括基于最优解它的子

下面，DP1 [V]为任何顶点v =当我们包括它。 DP2 [V]为任何顶点v =当我们不包括它。

DP1 [V] = 1个+ SUM（分钟（DP2并[c]，DP1并[c]）） - 。该装置包括电流，并且可以或可以不包括它的孩子，基于什么是最佳的

DP2 [V] =总和（DP1 [C]） - 这意味着不包括当前然后我们需要包括当前顶点的孩子。在这里，c是顶点v的孩子。

然后，我们的解决方案是min（DP1 [根]，DP2 [根]）

#include <bits/stdc++.h>
using namespace std;

vector<vector<int> > g;

int dp1[100010], dp2[100010];

void dfs(int curr, int p){
    for(auto it : g[curr]){
        if(it == p){
            continue;
        }
        dfs(it, curr);
        dp1[curr] += min(dp1[it], dp2[it]);
        dp2[curr] += dp1[it];
    }
    dp1[curr] += 1;
}

int main(){
    int n;
    cin >> n;
    g.resize(n+1);
    for(int i=0 ; i<n-1 ; i++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    dfs(1, 0);
    cout << min(dp1[1], dp2[1]);
    return 0;
}

我会简单地使用一个线性程序来解决最小顶点覆盖问题。 的制剂作为一个整数线性规划可能看起来像这里给出的一个： ILP制剂

我不认为自己的实现会比这些高度优化的LP求解器更快。

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top