- 算法设计与分析
- 家
- 算法基础知识
- DAA - 简介
- DAA - 算法分析
- DAA-分析方法
- 渐近符号和先验分析
- 时间复杂度
- 马斯特定理
- DAA - 空间复杂性
- 分而治之
- DAA-分而治之
- DAA - 最大最小问题
- DAA-归并排序
- DAA-二分查找
- 施特拉森矩阵乘法
- 唐叶算法
- 河内塔
- 贪心算法
- DAA-贪婪法
- 旅行商问题
- Prim 的最小生成树
- 克鲁斯卡尔的最小生成树
- Dijkstra 的最短路径算法
- 地图着色算法
- DAA-分数背包
- DAA - 带截止日期的作业排序
- DAA - 最佳合并模式
- 动态规划
- DAA-动态规划
- 矩阵链乘法
- 弗洛伊德·沃歇尔算法
- DAA - 0-1 背包
- 最长公共子序列
- 旅行商问题| 动态规划
- 随机算法
- 随机算法
- 随机快速排序
- 卡格的最低削减
- 费舍尔-耶茨洗牌
- 近似算法
- 近似算法
- 顶点覆盖问题
- 设置封面问题
- 旅行推销员近似算法
- 排序技巧
- DAA-快速排序
- DAA-冒泡排序
- DAA——插入排序
- DAA-选择排序
- DAA——希尔排序
- DAA-堆排序
- DAA——桶排序
- DAA——计数排序
- DAA - 基数排序
- 搜索技巧
- 搜索技术介绍
- DAA - 线性搜索
- DAA-二分查找
- DAA - 插值搜索
- DAA - 跳转搜索
- DAA - 指数搜索
- DAA - 斐波那契搜索
- DAA - 子列表搜索
- DAA-哈希表
- 图论
- DAA-最短路径
- DAA - 多级图
- 最优成本二叉搜索树
- 堆算法
- DAA-二叉堆
- DAA-插入法
- DAA-Heapify 方法
- DAA-提取方法
- 复杂性理论
- 确定性计算与非确定性计算
- DAA-最大派系
- DAA - 顶点覆盖
- DAA - P 级和 NP 级
- DAA-库克定理
- NP 硬课程和 NP 完全课程
- DAA - 爬山算法
- DAA 有用资源
- DAA - 快速指南
- DAA - 有用的资源
- DAA - 讨论
设计与分析-顶点覆盖问题
您是否想过交通摄像头的位置?如何在不浪费政府太多预算的情况下有效地安置它们?答案以顶点覆盖算法的形式出现。摄像机位置的选择应使一台摄像机覆盖尽可能多的道路,即我们选择路口并确保摄像机覆盖尽可能多的区域。
无向图的顶点覆盖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)}
现在,我们首先选择任意边 (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]; // 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