Удовлетворение ограничений: выбор действительных чисел с определенными характеристиками

У меня есть набор из n действительных чисел. У меня также есть набор функций,

f_1, f_2, ..., f_m.

Каждая из этих функций принимает список чисел в качестве аргумента. У меня также есть набор из m диапазонов,

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

Я хочу несколько раз выбрать подмножество {r_1, r_2, ..., r_k} из 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 ограничений, которым я должен удовлетворять.

Более того, я хочу сделать это так, чтобы набор выбранных мной подмножеств был равномерно распределен по набору всех подмножеств размера k, которые удовлетворяют этим m ограничениям. Не только это, но я хочу сделать это эффективно. Насколько быстро он работает, будет зависеть от плотности решений в пространстве всех возможных решений (если это 0,0, алгоритм может работать бесконечно). (Предположим, что f_i (для любого i) может быть вычислено за постоянный промежуток времени.)

Обратите внимание, что n достаточно велико, чтобы я не мог перебрать проблему. То есть я не могу просто перебрать все подмножества из k элементов и найти, какие из них удовлетворяют ограничениям m.

Есть ли способ сделать это?

Какие методы обычно используются для подобных CSP? Может ли кто-нибудь указать мне на хорошие книги или статьи, в которых говорится о подобных проблемах (не только о CSP в целом, но и о CSP, предполагающих непрерывные, а не дискретные значения)?

1
задан Michael W 27 April 2013 в 01:31
поделиться