顶点覆盖算法
您是否想过交通摄像头的放置位置？如何高效地放置它们，又不浪费政府过多的预算？答案就在顶点覆盖算法中。摄像机的位置选择原则是，一个摄像机能够覆盖尽可能多的道路，也就是说，我们选择交叉路口并确保摄像机覆盖尽可能多的区域。
无向图 G = (V,E) 的 顶点覆盖 是图的顶点子集，对于图中的所有边 (u,v)，u 和 v ∈ V。交叉路口被视为图的节点，道路被视为边。该算法寻找覆盖最多道路数量的最小交叉路口集。
这是一个最小化问题，因为我们找到的是顶点覆盖的最小大小——顶点覆盖的大小就是其中的顶点数。该优化问题是 NP 完全问题，因此无法在多项式时间内求解；但多项式时间内能找到的是近似最优解。
顶点覆盖算法
顶点覆盖近似算法以无向图为输入，执行后会得到一个顶点集，该集合的大小肯定是最优顶点覆盖的两倍。
顶点覆盖是一种二阶近似算法。
算法
步骤 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)}
现在，我们先选择一条任意边 (1,6)。我们消除所有与顶点 1 或 6 相关的边，并添加边 (1,6) 进行覆盖。
下一步，我们随机选择了另一条边 (2,3)。
现在我们选择另一条边 (4,7)。
我们选择另一条边 (8,5)。
因此，该图的顶点覆盖为 {1,6,2,3,4,7,5,8}。
分析
容易看出，该算法的运行时间为 O(V + E)，使用邻接表表示 E'。
实现
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
bool included[MAX_VERTICES];
// 使用 APPROX-VERTEX_COVER 算法查找顶点覆盖的函数
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("
");
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);
// 使用 APPROX-VERTEX_COVER 算法查找顶点覆盖的函数
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)]
# 使用 APPROX-VERTEX_COVER 算法查找顶点覆盖的函数
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
