Paradigme de Programare

Diferențe

Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.

Link către această vizualizare comparativă

--- 15:teme:prolog-csp [2015/05/06 21:29]
Tudor Berariu [Algoritmul GAC3]
+++ 15:teme:prolog-csp [2016/02/26 18:21] (curent)
199.119.124.44 ↷ Links adapted because of a move operation
@@ Linia 3: / Linia 3: @@
 * Responsabil: [[tudor.berariu@gmail.com|Tudor Berariu]]
 * Deadline: 29.05.2015 23:59
-* Data publicării: 07.05.2015 00:00
+* Data publicării: 07.05.2015
-* Data ultimei modificări: 07.05.2015 00:00
+* Data ultimei modificări: 12.05.2015
-* Data arhivei: 07.05.2015 00:00
+* Data testerului: 12.05.2015
 == Obiective ==
@@ Linia 13: / Linia 13: @@
 * utilizarea limbajului **Prolog** pentru a implementa un mecanism general de rezolvare a problemelor de satisfacere a restricțiilor
-== Algoritmi pentru rezolvarea problemelor de satisfacere a restricțiilor ==
+== Probleme de satisfacere a restricțiilor ==
-O problemă de satisfacere a restricțiilor este descrisă printr-un set de variabile **V**, o mulțime de domenii finite de valori pentru acestea **D** și un set de constrângeri **C**. Vom nota D(X) domeniul variabilei X ∈ **V**. O constrângere c va fi reprezentată printr-o relație între
+O problemă de satisfacere a restricțiilor este descrisă printr-un set de variabile **X**, o mulțime de domenii finite de valori pentru acestea **D** și un set de constrângeri **C**. Vom nota //D//(//x//) domeniul variabilei //x// ∈ **X**. O constrângere //c// va fi reprezentată printr-o relație între una sau mai multe variabile din **X**.
+O soluție pentru o astfel de problemă este reprezentată printr-o instanțiere a variabilelor din **X** cu valori ce satisfac toate restricțiile din **C**.
+== Algoritmul GAC3 ==
+Arc-consistența reprezintă o metodă pentru propagarea restricțiilor (eliminarea din domeniile variabilelor a acelor valori care nu pot face parte dintr-o soluție a problemei). Arc-consistența este obținută atunci când pentru fiecare valoare din domeniul unei variabile și pentru orice restricție care implică acea variabilă există o instanțiere a tuturor variabilelor implicate care conține acea valoare astfel încât restricția să fie satisfăcută.
+**AC3** este un algoritm pentru impunerea arc-consistenței asupra domeniilor de valori ale variabilelor unei probleme descrise prin restricții. AC3 a fost ulterior generalizat pentru hiperarce, descrise pentru relații între mai mult de 2 variabile, această variantă fiind numită GAC3. Pseudocodul GAC3 este scris în Algoritmul 1.
+{{15:teme:prolog-csp:algoritmul1.png|}}
+Algoritmul GAC primește variabilele problemei **X**, domeniile acestora **D**, un set de hiperarce ce trebuie verificate și mulțimea tuturor constrângerilor problemei **C**. GAC3 consideră la fiecare pas un hiperarc care corespunde unei restricții //c// și unei variabile //x//. Ceea ce se urmărește la un ciclu este eliminarea tuturor valorilor din domeniul lui //x// pentru care restricția //c// nu poate fi satisfăcută. Verificarea se face cu ajutorul funcției ''Revise'' (Algoritmul 2) care pentru fiecare valoare //v// din domeniul variabilei //x// caută un set de valori de suport //τ// pentru care este satisfăcută restricția. Dacă un astfel de set suport nu este găsit, valoarea //v// este eliminată din domeniul lui //x//.
+{{ 15:teme:prolog-csp:algoritmul2.png |}}
+Mulțimea suport //τ// conține o instanțiere a tuturor variabilelor implicate în restricția //c// în care //x// are valoarea //v//. De aceea, pentru hiperarce cu un număr mare de variabile implicate, căutarea acestei mulțimi poate reprezenta o operație foarte costisitoare.
+Dacă, după aplicarea funcției ''Revise'' pentru un hiperarc domeniul variabilei //x// este redus, atunci se verifică domeniile tuturor variabilelor care apar împreună cu //x// într-o constrângere (alta decât //c//). Drept urmare, pentru orice constrângere //c'// care implică variabila //x// se adaugă câte un hiperarc pentru fiecare altă variabilă //y// ∈ //Vars(c')//, //y//≠//x//.
+Algoritmul se oprește atunci când nu mai există hiperarce de verificat sau când cel puțin unul dintre domeniile de valori este vid (în acest caz nu există soluție).
+== Algoritmul MAC ==
+Una dintre tehnicile clasice de rezolvare a problemelor de satisfacere a restricțiilor o reprezeintă algoritmul backtracking, algoritm complet (găsește soluțiile problemei, dacă acestea există). De cele mai multe ori se dorește o optimizare a algoritmului backtracking prin reducerea spațiului de căutare chiar în timpul rulării algoritmului. O metodă de optimizare o reprezintă impunerea și menținerea arc-consistenței la fiecare pas al algoritmului (atât timp cât există variabile neinstanțiate). Metoda a fost propusă de Gasching, iar algoritmul este cunoscut după acronimul MAC (Maintaining Arc Consistency).
+Înainte de începerea căutării se aplică un algoritm pentru obținerea arc-consistenței verificându-se toate hiperarcele posibile. Apoi, la fiecare nod al arborelui de căutare, se impune arc-consistența pentru acele restricții corespunzătoare variabilei instanțiate în acel nod. Mai precis, dacă variabila x este cea insanțiată la pasul curent, se va impune arc-consistența pentru toate hiperarcele (y, c), unde c ∈ **C** este o constrângere cu x ∈ Vars( c ), iar y ∈ Vars( c )\{x}.
+Pentru reducerea spațiului de căutare (a domeniilor variabilelor) la rularea algoritmului backtracking se pot impune restricții locale de consistență mai puternice decât arc-consistența, dar, în general, MAC reprezintă un compromis bun între costul propagării restricțiilor și dimensiunea spațiului efectiv explorat.
 == Cerințe ==
@@ Linia 27: / Linia 53: @@
 </code>
-unde:
+''%%Vars%%'' reprezintă mulțimea tuturor variabilelor problemei (o listă de variabile Prolog). De exemplu: ''%%[X, Y, Z]%%''.
-  * ''%%Vars%%'' reprezintă mulțimea tuturor variabilelor problemei (o listă de variabile Prolog)
-    * de exemplu: ''%%[X, Y, Z]%%''
-  * ''%%Domains%%'' reprezintă lista domeniilor de valori pentru variabilele ''%%Vars%%''
+''%%Domains%%'' reprezintă lista domeniilor de valori pentru variabilele ''%%Vars%%''. De exemplu: ''%%[[1,2,3], [3,4], [1,4,7]]%%''.
-    * de exemplu: ''%%[[1,2,3], [3,4], [1,4,7]]%%''
-  * ''%%Constraints%%'' reprezintă lista tuturor restricțiilor problemei. O constrângere va fi reprezentată printr-o structură ''%%constraint(CVars, Expression)%%'' unde
+''%%Constraints%%'' reprezintă lista tuturor restricțiilor problemei. O constrângere va fi reprezentată printr-o structură ''%%constraint(CVars, Expression)%%'' unde
     * ''%%CVars%%'' reprezintă lista variabilelor implicate de acea constrângere (o listă de variabile Prolog)
     * ''%%Expression%%'' reprezintă un scop Prolog ce va putea fi verificat după instanțierea variabilelor din ''%%CVars%%''
-    * de exemplu: ''%%[constraint([X], X > 0), constraint([X, Y, Z], X =:= Y + Z)]%%''
+De exemplu: ''%%[constraint([X], X > 0), constraint([X, Y, Z], X =:= Y + Z)]%%''.
-  * ''%%HyperArcs%%'' reprezintă lista hiper-arcelor ce trebuie verificate. Un hiper-arc va fi reprezentat astfel: ''%%hypeararc(X, Ys, Constraint)%%'', unde
+''%%HyperArcs%%'' reprezintă lista hiperarcelor ce trebuie verificate. Un hiperarc va fi reprezentat astfel: ''%%hypeararc(X, Ys, Constraint)%%'', unde
     * ''%%X%%'' reprezintă variabila al cărei domeniu trebuie verificat pentru consistență
     * ''%%Ys%%'' reprezintă lista celorlalte variabile implicate în restricție
     * ''%%Constraint%%'' reprezintă un scop Prolog ce va putea fi verificat după instanțierea lui ''%%X%%'' și a celorlalte variabile ''%%Ys%%''
-    * exemplu: ''%%[hyperarc(X,[], X>0), hyperarc(Z, [X, Y], X =:= Y + Z)]%%''
+De exemplu: ''%%[hyperarc(X,[], X>0), hyperarc(Z, [X, Y], X =:= Y + Z)]%%''.
-  * ''%%RevisedDomains%%'' reprezintă lista domeniilor variabilelor problemei după impunerea arc-consistenței
+''%%RevisedDomains%%'' reprezintă lista domeniilor variabilelor problemei după impunerea arc-consistenței.
 Observație: listele ''%%Vars%%'', ''%%Domains%%'' și ''%%RevisedDomains%%'' vor avea același număr de elemente.
+=== Cerința 2 (0.3p): Algoritmul MAC ===
+Să se scrie un predicat ''%%solve_csp/4%%'' pentru rezolvarea problmelor de satisfacere a restricțiilor:
+<code prolog>
+solve_csp(+Vars, +Domains, +Constraints, -Solution)
+</code>
+Argumentele ''%%Vars%%'', ''%%Domains%%'' și ''%%Constraints%%'' reprezintă aceleași lucruri precum în cazul predicatului ''%%gac3/5%%''.
+Prin satisfacerea unui scop ''%%solve_csp%%'', variabila ''%%Solution%%'' va fi legată la o listă de valori pentru variabilele ''%%Vars%%'' care compun o soluție a problemei.
+De exemplu:
+<code prolog>
+?- solve_csp([X,Y,Z],
+             [[1,2,3], [1,2,3], [1,2,3]],
+             [constraint([X], X > 2), constraint([X, Y, Z], X < Y + Z)],
+             Solution).
+Solution = [3, 1, 3];
+Solution = [3, 2, 2];
+Solution = [3, 3, 1].
+</code>
+=== Cerința 3 (BONUS 0.2p): Reprezentarea unei probleme cu ajutorul restricțiilor ===
+Asemeni exemplelor oferite, se cere reprezentarea Problemei lui Einstein folosind restricții (după modelul celor date ca exemplu în fișierul de test). Trebuie identificate variabilele, domeniile acestora, precum și constrângerile problemei.
+Problema spune că în cinci case așezate de-a lungul unui drum locuiesc cinci bărbați de naționalitîți diferite care fumează cinci mărci diferite de țigări, au cinci băuturi preferate diferite și cinci animale de companie diferite.
+În plus, se știu următoarele:
+• Englezul locuiește în casa roșie.
+• Suedezul are câini.
+• Danezul bea ceai.
+• Casa verde este în stânga celei albe.
+• Stăpânul casei verzi bea cafea.
+• Fumătorul de Pall Mall crește păsări.
+• Stăpânul casei galbene fumează Dunhills.
+• Omul din casa din mijloc bea lapte.
+• Norvegianul locuiește în prima casă.
+• Fumătorul de Blend are un vecin nebun ce ține pisici.
+• Fumătorul de Blue Masters bea bere.
+• Bărbatul care are cai locuiește lângă fumătorul de Dunhill.
+• Germanul fumează Prince.
+• Norvegianul locuiește lângă casa albastră.
+• Fumătorul de Blend are un vecin a cărui băutură favorită este apa.
+Se cere să se afle ce naționalitate are cel cu Pești
+Scrieți un predicat ''%%einstein(-Vars, -FishNationality, -Domains, -Constraints)%%'' prin sastisfacerea căruia ''%%Vars%%'' devine lista variabilelor, ''%%FishNationality%%'' va fi variabila ce va conține răspunsul ghicitorii, ''%%Domains%%'' va fi lista cu domeniile de valori, iar ''%%Constraints%%'' va fi lista tuturor constrângerilor problemei.
+<code prolog>
+?- einstein(Vars, FishNationality, Domains, Constraints).
+</code>
+== Testare ==
+Pentru testare folosiți fișierul {{15:teme:prolog-csp:tests.pl|tester}}.
+Puteți începe implementarea de la fișierul {{15:teme:prolog-csp:tema3.pl|skel}}.

Paradigme de Programare

Unelte utilizator

Unelte site

Diferențe

Unelte pagină