Quel est un bon algorithme pour obtenir la couverture minimale des sommets d'un arbre ?

Question

Quel est un bon algorithme pour obtenir la couverture minimale des sommets d'un arbre ?

INPUT :

Les voisins du nœud.

SORTIE :

Le nombre minimum de sommets.

Answer 1

Nous devons trouver la couverture minimale de sommets pour chaque nœud, nous avons des choix à faire, soit l'inclure, soit ne pas l'inclure. Mais selon le problème, pour chaque arête (u, v), l'un ou l'autre de 'u' ou 'v' doit être dans la couverture. Nous devons donc faire attention à ce que si le sommet actuel n'est pas inclus, nous devrions inclure ses enfants, et si nous incluons le sommet actuel, nous pouvons ou non inclure ses enfants en fonction de la solution optimale.

Ici, DP1[v] pour tout sommet v = Lorsque nous l'incluons. DP2[v] pour tout sommet v = lorsque nous ne l'incluons pas.

DP1[v] = 1 + sum(min(DP2[c], DP1[c])) - cela signifie inclure le courant et peut ou non inclure ses enfants, en fonction de ce qui est optimal.

DP2[v] = sum(DP1[c]) - cela signifie que sans inclure le sommet actuel, nous devons inclure les enfants du sommet actuel. Ici, c est l'enfant du sommet v.

Alors, notre solution est 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 2

J'utiliserais simplement un programme linéaire pour résoudre le problème de la couverture minimale des sommets. Une formulation sous forme de programme linéaire entier pourrait ressembler à celle donnée ici : Formulation ILP

Je ne pense pas que votre propre mise en œuvre soit plus rapide que ces solveurs LP hautement optimisés.