1

我有一组 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

4 回答 4

1

鉴于您描述的问题，您可以从每个范围中r_i统一选择并丢弃任何不符合标准的 m 维点。它将是均匀分布的，因为原始是均匀分布的，并且子集的集合是原始的二进制掩码。

在不了解 的形状的情况下f，您无法对时间是否为多项式做出任何保证（甚至不知道如何到达满足约束的点）。毕竟，如果f_1 = (x^2 + y^2 - 1)和f_2 = (1 - x^2 - y^2)约束是f_1 < 0和f_2 < 0，您根本无法满足这一点（如果无法访问函数的解析形式，您永远无法确定）。

于 2010-09-08T19:23:08.950 回答
1

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

于 2010-09-08T19:23:10.943 回答
0

这看起来是一个非常困难的问题。对于线性函数的最简单情况，您可以查看线性规划。

于 2010-09-08T19:37:25.857 回答
0

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

考虑：

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

现在，你能想出多少个 {1...100} 的子集来产生 10 到 50 之间的平均值？

于 2010-09-08T19:24:20.600 回答