Problemi di soddisfazione di vincoli: esempi
Problemi di soddisfazione di vincoli: esempi
Obbiettivi
Definire formalmente i problemi di soddisfazione con
vincoli (CSP),
Modellazione: rappresentazione di un problema come CSP.
Charire vari aspetti della modellazione:
in generale esistono varie rappresentazioni naturali,
alcune rappresentazioni sono ovvie, altre no,
alcune rappresentazioni si basano su una teoria.
Mostrare la generalita’ della nozione di CSP.
Problemi di soddisfazione di vincoli: esempi
Problemi di soddisfazione di vincoli (CSP)
Dati:
Variabili Y := y1 , . . ., yk ,
Domini D1 , . . ., Dk ,
Vincolo C su Y : sottoinsieme di D1 × . . . × Dk .
Problemi di soddisfazione di vincoli: esempi
Prodotto Cartesiano
Una tupla τ e’ una sequenza di elementi.
Una tupla contenente r elementi e’ detta una r -tupla.
L’i -esimo elemento di una r -tupla, con 1 ≤ i ≤ r , e’ denotato
da τ [i ].
Sia S1 , S2 , . . . , Sr una sequenza di r insiemi. Il prodotto
Cartesiano S1 × S2 × · · · × Sr , o Πii =r
=1 Si , e’ l’insieme
{(a1 , a2 , . . . , ar ) | a1 ∈ S1 , a2 ∈ S2 , . . . , ar ∈ Sr }. Ogni
elemento di Πii =r
=1 Si e’ una r -tupla.
Problemi di soddisfazione di vincoli: esempi
Esempio
Se x, y e z sono tre variabili con dom(x) = dom(y ) = {a, b} e
dom(z) = {a, c}, abbiamo:
(a, a, a),
(a, a, c),
( (a, b, a), )
(a, b, c),
dom(x) × dom(y ) × dom(z) =
.
(b, a, a),
(b, a, c),
(b, b, a),
(b, b, c)
Problemi di soddisfazione di vincoli: esempi
CSP
Dati:
Variabili x1 , . . ., xn ,
Domini D1 , . . ., Dn ,
un problema di soddisfazione di vincoli (CSP) e’:
{C ; x1 ∈ D1 , . . ., xn ∈ Dn }
C – vincoli, ognuno su una sottosequenza di x1 , . . ., xn .
(d1 , . . ., dn ) ∈ D1 × . . . × Dn e’ una soluzione per
{C ; x1 ∈ D1 , . . ., xn ∈ Dn }
se per ogni vincolo C ∈ C su xi1 , . . ., xim
(di1 , . . ., dim ) ∈ C .
Problemi di soddisfazione di vincoli: esempi
Arieta’ dei vincoli
L’arieta’ di un vincolo c e’ il numero di variabili coinvolte in c. Un
vincolo e’ detto:
unario se e solo se la sua arieta’ e’ 1,
binario se e solo se la sua arieta’ e’ 2,
ternario se e solo se la sua arieta’ e’ 3,
non-binario se e solo se la sua arieta’ e’ maggiore di 2.
Problemi di soddisfazione di vincoli: esempi
Esempio: SEND + MORE = MONEY
Rimpiazzare ogni lettera con una cifra diversa in modo che
SEND
+ MORE
MONEY
sia una somma corretta.
Soluzione unica:
9567
+ 1085
10652
Variabili: S, E , N, D, M, O, R, Y ,
Domini:
[1..9] per S, M,
[0..9] per E , N, D, O, R, Y .
Problemi di soddisfazione di vincoli: esempi
Alternative per i vincoli di uguaglianza
1. 1 vincolo di uguaglianza.
1000 · S + 100 · E + 10 · N + D
+ 1000 · M + 100 · O + 10 · R + E
= 10000 · M + 1000 · O + 100 · N + 10 · E + Y
2. 5 vincoli di uguaglianza.
Usare le variabili di riporto C1 , . . ., C4 ∈ [0..1]:
D + E = 10 · C1 + Y ,
C1 + N + R = 10 · C2 + E ,
C2 + E + O = 10 · C3 + N,
C3 + S + M = 10 · C4 + O,
C4 = M.
Problemi di soddisfazione di vincoli: esempi
Alternative per vincoli di disuguaglianza
1. 28 vincoli di disuguaglianza.
x 6= y for x, y ∈ {S, E , N, D, M, O, R, Y }, x ≺ y .
2. Un solo vincolo di disuguaglianza.
Per variabili x1 , . . ., xn con domini D1 , . . ., Dn :
all different(x1 , . . ., xn ) := {(d1 , . . ., dn ) | di 6= dj for i 6= j}.
Usare all different(S, E , N, D, M, O, R, Y ).
Problemi di soddisfazione di vincoli: esempi
3. Modellarlo come un problema IP.
Per x, y ∈ {S, E , N, D, MO, R, Y } trasformare x 6= y in
x − y ≤ 10 − 11zx,y
y − x ≤ 11zx,y − 1
dove zx,y ∈ [0..1].
Svantaggio: 28 nuove variabili.
Problemi di soddisfazione di vincoli: esempi
N Regine
Problema Piazzare n regine su una scacchiera n · n in modo che
non si attacchino.
0Z0ZQZ0Z
Z0L0Z0Z0
QZ0Z0Z0Z
Z0Z0Z0L0
0L0Z0Z0Z
Z0Z0Z0ZQ
0Z0Z0L0Z
Z0ZQZ0Z0
Problemi di soddisfazione di vincoli: esempi
Una possibile modellazione del problema
Variabili: x1 , . . ., xn ,
Domini: [1..n],
Vincoli:
Per i ∈ [1..n − 1] e j ∈ [i + 1..n]:
xi 6= xj (righe),
xi − xj 6= i − j
(diagonali SO – NE),
xi − xj 6= j − i
(diagonali NO – SE).
Problemi di soddisfazione di vincoli: esempi
Problema della zebra
Una strada ha cinque case colorate in modo diverso.
Cinque uomini di diverse nazionalita’ vivono in queste
cinque houses.
Ogni uomo ha una professione diversa, ad ogni uomo
piace una bibita diversa, e ogni uomo ha un diverso
animale.
Problemi di soddisfazione di vincoli: esempi
Problema della zebra
L’inglese vive nella casa rossa.
Lo spagnolo ha un cane.
Il giapponese e’ un pittore.
L’italiano beve te’.
Il norvegese vive nella prima casa sulla sinistra.
Il proprietario della casa verde beve caffe’.
La casa verde e’ sulla destra della casa bianca.
Lo scultore alleva lumache.
Il diplomatico vive nella casa gialla.
Nella casa di centro bevono latte.
Il norvegese vive accanto alla casa blu.
Il violinista beve succo di frutta.
La volpe e’ nella casa accanto a quella del dottore.
Il cavallo e’ nella casa accanto a quella del diplomatico.
Chi ha la zebra e chi beve acqua?
Problemi di soddisfazione di vincoli: esempi
Il problema della zebra
25 Variabili:
nazionalita’: inglese, spagnolo, giapponese, italiano,
norvegese,
animale: cane, lumache, volpe, cavallo, zebra,
professioni: pittore, scultore, diplomatico, violinista,
dottore,
bibita: te, caffe’, latte, succo, acqua,
colore: rosso, verde, bianco, giallo, blu.
Domini: [1...5].
Problemi di soddisfazione di vincoli: esempi
Vincoli:
all different(rosso, verde, bianco, giallo, blu),
all different(inglese, spagnolo, giapponese, italiano,
norvegiese),
all different(cane, lumache, volpe, cavallo, zebra),
all different(pittore, scultore, diplomatico, violinista,
dottore),
all different(te′ , caffe′ , latte, succo, acqua).
Problemi di soddisfazione di vincoli: esempi
Vincoli
L’inglese vive nella casa rossa:
inglese = rosso,
Lo spagnolo ha un cane:
spagnolo = cane,
Il giapponese e’ un pittore:
giapponese = pittore,
L’italiano beve te’:
italiano = te’,
Il norvegese vive nella prima casa sulla sinistra:
norvegese = 1,
Il proprietario della casa verde beve caffe’:
verde = caffe’,
La casa verde e’ sulla destra della casa bianca:
verde = bianco + 1,
Problemi di soddisfazione di vincoli: esempi
Vincoli
Lo scultore alleva lumache:
scultore = lumache,
Il diplomatico vive nella casa gialla:
diplomatico = giallo,
Nella casa di centro bevono latte:
latte = 3,
Il norvegese vive accanto alla casa blu:
|norvegese − blu| = 1,
Il violinista beve succo di frutta:
violinista = succo,
La volpe e’ nella casa accanto a quella del dottore:
|volpe − dottore| = 1,
Il cavallo e’ nella casa accanto a quella del diplomatico:
|cavallo − diplomatico| = 1.
Problemi di soddisfazione di vincoli: esempi
Parole crociate
2
1
4
6
3
5
7
8
Problemi di soddisfazione di vincoli: esempi
Riempire con parole prese da:
HOSES, LASER, SAILS, SHEET, STEER,
HEEL, HIKE, KEEL, KNOT, LINE,
AFT, ALE, EEL, LEE, TIE.
Variabili: x1 , . . ., x8 ,
Domini: x7 ∈ {AFT, ALE, EEL, LEE, TIE}, ecc.
Vincoli: uno per ogni incrocio
C1,2 := {(HOSES, SAILS), (HOSES, SHEET),
(HOSES, STEER), (LASER, SAILS),
(LASER, SHEET), (LASER, STEER)} .
ecc.
Problemi di soddisfazione di vincoli: esempi
Unica Soluzione
1
H
O
2
S
E
A
4
6
8
H
7
A
L
E
I
A
3
S
T
5
K
E
L
E
E
S
E
R
L
Problemi di soddisfazione di vincoli: esempi
Ragionamento temporale qualitativo
Consideriamo il seguente problema.
La riunione e’ durata tutto il giorno.
Ogni persona e’ stata alla riunione per un periodo
continuo di tempo.
La riunione e’ iniziata mentre Mr Jones era presente ed
e’ finita mentre Ms White era presente.
Ms White e’ arrivato dopo che e’ iniziata la riunione.
Anche Director Smith era presente ma e’ arrivato dopo
che Jones e’ andato via.
Mr Brown ha parlato con Ms White in presenza di
Smith.
E’ possibile che Jones e White abbiamo parlato durante
questa riunione?
Problemi di soddisfazione di vincoli: esempi
13 relazioni temporali (Allen ’83)
A before B, B after A
A meets B, B met-by A
A overlaps B, B overlapped-by A
A starts B
B started-by A
A during B
B contains A
A finishes B
B finished-by A
A equals B
Problemi di soddisfazione di vincoli: esempi
A before B
B after A
|-----|
A meets B
B met-by A
|-----|
|-----|
A overlaps B
B overlapped-by A
|------|
|-----|
|-------|
A starts B
B started-by A
|-------|
|-----------|
A during B
B contains A
|-----|
|---------|
A finishes B
B finished-by A
|-------|
|-----------|
Problemi di soddisfazione di vincoli: esempi
La tavola di composizione
Consideriamo tre eventi, A, B e C.
Si sanno: relazioni temporali
AB tra A e B,
BC tra B e C.
Domanda: Quale e’ la relazione temporale AC tra A e C?
Allen ha definito una tabella 13 × 13.
Esempio: se A si sovrappone a (overlaps) B e B e’ prima
di (before) C, allora A e’ before C.
Questo definisce una cella della tabella:
allen(overlaps, before, before).
In totale, 169 celle e 409 triple.
Problemi di soddisfazione di vincoli: esempi
Rappresentazione come un CSP
5 eventi:
M (riunione),
J (presenza di Jones),
B (presenza di Brown),
S (presenza di Smith),
W (presenza di White).
Quindi abbiamo 10 variabili, ognuna associata ad una coppia
ordinata di eventi e con un dominio:
TEMP := {before, after, meets, met-by, overlaps,
overlapped-by, starts, started-by, during,
contains,finishes, finished-by, equals},
REAL-OVERLAP :=
TEMP − {before, after, meets, met-by}
Problemi di soddisfazione di vincoli: esempi
xJ,M ∈ {overlaps, contains, finished-by},
xM,W ∈ {overlaps},
xM,S ∈ REAL-OVERLAP,
xJ,S ∈ {before},
xB,S ∈ REAL-OVERLAP,
xB,W ∈ REAL-OVERLAP,
xS,W ∈ REAL-OVERLAP,
xJ,B , xJ,W , xM,B ∈ TEMP.
Domanda
Se usiamo
– xJ,W ∈ REAL-OVERLAP.
Questo CSP e’ consistente?
Problemi di soddisfazione di vincoli: esempi
Vincoli
allen: la tavola di composizione come una relazione ternaria
(409 triple).
Per ogni tripla ordinata A,B,C degli eventi, un vincolo CA,B,C
sulle variabili xA,B , xB,C , xA,C :
CA,B,C := allen ∩ (DA,B × DB,C × DA,C ).
dove
xA,B ∈ DA,B ,
xB,C ∈ DB,C ,
xA,C ∈ DA,C .
In totale, 10 vincoli.
Problemi di soddisfazione di vincoli: esempi
Ragionamento spaziale quantitativo
Consideriamo il seguente problema.
Due case sono connesse da una strada. La prima casa e’
circondata dal suo giardino o e’ adiacente al suo confine,
mentre la seconda casa e’ circondata dal suo giardino.
Cosa possiamo concludere sulla relazione tra la seconda
casa e la strada?
Problemi di soddisfazione di vincoli: esempi
8 relazioni spaziali
0000000001111111
111111111
0000000
0000000
1111111111111111
000000000
0000000
1111111
000000000
111111111
0000000001111111
111111111
0000000
1111111
B
0000000
000000000
111111111
0000000001111111
111111111
0000000
0000000
1111111
000000000
111111111
A
0000000
1111111
000000000
111111111
000000000
111111111
000000000
111111111
000000000
111111111
000000000
111111111
(a) disjoint(A,B)
000000000
111111111
111111111
000000000
000000000
111111111
000000000
111111111
A
000000000
111111111
000000000
111111111
000000
111111
000000000
111111111
000000
111111
000000000
111111111
000000
111111
B
000000000
111111111
000000
111111
000000000
111111111
000000
111111
000000000
111111111
000000000
111111111
(d) covers(A,B)
coveredBy(B,A)
0000000
1111111
0000000
1111111
0000000
1111111
000000000
111111111
0000000
1111111
111111111
000000000
B
0000000
1111111
000000000
111111111
0000000
1111111
000000000
111111111
0000000
1111111
000000000
111111111
0000000
1111111
000000000
111111111
000000000
111111111
A
000000000
111111111
000000000
111111111
000000000
111111111
000000000
111111111
000000000
111111111
(b) meet(A,B)
111111111
000000000
000000000
111111111
000000000
111111111
000000000
111111111
A
000000000
111111111
000000000
111111111
000000
111111
000000000
111111111
000000
111111
000000000
111111111
000000
111111
B
000000000
111111111
000000
111111
000000000
111111111
000000
111111
000000000
111111111
000000000
111111111
(e) contains(A,B)
inside(B,A)
00000000000000
11111111111111
11111111111111
00000000000000
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
A
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
B
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
00000000000000
11111111111111
(c) equal(A,B)
111111111
000000000
000000000
111111111
000000000
111111111
000000
111111
000000000
111111111
000000
111111
A 111111
000000
000000000
111111111
000000
111111
000000
111111
000000000
111111111
000000
111111
000000
111111
000000000
111111111
B
000000
111111
000000
111111
000000000
111111111
000000
111111
000000
111111
000000000
111111111
000000
111111
000000
111111
000000000
111111111
000000
111111
000000
111111
000000000
111111111
000000
111111
000000000
111111111
000000
111111
(f) overlap(A,B)
RCC8 := {disjoint, meet,
equal, covers,
coveredby, contains,
inside, overlap}.
Problemi di soddisfazione di vincoli: esempi
La tavola di composizione per RCC8
disjoint
meet
equal
inside
coveredby
contains
covers
overlap
disjoint
RCC8
disjoint
disjoint
meet
inside
coveredby
overlap
meet
inside
disjoint
disjoint
meet
contains
covers
overlap
disjoint
meet
inside
coveredby
overlap
inside
coveredby
overlap
disjoint
meet
disjoint
disjoint
meet
disjoint
meet
inside
coveredby
overlap
disjoint
meet
inside
coveredby
overlap
equal
inside
disjoint
disjoint
disjoint
meet
inside
coveredby
overlap
disjoint
meet
equal
coveredby
covers
overlap
meet
disjoint
equal
inside
inside
inside
coveredby
inside
contains
RCC8
coveredby
disjoint
disjoint
meet
coveredby
inside
inside
coveredby
disjoint
meet
contains
covers
overlap
overlap
disjoint
meet
inside
coveredby
overlap
disjoint
meet
overlap
coveredby
overlap
contains
disjoint
meet
contains
covers
overlap
contains
covers
overlap
contains
contains
covers
overlap
contains
covers
disjoint
meet
contains
covers
overlap
disjoint
meet
contains
covers
overlap
meet
contains
covers
overlap
covers
equal
inside
coveredby
contains
covers
overlap
inside
coveredby
overlap
covers
disjoint
meet
inside
coveredby
overlap
disjoint
meet
equal
coveredby
covers
overlap
contains
equal
coveredby
covers
overlap
contains
contains
covers
contains
covers
overlap
disjoint
meet
contains
covers
overlap
overlap
inside
coveredby
overlap
inside
coveredby
overlap
disjoint
meet
contains
covers
overlap
disjoint
meet
contains
covers
overlap
RCC8
overlap
meet
contains
covers
overlap
Problemi di soddisfazione di vincoli: esempi
Rappresentazione come CSP
5 oggetti spaziali:
H1 (casa 1),
G1 (giardino 1),
H2 (casa 2),
G2 (giardino 2),
R (strada.
10 variabili con domini, ognuna associata con una coppia
ordinata di oggetti spaziali:
xH1,G1 ∈ {inside,coveredby},
xH2,G2 ∈ {inside},
xH1,H2 ∈ {disjoint},
xH1,R ∈ {meet},
xH2,R ∈ {meet},
xG1,G2 ∈ {disjoint,meet},
xH1,G2 ∈ {disjoint,meet},
xG1,H2 ∈ {disjoint,meet},
xG1,R ∈ RCC8,
xG2,R ∈ RCC8.
Problemi di soddisfazione di vincoli: esempi
Vincoli
S3 : la tavola di composizione come una relazione ternaria
(193 triple).
Per ogni tripla ordinata A,B,C degli oggetti, un vincolo CA,B,C
sulle variabili xA,B , xB,C , xA,C :
CA,B,C := S3 ∩ (DA,B × DB,C × DA,C ).
dove
xA,B ∈ DA,B ,
xB,C ∈ DB,C ,
xA,C ∈ DA,C .
In totale, 10 vincoli.
Problemi di soddisfazione di vincoli: esempi
Analisi di scene 3D
E
A
F
B
G
C
D
F
A
I
J
H
G
E
D
B
C
Problemi di soddisfazione di vincoli: esempi
Quattro etichette
+ per gli spigoli convessi,
(270 gradi per ruotare)
− per spigoli concavi,
(90 gradi per ruotare)
→ e ← per spigoli di confine
(due piani uno dei quali e’ nascosto).
Esempio
E
F
+
A
+
B
+
G
C
D
Problemi di soddisfazione di vincoli: esempi
Giunzioni legali
+
+
+
+
−
−
+
+
−
−
+
−
+
−
+
−
+
−
−
−
−
−
Problemi di soddisfazione di vincoli: esempi
Rappresentazione come un CSP
Variabili: spigoli,
Domini: {+, −, →, ← },
Vincoli: giunzioni.
Quattro tipi di vincoli: L, fork, T , e arrow .
Esempio:
L := {(→, ← ), ( ← , →), (+, →),
( ← , +), (−, ← ), (→, −)}.
Problemi di soddisfazione di vincoli: esempi
Il cubo come CSP:
arrow (AC , AE , AB),
fork(BA, BF , BD),
L(CA, CD),
arrow (DG , DC , DB),
L(EF , EA),
arrow (FE , FG , FB),
L(GD, GF ).
Problemi di soddisfazione di vincoli: esempi
Rappresentazione come CSP
C’e anche bisogno di
edge := {(+, +), (−, −), (→, ← ), ( ← , →)}.
edge cattura il carattere complementare di → e ← .
Nove vincoli:
edge(AB, BA),
edge(AC , CA),
edge(CD, DC ),
edge(BD, DB),
edge(AE , EA),
edge(EF , FE ),
edge(BF , FB),
edge(FG , GF ),
edge(DG , GD).
Problemi di soddisfazione di vincoli: esempi
CSP rispetto a SAT
CSP “generalizza” SAT.
Esempio: la formula CNF:
(x ∨ y ∨ ¬z) ∧ (¬w ∨ ¬x) ∧ (w ∨ ¬y ∨ z)
puo’ essere modlelata come il seguente CSP:
variabili {w , x, y , z} con
dom(w ) = dom(x) = dom(y ) = dom(z) = {false, true}
vincoli {cxyz : x ∨ y ∨ ¬z, cwx : ¬w ∨ ¬x, cwyz : w ∨ ¬y ∨ z}
Problemi di soddisfazione di vincoli: esempi
Problemi di ottimizzazione di vincoli
Dato:
— un CSP
P := hC ; x1 ∈ D1 , . . ., xn ∈ Dn i,
— una funzione
obj : Sol → R
(P, obj) e’ un problema di ottimizzazione di vincoli
(COP).
Problema: Trovare una soluzione d di P per cui il valore
obj(d) e’ ottimo (massimo).
Problemi di soddisfazione di vincoli: esempi
Esempio: problema dello zaino
Dato: uno zaino di un volume fissato e n oggetti, ognuno con un
volume e un value, trovare una collezione di questi oggetti con
valore totale massimo che entra nello zaino.
Rappresentazione come COP:
Dato: zaino con volume v e n oggetti con volumi a1 , ..., an e
valori b1 , ..., bn .
Variabili: x1 , . . ., xn ,
Domini: {0, 1},
Vincoli:
n
X
a i · xi ≤ v ,
i =1
Funzione obbiettivo:
n
X
bi · xi .
i =1
Problemi di soddisfazione di vincoli: esempi
Esempio: righello di Golomb
righello di Golomb con m tacche: una sequenza ordinata di
m numeri naturali tali che le distanze tra coppie di tali numeri
sono tutte diverse.
L’elemento piu’ grande del righello di Golomb e’ la sua
lunghezza.
Un righello di Golomb con m tacche ottimo: un righello
con lunghezza minima.
Problemi di soddisfazione di vincoli: esempi
Righello di Golomb ottimo con 5 tacche
0, 1, 4, 9, 11
e’ un righello di Golomb con 5 tacche. Infatti, le distanze sono:
per elementi distanti 1: 1, 3, 5, 2,
per elementi distanti 2: 4, 8, 7,
per elementi distanti 3: 9, 10,
per elementi distanti 4: 11.
0,1,4,9,11 e’ un righello di Golomb ottimo con 5 tacche.
Il piu’ lungo righello di Golomb ottimo ha 21 tacche e ha
lunghezza 333.
Problemi di soddisfazione di vincoli: esempi
Rappresentazione come COP
Fissiamo m.
Coppia: due numeri i , j tali che
1 ≤ i < j ≤ m.
Coppie i , j e k, l sono
– diverse se i 6= k o j 6= l ,
– disgiunte se i 6= k e j 6= l .
Esempio:
1,3 e 1,4 sono diverse ma non disgiunte.
1,3 e 2,4 sono disgiunte (e quindi diverse).
Problemi di soddisfazione di vincoli: esempi
Rappresentazione 1
Variabili: x1 , . . ., xm ,
Domini: N ,
Vincoli:
xi < xi +1 per i ∈ [1..m − 1],
xj − xi 6= xl − xk per tutte le coppie diverse i , j e k, l .
Funzione obbiettivo: −xm .
Problemi di soddisfazione di vincoli: esempi
Rappresentazione come COP
Rappresentazione 2
Vincoli:
xi < xi +1 per i ∈ [1..m − 1],
xj − xi 6= xl − xk per tutte le disgiunte i , j e k, l .
Rappresentazione 3
Variabili: x1 , . . ., xm , zi ,j per ogni i , j,
Domini:
N per x1 , . . ., xm ,
N \ {0} per zi ,j ,
Vincoli:
zi ,j = xj − xi per ogni coppia i , j,
zi ,j 6= zk,l per tutte le coppie diverse (o disgiunte) i , j e k, l .
Problemi di soddisfazione di vincoli: esempi
Rappresentazione 4
Rimpiazzare i vincoli di disuguaglianza con un singolo vincolo
all different sulle variabili zi ,j .
Problemi di soddisfazione di vincoli: esempi
Rappresentazioni diverse come CSP
Un problema di assegnamento di etichette a microcodice
CSP: 187 variabili a dominio intero finito,
IP: 2024 variabili Booleane,
Un problema di ”packing”
CSP: 7 variabili a dominio intero finito, 2 vincoli,
IP: 42 variabili Booleane, 18 vincoli,
Un problema di schedulazione di un torneo di golf
CP: 176 variabili,
IP 1: 2574 variabili,
IP 2: 592 variabili.
Problemi di soddisfazione di vincoli: esempi
Riassunto capitolo 2
Definizione formale di Problema di soddisfazione di vincoli
(CSP),
Modellazione: rappresentazione di un problema come CSP.
Vari aspetti della modellazione:
in generale, varie rappresentazioni naturali,
alcune banali, altre no,
alcune si basano su una teoria specifica del dominio.
Generalita’ della nozione di CSP.
Problemi di soddisfazione di vincoli: esempi