约束满足：选择具有某些特征的实数

我有一组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，而不是离散值）？

已邀请:

4 个回复

粱委教

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

镰茧钩

鉴于您所描述的问题，您可以从每个范围均匀地选取r_i并丢弃任何不符合标准的m维点。它将是均匀分布的，因为原始是均匀分布的，并且子集的集合是原始的二元掩模。如果不了解f的形状，就无法确定时间是否为多项式（或者甚至不知道如何击中满足约束的点）。毕竟，如果f_1 = (x^2 + y^2 - 1)和f_2 = (1 - x^2 - y^2)且约束条件为f_1 < 0和f_2 < 0，则根本无法满足此要求（并且无法访问函数的分析形式，您无法确定）。