Capitolo 3:
Vincoli a dominio finito
1
Vincoli a dominio finito
Problemi di soddisfazione di vincoli
 Un risolutore con backtracking
 Consistenza su nodi e archi
 Consistenza sui limiti
 Consistenza generalizzata
 Ottimizzazione per vincoli aritmetici

2
Vincoli a dominio finito
Una classe importante di problemi con
vincoli
 Usati per moellare problemi con vincoli che
hanno a che fare con delle scelte:

 es.:

Scheduling, routing and timetabling
Il piu’ grande impatto industriale della
programmazione con vincoli e’ stato su
questi problemi
3
Problemi di soddisfazione con
vincoli

Un problema di soddisfazione con vincoli
(CSP) consiste di:
 Un
vincolo C su variabli x1,..., xn
 Un dominio D che mappa ogni variabile xi ad
un insieme finito di possibili valori d(xi)

E’ inteso come il vincolo
C  x1  D( x1) xn  D( xn)
4
Colorazione di mappe
Un CSP classico e’ il problema della colorazione di
mappe in modo che regioni adiacenti non abbiamo lo
tesso colore.
Es.: puo’ la mappa
dell’Australia essere colorata
con 3 colori?
NT
Q
WA  NT  WA  SA  NT  SA 
NT  Q  SA  Q  SA  NSW 
SA  V  Q  NSW  NSW  V
D(WA)  D( NT )  D( SA)  D(Q) 
D( NSW )  D(V )  D(T ) 
{red , yellow, blue}
WA
SA
NSW
V
T
5
4-regine
Piazzare 4 regine su una scacchiera 4 x 4 in modo che
non si attacchino.
Q1
Q2
Q3
Q4
Quattro variabili Q1, Q2,
1
Q3, Q4 che
rappresentano la riga
2
della regine in ogni
colonna. Dominio di ogni
3
variabile: {1,2,3,4}
One solution! -->
4
6
4-regine
I vincoli:
Non sulla stessa riga:
Q1  Q2  Q1  Q3  Q1  Q4 
Q2  Q3  Q2  Q4  Q3  Q4 
Non nella stessa diagonale Q1  Q2  1  Q1  Q3  2  Q1  Q4  3 
up:
Q2  Q3  1  Q2  Q4  2  Q3  Q4  1 
Not nella stessa diagonale Q1  Q2  1  Q1  Q3  2  Q1  Q4  3 
down:
Q2  Q3  1  Q2  Q4  2  Q3  Q4  1
7
Lo zaino del ladro
Un ladro ha uno zaino con capacita’ 9, e deve
scegliere cose da rubare in modo da fare un
profitto di almeno 30
object
whiskey
profit
15
size
4
perfume
cigarretes
10
7
3
2
4W  3P  2C  9  15W  10 P  7C  30
Quale dovrebbe essere il dominio delle variabili?
8
Risolutore con backtracking


Il modo piu’ semplice per risolvere csps e’ di
enumerare le possibili soluzioni
Il risolutore con backtracking:



Enumera i valori per una variabile alla volta
Ad ogni passo, controlla che nessun vincolo primitivo
sia violato
Assumiamo che satisfiable(c) ritorna false quando
il vincolo primitivo c senza variabili e’ non
soddisfacibile
9
Partial Satisfiable
Controlla se un vincolo e’ non
soddisfacibile a causa di un vincolo
primitivo senza variabili
 Partial_satisfiable(c)

 For
ogni vincolo primitivo c in C
 If vars(c) e’ vuoto
 If satisfiable(c) = false return false
 Return true
10
Backtrack Solve

Back_solve(c,d)
vars(c) e’ vuoto return partial_satisfiable(c)
 Sceglie x in vars(c)
 For ogni valore d in d(x)
 Sia C1 uguale a C con x rimpiazzato da d
 If partial_satisfiable(c1) then
 If back_solve(c1,d) then return true
 Return false
 If
11
Backtracking Solve
X  Y Y  Z
D( X )  D(Y )  D( Z )  {1,2}
X  Y Y  Z
Choose
Variablevar
var
X YZ
X
Y
Sceglie
domain
domain {1,2}
{1,2}
dominio
{1,2}
X 1
X 2
2  Y Y  Z
1 Y Y  Z
Y 1
Y 2
1  1 1  Z
1 2 2  Z
partial_satisfiable false Z  1
Nessuna variabile,
e false
1 2 2 1
2  1 1  Z
Z 2
2  22  Z
Nessuna variabile,
e false
1 2 2  2
12
Consistenza sui nodi e sugli
archi




Idea di base: trovare un CSP equivalente
all’originale con domini delle variabili piu’ piccoli
Esamina 1 vincolo primitivo alla volta
Node consistency: (vars(c)={x}) rimuove dal
dominio di x ogni valore che non soddisfa c
Arc consistency: (vars(c)={x,y}) rimuove da d(x)
valori per cui non c’e’ nessun valore in d(y) tale
che (x,y) soddisfa c, e vice versa
13
Node Consistency

Un vincolo primitivo c e’ node consistent
con dominio D se |vars(c)| !=1 o
 Se
vars(c) = {x} allora per ogni d in d(x)
 X assegnato a d e’ una soluzione di c

Un CSP e’ consistente sui nodi se ogni
vincolo primitivo e’ consistente sui nodi
14
Esempi
CSP che non e’ consistente sui nodi (vedere Z):
X  Y Y  Z  Z  2
D( X )  D(Y )  D( Z )  {1,2,3,4}
CSP che e’ consistente sui nodi:
X  Y Y  Z  Z  2
D( X )  D(Y )  {1,2,3,4}, D( Z )  {1,2}
Il problema della colorazione della mappa e
quello delle 4 regine sono consistenti sui nodi.
15
Ottenere la consistenza sui
nodi


Node_consistent(c,d)
 For ogni vincolo primitivo c in C
 D := node_consistent_primitive(c, D)
 Return D
Node_consistent_primitive(c, D)
 If |vars(c)| =1 then
 Sia {x} = vars(c)
D( x) : {d  D( x) | {x  d} e' una soluzione di c}

Return D
16
Consistenza sugli archi

Un vincolo primitivo c e’ consistente sugli
archi con dominio D se |vars{c}| != 2 o
 Vars(c)
= {x,y} e per ogni d in d(x) esiste e in
d(y) tale che
{x  d , y  e} e' una soluzione di c
E

in modo simile per y
Un CSP e’ consistente sugli archi se ogni
vincolo primitivo e’ consistente sugli archi
17
Esempi
CSP consiste sui nodi ma non sugli archi:
X  Y Y  Z  Z  2
D( X )  D(Y )  {1,2,3,4}, D( Z )  {1,2}
Esempio: il valore 4 per X e X < Y.
CSP equivalente ma consistente sugli archi:
X  Y Y  Z  Z  2
D( X )  D(Y )  D( Z )  
La colorazione della mappa e le 4 regine sono
consistenti sugli archi.
18
Ottenere la consistenza sugli
archi

Arc_consistent_primitive(c, D)

If |vars(c)| = 2 then
D( x) : {d  D( x) | esiste e  D( y ),
{x  d , y  e} e' una sol. di c}
D( y ) : {e  D( y ) | esiste d  D( x),
{x  d , y  e} e' una sol. di c}


Return D
Rimuove valori che non sono arc-onsistent con c
19
Ottenere la consistenza sugli
archi

Arc_consistent(c,d)
 Repeat
W
:= d
 For ogni vincolo primitivo c in C
 D := arc_consistent_primitive(c,d)
 Until W = D
 Return D

Una versione molto naive
20
Usare la consistenza ui nodi e
sugli archi


Possiamo costruire risolutori basati sui metodi di
consistenza
Due tipi importanti di dominio:



False domain: alcune variabili hanno il dominio vuoto
Valuation domain: ogni variabile ha un solo valore nel
dominio
 Estendere satisfiable a CSP con domini
valutazione
21
Risolutore basato su
consistenza su nodi e archi
D := node_consistent(C,D)
 D := arc_consistent(C,D)
 if D e’ un dominio falso

 return

if D e’ un dominio valutazione
 return

false
satisfiable(C,D)
return unknown
22
Esempio
Colorare l’Australia: con vincoli
WA  red  NT  yellow
WA NT SA
Q NSW V
T
Consistenza
sui nodi
WA  NT
WA  SA
NT  SA
NT  Q
SA  V
SA  Q
Q  NSW
SA  NSW
NSW  V
23
Esempio
Colorare l’Australia: con vincoli
WA  red  NT  yellow
WA NT SA
Q NSW V
T
Consistenza
sugli archi
WA  NT
WA  SA
NT  SA
NT  Q
SA  V
SA  Q
Q  NSW
SA  NSW
NSW  V
24
Esempio
Colorare l’Australia: con vincoli
WA  red  NT  yellow
WA NT SA
Q NSW V
T
Consistenza
sugli archi
WA  NT
WA  SA
NT  SA
NT  Q
SA  V
SA  Q
Q  NSW
SA  NSW
NSW  V
25
Esempio
Colorare l’Australia: con vincoli
WA  red  NT  yellow
WA NT SA
Q NSW V
T
Consistenza
sugli archi
Risposta:
unknown
WA  NT
WA  SA
NT  SA
NT  Q
SA  V
SA  Q
Q  NSW
SA  NSW
NSW  V
26
Risolutore con backtracking
Possiamo combinare la consistenza con il
backtracking
 Applichiamo la consistenza sui nodi e sugli
archi prima di iniziare la ricerca con
backtracking, e dopo ogni assegnamento di
un valore ad una variabile

27
Esempio di risolutore con
backtracking
Q1
Nessun
valore
Quindi,
puo’
essere
dobbiamo
assegnatouna
scegliere
Q3valore
in
altro
questo
caso!
per Q2.
Q2
Q3
Q4
1
2
3
4
28
Esempio
Q1
Q2
Q3
Q4
1
backtracking,
Backtracking…
Non
possiamo
backtracking,
2
trovare nessun
Trovo
un
Trovo
unQ4
valore
per
Trovo
un
altro
valore
3
altroin
valore
altro
valore
per
per Q1?
Q3?
questo
caso!
per
Q2?
No!
4
No!
Si, Q1 = 2
29
Esempio
Q1
Q2
Q3
Q4
1
2
3
4
30
Esempio
Q1
Q2
Q3
Q4
1
2
3
4
31
Esempio
Colorare l’Australia: con vincoli
WA  red  NT  yellow
WA NT SA
Q NSW V
T
Enumerazione
con
backtracking
Seleziona una var. con dominio con piu’ di 1 valore, T
Aggiunge il vincolo T
Answer: true
 red
Applica la consistenza
32
Consistenza sui limiti
E I vincoli primitivi con piu’ di 2 variabili?
 hyper-arc consistency: estende la
consistenza sugli archi per un numero
arbitrario di variabili
 Sfortunatamente determinare la hyper-arc
consistency e’ NP-hard
 Qual e’ la soluzione?

33
Consistenza sui limiti
CSP aritmetici: i vincoli sono interi
 range: [l..u] rappresenta l’insieme degli
interi {l, l+1, ..., u}
 Idea: usare la consistenza sui numeri reali e
guardare solo i punti finali (limiti superiori
e inferiori) del dominio di ogni variabile
 Definire min(D,x) come il minimo elemento
nel dominio di x, simile per max(D,x)

34
Consistenza sui limiti

Un vincolo primitivo c e’ consistente sui limiti
con dominio D se per ogni var x in vars(c)

Esistono numeri reali d1, ..., dk per le rimanenti
variabili x1, ..., xk tali che
{x  min( D, x), x1  d 1, xk  dk}



e’ una soluzione di c
E simile per {x  max( D, x)}
Un CSP aritmetico e’ consistente sui limiti se lo
sono tutti i vincoli primitivi
35