约束满足：选择具有某些特征的实数
我有一组 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）？
I have a set of n real numbers. I also have a set of functions,
f_1, f_2, ..., f_m.
Each of these functions takes a list of numbers as its argument. I also have a set of m ranges,
[l_1, u_1], [l_2, u_2], ..., [l_m, u_m].
I want to repeatedly choose a subset {r_1, r_2, ..., r_k} of k elements such that
l_i <= f_i({r_1, r_2, ..., r_k}) <= u_i for 1 <= i <= m.
Note that the functions are smooth. Changing one element in {r_1, r_2, ..., r_k} will not change f_i({r_1, r_2, ..., r_k}) by much. average and variance are two f_i that are commonly used.
These are the m constraints that I need to satisfy.
Moreover I want to do this so that the set of subsets I choose is uniformly distributed over the set of all subsets of size k that satisfy these m constraints. Not only that, but I want to do this in an efficient manner. How quickly it runs will depend on the density of solutions within the space of all possible solutions (if this is 0.0, then the algorithm can run forever). (Assume that f_i (for any i) can be computed in a constant amount of time.)
Note that n is large enough that I cannot brute-force the problem. That is, I cannot just iterate through all k-element subsets and find which ones satisfy the m constraints.
Is there a way to do this?
What sorts of techniques are commonly used for a CSP like this? Can someone point me in the direction of good books or articles that talk about problems like this (not just CSPs in general, but CSPs involving continuous, as opposed to discrete values)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
假设您希望编写自己的应用程序并使用现有的库来执行此操作，则有多种语言可供选择，例如 Python 约束，或 Cream 或 Choco for Java，或 CSP 用于 C++。从您描述问题的方式来看，您似乎正在寻找通用 CSP 求解器。您的函数是否有任何有助于降低复杂性的属性，例如单调性？
Assuming you're looking to write your own application and use existing libraries to do this, there are choices in many languages, like Python-constraint, or Cream or Choco for Java, or CSP for C++. The way you've described the problem it sound like you're looking for a general purpose CSP solver. Are there any properties of your functions that may help reduce the complexity, such as being monotonic?
鉴于您所描述的问题，您可以从每个范围
r_i中统一选取，并丢弃任何不符合标准的 m 维点。它将是均匀分布的，因为原始数据是均匀分布的，并且子集集是原始数据上的二进制掩码。如果不了解更多关于 f 形状的信息，您就无法保证时间是否是多项式（甚至不知道如何找到满足约束的点）。毕竟，如果
f_1 = (x^2 + y^2 - 1)和f_2 = (1 - x^2 - y^2)并且约束条件为 <代码>f_1 < 0 和f_2 < 0，你根本无法满足这一点（并且如果无法访问函数的分析形式，你永远无法确定）。Given the problem as you've described it, you can pick from each range
r_iuniformly and throw away any m-dimensional point that fails to meet the criterion. It will be uniformly distributed because the original is uniformly distributed and the set of subsets is a binary mask over the original.Without knowing more about the shape of
f, you can't make any guarantees about whether time is polynomial or not (or even have any idea of how to hit a spot that meets the constraint). After all, iff_1 = (x^2 + y^2 - 1)andf_2 = (1 - x^2 - y^2)and the constraints aref_1 < 0andf_2 < 0, you can't satisfy this at all (and without access to the analytic form of the functions, you could never know for sure).鉴于您消息中的信息，我不确定它是否可以完成...
考虑：
现在，您可以想出多少个 {1...100} 的子集来产生 10 到 10 之间的平均值。 50？
Given the information in your message, I'm not sure it can be done at all...
Consider:
Now, how many subset of {1...100} can you come up with that produces an average between 10 & 50?
这看起来是一个非常难的问题。对于线性函数最简单的情况，您可以看一下线性规划。
This looks like a very hard problem. For the simplest case with linear functions you could take a look at linear programming.