Какой хороший алгоритм для получения минимального вершинного покрытия дерева?

Ответ 1

Я надеюсь, что здесь вы можете найти более близкий ответ на свой вопрос.

Я думал о своем решении, возможно, вам нужно будет отполировать его, но пока динамическое программирование находится в одном из ваших тегов, вам, вероятно, нужно:

• Для каждой u-вершины S + (u) размер крышки с вершинами u и S- (u) крышка без вершины u.
• S + (u) = 1 + Sum (S- (v)) для каждого дочернего v из u.
• S- (u) = Sum (max {S- (v), S + (v)}) для каждого дочернего v из u.
• Ответ max (S + (r), S- (r)), где r - корень вашего дерева.

После прочтения этого. Изменен алгоритм выше, чтобы найти максимальный независимый набор, поскольку в статье wiki указано

Множество является независимым тогда и только тогда, когда его дополнение является вершинным накрытием.

Таким образом, изменяя min на max, мы можем найти максимальное независимое множество и дополнять минимальное покрытие вершин, так как обе задачи эквивалентны.

Ответ 2

T (V, E) - дерево, из которого следует, что для любого листа любое минимальное покрытие вершин должно включать либо лист, либо вершину, смежную с листом. Это дает нам следующий алгоритм нахождения S: покрытие вершины:

• Найти все листья дерева (BFS или DFS), O (| V |) в дереве.
• Если (u, v) - ребро такое, что v является листом, добавьте u к вершинному покрытию и обрезаем (u, v). Это оставит вас с лесом T_1 (V_1, E_1),..., T_n (U_n, V_n).
• Теперь, если V_i = {v}, что означает | V_i | = 1, то это дерево можно отбросить, поскольку все ребра, инцидентные v, покрываются. Это означает, что у нас есть условие завершения для рекурсии, где у нас есть одна или никакие вершины, и мы можем вычислить S_i как обложку для каждого T_i и определить S, поскольку все вершины шага 2 объединяют обложку каждого T_i.

Теперь остается только проверить, что если исходное дерево имеет только одну вершину, мы возвращаем 1 и никогда не начинаем рекурсию, и можно вычислить минимальное покрытие вершин.

Edit:

На самом деле, немного подумав об этом, его можно выполнить с помощью простого варианта DFS.

Ответ 3

Я не совсем понял после прочтения ответов здесь, поэтому я подумал, что отправлю сообщение из здесь

Общая идея заключается в том, что вы создаете дерево на произвольном node и спрашиваете, находится ли этот корень в обложке или нет. Если это так, то вы вычисляете минимальное покрытие вершин поддеревьев, укорененных на своих дочерних элементах, путем рекурсии. Если это не так, то каждый ребенок корня должен находиться в крышке вершины, чтобы покрыть каждое ребро между корнем и его дочерними элементами. В этом случае вы возвращаетесь к корням внуков.

Так, например, если у вас было следующее дерево:

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

Обратите внимание, что при проверке вы знаете, что минимальная крышка вершины {B, C}. Мы найдем эту минимальную обложку.

Здесь мы начинаем с A.

A находится в обложке

Мы переходим к двум поддеревьям B и C и рекурсируем по этому алгоритму. Мы не можем просто заявить, что B и C не находятся в обложке, потому что даже если AB и AC покрыты, мы ничего не можем сказать о том, нужны ли нам B и C быть в обложке или нет.

(Подумайте о следующем дереве, где и корень, и один из его дочерних элементов находятся в обложке min ({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 children ),                    // root in cover
            len(x children) + sum( C(i) for i in x grandchildren)  // root not in cover
            )

Ответ 4

{- Haskell implementation of Artem 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)

Ответ 5

Мы можем использовать алгоритм, основанный на 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;
           }
        }
   }
}

Лист node никогда не будет выбран для крышки вершин.

Ответ 6

Я бы просто использовал линейную программу для решения проблемы минимального покрытия вершин. Формула как целочисленная линейная программа может выглядеть так, как показано здесь: формулировка ILP

Я не думаю, что ваша собственная реализация была бы быстрее, чем эти высоко оптимизированные решатели LP.

Ответ 7

Нам нужно найти минимальное покрытие вершин для каждого node, которое мы должны выбрать, чтобы включить его или нет, чтобы включить его. Но в соответствии с проблемой для каждого ребра (u, v) в обложке должно быть либо "u", либо "v", поэтому нам нужно позаботиться о том, чтобы, если текущая вершина не включена, мы должны включить ее дочерние элементы и если мы включаем текущую вершину, то мы можем или не можем включать своих детей на основе оптимального решения.

Здесь DP1 [v] для любой вершины v = Когда мы ее включаем. DP2 [v] для любой вершины v =, когда мы ее не включаем.

DP1 [v] = 1 + sum (min (DP2 [c], DP1 [c])) - это означает включение тока и может включать или не включать его детей на основе оптимального.

DP2 [v] = sum (DP1 [c]) - это означает, что не включает ток, тогда нам нужно включить дочерние элементы текущей вершины. Здесь c - дочерний элемент вершины 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;
}