Come faccio a risolvere una serie di vincoli in Perl?

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

Domanda

Ho il seguente insieme di vincoli in Perl (solo un esempio di insieme 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 soluzione è ingenuo

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 è garantito il fine, ed è piuttosto inefficiente in generale.C'è un modo migliore per fare questo in Perl?

Edit: Ho bisogno di questo per un casuale generatore di test, quindi la soluzione deve utilizzare funzioni casuali come rand().Una soluzione completamente deterministico non è sufficiente, anche se questa soluzione mi può dare una lista di possibili combinazioni che 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 qui sono semplici da risolvere con la forza bruta.Tuttavia, se ci sono molte variabili, con una vasta gamma di possibili valori, la forza bruta non è un'opzione.

È stato utile?

Soluzione

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

Il vostro obiettivo, come posso dedurre dalla tua definizione di gen_abc metodo, è quello di potare il vostro spazio di ricerca, ricerca di delimitazione intervalli per le varie variabili ($a, $b ecc.)

La strategia migliore è quella di estrarre il maggior numero lineare vincoli dal tuo set completo di vincoli, di tentare di dedurre i limiti (utilizzando programmazione lineare tecniche, vedere di seguito), quindi procedere con esauriente (o non-deterministico) trial-and-error test contro una potata variabile di spazio.

Un tipico un problema di programmazione lineare è della forma:

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

Per esempio, date tre variabili, a, b e c, e i seguenti vincoli lineari:

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

Si possono trovare limiti superiore e inferiore 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, si possono impiegare Per la matematica::LP per questo scopo.

ESEMPIO

Lineare vincolo di forma "C eqop C1×$V1 ± C2×$V2 ± C3×$V3 ..."dove

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

Per esempio, dato...

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

...spostare tutte le variabili (con i loro coefficienti) a sinistra della disuguaglianza, e l'unica costanti a destra della disuguaglianza:

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

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

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

...che è,

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

...poi scrivere qualcosa di simile a questo:

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, il sopra può essere generalizzato a qualsiasi numero di variabili V1, V2, ...(ad es. $a, $b, $c, $d, ...), con tutte coefficienti C1, C2, ...(ad es.-1, 1, 0, 123, etc.) e i valori di costanti C (ad es.-1, 1, 30, 29, etc.) a condizione che si può analizzare il vincolo di espressioni in un corrispondente matrice di rappresentazione, quali:

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

L'applicazione per l'esempio che ci hai 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 non deterministico (randbase di prove, si può o non può essere una buona idea per tenere traccia (ad es.in un hash) di cui ($a,$b,$c) le tuple sono già stati testati, per evitare di testare di nuovo, se e solo se:

  • il metodo è stato testato è più costoso di un hash di ricerca (questo non è il caso con il codice di esempio di cui sopra, ma può o non può essere un problema con il codice vero e proprio)
  • l'hash non crescerà di enormi proporzioni (tutte le variabili sono vincolate da determinati intervalli, il cui prodotto è un numero ragionevole - nel qual caso controllo dell'hash di dimensione possibile indicare se si sono completamente esplorato l'intero spazio o non, o è possibile cancellare l'hash periodicamente, così, almeno per un intervallo di tempo una volta che si hanno alcune rilevamento di collisione.)
    • in definitiva, se si pensa che l'esempio sopra si applicano a voi, nel tempo varie opzioni di implementazione (con e senza hash) e vedere se vale la pena di attuazione o non.

Altri suggerimenti

dati :: Vincolo . Si scrive poco subroutine che implementano i singoli vincoli quindi applicare in serie tutti i vincoli che si desidera. Parlo di questo un po 'in Mastering Perl nel capitolo "Le subroutine dinamici". 

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, href="http://search.cpan.org/dist/Brick" rel="nofollow noreferrer"> modulo mia gestisce alberi di vincoli, tra cui la potatura e la ramificazione. Queste cose hanno un senso per i sistemi più grandi, dove potrete combinare i vari vincoli per diverse situazioni poiché la maggior parte del codice è la creazione di oggetti di vincolo. Se avete solo il vostro una situazione, probabilmente vogliono solo attaccare con quello che hai.

In bocca al lupo,:)

Una risposta "vero" richiederebbe l'analisi delle espressioni e ragionamenti sulle relazioni. In mancanza di ciò, suggerirei usando un attraversamento sistematica dello spazio di valore, piuttosto che i valori solo cercando 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;
        }
    }
}

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

Almeno con questa struttura non si prova la stessa combinazione più volte (come la versione a caso è molto probabile che fare), e se si guarda correre, è possibile vedere modelli di emergere che permette di tagliare l'esecuzione breve.

Non sono sicuro che si sta andando a trovare una risposta semplice a questa (anche se mi piacerebbe essere smentito!).

Sembra che il problema sarebbe adatto per una genetica algoritmo . la forma fisica funzione dovrebbe essere facile da scrivere, solo punteggio 1 per ogni vincolo soddisfatti, 0 altrimenti. AI :: genetici sembrano essere un modulo che potrebbe aiutare, sia per scrivere il codice e per capire ciò che è necessario scrivere.

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

Simo :: vincolare è quello che vuoi

Vorrei invece creare un algoritmo che genera una serie di liste valide, generata in modo casuale o meno (dovrebbe essere banale), li scrivere in un file, e quindi utilizzare tale file per alimentare il programma di test, in modo che possa in modo casuale raccogliere ogni lista che vuole.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top