覆盖图中所有节点所需的最小摄像机数量

Question

我在 leetcode 中遇到了一个名为 "Binary Tree Camera" 的问题。

我想知道如何解决这个类似的问题：-

您必须将相机放置在图的节点上，以便覆盖整个图。节点上的摄像头监控其所有直接相邻节点及其自身。找到覆盖所有节点所需的最少摄像机数量。

Answer 1

这是一个set cover problem，其中有很多著名的算法。要将其建模为集合覆盖问题的实例，请将每个节点映射到该节点处的相机将覆盖的节点集。选择最少数量的节点的原始问题等同于选择最少数量的那些集合。

一般来说，这是一个 "NP Hard" 问题，这意味着没有已知的算法可以始终给出最小覆盖范围并且还可以很好地扩展到问题的大型实例。由于问题要求最小值，因此启发式算法不适合，因此您需要执行类似 backtracking search.

的操作

Answer 2

此问题称为最小值 Dominating Set，对于一般图形情况而言是 NP 难问题。存在通过近似、参数化或限制图的 class 来解决此问题的算法。有关详细信息，请参阅维基百科 link。