我在leetcode中遇到了一个名为“二叉树相机”的问题。
我想知道如何解决这个类似的问题：-
您必须将摄像机放置在图的节点处，以便覆盖整个图。节点上的摄像机监视其所有直接邻居节点及其自身。找到覆盖所有节点所需的最少摄像机数量。
这是set cover problem，有许多众所周知的算法。要将其建模为设置覆盖问题的一个实例，请将每个节点映射到该节点上的摄像机将覆盖的一组节点。
通常，这是一个“ NP Hard”问题，这意味着没有已知的算法总是能够提供最小的覆盖率，并且可以很好地扩展到问题的大实例。由于问题要求最小值，因此启发式算法不适合，因此您需要执行backtracking search之类的操作。