algorithm - 约束满足 : Choosing real numbers with certain characteristics

Question

我有一组 n 个实数。我也有一套功能，

f_1, f_2, ..., f_m.

这些函数中的每一个都将数字列表作为其参数。我还有一组 m 个范围，

[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].

我想重复选择 k 个元素的子集 {r_1, r_2, ..., r_k} 使得

l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.

请注意，函数是平滑的。改变 {r_1, r_2, ..., r_k} 中的一个元素不会改变 f_i({r_1, r_2, ..., r_k}) 太多。平均值和方差是两个常用的f_i。

这些是我需要满足的 m 个约束条件。

此外，我想这样做，以便我选择的子集集合均匀分布在满足这些 m 约束的所有大小为 k 的子集集合中。不仅如此，我还想以高效的方式做到这一点。它运行的速度将取决于所有可能解决方案空间内的解决方案密度(如果这是 0.0，则算法可以永远运行)。 (假设可以在恒定时间内计算出 f_i(对于任何 i)。)

请注意，n 足够大，我无法暴力破解问题。也就是说，我不能只遍历所有 k 元素子集并找到哪些满足 m 约束条件。

有办法吗？

像这样的 CSP 通常使用什么样的技术？有人能给我指出讨论此类问题的好书或文章的方向吗(不仅仅是一般的 CSP，而是涉及连续值而不是离散值的 CSP)？

Answer 1

假设您希望编写自己的应用程序并使用现有的库来执行此操作，可以选择多种语言，例如 Python-constraint , 或 Cream或 Choco对于 Java，或 CSP对于 C++。您描述问题的方式听起来像是您在寻找通用 CSP 求解器。您的函数是否有任何有助于降低复杂性的属性，例如单调性？