Problemi con soddisfacimento
dei vincoli
Slides Intelligenza Artificiale,
Vincenzo Cutello
1
Outline





Esempi di CSP
Ricerca generale applicata ai CSP
Backtracking
Controllo in avanti
Euristiche per i CSP
Slides Intelligenza Artificiale,
Vincenzo Cutello
2
Problemi con soddisfacimento dei
vincoli
Problema di ricerca standard:
lo stato è una “black box”
una qualsiasi vecchia struttura dati che supporta
verifica dell’obiettivo, valutazione, successore
CSP:
lo stato è definito da variabili Vi con valori dal
dominio Di
la verifica dell’obiettivo è un insieme di vincoli
specificanti le combinazioni permesse di valori per
sottoinsiemi di variabili
Slides Intelligenza Artificiale,
Vincenzo Cutello
3
Esempio: 4-regine come CSP
Assumiamo una regina in ogni colonna. In quale riga andrà
ognuna ?
Variabili Q1,Q2,Q3,Q4
Domini Di = {1,2,3,4}
Vincoli
Qi ≠ Qk (non possono essere
nella stessa riga)
Q1 = 1
Q2 = 3
| Qi - Qk| ≠ |i-k| (o stessa diagonale)
Traduciamo ogni vincolo in un insieme di valori permessi per
le sue variabili
Cioè, i valori per (Q1,Q2) sono (1,3) (1,4) (2,4) (3,1) (4,1) (4,2)
Slides Intelligenza Artificiale,
Vincenzo Cutello
4
Grafo dei vincoli
CSP binario; ogni vincolo coinvolge al più due
variabili
Grafo dei vincoli; i nodi sono variabili, gli archi
rappresentano i vincoli
Q1
Q2
Q3
Q4
Slides Intelligenza Artificiale,
Vincenzo Cutello
5
Esempio: Crittoaritmetica
Variabili
DEMNORSY
Domini
{0,1,2,3,4,5,6,7,8,9}
Vincoli
M ≠ 0, S ≠ 0 (vincoli unari)
Y = D+E o Y = D+E-10, etc.
D ≠ E, D ≠ M, D ≠ N, etc.
Slides Intelligenza Artificiale,
Vincenzo Cutello
SEND
+ MORE
MONEY
6
Esempio: Colorazione di mappe
Colorare una mappa in maniera
tale che non esistano due paesi
adiacenti con lo stesso colore
Variabili
Paesi Ci
Domini
{Rosso, Blu, Verde}
Vincoli
C1 ≠ C2, C1 ≠ C5, etc.
Grafo dei vincoli:
C1
C2
C3
C5
C6
C4
C1
C2
C5
C3
C6
C4
Slides Intelligenza Artificiale,
Vincenzo Cutello
7
CSP nel mondo reale
 Problemi di assegnamento
– per esempio, chi insegna questo corso
 Problemi di orari
– per esempio, quale corso è offerto, quando e
dove ?
 Problemi di Scheduling
Si noti che molti problemi del mondo reale
coinvolgono variabili con valori reali
Slides Intelligenza Artificiale,
Vincenzo Cutello
8
Applicando la ricerca standard
Iniziamo con l’approccio diretto
Gli stati sono definiti tramite i valori fin qui
assegnati
Stato iniziale: Tutte le variabili senza alcun valore
Operatori: assegna un valore a una variabile senza
valore
Verifica dell’obiettivo: tutte le variabili assegnate,
nessun vincolo violato
Si noti che questo è uguale per tutti i CSP
Slides Intelligenza Artificiale,
Vincenzo Cutello
9
Implementazione
Lo stato del CSP mantiene traccia di quali variabili hanno finora un valore
Ogni variabile ha un dominio e un valore corrente
datatype CSP-State
components: UNASSIGNED, una lista di variabili ancore senza valore
ASSIGNED, una lista di variabili che hanno un valore
datatype CSP-Var
components: NAME, per scopi di input/output
DOMINIO, una lista di possibili valori
VALORI, valore corrente (se esiste !)
I vincoli possono essere rappresentati
esplicitamente come insiemi di valori permessi
implicitamente per mezzo di una funzione che verifica il
soddisfacimento del vincolo
Slides Intelligenza Artificiale,
Vincenzo Cutello
10
Ricerca Standard: colorazione di mappe
NON ASSEGNATO
C1 C2 C3
ASSEGNATO
NON ASSEGNATO
C2 C3
ASSEGNATO
C1 = ROSSO
NON ASSEGNATO
C1 C3
ASSEGNATO
C2 = BLU
Slides Intelligenza Artificiale,
Vincenzo Cutello
NON ASSEGNATO
C1 C2
ASSEGNATO
C3 = VERDE
11
Complessità dell’approccio “Dumb”
Max profondità dello spazio m = ?? n (numero di variabili)
Profondità dello stato soluzione d = ?? n (tutte le variabili
assegnate)
Algoritmo di ricerca da usare ?? Depth-first
Fattore di ramificazione b = ?? i |Di| (in cima all’albero)
Questo può essere migliorato sostanzialmente notando:

L’ordine di assegnamento è irrilevante così molti percorsi
sono equivalenti

L’aggiunta di un assegnamento non può correggere un
vincolo già violato
Slides Intelligenza Artificiale,
Vincenzo Cutello
12
Ricerca con backtracking
Usiamo la ricerca depth-first, ma
1) Fissiamo l’ordine di assegnamento,  b = |Di| (può essere
fatto nella funzione SUCCESSORI)
2) Controllo per le violazioni dei vincoli
Il controllo del vincolo violato può essere implementato in due
maniere:
1) modificando SUCCESSORI per assegnare solo valori
che sono permessi, dati i valori già assegnati
2) controllare che i vincoli siano soddisfatti prima di
espandere uno stato
La ricerca con backtracking è l’algoritmo di base non
informato per i CSP
Può risolvere il problema delle n-regine con n ≈ 15
Slides Intelligenza Artificiale,
Vincenzo Cutello
13
Controllo in avanti
Idea: mantenere traccia dei rimanenti valori legali per le variabili ancora
senza valore
Terminare la ricerca quando qualche variabile non ha più valori legali
Esempio di colorazione di mappe semplificato:
ROSSO
BLU
VERDE
C1
C1
C4
C2
C5
C2
C3
C4
C3
C5
Può risolvere il problema delle n-regine fino a n ≈ 30
Slides Intelligenza Artificiale,
Vincenzo Cutello
14
ROSSO
C1
√
C2
Х
BLU
VERDE
C3
C4
Х
C5
Х
Slides Intelligenza Artificiale,
Vincenzo Cutello
15
ROSSO BLU
VERDE
C1
C2
√
C3
Х
C4
Х
C5
Х
Slides Intelligenza Artificiale,
Vincenzo Cutello
16
ROSSO BLU
VERDE
C1
C2
C3
√
C4
Х
C5
Х
Slides Intelligenza Artificiale,
Vincenzo Cutello
17
Euristiche per i CSP
Più decisioni intelligenti su
quali valori scegliere per ogni variabile
quali variabili scegliere per l’assegnamento
Dati C1 = Rosso, C2 = Verde ??
C3 = Verde: valore meno vincolante
Dati C1 = Rosso, C2 = Verde ??
C5 : variabile più vincolata
C1
Può risolvere il problema delle
n-regine fino a n ≈ 1000
C2
C3
C5
C6
Slides Intelligenza Artificiale,
Vincenzo Cutello
C4
18
Algoritmi iterativi per i CSP
Hill-climbing, simulated annealing lavorano tipicamente con
stati “completi”, cioè, con tutte le variabili assegnate
Per applicarli ai CSP:
permettere stati con vincoli non soddisfatti
operatori che riassegnano i valori alle variabili
Selezione della variabile: selezionare in maniera random una
qualsiasi variabile con conflitti
Euristica min-conflicts:
scegliere il valore che vìola il minor numero di conflitti,
cioè, hillclimb con h(n) = numero totale di vincoli violati
Slides Intelligenza Artificiale,
Vincenzo Cutello
19
Esempio: 4-regine
Stati: 4 regine in 4 colonne (44 = 256 stati)
Operatori: muovi la regina lungo la colonna
Verifica dell’obiettivo: nessuno attacco
Valutazione: h(n) = numero di attacchi
h=5
h=2
Slides Intelligenza Artificiale,
Vincenzo Cutello
h=0
20
Prestazioni del min-conflicts
Dato uno stato iniziale random, può risolvere il problema delle
n-regine in al più un tempo costante per n arbitrario con
alta probabilità (cioè, n = 10.000.000)
Lo stesso sembra essere vero per un qualsiasi CSP generato
in maniera random
Eccetto in un piccolo range del rapporto
numero di vincoli
R = ────────────
numero di variabili
Tempo
di CPU
Rapporto critico
Slides Intelligenza Artificiale,
Vincenzo Cutello
21
CSP strutturati ad albero
Teorema: se il grafo dei vincoli non ha cicli, il CSP può essere risolto in
tempo O(n|D|2)
Comparato al CSP generale, dove il tempo nel caso peggiore è O(|D|n)
Questa proprietà si applica anche ai ragionamenti logici e probabilistici:
un importante esempio della relazione tra restrizioni sintattiche e
complessità di ragionamento
A
E
B
D
C
F
Slides Intelligenza Artificiale,
Vincenzo Cutello
22
Algoritmi per i CSP strutturati ad
alberi
Il passo base è chiamato filtering
FILTER (Vi, Vk)
rimuovi i valori di Vi che sono inconsistenti
con tutti i valori di Vk
Esempio di filtering
Vi
Vk
Coppie permesse
<1,1>
<3,2>
<3,3>
Slides Intelligenza Artificiale,
Vincenzo Cutello
Rimuovi 2 dal
dominio di Vi
23
Algoritmi (cont.)
E
A
B
D
F
C
1) Ordina nodi con BFS partendo da una foglia qualunque
A
B
C
D
E
F
2) Per k = n fino a 1, applica FILTER(Vi, Vk) dove Vi è un
genitore di Vk
3) Per k = 1 fino a n, scegli un valore legale per Vk dato il
valore del genitore
Slides Intelligenza Artificiale,
Vincenzo Cutello
24
Riassunto
I CSP sono un genere speciale di problema:
stati definiti da valori di un insieme fissato di variabili
verifica dell’obiettivo definito da vincoli sui valori delle variabili
Backtracking = ricerca depth-first con

Ordine fissato delle variabili

Solo successori legali
Il controllo in avanti previene assegnamenti che portano al fallimento
Euristiche per l’ordine delle variabili e la selezione dei valori aiutano
significativamente
Il min-conflicts iterativo è solitamente efficace in pratica
I CSP strutturati ad albero possono sempre essere risolti efficacemente
Slides Intelligenza Artificiale,
Vincenzo Cutello
25