Inteligență Artificială: Problema satisfacerii restricțiilor

Inteligent, ă Artificială Problema satisfacerii restrict, iilor Slides: Andrei Olaru, Adina Florea Problema satisfacerii restrict, iilor | 0 / 22 Satisfacerea restrict, iilor Backtracking Propa...

Inteligent, ă Artificială Problema satisfacerii restrict, iilor Slides: Andrei Olaru, Adina Florea Problema satisfacerii restrict, iilor | 0 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor WA, NT , Q, SA, NSW , V , T ∈ Colors WA ̸= NT , WA ̸= SA, NT ̸= SA,... Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku a, b,... , i ∈ {1, 2, 3, 4} a∈ / {1, 2, 4, d, i} b∈ / {2, 4, c, e, h} c∈ / {2, 4, b, c, f } d∈ / {1, 3, 4, a, g}... Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku orarul Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku orarul problema lui Einstein (Zebra puzzle) Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP T W O Problema satisfacerii restrict, iilor + T W O (Constraint Satisfaction Problem – CSP) F O U R problema colorării hărt, ilor W , O, U, R ∈ 0... 9 sudoku T,F ∈ 1...9 orarul 2 · O % 10 = R problema lui Einstein (Zebra puzzle) 2 · W % 10 + 2 · O ÷ 10 = U puzzle-uri matematice 2 · T % 10 + 2 · W ÷ 10 = O 2 · T ÷ 10 = F Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Problema satisfacerii restrict, iilor (Constraint Satisfaction Problem – CSP) problema colorării hărt, ilor sudoku orarul problema lui Einstein (Zebra puzzle) puzzle-uri matematice... Problema satisfacerii restrict, iilor | 1 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP {X1... XN } = V – Variable {D1... DN } – Domenii {R1... Rk } = R – Restrict, ii, Rj = ⟨tj , rj ⟩, tj ⊆ V , rj : ×Xi ∈tj Di → − {True, False} {⟨X1 , x1 ⟩... ⟨XN , xN ⟩} – Atribuire la valori, cu xi ∈ Di ∪ {⊥} (⊥ ≡ neatribuit la o valoare) o atribuire este solut, ie dacă xi ∈ Di , i = 1, N, i.e. toate variabilele au atribuită o valoare (atribuire completă) ∀Rj ∈ R, rj (vals) = True, cu vals valorile variabilelor din tj (solut, ie validă) Problema satisfacerii restrict, iilor | 2 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP totală – solut, ia este completă s, i nu încalcă nicio restrict, ie Problema satisfacerii restrict, iilor | 3 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP totală – solut, ia este completă s, i nu încalcă nicio restrict, ie CSP part, ială – solut, ia este completă dar încalcă unele restrict, ii Rj = ⟨tj , rj , cj ⟩, cu cj costul restrict, iei Rj P costul solut, iei c = cj Rj ∈R,rj (vals(tj ))=False Problema satisfacerii restrict, iilor | 3 / 22 Satisfacerea restrict, iilor : Terminologie Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP totală – solut, ia este completă s, i nu încalcă nicio restrict, ie CSP part, ială – solut, ia este completă dar încalcă unele restrict, ii Rj = ⟨tj , rj , cj ⟩, cu cj costul restrict, iei Rj P costul solut, iei c = cj Rj ∈R,rj (vals(tj ))=False CSP binară – toate restrict, iile sunt binare ∀Rj ∈ R, tj ∈ V × V Problema satisfacerii restrict, iilor | 3 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Backtracking Problema satisfacerii restrict, iilor | 4 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP este o problemă NP, apropiată de problema SAT ⇒ CSP trebuie rezolvat prin backtracking ce putem face este să încercăm să reducem spat, iul de căutare s, i factorul de ramificare îmbunătăt, irea consistent, ei căutării reducerea spat, iului de căutare Problema satisfacerii restrict, iilor | 5 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP CSP-BKT Intrări: Vars – variabile rămase de atribuit, init, ial X ; Sol – solut, ia (atribuirea) part, ială, init, ial ∅ Ies, ire: O atribuire completă sau E S, EC 1. dacă Vars = ∅ atunci întoarce Sol 2. Xi ← − alege_variabila(Vars) 3. pentru fiecare x ∈ Di 4. dacă consistent(Sol ∪ ⟨Xi , x⟩, R) atunci 5. res ← − CSP-BKT (Vars \ {Xi }, Sol ∪ ⟨Xi , x⟩) 6. dacă res ̸= E S, EC atunci întoarce res 7. întoarce E S, EC Problema satisfacerii restrict, iilor | 6 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Propagarea locală a restrict, iilor Problema satisfacerii restrict, iilor | 7 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d e f g h i Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g h i Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g 3. i poate fi doar 1, se învecinează cu h, deci h nu poate fi 1 ⇒ restrict, ionăm domeniul lui h la {2} h i Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g 3. i poate fi doar 1, se învecinează cu h, deci h nu poate fi 1 ⇒ restrict, ionăm domeniul lui h la {2} h i 4. restrict, ionarea nu afectează pe b, e, f Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Intuitiv: init, ial, după aplicarea restrict, iilor unare, avem a ∈ {3} d ∈ {2} b, c, e, f ∈ {1, 3} h ∈ {1, 2} g ∈ {4} i ∈ {1} a 1. a poate fi doar 3; a se învecinează cu d, i; ambele au domenii compatibile cu valoarea lui a b c d 2. d poate fi doar 2, se învecinează cu b, c, g; sunt compatibile e f g 3. i poate fi doar 1, se învecinează cu h, deci h nu poate fi 1 ⇒ restrict, ionăm domeniul lui h la {2} h i 4. restrict, ionarea nu afectează pe b, e, f 5. rămân b, c, e, f cu domeniul {1, 3} Problema satisfacerii restrict, iilor | 8 / 22 CSP Backtracking Propagarea locală a restrict, iilor Îmbunătăt, iri BKT PCSP Pe cazul general, dacă o variabilă i poate avea doar valorile Di′ , ajustăm domeniile tuturor variabilelor vecine (care au restrict, ii binare cu variabila i), în as, a fel încât să cont, ină doar valori compatibile cu valorile din Di′. Dacă un domeniu Dk , al variabilei k vecină cu i, a fost ajustat, trebuie verificate din nou toate variabilele vecine cu variabila k , mai put, in variabila i. Problema satisfacerii restrict, iilor | 9 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP Algoritmul AC-3 (Arc Consistency 3) trebuie ca toate restrict, iile să fie unare sau binare putem forma un graf de restrict, ii în care nodurile corespund variabilelor arcele corespund restrict, iilor binare. Considerăm pentru fiecare restrict, ie două arce orientate. un arc (Xi , Xj ) corespunzător unei restrict, ii Rij este arc-consistent dacă ∀xi ∈ Di , ∃xj ∈ Dj , rij (xi , xj ) = True dacă toate arcele din graf sunt arc-consistente, graful este arc-consistent s, i nu putem reduce mai mult (prin acest mecanism) spat, iul de căutare Problema satisfacerii restrict, iilor | 10 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP AC-3 1. reduce toate domeniile conform cu restrict, iile unare 2. Q← − {(Xi , Xj ) | Rij ∈ R sau Rji ∈ R} 3. cât timp Q ̸= ∅ 4. (Xi , Xj ) ← − Q.pop() 5. dacă check (Xi , Xj ) atunci domeniul lui Xi s-a modificat 6. dacă Di = ∅ atunci întoarce E S, EC 7. Q = Q ∪ {(Xk , Xi ) | Rki ∈ R, k ̸= j} 8. întoarce S UCCES check (Xi , Xj ) 1. pentru xi ∈ Di 2. dacă ∄xj ∈ Dj. rij (xi , xj ) = True 3. atunci Di ← − Di \ {xi } 4. întoarce True dacă Di s-a modificat, altfel False Problema satisfacerii restrict, iilor | 11 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP complexitatea temporală pentru AC-3 este O(e · d 3 ), unde e = |R| – numărul de restrict, ii (muchii) d = maxi=1,N |Di | – cardinalitatea maximă a domeniilor complexitatea spat, ială este O(e) algoritmi mai noi – dar mai complicat, i – pot fi mai buni. E.g., AC-4 are complexitate O(e · d 2 ) Problema satisfacerii restrict, iilor | 12 / 22 CSP Backtracking Propagarea locală a restrict, iilor : AC-3 Îmbunătăt, iri BKT PCSP dacă AC-3 întoarce E S, EC atunci înseamnă că problema nu are solut, ie dacă după realizarea AC-3, toate domeniile au cardinalitate 1 (spunem că lăt, imea grafului de restrict, ii este 1), atunci nu mai este necesar backtracking dacă lăt, imea grafului de restrict, ii este mai mare de 1, atunci nu este garantat că problema are solut, ie, s, i trebuie făcut backtracking pe variabilele cu domenii de cardinalitate > 1 Problema satisfacerii restrict, iilor | 13 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Îmbunătăt, iri BKT Problema satisfacerii restrict, iilor | 14 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : MAC PCSP Reducerea spat, iului de căutare prin detectarea timpurie a inconsistent, elor: combinăm backtracking cu arc consistent, a, ment, inând arc-consistent, a pe măsură ce avansăm în recursivitate. (Maintaining arc-consistency – MAC) verificăm arc-consistent, a după ce atribuim o valoare în solut, ia part, ială Problema satisfacerii restrict, iilor | 15 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : MAC PCSP BKT-MAC 1. dacă Vars = ∅ atunci întoarce Sol 2. Xi ←− alege_variabila(Vars) 3. pentru fiecare x ∈ Di 4. Dcopy ← −D copiem toate domeniile arcs_out întoarce toate arcele care pornesc din Xi 5. −AC-3′ (arcs_out(Xi )) r← AC-3’ este AC-3 începând de la pasul 3., cu Q pornind de la valoarea din argument 6. dacă r s, i consistent(Sol ∪ ⟨Xi , x⟩, R) atunci 7. res ← − BKT -MAC(Vars \ {Xi }, Sol ∪ ⟨Xi , x⟩) 8. dacă res ̸= E S, EC atunci întoarce res 9. D← − Dcopy 10. întoarce E S, EC refacem domeniile Problema satisfacerii restrict, iilor | 16 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : Ordonarea variabilelor PCSP Putem ordona variabilele (funct, ia alege_variabila): aleator alegând variabila cea mai restrict, ionată (cu domeniul cel mai redus) – Minimum remaining value – MRV util atunci când ne dorim o singură solut, ie s, i vrem să fort, ăm, dacă e cazul, un es, ec mai rapid alegând variabila cea mai put, in restrict, ionată util atunci când ne dorim aflarea tuturor solut, iilor s, i ne dorim un arbore de BKT mai lat s, i mai put, in adânc alegând variabila implicată în cele mai multe restrict, ii cu variabile încă ne-atribuite – Degree heuristic Problema satisfacerii restrict, iilor | 17 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT : Ordonarea valorilor PCSP Putem parcurge valorile din domeniu într-o anumită ordine: selectăm întâi valoarea care elimină cele mai put, ine valori din variabilele vecine la ment, inerea arc-consistent, ei util atunci când ne dorim o singură solut, ie s, i vrem să ajungem la o solut, ie mai repede selectăm întâi valoarea care elimină cele mai multe valori din variabilele vecine la ment, inerea arc-consistent, ei util atunci când ne dorim toate solut, ile s, i preferăm un graf mai put, in adânc Problema satisfacerii restrict, iilor | 18 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială CSP Part, ială Problema satisfacerii restrict, iilor | 19 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială Pentru o problemă de tip CSP cu multe restrict, ii, este posibil ca nu toate restrict, iile să fie la fel de importante (vezi, de exemplu, problema orarului) ⇒ CSP Part, ială (Flexible CSP). asociem un cost cu fiecare restrict, ie: Rj = ⟨tj , rj , cj ⟩,cu cj > 0 P stabilim o limită suficientă S – considerăm o solut, ie Sol ca validă dacă cj ≤ S j,rj (Sol)=False optimizare: dacă în parcurgere costul total al restrict, iilor încălcate de atribuirea part, ială curentă depăs, es, te S, sau depăs, es, te costul restrict, iilor pentru cea mai bună solut, ie găsită până acum, nu are sens să mai continuăm pe aceast cale Problema satisfacerii restrict, iilor | 20 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială PCSP – găses, te prima solut, ie acceptabilă Intrări: Vars – variabile rămase de atribuit, init, ial X ; Sol – solut, ia (atribuirea) part, ială, init, ial ∅ cost – costul solut, iei part, iale Sol, cu S – limita suficientă Ies, ire: O atribuire completă de cost ≤ S sau E S, EC 1. dacă Vars = ∅ atunci întoarce Sol 2. Xi ← − alege_variabila(Vars) 3. pentru fiecare x ∈ Di 4. Sol ′ ←− Sol ∪ ⟨Xi , x⟩ P 5. c = cost + cj Xi ∈tj ,rj (Sol ′ )=False 6. dacă c ≤ S 7. − PCSP(Vars \ {Xi }, Sol ′ , c) res ← 8. dacă res ̸= E S, EC atunci întoarce res 9. întoarce E S, EC Problema satisfacerii restrict, iilor | 21 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT CSP Part, ială PCSP – găses, te cea mai bună solut, ie acceptabilă Intrări: Vars – variabile rămase de atribuit, init, ial X ; Sol – solut, ia (atribuirea) part, ială, init, ial ∅ cost – costul solut, iei part, iale Sol, cu S – limita suficientă Global: sols – toate solut, iile complete acceptabile găsite până acum best_cost – costul minim al unei solut, ii din sols Ies, ire: O mult, ime de atribuiri complete de cost ≤ S, sau E S, EC 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⟩ P 7. c = cost + cj Xi ∈tj ,rj (Sol ′ )=False 8. dacă c ≤ S s, i c < best_cost 9. PCSP(Vars \ {Xi }, Sol ′ , c) va actualiza sols dacă este cazul Problema satisfacerii restrict, iilor | 22 / 22 CSP Backtracking Propagare restrict, ii Îmbunătăt, iri BKT PCSP Mult, umesc! https://forms.gle/DJUdkejstkvyNRF5A Feedbackul este binevenit! Problema satisfacerii restrict, iilor | 22 / 22