木の頂点カバーを最小限に抑えるための適切なアルゴリズムは何ですか?

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

質問

木の頂点カバーを最小限に抑えるための適切なアルゴリズムは何ですか?

入力：

ノードの近隣ノード。

出力：

頂点の最小数。

役に立ちましたか？

解決

願っています ここ あなたの質問にさらに関連した答えを見つけることができます。

私は自分の解決策を考えていました。おそらくそれを洗練する必要があるでしょうが、動的プログラミングがタグの1つに含まれている限り、おそらく次のことを行う必要があります。

  1. 各u頂点について定義s+（u）は、頂点uを使用せずに頂点uとs-（u）カバーを備えたカバーサイズです。
  2. u の各子 v について、S+(u)= 1 + Sum(S-(v))。
  3. u の各子 v に対する S-(u)=Sum(max{S-(v),S+(v)})。
  4. 答えは max(S+(r), S-(r)) です。ここで、r はツリーのルートです。

読んだあと これ. 。Wiki の記事に記載されているため、最大の独立セットを見つけるために上記のアルゴリズムを変更しました。

セットは、その補数が頂点カバーである場合にのみ独立しています。

したがって、最小値を最大値に変更することによって、最大の独立セットを見つけることができ、両方の問題が同等であるため、補うことによって最小の頂点カバーを見つけることができます。

他のヒント

T(V,E) はツリーであり、これは、任意のリーフについて、最小の頂点カバーにはリーフまたはリーフに隣接する頂点のいずれかが含まれなければならないことを意味します。これにより、頂点カバー S を見つけるための次のアルゴリズムが得られます。

  1. ツリーのすべてのリーフ (BFS または DFS)、O(|V|) をツリー内で検索します。
  2. v が葉であるような (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 に付随するすべてのエッジがカバーされるため、そのツリーを削除できます。これは、再帰の終了条件があり、頂点が 1 つあるかまったくなく、計算できることを意味します。 S_i それぞれの表紙として てぃ, 、ステップ 2 のすべての頂点が各頂点のカバーを結合するものとして S を定義します。 てぃ.

ここで、残っているのは、元のツリーに頂点が 1 つしかない場合、1 を返し、再帰を開始しないこと、および最小限の頂点カバーが計算できることを確認することだけです。

編集：

実際、少し考えてみると、これは単純な DFS バリアントで実現できます。

私は完全にここで答えを読んだ後、理解していなかったので、私は、私は<のhref = "http://courses.csail.mit.edu/6.006/spring11/lectures/lec21.pdfから1を投稿しようと思いました"REL =" noreferrer ">ここの

一般的な考え方は、あなたが任意のノードでツリーをルートとそのルートがカバー内にあるか否かを問うことです。それがある場合は、再帰的でその子をルートとする部分木の最小頂点被覆を計算します。そうでない場合は、ルートとその子の間のすべてのエッジが覆われるように、その後、ルートのすべての子が頂点被覆である必要があります。このケースでは、ルートの孫に再帰ます。

ですから、例えば、次のようなツリーを持っていた場合：

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

検査によって、あなたが最小頂点被覆が{B, C}である知っていることに注意してください。私たちは、この分のカバーを見つけます。

ここでは、Aで始まります。

Aをカバーしている

私たちはBとCの2つのサブツリーを下に移動し、このアルゴリズムに再帰します。私たちは、単にBとCが覆われている場合でも、我々は我々がカバーにかないようにABとACを必要とするかどうかについては何も言うことができないので。

BとCは、カバーされていないことを述べることはできません>

（）ルートとその子の1つの両方をカバー分（{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」のいずれかは、我々が現在の頂点が含まれていないならば、私たちはその子を含める必要があることを世話をする必要がありますので、カバーであること、および必要があります私たちはその後、現在の頂点を含めている場合、我々は、または最適解に基づいてその子を含んでも含まなくてもよい。

ここで、任意の頂点v =とき、我々はそれを含めるためのDP1 [V]。 我々はそれを含まない任意の頂点v =用DP2 [V]。

DP1 [V] = 1つの+ SUM（分（DP2は、[C]、DP1は、[C]）） - 。この手段は、現在含まれ、または最適であるものに基づいてその子を、含んでも含まなくてもよい。

DP2 [V] = SUM（DP1 [C]） - これは私たちが現在の頂点の子を含める必要があり、現在は含まないことを意味します。ここで、cは頂点vの子である。

次に、我々の解決策は、分（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