Problema Satisfacerii Restricțiilor (CSP)

Problema Satisfacerii Restricțiilor (CSP)

• Reprezintă o arie a Inteligenței Artificiale

Exemple de Probleme CSP

• Colorarea hărților
• Sudoku
• Orarul
• Problema lui Einstein (Zebra puzzle)
• Puzzle-uri matematice

Terminologie CSP

• V reprezintă mulțimea variabilelor: {X1... XN}
• D reprezintă domeniile variabilelor: {D1... DN}
• R reprezintă restricțiile: {R1... Rk}, unde Rj = (tj, rj), tj ⊆ V, iar rj aplică o funcție variabilelor din tj și returnează {True, False}.
• O atribuire este o asociere de valori pentru variabile: {(X1, x1)... (XN, xN)}, unde xi ∈ Di ∪ {⊥}, iar ⊥ înseamnă neatribuit.
• O atribuire este o soluție dacă toate variabilele au o valoare atribuită (atribuire completă) și toate restricțiile sunt respectate (soluție validă).
• CSP totală: soluția este completă și nu încalcă nicio restricție.
• CSP parțială: soluția este completă, dar încalcă unele restricții. Rj = (tj, rj, cj), unde cj este costul restricției Rj.
• Costul soluției este suma costurilor restricțiilor încălcate.
• CSP binară: toate restricțiile sunt binare, adică ∀Rj ∈ R, tj ∈ V × V.

Backtracking

• Este o metodă de rezolvare a problemelor CSP
• Poate fi aplicat prin încercarea de a reduce spațiul de căutare și factorul de ramificare.
• Îmbunătățirea consistenței căutării contribuie la eficiență.

Algoritmul CSP-BKT

• Algoritmul primește ca intrare variabilele rămase de atribuit (Vars) și atribuirea inițială X, Soluția inițială fiind ∅.
• Ieșirea poate fi o atribuire completă sau Eșec.
• Dacă Vars este vid, atunci Soluția este returnată.
• Se alege o variabilă Xi din Vars.
• Pentru fiecare valoare x din domeniul Di,
• dacă atribuirea Sol ∪ {(Xi, x)} este consistentă cu restricțiile R, atunci se apelează recursiv CSP-BKT cu Vars \ {Xi} și Sol ∪ {(Xi, x)}.
• Dacă rezultatul recursiv este diferit de Eșec, atunci rezultatul este returnat.
• Dacă nicio valoare nu duce la o soluție, atunci se returnează Eșec.

Propagarea Locală a Restricțiilor

• Este un proces de reducere a domeniilor variabilelor pe baza restricțiilor, cu scopul de a simplifica problema.
• Inițial, după aplicarea restricțiilor unare, domeniile variabilelor pot fi predefinite.
• Pe cazul general, dacă o variabilă i poate avea doar valorile Di′, domeniile tuturor variabilelor vecine se ajustează astfel încât să conțină doar valori compatibile cu valorile din Di′ .
• Dacă un domeniu Dk, al variabilei k vecină cu i, a fost ajustat, toate variabilele vecine cu variabila k, mai puțin variabila i, se verifică din nou.

Algoritmul AC-3 (Arc Consistency 3)

• Trebuie ca toate restricțiile să fie unare sau binare.
• Se formează un graf de restricții în care nodurile corespund variabilelor, iar arcele corespund restricțiilor binare. Pentru fiecare restricție există două arce orientate.
• Un arc (Xi, Xj) corespunzător unei restricții Rij este arc-consistent dacă ∀xi ∈ Di, ∃xj ∈ Dj, astfel încât rij(xi, xj) = True.
• Graful este arc-consistent dacă toate arcele sunt arc-consistente
• Nu se mai poate reduce spațiul de căutare prin acest mecanism, dacă graful este arc-consistent

Pași AC-3

• Reduce toate domeniile conform cu restrictiile unare.
• Inițializează o coadă Q cu toate arcele (Xi, Xj) corespunzătoare restricțiilor Rij ∈ R.
• Cât timp Q nu este goală:
  • Extrage un arc (Xi, Xj) din Q.
  • Dacă domeniul lui Xi s-a modificat ca urmare a procesului check,
    • Dacă Di devine vid, algoritmul întoarce EȘEC.
    • Altfel, adaugă în Q toate arcele (Xk, Xi) unde Rki ∈ R și k ≠ j.
• Întoarce SUCCES.

Subrutina check(Xi, Xj)

  Pentru fiecare valoare xi ∈ Di:

• Dacă nu există nicio valoare xj ∈ Dj, astfel încât rij(xi, xj) = True,
  • Atunci elimină xi din Di.
• Întoarce True dacă Di s-a modificat, altfel False.

Complexitatea AC-3

• Complexitatea temporală este O(e * d³), unde e este numărul de restricții (muchii), iar d este cardinalitatea maximă a domeniilor.
• Complexitatea spațială este O(e).
• Dacă AC-3 întoarce EȘEC, atunci 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, atunci trebuie făcut backtracking pe variabilele cu domenii de cardinalitate > 1.

Îmbunătățiri BKT: Menținerea Arcu-Consistenței (MAC)

• Combină backtracking cu arc consistența, menținând arc-consistența pe măsură ce se avansează în recursivitate (Maintaining arc-consistency – MAC).
• Se verifică arc-consistența după ce se atribuie o valoare în soluția parțială.

Algoritmul BKT-MAC

1. Dacă Vars este vid, atunci se returnează Sol.
2. Se alege o variabilă Xi din Vars.
3. Pentru fiecare valoare x din domeniul Di:
4. copiază toate domeniile
5. r ← AC-3′(arcs_out(Xi))
6. Dacă r și consistent(Sol ∪ ⟨Xi, x⟩, R) atunci
7. res ← BKT-MAC(Vars \ {Xi}, Sol ∪ ⟨Xi, x⟩)
8. Dacă res ≠ EȘEC atunci întoarce res
9. restaurează domeniile
10. Întoarce EȘEC

Ordonarea Variabilelor

• Se poate ordona variabilele (funcția alege_variabila) astfel:
  • Aleator
  • Alegând variabila cea mai restricționată (cu domeniul cel mai redus) – Minimum remaining value – MRV.
    • Util atunci când se dorește o singură soluție și se vrea să se forțeze un eșec mai rapid.
  • Alegând variabila cea mai puțin restricționată.
    • Util atunci când se dorește aflarea tuturor soluțiilor și ne dorim un arbore de BKT mai lat și mai puțin adânc.
  • Alegând variabila implicată în cele mai multe restricții cu variabile încă ne-atribuite – Degree heuristic.

Ordonarea Valorilor

• Se pot parcurge valorile din domeniu într-o anumită ordine:
  • Se selectează întâi valoarea care elimină cele mai puține valori din variabilele vecine la menținerea arc-consistenței.
    • Util atunci când se dorește o singură soluție și vrem să ajungem la o soluție mai repede.
  • Se selectează întâi valoarea care elimină cele mai multe valori din variabilele vecine la menținerea arc-consistenței.
    • Util atunci când se doresc toate soluțiile și preferăm un graf mai puțin adânc.

CSP Parțială (Flexible CSP)

• Pentru o problemă de tip CSP cu multe restricții, este posibil ca nu toate restricțiile să fie la fel de importante.
• Se asociază un cost cu fiecare restricție: Rj = ⟨tj, rj, cj⟩, cu cj > 0.
• Se stabilește o limită suficientă S: o soluție Sol ca validă dacă Σ cj ≤ S cu [ Σ luată peste toate restricțiile j, rj(Sol) = False]
• Optimizare: dacă în parcurgere costul total al restricțiilor încălcate de atribuirea parțială curentă depășește S, sau depășește costul restricțiilor pentru cea mai bună soluție găsită până acum, nu are sens să mai continuăm pe această cale.

Algoritmul PCSP - găsește prima soluție acceptabilă

- Intrări: Vars – variabile rămase de atribuit, initial X;
- Sol – soluția (atribuirea) parțială, inițial ∅
- cost – costul soluției parțiale Sol, cu S – limita suficientă
- Ieșire: O atribuire completă de cost ≤ S sau ESEC

1. dacă Vars = ∅ atunci întoarce Sol
2. Xi ← alege_variabila(Vars)
3. pentru fiecare x ∈ Di
4. Sol' ← Sol ∪ ⟨Xi, x⟩
5. c = cost + Σ cj cu [ Σ luată peste toate restricțiile Xi ∈ tj, rj(Sol') = False]
6. dacă c ≤ S
7. res ← PCSP(Vars \ {Xi}, Sol', c)
8. dacă res ≠ ESEC atunci întoarce res
9. întoarce ESEC

Algoritmul PCSP - găsește cea mai bună soluție acceptabilă

1. dacă Vars = ∅ atunci
2. sols ← sols ∪ {Sol}
3. dacă cost < best_cost atunci best_cost ← cost
4. Xi ← alege_variabila(Vars)
5. pentru fiecare x ∈ Di
6. Sol' ← Sol ∪ ⟨Xi, x⟩
7. c = cost + Σ cj cu [ Σ luată peste toate restricțiile Xi ∈ tj, rj(Sol') = False]
8. dacă c ≤ S și c < best_cost
9. PCSP(Vars \ {Xi}, Sol', c)

• Va actualiza soluția, dacă este cazul