我需要找到一种有效的算法,找到一组最佳二进制向量,使得每个索引都有一个在该集合中至少有一个向量中设置的位.
有趣的动机:我想闯入一座城堡并偷走它的宝藏.为了做到这一点,我必须解锁4扇门:蓝色的门,红色的门,黄色和绿色.有3个矮人,每个人都有一套不同的钥匙.矮人1有:蓝键和红键.矮人2有:红色键和黄色键.矮人3有:蓝色键和绿色键.我想杀死最少量的矮人以进入城堡.所以在这种情况下,很明显我们应该只杀死矮人2和矮人3来获得所有的钥匙,并且不需要杀死矮人1.
一般来说,我们有n个大小为m(n dwarfs和m门)的二进制向量:a0,a1 ...... a(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个选项.
接下来我想到了一个贪婪的算法,每次都使用大多数键的向量.但这是一个反例,证明这种方法是错误的:
使用此算法,我们将选择所有4个向量,但最优解只有3个向量{a1,a2,a3}.
现在,我想到了另一种贪婪的算法,我们选择具有最罕见密钥的向量(如果是平局,我们搜索下一个稀有密钥等等),但是我再次找到了一个反例:
在这个例子中,所有索引都具有相同的"稀有性"(2),所以我们最终选择a0虽然a0(例如{a0,a1,a2,a3})至少有4个向量并且最优解是只有3 {a1,a2,a3}.
我想也许如果我将消除作为另一个向量的子集的向量(例如a6是a3的子集),那么这个算法可能会起作用,但即便如此,检查这将花费n!.
我希望你能帮我找到一个有效的算法,或者帮助我证明这种算法不存在.