Data Structures Algorithms 简明教程
Vertex Cover Algorithm
你是否曾思考过交通摄像头的放置问题？例如，如何在不过度浪费政府预算的情况下有效地安放摄像头？这个问题的答案就是 vertex-cover algorithm 。摄像头的放置方式是力求让一个摄像头覆盖尽可能多的道路，也就是，选择交叉口，并确保摄像头覆盖尽可能大的区域。
无向图 G = (V,E) 的一个 vertex-cover 是图的顶点的子集，对于图中的所有边 (u,v) ， мають u and v ∈ V 。交汇点被视为图的节点，道路被视为边。该算法找出覆盖最大数量道路的最小交汇点集合。
这是一个最小化问题，因为我们要找出最小规模的顶点覆盖 − 顶点覆盖的规模是其中包含顶点的数量。优化问题是一个 NP 完备问题，因此无法在多项式时间内求解；但可以在多项式时间内找出近似最优解。
Vertex Cover Algorithm
顶点覆盖近似算法以无向图作为输入，并执行此算法以获得一个集合，该集合的大小肯定刚好是最佳顶点覆盖的两倍。
顶点覆盖是一种 2-近似算法。
Algorithm
Step 1 − 从输入图中选择任意一条随机边，并将该边的各个顶点相邻的边全部标记。
Step 2 − 将随机边的各个顶点添加到输出集中。
Step 3 − 对图中剩下的未标记边重复第 1 步，并将其添加到输出集中直到无边未标记。
Step 4 − 最后的输出集将会是接近最优的顶点覆盖。
Pseudocode
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
