顶点覆盖算法

Table of content
上一个
下一个

你有没有想过交通摄像头的摆放位置？以及它们如何在不浪费政府过多预算的情况下高效地放置？答案以**顶点覆盖算法**的形式出现。摄像头的放置位置以一种方式选择，即一个摄像头覆盖尽可能多的道路，也就是说，我们选择路口并确保摄像头覆盖尽可能大的区域。

无向图**G = (V,E)**的**顶点覆盖**是指图的顶点子集，使得对于图中的所有边**（u,v）**，**u 和 v ∈ V**。路口被视为图的节点，道路被视为边。该算法找到覆盖最大数量道路的最小路口集。

这是一个最小化问题，因为我们找到顶点覆盖的最小大小——顶点覆盖的大小是其中的顶点数。优化问题是一个NP完全问题，因此不能在多项式时间内解决；但可以在多项式时间内找到的是近似最优解。

顶点覆盖算法

顶点覆盖近似算法以无向图作为输入，并执行以获得一组顶点，该顶点的数量肯定是不小于最优顶点覆盖的两倍。

顶点覆盖是一个2-近似算法。

算法

**步骤1** - 从输入图中选择任意一条边，并标记与该边对应的顶点相关联的所有边。

**步骤2** - 将任意边的顶点添加到输出集中。

**步骤3** - 对图中剩余的未标记边重复步骤1，并将选择的顶点添加到输出中，直到没有未标记的边。

**步骤4** - 最终得到的输出集将是近似最优的顶点覆盖。

伪代码

APPROX-VERTEX_COVER (G: Graph)
c ← { }
E’ ← E[G]
while E’ is not empty do
   Let (u, v) be an arbitrary edge of E’
   c ← c U {u, v}
   Remove from E’ every edge incident on either u or v
return c

示例

给定图的边集为：

{(1,6),(1,2),(1,4),(2,3),(2,4),(6,7),(4,7),(7,8),(3,5),(8,5)}
Vertex_Cover_Problem

现在，我们从选择任意边（1,6）开始。我们消去所有与顶点1或6相关联的边，并将边（1,6）添加到覆盖中。

arbitrary_edge

在下一步中，我们随机选择了另一条边（2,3）。

chosen_another_edge

现在我们选择另一条边（4,7）。

select_another_edge

我们选择另一条边（8,5）。

another edge 8 to 5

因此，该图的顶点覆盖为{1,6,2,3,4,7,5,8}。

分析

很容易看出该算法的运行时间为O(V + E)，使用邻接表来表示E'。

实现

以下是上述方法在各种编程语言中的实现：

C C++ Java Python
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
bool included[MAX_VERTICES];
// Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
void approxVertexCover(int vertices, int edges) {
   bool edgesRemaining[MAX_VERTICES][MAX_VERTICES];
   for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
         edgesRemaining[i][j] = graph[i][j];
      }
   }
   while (edges > 0) {
      int u, v;
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            if (edgesRemaining[i][j]) {
               u = i;
               v = j;
               break;
            }
         }
      }
      included[u] = included[v] = true;
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[u][i] = edgesRemaining[i][u] = false;
         edgesRemaining[v][i] = edgesRemaining[i][v] = false;
      }
      edges--;
   }
}
int main() {
   int vertices = 8;
   int edges = 10;
   int edgesData[10][2] = {
   {1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
   {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   printf("Vertex Cover: ");
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         printf("%d ", i);
      }
   }
   printf("\n");
   return 0;
}

输出

Vertex Cover: 1 3 4 5 6 7 

#include <iostream>
#include <vector>
using namespace std;
const int MAX_VERTICES = 100;
vector<vector<int>> graph(MAX_VERTICES, vector<int>(MAX_VERTICES, 0));
vector<bool> included(MAX_VERTICES, false);
// Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
void approxVertexCover(int vertices, int edges) {
   vector<vector<bool>> edgesRemaining(vertices, vector<bool>(vertices, false));
   for (int i = 0; i < vertices; i++) {
      for (int j = 0; j < vertices; j++) {
         edgesRemaining[i][j] = graph[i][j];
      }
   }
   while (edges > 0) {
      int u, v;
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            if (edgesRemaining[i][j]) {
               u = i;
               v = j;
               break;
            }
         }
      }
      included[u] = included[v] = true;
      for (int i = 0; i < vertices; i++) {
         edgesRemaining[u][i] = edgesRemaining[i][u] = false;
         edgesRemaining[v][i] = edgesRemaining[i][v] = false;
      }
      edges--;
   }
}
int main() {
   int vertices = 8;
   int edges = 10;
   int edgesData[10][2] = {
   {1, 6}, {1, 2}, {1, 4}, {2, 3}, {2, 4},
   {6, 7}, {4, 7}, {7, 8}, {3, 5}, {8, 5}};
   for (int i = 0; i < edges; i++) {
      int u = edgesData[i][0];
      int v = edgesData[i][1];
      graph[u][v] = graph[v][u] = 1;
   }
   approxVertexCover(vertices, edges);
   cout << "Vertex Cover: ";
   for (int i = 1; i <= vertices; i++) {
      if (included[i]) {
         cout << i << " ";
      }
   }
   cout << endl;
   return 0;
}

输出

Vertex Cover: 1 3 4 5 6 7 

import java.util.ArrayList;
import java.util.List;
public class Main {
   static final int MAX_VERTICES = 100;
   static int[][] graph = new int[MAX_VERTICES][MAX_VERTICES];
   static boolean[] included = new boolean[MAX_VERTICES];
   public static void approx_vertex_cover(int vertices, int edges) {
      int[][] edges_remaining = new int[MAX_VERTICES][MAX_VERTICES];
      for (int i = 0; i < vertices; i++) {
         for (int j = 0; j < vertices; j++) {
            edges_remaining[i][j] = graph[i][j];
         }
      }
      while (edges > 0) {
         int u = 1, v = 1;
         for (int i = 0; i < vertices; i++) {
            for (int j = 0; j < vertices; j++) {
               if (edges_remaining[i][j] != 0) {
                  u = i;
                  v = j;
                  break;
               }
            }
         }
         included[u] = included[v] = true;
         for (int i = 0; i < vertices; i++) {
            edges_remaining[u][i] = edges_remaining[i][u] = 0;
            edges_remaining[v][i] = edges_remaining[i][v] = 0;
         }
         edges--;
    }
}
public static void main(String[] args) {
   int vertices = 8;
   int edges = 10;
   List<int[]> edges_data = new ArrayList<>();
   edges_data.add(new int[] {1, 6});
   edges_data.add(new int[] {1, 2});
   edges_data.add(new int[] {1, 4});
   edges_data.add(new int[] {2, 3});
   edges_data.add(new int[] {2, 4});
   edges_data.add(new int[] {6, 7});
   edges_data.add(new int[] {4, 7});
   edges_data.add(new int[] {7, 8});
   edges_data.add(new int[] {3, 5});
   edges_data.add(new int[] {8, 5});
   for (int[] edge : edges_data) {
      int u = edge[0];
      int v = edge[1];
      graph[u][v] = graph[v][u] = 1;
}
approx_vertex_cover(vertices, edges);
System.out.print("Vertex Cover: ");
for (int i = 1; i <= vertices; i++) {
   if (included[i]) {
      System.out.print(i + " ");
   }
}
System.out.println();
}
}

输出

Vertex Cover: 1 3 4 5 6 7 

MAX_VERTICES = 100
graph = [[0 for _ in range(MAX_VERTICES)] for _ in range(MAX_VERTICES)]
included = [False for _ in range(MAX_VERTICES)]
# Function to find Vertex Cover using the APPROX-VERTEX_COVER algorithm
def approx_vertex_cover(vertices, edges):
    edges_remaining = [row[:] for row in graph]
    while edges > 0:
        for i in range(vertices):
            for j in range(vertices):
                if edges_remaining[i][j]:
                    u = i
                    v = j
                    break
        included[u] = included[v] = True
        for i in range(vertices):
            edges_remaining[u][i] = edges_remaining[i][u] = False
            edges_remaining[v][i] = edges_remaining[i][v] = False
        edges -= 1
if __name__ == "__main__":
    vertices = 8
    edges = 10
    edges_data = [(1, 6), (1, 2), (1, 4), (2, 3), (2, 4),
                  (6, 7), (4, 7), (7, 8), (3, 5), (8, 5)]
    for u, v in edges_data:
        graph[u][v] = graph[v][u] = 1
    approx_vertex_cover(vertices, edges)
    print("Vertex Cover:", end=" ")
    for i in range(1, vertices + 1):
        if included[i]:
            print(i, end=" ")
    print()

输出

Vertex Cover: 1 3 4 5 6 7
打印页面
上一个
下一个
广告