Come posso risolvere una serie di vincoli in Perl?

Question

Ho la seguente serie di vincoli in Perl (solo un insieme campione di vincoli, non quelli che ho davvero bisogno):

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

e ho bisogno di trovare un elenco ($a, $b, $c) che soddisfano i vincoli. La mia ingenua soluzione è

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

Ora, questa soluzione non è garantita alla fine, ed è piuttosto inefficiente in generale. C'è un modo migliore per farlo in Perl?

Modifica: Ho bisogno di questo per un generatore di test casuale, quindi la soluzione deve utilizzare funzioni casuali come rand(). Una soluzione che è completamente deterministica non è sufficiente, anche se questa soluzione può darmi un elenco di possibili combinazioni posso selezionare un indice a caso:

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

Edit 2: I vincoli sono semplici da risolvere con forza bruta. Tuttavia, se ci sono molte variabili con una vasta gamma di valori possibili, la forza bruta non è un'opzione.

Answer 1

La principale sfida in questo problema di ottimizzazione è di natura matematica.

L'obiettivo, come posso dedurre dalla definizione del metodo gen_abc, è di ridurre lo spazio di ricerca individuando intervalli di delimitazione per le varie variabili ($a, $b ecc.)

La strategia migliore è quella di estrarre il maggior numero di lineari vincoli dal set completo di vincoli, il tentativo di dedurre i limiti (utilizzando linear programming tecniche, vedi sotto), quindi procedere con esaustivo (o non-deterministico) trial- e-error test contro uno spazio variabile potato.

Un tipico linear programming problem è della forma:

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

Ad esempio, dato tre variabili, a, b e c, ed i seguenti vincoli lineari:

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

Potete trovare superiore e limiti inferiori per $a, $b e $c come segue:

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

In Perl è possibile utilizzare Math::LP a questo scopo.

---

ESEMPIO

Un vincolo lineare è del tipo "C eqop C1×$V1 ± C2×$V2 ± C3×$V3 ...", dove

• eqop è uno dei <, >, ==, >=, <=
• $V1 , $V2 ecc sono variabili, e
• C, C1, C2 ecc sono costanti, possibilmente pari a 0.

Ad esempio, dato ...

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

... spostare tutto variabili (con i loro coefficienti) a sinistra della disuguaglianza e le costanti solitarie a destra della disuguaglianza:

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

... e regolare i vincoli in modo che solo =, <= e >= (a) uguaglianze sono utilizzati (assumendo cioè i valori interi discreti per le nostre variabili):

• '... < C' diventa'. .. < = C-1'
• '...> C' diventa' ...> = C + 1'

... cioè,

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

...poi scrivere qualcosa del genere:

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 

Naturalmente, quanto sopra può essere generalizzato a qualsiasi numero di variabili V1, V2, ... (ad esempio $a, $b, $c, $d, ...), con qualsiasi coefficienti C1, C2, ... (ad esempio -1, 1, 0, 123, ecc.) e qualsiasi valore costante C (ad esempio -1, 1, 30, 29, ecc.) purché sia ​​possibile analizzare le espressioni di vincolo in un corrispondente matrice di rappresentazione come:

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

Applicando l'esempio che ci ha fornito,

$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

Come nota a margine, se si esegue (rand basati su test) non deterministici, si può o non può essere una buona idea per tenere traccia (es in un hash) di cui ($a,$b,$c) tuple sono già stati testati, per evitare di testare nuovamente, se e solo se:

• il metodo essendo testato è più costoso di una ricerca hash (questo non è il caso con il codice di esempio che hai fornito sopra, ma potrebbe essere o meno un problema con il tuo codice reale)
• l'hash non crescerà in proporzioni enormi (o tutte le variabili sono legate da intervalli finiti, il cui prodotto è un numero ragionevole - in quale caso controllando la dimensione dell'hash può indicare se hai esplorato completamente l'intero spazio o no, oppure puoi cancellare l'hash periodicamente così almeno per un intervallo di tempo alla volta hai qualche collisione det .)
  • in ultima analisi, se pensi che quanto sopra potrebbe applicarti, puoi tempo varie opzioni di implementazione (con e senza hash) e vedere se vale la pena implementarle o meno.

Answer 2

sembra che Simo::Constrain è quello che volete

Answer 3

Una risposta "vero" richiederebbe l'analisi delle espressioni e ragionamenti sulle relazioni. A parte questo, suggerirei di utilizzare una traversata sistematica dello spazio di valori, piuttosto che provare i valori a caso. Per esempio,

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

avevo messo la variabile con più singoli vincoli al livello più esterno, il prossimo più costretti successiva, ecc

Almeno con questa struttura non sarà possibile testare la stessa combinazione più volte (come è probabile che la versione casuale sia molto probabile) e se la guardi correre, potresti vedere dei pattern emergenti che ti permettono di ridurre l'esecuzione.

Answer 4

Non sono sicuro che troverete una risposta semplice a questo (anche se mi piacerebbe essere smentito!).

Sembra che il tuo problema sarebbe adatto per un genetic algorithm. La funzione fitness dovrebbe essere facile da scrivere, solo punteggio 1 per ogni vincolo soddisfatto, 0 altrimenti. AI::Genetic sembra essere un modulo che potrebbe aiutarti, sia per scrivere il codice che per capire cosa hai bisogno di scrivere.

Questo dovrebbe essere più veloce di un metodo di forza bruta.

Answer 5

Vorrei invece creare un algoritmo che genera un gruppo di liste valide, generate casualmente o meno (dovrebbe essere banale), scriverle in un file e quindi utilizzare quel file per alimentare il programma di test, in modo che possa casualmente scegli una lista che vuole.

Answer 6

io uso Data::Constraint. Scrivi piccole subroutine che implementano i singoli vincoli, quindi applica in serie tutti i vincoli che desideri. Ne parlo un po 'in Mastering Perl nel capitolo "Subroutine dinamiche".

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

Facendo in questo modo significa che è facile per ispezionare il risultato di vedere ciò che non è riuscito invece di un fallimento globale:

 
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 

Se volete qualcosa di più hardcore, il mio modulo Brick gestisce alberi di vincoli, tra cui potatura e ramificazione. Queste cose hanno senso per i sistemi più grandi in cui si combinano i vari vincoli per le diverse situazioni poiché la maggior parte del codice sta configurando gli oggetti vincolo. Se hai solo la tua situazione, probabilmente vuoi semplicemente mantenere quello che hai.

Buona fortuna, :)