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

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约束的所有大小K的集合集上。不仅如此，我还想以有效的方式这样做。它运行的速度将取决于所有可能解决方案空间内的解决方案的密度（如果是0.0，则该算法可以永远运行）。 （假设F_I（对于任何I）可以在恒定的时间内计算。）

请注意，n足够大，我无法施加问题。也就是说，我不能仅仅迭代所有K元素子集，并发现哪些子集满足了M的约束。

有没有办法做到这一点？

这样的CSP通常使用哪些类型的技术？有人可以将我指向谈论此类问题的好书或文章的方向（不仅是CSP，而是涉及连续的CSP，而不是离散价值）？

Answer 1

假设您想编写自己的应用程序并使用现有库来执行此操作，那么许多语言中都有选择，例如 Python-Constraint, ， 或者 奶油 或者 巧克力 对于Java或 CSP 对于C ++。您描述的问题听起来好像您正在寻找通用CSP求解器。您的功能是否有可能有助于降低复杂性的属性，例如单调？

Answer 2

考虑到您所描述的问题，您可以从每个范围中选择 r_i 统一，丢弃任何无法满足标准的M维点。它将被统一分布，因为原件是均匀分布的，并且子集的集合是原始的二进制掩码。

不知道更多关于形状的 f, ，您不能保证时间是否是多项式（甚至对如何达到符合约束的位置有任何了解）。毕竟，如果 f_1 = (x^2 + y^2 - 1) 和 f_2 = (1 - x^2 - y^2) 限制是 f_1 < 0 和 f_2 < 0, ，您根本无法满足（如果没有访问功能的分析形式，您就无法确定）。

Answer 3

鉴于您的消息中的信息，我不确定它是否可以完成...

考虑：

• 数字= {1 .... 100}
• m = 1（保持简单）
• F1 =平均值
• L1 = 10
• U1 = 50

现在，您可以提出多少个{1 ... 100}的子集，该子集的平均值在10到50之间？

Answer 4

这看起来像是一个很难的问题。对于最简单的线性功能，您可以看一下线性编程。