如何找到最小的密钥集？
How to find a minimal set of keys?
我有一组键 K 和一个有限集 S ⊂ K n 的 n-键元组。是否有一种有效的算法来找到双射映射 f : S ↦ S' 其中 S' ⊂ K k 与 k < n 剥离一些键而其他键保持不变的最小值?
恐怕这是 NP 完全的。
相当于set cover.
您的每个键都可以让您区分某些元素对（即一组边）。您的任务是 select 允许您区分每个元素的最少数量的键 - 即允许您覆盖每条边的最少数量的边集。
但是，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)
如果你能有效地解决你的问题，你就可以使用这个映射来有效地解决集合覆盖问题。
我有一组键 K 和一个有限集 S ⊂ K n 的 n-键元组。是否有一种有效的算法来找到双射映射 f : S ↦ S' 其中 S' ⊂ K k 与 k < n 剥离一些键而其他键保持不变的最小值?
恐怕这是 NP 完全的。
相当于set cover.
您的每个键都可以让您区分某些元素对（即一组边）。您的任务是 select 允许您区分每个元素的最少数量的键 - 即允许您覆盖每条边的最少数量的边集。
但是，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)
如果你能有效地解决你的问题，你就可以使用这个映射来有效地解决集合覆盖问题。