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

StackOverflow https://stackoverflow.com/questions/575515

Вопрос

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

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

Это было полезно?

Решение

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

Ваша цель, как я могу заключить из вашего определения 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 вы можете использовать Математика::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

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

  • '...< 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, 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

ПРИМЕЧАНИЕ

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

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

Другие советы

Я использую Данные::Ограничение.Вы пишете небольшие подпрограммы, которые реализуют отдельные ограничения, а затем последовательно применяете все ограничения, которые вы хотите.Я немного рассказываю об этом в Освоение 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

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

Удачи , :)

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

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;
        }
    }
}

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

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

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

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

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

кажется , что Симо::Сдерживать это то, чего ты хочешь

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

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top