Как решить набор ограничений в Perl?

Question

У меня есть следующий набор ограничений в Perl (просто набор образцов ограничений, а не те, что я на самом деле нужно):

$a < $b 
$b > $c 
$a is odd => $a in [10..18] 
$a > 0 
$c < 30 

И мне нужно, чтобы найти список ($a, $b, $c), которые удовлетворяют ограничениям. Мое наивное решение -

sub check_constraint { 
    my ($a, $b, $c) = @_; 
    if !($a < $b) {return 0;} 
    if !($b > $c) {return 0;} 
    if (($a % 2) && !(10 <= $a && $a <= 18)) {return 0;} 
    if !($a > 0) {return 0;} 
    if !($c < 30) {return 0;} 
    return 1; 
} 

sub gen_abc { 
    my $c = int rand 30; 
    my $b = int rand $c; 
    my $a = int rand $b; 
    return ($a, $b, $c); 
} 

($a, $b, $c) = &gen_abc(); 
while (!&check_constraint($a, $b, $c)) { 
    ($a, $b, $c) = &gen_abc(); 
} 

Теперь это решение не гарантируется на конец и в целом довольно неэффективно. Есть ли лучший способ сделать это в Perl?

Редактировать: Мне нужно это для случайного тестового генератора, поэтому в решении должны использоваться случайные функции, такие как rand(). Решение, которое абсолютно детерминированным не является достаточно, хотя, если это решение может дать мне список возможных комбинаций можно выбрать индекс случайным образом:

@solutions = &find_allowed_combinations(); # solutions is an array of array references 
$index = int rand($#solutions); 
($a, $b, $c) = @$solution[$index]; 

Edit 2: Ограничения здесь просты решить с грубая сила. Однако, если есть много переменных с большим рядом возможных значений, грубая сила не является опцией.

Answer 1

Основная проблема в этой проблеме оптимизации носит математический характер.

Ваша цель, поскольку я могу сделать вывод из вашего определения метода gen_abc, заключается в том, чтобы обрезать ваше пространство поиска, найдя ограничивающие интервалы для различных переменных ($a, $b и т. Д.)

Лучшая стратегия для извлечения столько линейных ограничений из вашего полного набора ограничений, попытка вывести границы (используя linear programming метод, см ниже), а затем приступить к исчерпывающему (или недетерминированы) Триал и-ошибки против обрезанного пространства переменных.

Типичный linear programming problem имеет вид:

minimize (maximize) <something> 
subject to <constraints> 

Например, если три переменные, a, b и c, а также следующие линейные ограничения:

<<linear_constraints>>:: 
    $a < $b 
    $b > $c 
    $a > 0 
    $c < 30 

Вы можете найти верхнюю и нижние границы для $a, $b и $c следующим образом:

lower_bound_$a = minimize $a subject to <<linear_constraints>> 
upper_bound_$a = maximize $a subject to <<linear_constraints>> 
lower_bound_$b = minimize $b subject to <<linear_constraints>> 
upper_bound_$b = maximize $b subject to <<linear_constraints>> 
lower_bound_$c = minimize $c subject to <<linear_constraints>> 
upper_bound_$c = maximize $c subject to <<linear_constraints>> 

Для перевода на Perl вы можете использовать Math::LP.

---

ПРИМЕР

Линейное ограничение имеет вид "C eqop C1×$V1 ± C2×$V2 ± C3×$V3 ...", где

• eqop является одним из <, >, ==, >=, <=
• $V1 , $V2 и т.д. являются переменными, и
• C, C1, C2 и т.д. являются постоянными, возможно, равны 0.

К примеру, данный ...

$a < $b 
$b > $c 
$a > 0 
$c < 30 

... переместить все переменные (с их коэффициентами) слева от неравенства, а одиночные константы справа от неравенства:

$a - $b  < 0 
    $b - $c > 0 
$a   > 0 
      $c < 30 

... и настроить ограничения таким образом, что только =, <= и >= (в) Равенства используются (предполагается, что дискретные т.е. целые значения для наших переменных):

• '... < C' становится». .. < = C-1'
• '...> C' становится»...> = C + 1'

... то есть,

$a - $b  <= -1 
    $b - $c >= 1 
$a   >= 1 
      $c <= 29 

...затем написать что-то вроде этого:

use Math::LP qw(:types);    # imports optimization types 
use Math::LP::Constraint qw(:types); # imports constraint types 

my $lp = new Math::LP; 

my $a = new Math::LP::Variable(name => 'a'); 
my $b = new Math::LP::Variable(name => 'b'); 
my $c = new Math::LP::Variable(name => 'c'); 

my $constr1 = new Math::LP::Constraint(
    lhs => make Math::LP::LinearCombination($a, 1, $b, -1), # 1*$a -1*$b 
    rhs => -1, 
    type => $LE, 
); 
$lp->add_constraint($constr1); 
my $constr2 = new Math::LP::Constraint(
    lhs => make Math::LP::LinearCombination($b, 1, $c, -1), # 1*$b -1*$c 
    rhs => 1, 
    type => $GE, 
); 
$lp->add_constraint($constr2); 

... 

my $obj_fn_a = make Math::LP::LinearCombination($a,1); 
my $min_a = $lp->minimize_for($obj_fn_a); 
my $max_a = $lp->maximize_for($obj_fn_a); 

my $obj_fn_b = make Math::LP::LinearCombination($b,1); 
my $min_b = $lp->minimize_for($obj_fn_b); 
my $max_b = $lp->maximize_for($obj_fn_b); 

... 

# do exhaustive search over ranges for $a, $b, $c 

Конечно, выше может быть обобщена на любое количество переменных V1, V2 ... (например, $a, $b, $c, $d, ...), с любым коэффициенты C1,, ... (например, -1, 1, 0, 123 и т. д.) и любые постоянные значения C (например, -1, 1, 30, 29 и т. д.), если вы можете анализировать выражения ограничений в соответствующее матричное представление, такое как:

V1 V2 V3  C 
[ C11 C12 C13 <=> C1 ] 
[ C21 C22 C23 <=> C2 ] 
[ C31 C32 C33 <=> C3 ] 
... ... ... ... ... ... 

Применяя к примеру, вы предоставили,

$a $b $c  C 
[ 1 -1 0 <= -1 ] <= plug this into a Constraint + LinearCombination 
[ 0 1 -1 >= 1 ] <= plug this into a Constraint + LinearCombination 
[ 1 0 0 >= 1 ] <= plug this into a Constraint + LinearCombination 
[ 0 0 1 <= 29 ] <= plug this into a Constraint + LinearCombination 

---

ПРИМЕЧАНИЕ

В качестве примечания, если выполнение недетерминированных (rand -На) испытаний, он может или не может быть хорошая идея отслеживать (например, в хэш), из которых ($a,$b,$c) кортежи уже испытанной, чтобы избежать снова испытывать их, тогда и только тогда, когда:

• метод испытывается дороже хэш-поиска (это не так с кодом примера, который вы указали выше, но может или не может быть проблемой с вашим реальным кодом)
• хэш не будет расти до огромных размеров (либо все переменные связаны конечными интервалами, продукт которых является разумным числом - в в каком случае проверка размера хэша может указывать, полностью ли вы изучили все пространство или нет, или вы можете периодически очищать хэш, так что, по крайней мере, за один временной интервал в то время, когда у вас есть некоторое столкновение det ection.)
  • В конечном счете, если вы считаете, что вышеуказанное может применяться к вам, вы можете использовать различные варианты реализации (с хешем и без него) и посмотреть, стоит ли это реализовать или нет.

Answer 2

кажется, что Simo::Constrain является то, что вы хотите

Answer 3

А «реальный» ответ потребует разбора выражения и рассуждения об отношениях. Короче говоря, я бы предложил использовать систематический обход пространства значений, а не просто попробовать значения наугад. Например,

my $count = 0; 
for (my $c = 0; $c < 30 && $count < $SOMELIMIT; ++$c) { 
    # check all other constraints on only $c here 
    # next if any fail 
    for (my $b = $c + 1; $b < $UPPERLIMIT && $count < $SOMELIMIT; ++$b) { 
     # check all other constraints on only $b and $c here 
     # next if any fail 
     for (my $a = 1; $a < $b && $count < $SOMELIMIT; ++$a) { 
      #check all remaining constraints on $a, $b, and $c here 
      # next if any fail 
      # now use surviving combinations 
      ++$count; 
     } 
    } 
} 

Я бы поставил переменную с самыми индивидуальными ограничениями на внешнем уровне, рядом наиболее ограничены рядом и т.д.

По крайней мере, с этой структурой вы не будете испытывать ту же самую комбинацию несколько раз (как вероятна случайная версия), и если вы посмотрите, как он запускается, вы можете увидеть шаблоны, которые позволяют сократить выполнение.

Answer 4

Я не уверен, что вы найдете простой ответ на этот вопрос (хотя я бы хотел, чтобы вас доказали неправильно!).

Кажется, что ваша проблема была бы хорошо подходит для genetic algorithm. Функцию фитнеса следует легко написать, просто забив 1 за каждое удовлетворенное ограничение, 0 в противном случае. AI::Genetic, кажется, модуль, который может помочь вам, как написать код, так и понять, что вам нужно написать.

Это должно быть быстрее, чем метод грубой силы.

Answer 5

Я бы вместо этого создал алгоритм, который генерирует кучу допустимых списков, случайным образом сгенерированных или нет (это должно быть тривиально), записать их в файл, а затем использовать этот файл для подачи тестовой программы, чтобы он мог случайно выберите любой список, который он хочет.

Answer 6

Я использую Data::Constraint. Вы пишете небольшие подпрограммы, которые реализуют индивидуальные ограничения, затем последовательно применяют все требуемые ограничения. Я немного об этом говорю в Mastering Perl в главе «Динамические подпрограммы».

 
use Data::Constraint; 

Data::Constraint->add_constraint(
    'a_less_than_b', 
    run   => sub { $_[1] < $_[2] }, 
    description => "a < b", 
    ); 

Data::Constraint->add_constraint(
    'b_greater_than_c', 
    run   => sub { $_[2] > $_[3] }, 
    description => "b > c", 
    ); 

Data::Constraint->add_constraint(
    'a_greater_than_0', 
    run   => sub { $_[1] > 0 }, 
    description => "a > 0", 
    ); 

Data::Constraint->add_constraint(
    'c_less_than_30', 
    run   => sub { $_[3] < 30 }, 
    description => "c < 30", 
    ); 

Data::Constraint->add_constraint(
    'a_is_odd_between_10_18', 
    run   => sub { 
     return 1 if($_[1] < 10 or $_[1] > 18); 
     return 0 unless $_[1] % 2, 
     }, 
    description => "a is odd between 10 and 18", 
    ); 

for (1 .. 10) 
    { 
    my($a, $b, $c) = gen_abc(); 
    print "a = $a | b = $b | c = $c\n"; 

    foreach my $name (Data::Constraint->get_all_names) 
     { 
     print "\tFailed $name\n" 
      unless Data::Constraint->get_by_name($name)->check($a, $b, $c), 
     } 
    } 

sub gen_abc { 
    my $c = int rand 30; 
    my $b = int rand $c; 
    my $a = int rand $b; 
    return ($a, $b, $c); 
} 

Делая это таким образом означает, что легко проверить результат, чтобы увидеть то, что не удалось вместо общего сбоя:

 
a = 2 | b = 4 | c = 5 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 2 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 2 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 7 | b = 14 | c = 25 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 29 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 0 | c = 20 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 4 | c = 22 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 4 | b = 16 | c = 28 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 22 | c = 26 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 
a = 0 | b = 3 | c = 6 
    Failed a_greater_than_0 
    Failed a_less_than_b 
    Failed b_greater_than_c 

Если вы хотите что-то больше хардкора, мой Brick модуль обрабатывает деревья ограничений, включая обрезку и разветвление. Эти вещи имеют смысл для более крупных систем, где вы будете смешивать и сопоставлять различные ограничения для разных ситуаций, поскольку большая часть кода настраивает объекты ограничений. Если у вас есть только одна ситуация, вы, вероятно, просто хотите придерживаться того, что у вас есть.

Удачи, :)