Ce este o CSP?

Satisfacerea Restricțiilor (Constraint Satisfaction Problem - CSP)

• CSP reprezintă Problema Satisfacerii Restricțiilor
• Problemele CSP includ colorarea hărților, sudoku, orarul și puzzle-ul lui Einstein (Zebra puzzle)
• Puzzle-urile matematice pot, de asemenea, fi reprezentate ca probleme CSP

Terminologie CSP

• V reprezintă un set de variabile: {X1... XN}
• Domeniile reprezintă seturi de valori posibile pentru variabile: {D1... DN}
• Restricțiile sunt relații ce limitează valorile pe care le pot lua variabilele: {R1... Rk}
• Rj = ⟨tj , rj ⟩ unde tj ⊆ V și rj : ×Xi∈tj Di → {True, False} reprezintă restricțiile
• Atribuirea la valori înseamnă a da o valoare din domeniu sau o valoare "neatribuită" (⊥) fiecărei variabile: {(X1,x1) ... (XN,xN)}
• O atribuire este o soluție dacă toate variabilele au o valoare atribuită(atribuire completă), iar toate restricțiile sunt respectate (soluție validă)
• O soluție CSP totală este completă și nu încalcă nicio restricție
• O soluție CSP parțială este completă, dar încalcă unele restricții
• Rj = ⟨tj , rj , cj ⟩ unde cj reprezintă costul restricției
• Costul soluției se calculează ca suma costurilor restricțiilor încălcate: ∑ cj, unde Rj ∈R, rj(vals(tj))=False
• Un CSP este binar dacă toate restricțiile implică doar două variabile: ∀Rj ∈ R, tj ∈ V×V

Backtracking

• CSP este o problemă NP, similară cu problema SAT
• Problemele CSP pot fi rezolvate folosind backtracking
• Pentru a face backtracking-ul mai eficient, se poate încerca reducerea spațiului de căutare și a factorului de ramificare
• Îmbunătățirea consistenței căutării și reducerea spațiului de căutare ajută la optimizare

Propagarea Locală a Restricțiilor

• Prin aplicarea inițială a restricțiilor unare, domeniile variabilelor sunt restrânse
• Modificările domeniului unei variabile se propagă către variabilele vecine, reducând domeniile acestora
• Dacă o variabilă i poate lua doar valorile D′, domeniile variabilelor vecine cu i sunt ajustate pentru a conține doar valori compatibile cu D'
• Verificarea consistenței se reia pentru variabilele vecine cu variabilele al căror domeniu a fost modificat

Algoritmul AC-3 (Arc Consistency 3)

• Funcționează corect, dacă toate restricțiile sunt unare sau binare
• Se formează un graf de restricții: nodurile reprezintă variabilele, arcele reprezintă restricțiile binare
• Un arc (Xi, Xj) este arc-consistent dacă pentru fiecare valoare xi ∈ Di, există o valoare xj ∈ Dj astfel încât rij(xi, xj) = True
• Dacă toate arcele sunt arc-consistente, graful este arc-consistent, și nu se mai poate reduce spațiul de căutare
• Complexitatea temporală pentru AC-3 este O(e * d^3)
• "e" este numărul de restricții (muchii)
• "d" este cardinalitatea maximă a domeniilor
• Complexitatea spațială pentru AC-3 este O(e)
• AC-4 are complexitate O(e* d^2)
• Dacă AC-3 întoarce EȘEC, înseamnă că problema nu are soluție
• Dacă după AC-3 toate domeniile au cardinalitatea 1, nu mai este necesar backtracking
• Dacă lățimea grafului de restricții este mai mare de 1, nu este garantat că problema are soluție, și trebuie făcut backtracking

Îmbunătățiri BKT : MAC (Maintaining Arc Consistency)

• Se combină backtracking cu arc consistența, menținând arc-consistența pe măsură ce se avansează în recursivitate
• Arc-consistența se verifică după atribuirea unei valori în soluția parțială

Îmbunătățiri BKT: Ordonarea Variabilelor

• Variabilele pot fi ordonate folosind mai multe strategii.
  • Aleator: Alegerea aleatorie a variabilelor
  • Alegerea variabilei cele mai restricționate(Minimum Remaining Value - MRV): cu domeniul cel mai redus; utilă pentru o soluție rapidă sau identificarea rapidă a eșecului
  • Alegerea variabilei cele mai puțin restricționate, utilă când se doresc toate soluțiile
  • "Degree heuristic": Se alege variabila implicată în cele mai multe restricții cu variabile încă ne-atribuite

Îmbunătățiri BKT: Ordonarea Valorilor

• Se pot parcurge valorile dintr-un domeniu într-o anumită ordine
• Inițial, se selectează valoarea care elimină cele mai puține valori din variabilele vecine menținând consistența arcului, util pentru a găsi o singură soluție rapid
• Sau, se selectează valoarea care elimină cele mai multe valori din variabilele vecine menținând consistența arcului, util pentru a găsi toate soluțiile

CSP Parțial (Flexible CSP)

• Atunci când nu toate restricțiile sunt la fel de importante
• Fiecărei restricții i se asociază un cost (cj > 0)
• Se stabilește o limită suficientă S, iar o soluție este considerată validă dacă suma costurilor restricțiilor încălcate este mai mică sau egală cu S: ∑ cj ≤ S, unde j cu rj (Sol)=False
• Optimizare: dacă în parcurgere, costul total al restricțiilor încălcate depășește S, sau depășește costul celei mai bune soluții găsite, atunci nu are sens să continuăm pe acea cale

Algoritmul PCSP

• Găsește prima soluție acceptabilă

• Intrări: Vars (variabile rămase de atribuit), Sol(soluția parțială), cost (costul soluției parțiale), S (limita suficientă)

• Ieșire: O atribuire completă cu cost < S sau EȘEC

• Dacă Vars = ∅, atunci întoarce Sol

• Altfel, se alege o variabilă xi din Vars

• Pentru fiecare valoare x din domeniul Di, se construiește o soluție nouă Sol' = Sol ∪ {xi, x} și se recalculează costul: c = cost + ∑ cj, unde xj în tj, rj(Sol')=False

• Dacă noul cost c ≤ S, se apelează recursiv PCSP(Vars \ {xi}, Sol', c)

• Dacă apelul recursiv întoarce un rezultat diferit de EȘEC, atunci s-a găsit o soluție acceptabilă, care este întoarsă Altfel, se întoarce EȘEC, indicând că nu există soluții acceptabile cu atribuirea curentă PCSP –

• Găsește cea mai bună soluție acceptabilă

• Vars (variabile rămase de atribuit), Sol(soluția parțială), cost (costul soluției parțiale), S (limita suficientă

• Toate soluțiile complete acceptabile găsite până acum

• Costul minim al unei soluții din „sols”

• 0 mulțime de atribuiri complete de cost < S sau ESEC