트리의 최소 정점 덮개를 얻기위한 좋은 알고리즘은 무엇입니까?

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

문제

트리의 최소 정점 덮개를 얻기위한 좋은 알고리즘은 무엇입니까?

입력:

노드의 이웃.

산출:

정점의 최소 수.

도움이 되었습니까?

해결책

나는 희망 여기 질문에 대한 관련 답변을 더 찾을 수 있습니다.

나는 내 솔루션에 대해 생각하고 있었는데 아마도 당신은 그것을 연마해야 할 것입니다. 그러나 동적 프로그래밍이 당신의 태그 중 하나에있는 한 : 아마도 다음과 같습니다.

  1. 각각의 u vertex define s+(u)는 vertex u가없는 vertex u 및 s- (u) 덮개를 갖는 커버 크기입니다.
  2. u의 각 자식 V에 대한 s + (u) = 1 + sum (s- (v)).
  3. s- (u) = sum (u의 각 자식 V에 대한 sum (max {s- (v), s+(v)}).
  4. 대답은 최대 (s+(r), s- (r))입니다. 여기서 r은 나무의 뿌리입니다.

읽고 나서 이것. 위키 기사에서 언급 한 이후 최대 독립 세트를 찾도록 위의 알고리즘을 변경했습니다.

보완이 정점 덮개 인 경우에만 세트가 독립적입니다.

따라서 최소를 최대로 바꾸면 최대 독립 세트를 찾을 수 있으며 최소 정점 덮개를 칭찬 할 수 있습니다. 두 문제는 모두 동일하기 때문입니다.

다른 팁

T (v, e)는 나무이며, 이는 임의의 잎에 대해 최소 정점 덮개는 잎 또는 잎에 인접한 잎사귀를 포함해야 함을 의미합니다. 이것은 우리에게 다음과 같은 알고리즘을 찾아야합니다.

  1. 나무에서 나무의 모든 잎 (bfs 또는 dfs), o (| v |)를 나무에서 찾으십시오.
  2. 경우 (u, v)가 v가 잎이되는 가장자리 인 경우, u를 정점 덮개에 추가하고 자두 (u, v). 이것은 숲 t_1 (v_1, e_1), ..., t_n (u_n, v_n)을 남길 것입니다.
  3. 이제 v_i = {v} 인 경우 | v_i | = 1을 의미하면 V의 모든 모서리가 덮여 있으므로 트리를 떨어 뜨릴 수 있습니다. 이것은 우리가 재귀를위한 종료 조건이 있고, 여기서 정점이 없거나 전혀없고, 우리는 계산할 수 있음을 의미합니다. 시 각각의 표지로 t_i, 그리고 2 단계의 모든 정점으로서 s를 각각의 표지로 정의하십시오. t_i.

이제 원래 트리에 vertex가 하나만 있으면 1을 반환하고 재귀를 시작하지 않으며 최소 정점 덮개를 계산할 수 있는지 확인하는 것이 남아 있습니다.

편집하다:

실제로, 그것에 대해 조금 생각한 후에는 간단한 DFS 변형으로 달성 할 수 있습니다.

여기서 답을 읽은 후에 완전히 이해하지 못했기 때문에 하나를 게시 할 것이라고 생각했습니다. 여기

일반적인 아이디어는 임의의 노드에 나무를 뿌리며 그 루트가 덮개에 있는지 여부를 묻습니다. 그것이 있다면, 당신은 재발함으로써 어린이들에게 뿌리를 둔 하위 트리의 최소 정점 덮개를 계산합니다. 그렇지 않은 경우, 뿌리의 모든 어린이는 뿌리와 어린이 사이의 모든 가장자리가 덮여 있도록 정점 덮개에 있어야합니다. 이 경우, 당신은 뿌리의 손자를 되풀이합니다.

예를 들어, 다음 나무가있는 경우 :

    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;
           }
        }
   }
}

vertex 커버에 대해서는 리프 노드가 선택되지 않습니다.

우리는 그것을 포함 시키거나 포함시키지 않기 위해 선택해야 할 각 노드에 대한 최소 정점 덮개를 찾아야합니다. 그러나 각 모서리 (U, V)에 대한 문제에 따르면, 'U'또는 'V'중 하나는 덮개에 있어야하므로 현재 정점에 포함되지 않으면 자녀를 포함시키고 포함해야합니다. 우리가 현재 정점을 포함하고 있다면, 우리는 최적의 솔루션을 기반으로 자녀를 포함 시키거나 포함하지 않을 수 있습니다.

여기서는 vertex v =를 포함시킬 경우 dp1 [v]. Vertex v =에 대한 dp2 [v].

dp1 [v] = 1 + sum (min (dp2 [c], dp1 [c]) - 이것은 전류를 포함하며 최적의 내용에 따라 어린이를 포함하거나 포함하지 않을 수 있습니다.

dp2 [v] = sum (dp1 [c]) - 이것은 전류를 포함하지 않으면 현재 정점의 어린이를 포함해야한다는 것을 의미합니다. 여기서 C는 vertex v의 자녀입니다.

그런 다음 우리의 솔루션은 Min (dp1 [root], dp2 [root]입니다.

#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