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 回答