2

したがって、特定の重みとエッジを持つ頂点のグラフがあります。最小加重頂点カバーを見つけようとしています。たとえば、サイズ 10 の頂点カバーがあり、各ノードの重みが 10 の場合、合計カバーの重みは 100 になります。しかし、サイズ 99 の頂点カバーで各ノードの重みが 1 の場合、前のものよりもこの表紙を選んでください。

これは NP-Complete だと思うので、効率的なアルゴリズムはありませんが、ノードの数が比較的少ないため、網羅的な検索でもうまくいくと思います。私がこれを行うと考えることができる唯一の方法は、セット [1 ... n] (各整数はグラフ上のノードに対応する) の累乗セットを生成し、個々のセットをテストして、それが正しいかどうかを確認することです。 1) 有効な頂点カバー、および 2) 最小ウェイトの頂点カバーを追跡します。

しかし、これは恐ろしく非効率的です。これが最善の方法ですか？

4

1 に答える 1

0

最小重みの頂点カバーは NP-Complete であるため、一般的に網羅的な検索よりも優れているとは期待できませんが、バックトラッキングを使用して、次のような最小重みの頂点カバーを見つけることができます。

MinCover(Graph G, List<Vertex> selectedVertices, int min)
{
   var coveredAll = covered(G,selectedVertices);
   if ( coveredAll && weight(selectedVertices) < min)
   {
       cover = selectedVertices.ToList();
       min = weight(cover);
   }
   else if (!coveredAll && weight(selectedVertices) < min)
   {
      select another unvisited vertex and add it to selectedVertices
      call MinCover
      remove the previously selected vertex from the list
   }

   return;

}
于 2012-08-20T21:49:09.143 に答える