启发式算法，加速对大集合子集的搜索的方法(可能组合NP很难)

Question

我有一组大小合理的N (例如10000个对象)，在其中我正在搜索一组兼容的元素。这意味着我有一个函数y = f(x_1, x_2, x_3, ..., x_n)返回bool 0/1，回答n元素是否兼容。我们有兴趣在N的每个小于8个元素的子集上执行此搜索。这显然不是NP硬就是接近这个。即使是对n元素集的成对搜索，我们也要探索n^2对，这在某种程度上是可行的，但对于大集合仍然增长得相当快。然而，当我们寻找三元组(识别三元素团)和四重或更大的星等时，它会变得非常糟糕。

你能建议用机器学习的方法来帮助完成这项任务吗？也许在有效地采样搜索空间和确定搜索的子集时，可能会对函数进行快速的健康评估以指导搜索。

Answer 1

这不是ML，但是您的设置让我想起了覆盖阵列问题，它用于软件测试。

如果您认为您的配置数组0 0 1 0 1 0 0 1作为某些测试运行，一个典型的问题是，我需要运行的测试的最小数量是多少，而我可以涵盖大多数不同的设置？重要的是要提高测试的完整性，但也要尽量减少运行它们所需的时间。

一些可能的覆盖数组解决方案可能会有所帮助。甚至有些表是预先计算出来的，可以用于不同数量的N和覆盖强度https://math.nist.gov/coveringarrays/coveringarray.html。

正如你所指出的，这是一个组合问题，受到组合爆炸的影响。您可能希望分而治之(将N划分为k个可管理组)。