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

Question

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

У меня есть следующий набор ограничений в 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?

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

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

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

6 9

perl linear-programming linear-algebra constraints

6 ответов:

Я использую Data:: Constraint . Вы пишете небольшие подпрограммы, которые реализуют отдельные ограничения, а затем последовательно применяете все ограничения, которые вы хотите. Я немного расскажу об этом в главеосвоение 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 обрабатывает деревья ограничений, включая обрезку и ветвление. Эти вещи имеют смысл для больших систем, где вы будете смешивать и сопоставлять различные ограничения для различных ситуаций, так как большая часть кода настраивает объекты ограничений. Если у вас есть только одна ситуация, вы, вероятно, просто хотите придерживаться того, что у вас есть.

Удачи, :)

2

"Реальный" ответ потребует разбора выражений и рассуждений об отношениях. Короче говоря, я бы предложил использовать систематический обход пространства значений, а не просто пробовать значения наугад. Например,
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;
        }
    }
}
Я бы поместил переменную с наиболее индивидуальными ограничениями на самый внешний уровень, следующий наиболее ограниченный следующий и т. д.

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

1

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

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

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

1

Похоже, что Simo:: Constrain - это то, что вы хотите

0

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

0

vladr · Accepted Answer · 2009-02-23 08:43:42

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

Типичная задача линейного программирования имеет вид:
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 '

...то есть
$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, C2, ... (например, -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
Примечание

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

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

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

в конечном счете, если вы считаете, что вышесказанное может относиться к вам, вы можете рассчитать различные варианты реализации (с хэшем и без него) и посмотреть, стоит ли это реализовывать или нет.