Che cosa è un buon algoritmo per ottenere la copertura minima vertice di un albero?

Question

Che cosa è un buon algoritmo per ottenere la copertura minima vertice di un albero?

INPUT:

i vicini del nodo.

USCITA:

Il numero minimo di vertici.

Answer 1

Spero qui si possono trovare risposta più legati alla tua domanda.

---

stavo pensando a mia soluzione, probabilmente sarà necessario lucidarlo, ma di programmazione finché dinamica è in uno dei tag probabilmente è necessario:

1. Per ogni u vertice definire S + (u) è coprire dimensioni con vertice u e S- (u) coprire senza vertice u.
2. S + (u) = 1 + Sum (S- (v)) per ciascun figlio contro di u.
3. S- (u) = Sum (max {S (v), S + (v)}) per ciascun figlio contro di u.
4. La risposta è massima (S + (r), S (r)) dove r è la radice del vostro albero.

---

Dopo aver letto questo . Cambiato l'algoritmo sopra per trovare insieme la massima indipendenti, dal momento che in un articolo wiki dichiarato

  

Un insieme è indipendente se e solo se il suo complemento è una copertura vertice.

Quindi, cambiando minimo al massimo possiamo trovare l'insieme indipendente massimo e dal complimento la copertura minima vertice, dal momento che entrambi sono equivalenti problema.

Answer 2

T (V, E) è un albero, che implica che per ogni foglio, ogni copertura dei vertici minima deve includere sia la foglia o il vertice adiacente alla foglia. Questo ci dà il seguente algoritmo per trovare S, la copertura dei vertici:

1. Trova tutte le foglie dell'albero (BFS o DFS), O (| V |) in un albero
.
2. Se (u, v) è un vantaggio tale che v è una foglia, aggiungere u per la copertura dei vertici, e potare (u, v). Questo vi lascerà con un T_1 foresta (V_1, E_1), ..., T_n (U_n, V_n).
3. Ora, se V_i = {v} significato | V_i | = 1, allora questo albero può essere eliminato in quanto tutti i bordi incidente su v sono coperti. Questo significa che abbiamo una condizione di terminazione per una ricorsione, dove abbiamo uno o nessun vertici, e siamo in grado di calcolare S_i come copertina per ogni t_i , e definire S come tutti i vertici dal punto 2 unione copertina di ogni t_i .

Ora, tutto ciò che rimane è quello di verificare che se l'albero originale ha un solo vertice, abbiamo ritornare 1 e mai iniziare la ricorsione, e la copertura dei vertici minima può essere calcolato.

Modifica

In realtà, dopo averci pensato per un po ', può essere realizzato con una semplice variante DFS.

Answer 3

Non ho capito pienamente dopo aver letto le risposte qui, quindi ho pensato di postare uno da qui

L'idea generale è che si sradicare l'albero in un nodo arbitrario, e chiedere se tale radice è nella copertura o non. Se lo è, allora si calcola la copertura min vertici delle sottostrutture radicate nei suoi figli recursing. Se non lo è, allora ogni figlio della radice deve essere nella copertura dei vertici in modo che ogni bordo tra la radice ed i suoi figli è coperto. In questo caso, si ricorsioni nipoti del root.

Così, per esempio, se si ha la seguente struttura:

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

Si noti che mediante ispezione, si conosce il coperchio min vertice è {B, C}. Troveremo questo min coperchio.

Qui si parte con A.

A è nel coperchio

Ci spostiamo verso il basso per le due sottostrutture di B e C, e recurse su questo algoritmo. Non possiamo semplicemente affermare che B e C non sono nella copertura, perché anche se AB e AC sono coperti, non possiamo dire nulla sul fatto che avremo bisogno B e C di essere in copertura o non.

(Pensate alla seguente albero, dove sia la radice e uno dei suoi figli sono nel coperchio min ({A, D})

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

)

A non è nella copertura

Ma sappiamo che AB e AC devono essere coperti, quindi dobbiamo aggiungere B e C al coperchio. Dal momento che B e C sono nel coperchio, possiamo recurse sui loro figli, invece di recursing su B e C (anche se abbiamo fatto, non sarebbe darci più informazioni).

"Formalmente"

Sia C(x) essere la dimensione della copertura min radice in x.

Poi,

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
            )

Answer 4

{- 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)

Answer 5

Possiamo usare un algoritmo basato DFS per risolvere questo problema:

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

Il nodo foglia non verrà mai selezionata per la copertura dei vertici.

Answer 6

Abbiamo bisogno di trovare la copertura minima vertice per ogni nodo che dobbiamo scelte da fare, sia per includere o non includere esso. Ma secondo il problema per ogni arco (u, v), uno dei 'u' o 'v' dovrebbe essere nel coperchio così abbiamo bisogno di fare in modo che, se il vertice corrente non è incluso quindi dovremmo includere i suoi figli, e se siamo tra cui il vertice corrente, allora, si può o non può includere i suoi figli sulla base di soluzione ottimale.

Qui, DP1 [v] per qualsiasi vertice v = Quando includerlo. DP2 [v] per qualsiasi vertice v = quando non lo si includa.

DP1 [v] = 1 + sum (min (DP2 [c], DP1 [c])) -. Questo mezzo includono corrente e può o non può includere i suoi figli, in base a ciò che è ottimale

DP2 [v] = somma (DP1 [c]) - questo significa che non compresa la corrente quindi abbiamo bisogno di includere i bambini di vertice corrente. Qui, c è il figlio di vertice v.

Quindi, la nostra soluzione è 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;
} 

Answer 7

avrei semplicemente utilizzare un programma lineare per risolvere il problema di minimo copertura dei vertici. Una formulazione come un intero programma lineare potrebbe essere simile a quello dato qui: formulazione ILP

Non credo che la vostra applicazione potrebbe essere più veloce di questi risolutori LP altamente ottimizzati.