Constraint Satisfaction Problems (CSP)
Un Constraint Satisfaction Problem (Problemă de Satisfacere a Constrângerilor) este un tip de problemă în care trebuie să găsim valori pentru un set de variabile astfel încât să respectăm anumite constrângeri.
Componente CSP
Un CSP este definit de trei componente:
- Variabile (X): mulțimea variabilelor X = \{X_1, X_2, ..., X_n\}
- Domenii (D): pentru fiecare variabilă, domeniul valorilor posibile D = \{D_1, D_2, ..., D_n\}
- Constrângeri (C): restricții care specifică combinațiile permise de valori
Exemplu clasic: Colorarea hărții
Problema: colorarea regiunilor unei hărți astfel încât regiunile vecine să aibă culori diferite.
+-------+-------+
| | |
| A | B |
| | |
+-------+-------+
| | |
| C | D |
| | |
+-------+-------+
- Variabile: X = \{A, B, C, D\}
- Domenii: D_i = \{rosu, verde, albastru\} pentru fiecare variabilă
- Constrângeri: A \neq B, A \neq C, B \neq D, C \neq D
Tipuri de constrângeri
Constrângeri unare
Implică o singură variabilă.
# X trebuie să fie par
def constrangere_unara(x):
return x % 2 == 0
Constrângeri binare
Implică două variabile.
# X și Y trebuie să fie diferite
def constrangere_binara(x, y):
return x != y
Constrângeri globale
Implică mai multe variabile.
# Toate valorile trebuie să fie diferite (AllDifferent)
def all_different(valori):
return len(valori) == len(set(valori))
Reprezentarea în Python
class CSP:
def __init__(self, variabile, domenii, vecini, constrangeri):
self.variabile = variabile
self.domenii = domenii
self.vecini = vecini
self.constrangeri = constrangeri
def este_consistent(self, var, val, atribuire):
"""Verifică dacă atribuirea var=val este consistentă."""
for vecin in self.vecini[var]:
if vecin in atribuire:
if not self.constrangeri(var, val, vecin, atribuire[vecin]):
return False
return True
Exemplu: Colorarea hărții
# Definire CSP pentru colorarea hărții
variabile = ['A', 'B', 'C', 'D']
domenii = {
'A': ['rosu', 'verde', 'albastru'],
'B': ['rosu', 'verde', 'albastru'],
'C': ['rosu', 'verde', 'albastru'],
'D': ['rosu', 'verde', 'albastru']
}
vecini = {
'A': ['B', 'C'],
'B': ['A', 'D'],
'C': ['A', 'D'],
'D': ['B', 'C']
}
def constrangeri(var1, val1, var2, val2):
"""Culorile trebuie să fie diferite."""
return val1 != val2
Algoritmi de rezolvare
Backtracking simplu
def backtracking(csp, atribuire={}):
# Dacă atribuirea este completă, returnează soluția
if len(atribuire) == len(csp.variabile):
return atribuire
# Alege o variabilă neatribuită
var = selecteaza_variabila_neatribuita(csp, atribuire)
# Încearcă fiecare valoare din domeniu
for valoare in csp.domenii[var]:
if csp.este_consistent(var, valoare, atribuire):
# Adaugă atribuirea
atribuire[var] = valoare
# Continuă recursiv
rezultat = backtracking(csp, atribuire)
if rezultat is not None:
return rezultat
# Backtrack - elimină atribuirea
del atribuire[var]
return None
def selecteaza_variabila_neatribuita(csp, atribuire):
for var in csp.variabile:
if var not in atribuire:
return var
return None
Euristici pentru îmbunătățire
MRV (Minimum Remaining Values)
Alege variabila cu cele mai puține valori rămase în domeniu.
def mrv(csp, atribuire):
"""Selectează variabila cu cele mai puține valori posibile."""
neatribuite = [v for v in csp.variabile if v not in atribuire]
return min(neatribuite,
key=lambda var: len(csp.domenii[var]))
Degree Heuristic
Alege variabila implicată în cele mai multe constrângeri.
def degree_heuristic(csp, atribuire):
"""Selectează variabila cu cele mai multe constrângeri."""
neatribuite = [v for v in csp.variabile if v not in atribuire]
return max(neatribuite,
key=lambda var: len([v for v in csp.vecini[var]
if v not in atribuire]))
LCV (Least Constraining Value)
Alege valoarea care elimină cele mai puține opțiuni pentru vecini.
def lcv(csp, var, atribuire):
"""Ordonează valorile după impactul asupra vecinilor."""
def numar_conflicte(val):
count = 0
for vecin in csp.vecini[var]:
if vecin not in atribuire:
for val_vecin in csp.domenii[vecin]:
if not csp.constrangeri(var, val, vecin, val_vecin):
count += 1
return count
return sorted(csp.domenii[var], key=numar_conflicte)
Propagarea constrângerilor
Arc Consistency (AC-3)
Reduce domeniile variabilelor eliminând valorile inconsistente.
def ac3(csp):
"""Algoritm AC-3 pentru consistența arcelor."""
coada = [(xi, xj) for xi in csp.variabile
for xj in csp.vecini[xi]]
while coada:
xi, xj = coada.pop(0)
if revizuieste(csp, xi, xj):
if len(csp.domenii[xi]) == 0:
return False # Nicio soluție
for xk in csp.vecini[xi]:
if xk != xj:
coada.append((xk, xi))
return True
def revizuieste(csp, xi, xj):
"""Elimină valorile inconsistente din domeniul lui xi."""
revizuit = False
for val_i in csp.domenii[xi][:]:
# Verifică dacă există o valoare consistentă pentru xj
if not any(csp.constrangeri(xi, val_i, xj, val_j)
for val_j in csp.domenii[xj]):
csp.domenii[xi].remove(val_i)
revizuit = True
return revizuit
Exemplu complet: Sudoku
def creeaza_sudoku_csp(grid):
"""Creează un CSP pentru Sudoku."""
variabile = [(i, j) for i in range(9) for j in range(9)]
domenii = {}
for i, j in variabile:
if grid[i][j] != 0:
domenii[(i, j)] = [grid[i][j]]
else:
domenii[(i, j)] = list(range(1, 10))
def vecini(var):
i, j = var
rezultat = set()
# Același rând
for k in range(9):
if k != j:
rezultat.add((i, k))
# Aceeași coloană
for k in range(9):
if k != i:
rezultat.add((k, j))
# Același pătrat 3x3
bi, bj = 3 * (i // 3), 3 * (j // 3)
for di in range(3):
for dj in range(3):
if (bi + di, bj + dj) != (i, j):
rezultat.add((bi + di, bj + dj))
return rezultat
vecini_dict = {var: vecini(var) for var in variabile}
def constrangeri(var1, val1, var2, val2):
return val1 != val2
return CSP(variabile, domenii, vecini_dict, constrangeri)
# Rezolvare
grid = [
[5, 3, 0, 0, 7, 0, 0, 0, 0],
[6, 0, 0, 1, 9, 5, 0, 0, 0],
[0, 9, 8, 0, 0, 0, 0, 6, 0],
[8, 0, 0, 0, 6, 0, 0, 0, 3],
[4, 0, 0, 8, 0, 3, 0, 0, 1],
[7, 0, 0, 0, 2, 0, 0, 0, 6],
[0, 6, 0, 0, 0, 0, 2, 8, 0],
[0, 0, 0, 4, 1, 9, 0, 0, 5],
[0, 0, 0, 0, 8, 0, 0, 7, 9]
]
csp = creeaza_sudoku_csp(grid)
solutie = backtracking(csp)
Problema celor N Dame
def n_dame_csp(n):
"""CSP pentru problema celor N dame."""
variabile = list(range(n)) # Coloana pentru fiecare rând
domenii = {i: list(range(n)) for i in range(n)}
def vecini(var):
return [v for v in range(n) if v != var]
vecini_dict = {var: vecini(var) for var in variabile}
def constrangeri(var1, val1, var2, val2):
# Nu pe aceeași coloană
if val1 == val2:
return False
# Nu pe aceeași diagonală
if abs(var1 - var2) == abs(val1 - val2):
return False
return True
return CSP(variabile, domenii, vecini_dict, constrangeri)
# Rezolvare pentru 8 dame
csp = n_dame_csp(8)
solutie = backtracking(csp)
print(solutie) # {0: 0, 1: 4, 2: 7, 3: 5, 4: 2, 5: 6, 6: 1, 7: 3}
Complexitate
| Algoritm | Timp | Spațiu |
|---|---|---|
| Backtracking | O(d^n) | O(n) |
| Backtracking + MRV | Îmbunătățit | O(n) |
| AC-3 | O(n^2 d^3) | O(n^2) |
Unde n = numărul de variabile, d = dimensiunea maximă a domeniului.