¿Cómo resuelvo un conjunto de restricciones en Perl?

math constraints

Question

Tengo el siguiente conjunto de restricciones en Perl (solo un conjunto de restricciones de muestra, no las que realmente necesito):

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

Y necesito encontrar una lista ($a, $b, $c) que cumpla con las restricciones. Mi ingenua solución es

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

Ahora, no se garantiza que esta solución finalice, y es bastante ineficiente en general. ¿Hay una mejor manera de hacer esto en Perl?

Edición: Necesito esto para un generador de prueba aleatorio, por lo que la solución necesita usar funciones aleatorias como rand() . Una solución que es completamente determinista no es suficiente, aunque si esa solución puede darme una lista de combinaciones posibles, puedo seleccionar un índice al azar:

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

Edición 2: las restricciones aquí son simples de resolver con la fuerza bruta. Sin embargo, si hay muchas variables con un amplio rango de valores posibles, la fuerza bruta no es una opción.

Answer 1

En su lugar, crearía un algoritmo que genere un montón de listas válidas, generadas aleatoriamente o no (debe ser trivial), escríbalas en un archivo y luego use ese archivo para alimentar el programa de prueba, para que pueda seleccionar aleatoriamente cualquier lista. quiere.

Answer 2

No estoy seguro de que encuentres una respuesta simple a esto (¡aunque me gustaría que se demuestre que estoy equivocado!).

Parece que su problema sería adecuado para un algoritmo genético . La función de aptitud debe ser fácil de escribir, solo puntúe 1 para cada restricción satisfecha, 0 en caso contrario. AI :: Genetic parece ser un módulo que podría ayudarlo, tanto para escribir el código como para comprender lo que necesita escribir.

Esto debería ser más rápido que un método de fuerza bruta.

Answer 3

Una respuesta "real" requeriría analizar las expresiones y el razonamiento sobre las relaciones. A falta de eso, sugeriría utilizar un recorrido sistemático del espacio de valor, en lugar de simplemente intentar valores al azar. Por ejemplo,

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

Colocaría la variable con las restricciones más individuales en el nivel más externo, luego la siguiente más restringida, etc.

Al menos con esta estructura, no probará la misma combinación varias veces (como es muy probable que lo haga la versión aleatoria) y si la mira funcionar, es posible que vea patrones que le permiten cortar la ejecución.

Answer 4

parece que Simo :: Constrain es lo que quieres

Answer 5

El principal desafío en este problema de optimización es de naturaleza matemática.

Su objetivo, como lo puedo deducir de su definición del método gen_abc , es podar su espacio de búsqueda al encontrar intervalos delimitadores para sus diversas variables ( $a , $b etc.)

La mejor estrategia es extraer tantas restricciones lineales de su conjunto completo de restricciones, intentar inferir los límites (usando técnicas de programación lineal , ver abajo), luego proceder con pruebas exhaustivas (o no determinísticas) de prueba y error espacio variable podado.

Un problema típico de programación lineal es de la forma:

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

Por ejemplo, dadas tres variables, a , c , y las siguientes restricciones lineales:

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

Puede encontrar límites superiores e inferiores para $a , $b y $c siguiente manera:

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

En Perl puedes emplear Math :: LP para este propósito.

EJEMPLO

Una restricción lineal tiene la forma " C eqop C1×$V1 ± C2×$V2 ± C3×$V3 ... ", donde

• eqop es uno de < , > , == , >= , <=
• $V1 , $V2 etc. son variables, y
• C , C1 , C2 , etc. son constantes, posiblemente iguales a 0.

Por ejemplo, dado ...

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

... mueve todas las variables (con sus coeficientes) a la izquierda de la desigualdad, y las constantes solitarias a la derecha de la desigualdad:

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

... y ajuste las restricciones de modo que solo se utilicen igualdades = , <= y >= (in) (suponiendo valores enteros enteros discretos para nuestras variables):

• ''... <C'' se convierte en ''... <= C-1''
• ''...> C'' se convierte en ''...> = C + 1''

...es decir,

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

... luego escribe algo como esto:

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

Por supuesto, lo anterior se puede generalizar a cualquier número de variables V1 , V2 , ... (por ejemplo, $a , $b , $c , $d , ...), con cualquier coeficiente C1 , C2 , ... ( ej. -1, 1, 0, 123, etc.) y cualquier valor constante C (por ejemplo, -1, 1, 30, 29, etc.) siempre que pueda analizar las expresiones de restricción en una representación de matriz correspondiente, como:

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

Aplicando al ejemplo que ha provisto,

  $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

NOTA

Como nota al margen, si se realizan pruebas no deterministas (basadas en rand ), puede o no ser una buena idea realizar un seguimiento (por ejemplo, en un hash) del cual ($a,$b,$c) tuplas ya tienen ha sido probado, para evitar volver a probarlos, si y solo si :

• el método que se prueba es más costoso que una búsqueda hash (este no es el caso con el código de muestra que proporcionó anteriormente, pero puede o no ser un problema con su código real)
• el hash no crecerá en proporciones enormes (o todas las variables están vinculadas por intervalos finitos, cuyo producto es un número razonable, en cuyo caso, verificar el tamaño del hash puede indicar si usted ha explorado completamente el espacio completo), o puede borrar el hash periódicamente, por lo menos por un intervalo de tiempo a la vez que tiene alguna detección de colisión).
  • en última instancia, si cree que lo anterior podría aplicarse a usted, puede medir el tiempo de varias opciones de implementación (con y sin hash) y ver si vale la pena implementarlo o no.

Answer 6

Yo uso Data :: Restraint . Escribe pequeñas subrutinas que implementan las restricciones individuales y luego aplica en serie todas las restricciones que desee. Hablo de esto un poco en Mastering Perl en el capítulo "Subrutinas dinámicas".

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

Hacerlo de esta manera significa que es fácil inspeccionar el resultado para ver qué falló en lugar de una falla general:

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

Si quieres algo más hardcore, mi módulo Brick maneja árboles de restricciones, incluyendo poda y ramificación. Estas cosas tienen sentido para sistemas más grandes donde se mezclarán y combinarán las diversas restricciones para diferentes situaciones, ya que la mayor parte del código está configurando los objetos de restricción. Si solo tienes tu única situación, probablemente solo quieras seguir con lo que tienes.

Buena suerte, :)