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

Question

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

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

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

标签： algorithmgraphdynamic-programminggraph-theorygraph-algorithm

Answer 1

这是一个集合覆盖问题，有许多众所周知的算法。要将其建模为集覆盖问题的一个实例，请将每个节点映射到该节点处的相机将覆盖的节点集。选择最少节点的原始问题等价于选择这些集合中的最少数量。

一般来说，这是一个“NP Hard”问题，这意味着没有已知的算法总是给出最小覆盖并且也可以很好地扩展到问题的大型实例。由于问题要求最小值，因此启发式算法不适合，因此您需要执行回溯搜索之类的操作。