Satisfacción de Restricciones: La elección de los números reales con ciertas características

Question

Tengo un conjunto de n números reales. También tengo un conjunto de funciones,

f_1, f_2, ..., f_m.

Cada una de estas funciones tiene una lista de números como su argumento. También tengo un conjunto de rangos m,

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

Quiero varias veces elija un subconjunto {r_1, r_2, ..., r_k} de k elementos de tal manera que

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

Tenga en cuenta que las funciones aparecen difuminadas. Cambio de un elemento en {r_1, r_2, ..., r_k} no cambiará f_i ({r_1, r_2, ..., r_k}) por mucho. la media y la varianza son dos f_i que se utilizan comúnmente.

Estas son las m restricciones que tengo que satisfacer.

Por otra parte quiero hacer esto para que el conjunto de subconjuntos elijo se distribuye de manera uniforme sobre el conjunto de todos los subconjuntos de tamaño k que satisfacen estas restricciones m. No sólo eso, pero yo quiero hacer esto de una manera eficiente. La rapidez con que se ejecuta dependerá de la densidad de las soluciones en el espacio de todas las posibles soluciones (si esto es 0.0, entonces el algoritmo puede funcionar para siempre). (Suponga que f_i (para cualquier i) puede ser calculada en una cantidad constante de tiempo.)

Tenga en cuenta que n es lo suficientemente grande que no puedo fuerza bruta del problema. Es decir, no puedo simplemente iterar a través de todos los subconjuntos de k elementos y encontrar cuáles satisfacen las m restricciones.

¿Hay una manera de hacer esto?

¿Qué tipo de técnicas se utilizan comúnmente para un CSP como este? ¿Puede alguien me punto en la dirección de los buenos libros o artículos que hablan de problemas de este tipo (no sólo los CSP en general, sino que implican los CSP continua, en contraposición a los valores discretos)?

Answer 1

Si se asume que usted está buscando para escribir sus propias bibliotecas de aplicaciones y el uso existente para ello, hay opciones en muchos idiomas, como el Python-restricción , o crema o < a href = "http://www.emn.fr/z-info/choco-solver/" rel = "nofollow noreferrer"> Choco para Java, o CSP para C ++. La forma en que has descrito el problema que suene como si está buscando un solucionador de CSP de propósito general. ¿Hay algunas propiedades de sus funciones que pueden ayudar a reducir la complejidad, tales como ser monótona?

Answer 2

Teniendo en cuenta el problema como lo has descrito, se puede escoger de cada r_i gama uniforme y tire cualquier punto de m-dimensional que no cumple con el criterio. Se distribuye uniformemente porque el original se distribuye uniformemente y el conjunto de subconjuntos es una máscara binaria sobre el original.

Sin saber más sobre la forma de f, no se puede ofrecer ninguna garantía acerca de si el tiempo es polinómica o no (o incluso tener alguna idea de cómo golpear un lugar que cumpla la restricción). Después de todo, si f_1 = (x^2 + y^2 - 1) y f_2 = (1 - x^2 - y^2) y las restricciones son f_1 < 0 y f_2 < 0, puede no satisface en absoluto (y sin acceso a la forma analítica de las funciones, puede que nunca sepamos a ciencia cierta).

Answer 3

Teniendo en cuenta la información contenida en el mensaje, no estoy seguro de que se puede hacer en todos los ...

Considere lo siguiente:

• números = {1 .... 100}
• m = 1 (mantenerlo simple)
• F1 = Media
• L1 = 10
• U1 = 50

Ahora, ¿cuántos subconjunto de {1} ... 100 puede llegar a que produce un promedio entre 10 y 50?

Answer 4

Esto parece un problema muy difícil. Para el caso más sencillo con funciones lineales que podría echar un vistazo a la programación lineal.