找到鉴别数据点的算法？

Question

给定 n 个样本和 n 个样本中每个样本的 p >> n 个(离散)数据点，找到最小可能的 k 个数据点集合以使这 k 个数据点区分所有 n 个样本的好算法是什么？

就我的目的而言，找到近似最小集合的良好算法也足够了。

Answer 1

听起来您的问题与测试封面问题密切相关。测试覆盖问题是，给定一个地面集 X = {1, …, n} 和一个子集的集合 T = {T₁, …, T_m} X，找到 T 的最小子集合 U，使得对于 X 中的所有 y ≠ z，在 T 中存在一个集合 S，使得 (x in S and y not in S) or (x not in S and y in S ).

测试覆盖问题是 NP-hard 问题，因此在实践中，最佳解决方案是使用分支定界技术找到的。参见 De Bontridder et al.