代码之家 › 专栏 › 技术社区 › Paul Reiners

约束满足:选择具有一定特征的实数

constraint-satisfaction constraint-programming statistics algorithm

Paul Reiners · 技术社区 · 15 年前

f_1, f_2, ..., f_m.

每个函数都以一个数字列表作为其参数。我还有一套m系列,

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

我想 反复地

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

注意函数是平滑的。改变{r\u 1,r\u 2,…,r\u k}中的一个元素不会改变f\u i({r\u 1,r\u 2,…,r\u k})。平均值和方差是常用的两个fèi。

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

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

注意,n足够大,我不能强行解决这个问题。也就是说,我不能只是遍历所有的k元素子集,然后找出哪些子集满足m约束。

有办法吗?

像这样的CSP通常使用哪种技术?有人能给我指出一些好的书籍或文章的方向吗?这些书或文章讨论了这样的问题(不只是一般的csp,而是涉及连续值而不是离散值的csp)?

4 回复 | 直到 13 年前

John Ellinwood 15 年前

Python-constraint ,或 Cream 或 Choco CSP 对于C++。你描述问题的方式听起来像是在寻找一个通用的CSP解决方案。你的函数有什么特性可以帮助降低复杂性,比如单调性吗?

Rex Kerr 15 年前

根据您描述的问题,您可以从每个范围中进行选择 r_i

不知道更多关于 f ,您不能保证时间是否是多项式(甚至不知道如何到达满足约束的点)。毕竟,如果 f_1 = (x^2 + y^2 - 1) f_2 = (1 - x^2 - y^2) 约束条件是 f_1 < 0 和 f_2 < 0 ,您根本无法满足这一点(如果没有函数的分析形式,您永远无法确定)。

James Curran 15 年前

根据你留言里的信息,我不确定能不能做到。。。

考虑:

数字={1….100}
F1=平均值
U1=50

starblue 15 年前

推荐文章

RSW · Python-检查序列中的最后一个值是否相对高于其余值

2 年前

mayen · Z-Score作为差异值的度量

2 年前

John Philips · Python中的重命名函数

2 年前

Yneedtobeserious · 给定的数据点,形成它们的关系

2 年前

Pacific Bird · 即使考虑了不同的参数化,R`dnbinom`也会给出与Python`scipy.stats.nbinom.pmf`不同的结果

2 年前

JCWong · 手工实现协方差

2 年前

Idan Hazan · 转换总和为1的列表并保持值之间的关系[重复]

2 年前

Jimmy3421 · 为什么pd.cut会产生NaN值

2 年前

JoRayMe · 有没有办法从数据数组中识别浮点数中的小数位数?

2 年前

Pbro98 · 均匀随机抽样未返回均匀样本(Scipy Uniform)

2 年前