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

Question

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

f_1, f_2, ..., f_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, которые обычно используются.

Это те ограничения, которые мне нужно выполнить.

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

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

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

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

Answer 1

Предполагая, что вы хотите написать свое собственное приложение и использовать для этого существующие библиотеки, есть варианты на многих языках, например Python-ограничение или Cream или Choco для Java или CSP для C ++.То, как вы описали проблему, звучит так, как будто вы ищете универсальный CSP решатель.Существуют ли какие-либо свойства ваших функций, которые могут помочь снизить сложность, например монотонность?

Answer 2

Учитывая проблему, как вы ее описали, вы можете выбрать из каждого диапазона r_i равномерно и отбросить любую m-мерную точку, которая не соответствует критерию. Он будет равномерно распределен, потому что оригинал распределен равномерно, а набор подмножеств является двоичной маской над оригиналом.

Не зная больше о форме f, вы не можете дать никаких гарантий относительно того, является ли время полиномиальным или нет (или даже иметь представление о том, как попасть в точку, соответствующую ограничению). В конце концов, если f_1 = (x^2 + y^2 - 1) и f_2 = (1 - x^2 - y^2) и ограничения равны f_1 < 0 и f_2 < 0, вы вообще не сможете это удовлетворить (и без доступа к аналитической форме функций вы никогда не сможете знать наверняка) .

Answer 3

Это выглядит как очень сложная проблема.Для простейшего случая с линейными функциями вы можете взглянуть на линейное программирование.

Answer 4

Учитывая информацию в вашем сообщении, я не уверен, что это вообще можно сделать ...

Учтите:

• числа = {1 .... 100}
• m = 1 (сделайте это просто)
• F1 = Среднее
• L1 = 10
• U1 = 50

Теперь, сколько подмножеств из {1 ... 100} вы можете придумать, что в среднем составляет от 10 до 50?