Vincolo Soddisfazione: Scegliere i numeri reali con determinate caratteristiche

Question

Ho un insieme di n numeri reali. Ho anche un insieme di funzioni,

f_1, f_2, ..., f_m.

Ciascuna di queste funzioni prende una lista di numeri come argomento. Ho anche un insieme di m gamme,

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

Voglio più volte scegliere un sottoinsieme {R_1, R_2, ..., r_k} di k elementi tali che

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

Si noti che le funzioni sono uniformi. Cambiare un elemento {R_1, R_2, ..., r_k} non cambierà f_i ({R_1, R_2, ..., r_k}) di molto. media e varianza sono due f_i che sono comunemente usati.

Queste sono le m vincoli che ho bisogno di soddisfare.

Inoltre voglio fare questo in modo che l'insieme di sottoinsiemi scelgo è distribuita uniformemente sopra l'insieme di tutti i sottoinsiemi di dimensione k che soddisfano questi m vincoli. Non solo, ma io voglio fare questo in modo efficace. In quanto tempo si corre dipenderà dalla densità delle soluzioni all'interno dello spazio di tutte le possibili soluzioni (se questo è 0,0, quindi l'algoritmo può essere eseguito per sempre). (Si supponga che f_i (per ogni i) può essere calcolato in una quantità costante di tempo.)

Si noti che n è abbastanza grande che non riesco a forza bruta il problema. Cioè, non posso semplicemente scorrere tutti i sottoinsiemi k-elemento e trovare quelli che soddisfano i vincoli di m.

C'è un modo per fare questo?

Quali tipi di tecniche sono comunemente utilizzati per un CSP come questo? Qualcuno può punto me nella direzione di buoni libri o articoli che parlano di problemi come questo (non solo CSP in generale, ma che coinvolgono CSP continua, al contrario di valori discreti)?

Answer 1

Supponendo che si sta cercando di scrivere le proprie librerie di applicazioni e utilizzare esistenti per fare questo, ci sono scelte in molte lingue, come Python-vincolo , o Cream o < a href = "http://www.emn.fr/z-info/choco-solver/" rel = "nofollow noreferrer"> Choco per Java, oppure CSP per C ++. Il modo in cui hai descritto il problema il suono come siete alla ricerca di un CSP risolutore di uso generale. Ci sono delle proprietà delle funzioni che possono contribuire a ridurre la complessità, come ad esempio essere monotona?

Answer 2

Dato il problema come hai descritto, si può scegliere da ogni gamma r_i uniformemente e buttare via qualsiasi punto m-dimensionale che non riesce a soddisfare il criterio. Sarà distribuito in modo uniforme perché l'originale è distribuita in modo uniforme e l'insieme dei sottoinsiemi è una maschera binaria sopra l'originale.

Senza sapere di più sulla forma della f, non è possibile fare alcuna garanzia sul fatto che il tempo è polinomiale o meno (o addirittura avere alcuna idea di come colpire un luogo che soddisfi il vincolo). Dopo tutto, se f_1 = (x^2 + y^2 - 1) e f_2 = (1 - x^2 - y^2) ed i vincoli sono f_1 < 0 e f_2 < 0, non si può soddisfare questo a tutti (e senza accesso alla forma analitica delle funzioni, si poteva mai sapere con certezza).

Answer 3

Data l'informazione nel messaggio, io non sono sicuro che possa essere fatto a tutti ...

Si consideri:

• Numeri = {1 .... 100}
• m = 1 (mantenerlo semplice)
• F1 = media
• L1 = 10
• U1 = 50

Ora, quanti sottoinsieme di {1} ... 100 si può trovare con che produce una media tra il 10 e il 50?

Answer 4

Questo appare come un problema molto difficile. Per il caso più semplice, con funzioni lineari si potrebbe dare un'occhiata a programmazione lineare.