algorithm - 如何找到图的加权最小顶点覆盖

Question

所以，我有一个具有特定权重和边的顶点图。我正在尝试找到最小加权顶点覆盖。例如，如果我有一个大小为 10 的顶点覆盖，但每个节点的权重为 10，则总覆盖的权重为 100。但是如果我有一个大小为 99 且每个节点的权重为 1 的顶点覆盖，那么我会选择这个封面而不是之前的封面。

我认为这是 NP-Complete，因此没有有效的算法，但我认为即使是穷举搜索也对我有用，因为节点数量相对较少。我能想到的唯一方法是生成集合 [1 ... n] 的幂集(其中每个整数对应于图上的一个节点)，然后测试每个单独的集合以查看它是否是1) 一个有效的顶点覆盖，以及 2) 跟踪最低权重的顶点覆盖。

但这似乎非常低效。这是最好的方法吗？

Answer 1

最小权重顶点覆盖是 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;

}