如何找到最小的密钥集

Question

我有一组键K和一个有限集S&子集K^<<em>n的em>n-密钥元组。是否有一种有效的算法来找到双射映射f：S&mapstoS'其中S'&子集K^k与k<nminimum会剥去一些钥匙，而不影响其他钥匙吗？

Answer 1

恐怕这是NP完全的。

它相当于设置封面。

每个键都允许您区分某些元素对(即一组边(。您的任务是选择允许您区分每个元素的最小键数，即允许您覆盖每个边的最小边集数。

然而，wiki页面显示了一个基于整数编程的近似解决方案，该方案可能在实践中提供有用的解决方案。

证明草图

假设我们有一个通用的集覆盖问题：

A,B,C
C,D
A,B,D

其中我们需要找到这些集合的最小数量来覆盖每个元素A、B、C、D。

我们为每个字母a、B、C、D构造一个元组。

元组在位置i有一个唯一的数字，当且仅当集合i包含字母。否则，它们包含0。

还有一个零元组。

这意味着元组看起来像：

(0,0,0)  The zero tuple
(1,0,2)  The tuple for A (in sets 1 and 3)
(3,0,4)  The tuple for B (in sets 1 and 3)
(5,6,0)  The tuple for C (in sets 1 and 2)
(0,7,8)  The tuple for D (in sets 2 and 3)

如果你能有效地解决你的问题，那么你就可以使用这个映射来有效地解决集合覆盖。