找到最小的唯一性标准

Question

我有一组具有属性的对象.我想找到最简单的一组标准,它们将准确指定其中一个对象(我不关心哪一个).

例如,给定{a = 1,b = 1,c = 1},{a = 1,b = 2,c = 1},{a = 1,b = 1,c = 2},指定b == 2(或c == 2)会给我一个独特的对象.

同样,给定{a = 1,b = 1,c = 1},{a = 1,b = 2,c = 2},{a = 1,b = 2,c = 1},指定b == 2和c == 2(或b == 1 && c == 1或b == 2 && c == 1)将给我一个独特的对象.

这听起来像一个已知的问题,有一个已知的解决方案,但我无法找到问题的正确表达,以允许我谷歌它.

Answer 1

选择目标的自由有点不寻常。如果指定了目标，那么这本质上就是集合覆盖问题。这是并排的两个相应实例。

A={1,2,3} B={2,4} C={3,4} D={4,5}

0: {a=0, b=0, c=0, d=0}  # separate 0 from the others
1: {a=1, b=0, c=0, d=0}
2: {a=1, b=1, c=0, d=0}
3: {a=1, b=0, c=1, d=0}
4: {a=0, b=1, c=1, d=1}
5: {a=0, b=0, c=0, d=1}

虽然集合覆盖是 NP 难的，但是，您的问题具有 O(m ^{log n + O(1)} poly(n)) 算法，其中 m 是属性数量，n 是项目数量（最佳标准集）其大小最多为 log n)，这使得 NP 难度证明不太可能出现。我想起了军政府问题的情况（基本上是特征选择的理论表述）。