java - 如何用最少的节点覆盖图形的所有边？

Question

我被一个 NP 问题困扰了几天，我正在寻找新的方法来看待这个问题。

这座城市有 360 个安全摄像头，需要在城市的所有街道交叉口放置。这个想法是寻找需要放置的最少数量的摄像机，以便覆盖所有街道。

不幸的是，摄像机只能覆盖一个街区。

我将每个交叉路口视为图形节点，而街道是边缘，最初我认为这是某种中国邮递员问题，但该算法主要适用于您想从一个起始节点行进并覆盖所有边缘并返回初始节点。

那么如何用最少的摄像头覆盖所有街道呢？

任何形式的启蒙都将不胜感激。

标签： javaalgorithmgraphgraph-algorithmnp

Answer 1

通过选择最小数量的顶点来覆盖图中的所有边是（最小）顶点覆盖问题。这是一个 NP完全问题，因此解决一般实例的最著名算法需要指数级的时间。（就像所有的 NP 完全问题一样，它也在 NP 中，但这在这里不是一个有用的描述，因为许多简单的问题也是如此。）

然而，一些图的子类可以更快地解决。二分图就是这样一个类，而网格图（或此类的子图）是二分的，所以你很幸运。对于网格图，坐标和为偶数的顶点（图中的黑点）构成分区中的一个部分，坐标和为奇数的顶点构成另一个部分：注意同一部分内的顶点之间没有边. 可以通过首先找到最大基数二分匹配来找到最小顶点覆盖，例如在 O(|E|*sqrt(|V|)) 时间内使用Hopcroft-Karp 算法，然后应用该算法。