Risoluzione dei vincoli geometrici con Minion

2

Sto facendo ricerche sui quadrati, e ho pensato di usare risolutori di problemi di soddisfazione dei vincoli per dimostrare o confutare alcune congetture. Come semplice esempio di problema, considera il seguente compito:

Draw two green squares and two red squares, such that:
 - All squares of the same color are interior-disjoint;
 - All squares of different colors are interior-intersecting.

Per risolvere questo problema, ho scritto il seguente script nella lingua Minion . Per abbreviare il programma, ho utilizzato macro in stile C:

MINION 3

**VARIABLES**
// There are 2 red squares and 2 green squares.
// for every square, x and y are the south-west corner, and s is the side-length:
DISCRETE xred[2] {1..100}
DISCRETE yred[2] {1..100}
DISCRETE sred[2] {1..100}

DISCRETE xgrn[2] {1..100}
DISCRETE ygrn[2] {1..100}
DISCRETE sgrn[2] {1..100}

**CONSTRAINTS**
// The following macros handle intersection relations between squares. 
// Let a and b be names of squares. 
// intersect(a,b) defines constraints meaning "rectangle a intersects rectangle b".
// disjoint(a,b) defines constraints meaning "rectangle a does not intersect rectangle b".

// a and b interior-intersect, if ALL the following equalities hold:
//  a.x + a.s > b.x
//  b.x + b.s > a.x
//  a.y + a.s > b.y
//  b.y + b.s > a.y
#define intersect(a,b) \
watched-and({\
    sumgeq([x##a,s##a,-1], x##b), \
    sumgeq([x##b,s##b,-1], x##a), \
    sumgeq([y##a,s##a,-1], y##b), \
    sumgeq([y##b,s##b,-1], y##a)})

// a and b are interior-disjoint if they do not interior-intersect.
// We need a special macro for this because Minion does not support negation of constraints.
#define disjoint(a,b) \
watched-or({\
    sumleq([x##a,s##a], x##b), \
    sumleq([x##b,s##b], x##a), \
    sumleq([y##a,s##a], y##b), \
    sumleq([y##b,s##b], y##a)\
    })

// Squares of the same color must be disjoint:
disjoint(red[0],red[1])
disjoint(grn[0],grn[1])

// Squares of the different colors must intersect:
intersect(red[0],grn[0])
intersect(red[0],grn[1])
intersect(red[1],grn[0])
intersect(red[1],grn[1])

**EOF**

Ho eseguito il risolutore utilizzando il seguente comando shell:

cpp myfile > myfile.tmp
minion myfile.tmp

Minion ha restituito il seguente risultato

Sol: 1 1 
Sol: 1 4 
Sol: 3 3 

Sol: 1 3 
Sol: 3 1 
Sol: 2 4 

leggi:

  • red # 0 inizia a (1,1) con il lato 3;
  • il rosso # 1 inizia a (1,4) con il lato 3;
  • grn # 0 inizia da (1,3) con il lato 2;
  • grn # 1 inizia a (3,1) con il lato 4;

Ecco come appare sull'aereo:

Ineffetti,iquadratidellostessocoloresonointerni-disgiuntimentreiquadratidicoloridiversisiintersecano!

(Naturalmentecisonomoltealtresoluzioni:Minionrestituiscelaprimasoluzionechetrova,cheèOKperlemieesigenze).

Oralemiedomandesono:

  • Perprimacosa,utilizzolostrumentogiustoperl'attività?C'èunmodoperfareciòchehoappenafattosenzalanecessitàdidefinireesplicitamentecosasignifica"intersecare"?
  • In secondo luogo, utilizzo correttamente la lingua di Minion?
posta Erel Segal-Halevi 20.01.2014 - 09:22
fonte

0 risposte

Leggi altre domande sui tag