我需要找到一种有效的算法，该算法可以找到一组最佳的二进制向量，使每个索引都有一个位，该位至少设置在集合中的一个向量中。
有趣的动机：我想闯入一座城堡，偷走它的宝藏。为了做到这一点，我必须解锁 4 扇门：蓝色门、红色门、黄色和绿色。有3个矮人，每个矮人都有一组不同的钥匙。矮人1有：蓝键和红键。矮人2有：红键和黄键。矮人3有：蓝钥匙和绿钥匙。我想杀死最少数量的矮人才能进入城堡。所以在这种情况下，很明显我们应该只杀死矮人 2 和矮人 3 来获得所有钥匙，没有必要杀死矮人 1。
一般来说，我们有 n 个大小为 m 的二进制向量（n 个矮人和 m 个门）：a0，a1....答（n-1）。我们需要一组向量，以便向量中的每个索引至少有一个键。如果 a1[5]=1，那么我们知道第二个向量中的第 6 位是设置的。这意味着矮人#2有键#6。开头的例子实际上是这样的：A0 （1,1,0,0）A1 （0,1,1,0）A2 （1,0,0,1）因此，我们选择载体：A1，A2以最小的载体获得完全覆盖。
蛮力朴素算法是尝试每个选项，然后以最少的向量返回解决方案，但由于有 n 个向量，因此有 2^n 个选项。
接下来，我想到了一种贪婪的算法，它每次都采用具有大多数键的向量。但这里有一个反例证明这种方法是错误的：
- a0 （1,1,1,0,0,0） --贪婪和错误的选择--
- A1 （1,0,0,1,0,0）
- A2 （0,1,0,0,1,0）
- A3 （0,0,1,0,0,1）
使用此算法，我们将选择所有 4 个向量，但最优解只有 3 个向量 {a1，a2，a3}。
现在，我想到了另一个贪婪的算法，我们选择具有最稀有键的向量（如果平局，我们搜索下一个稀有键，依此类推），但随后我又发现了一个反例：
- a0 （1,1,1,0,0,0） --贪婪和错误的选择--
- A1 （1,0,0,1,0,0）
- A2 （0,1,0,0,1,0）
- A3 （0,0,1,0,0,1）
- A4 （0,0,0,1,0,0）
- A5 （0,0,0,0,0,1,0）
- A6 （0,0,0,0,0,0,1）
在这个例子中，所有的索引都有相同的"稀有度"（2），所以我们最终选择了A0，尽管a0的sulotion（如{a0，a1，a2，a3}）至少有4个向量，而最优解只有3个{a1，a2，a3}。
我认为也许如果我消除作为另一个向量子集的向量（例如 a6 是 a3 的子集），那么这个算法可能会起作用，但即便如此，检查这个也会花费 n！。
我希望你能帮我找到一个有效的算法，或者帮助我证明这样的算法不存在。
这个问题称为设置覆盖问题，它是NP-Hard。
您可能会发现这个简短的视频很有帮助：离散优化（您必须登录您的 coursera 帐户）。它来自离散优化的伟大课程 - 该类的存档仍然打开。
（你关于修剪空间搜索的理由非常合理：你可以立即删除所有由另一个向量主导的向量，如果没有其他向量具有相同的键，你必须采用一个向量。