Unelte utilizator
15:teme:prolog-csp
Diferențe
Aici sunt prezentate diferențele dintre versiunile selectate și versiunea curentă a paginii.
| Both sides previous revision Versiuni anterioare Urmatoarea versiune | Versiuni anterioare | ||
|
15:teme:prolog-csp [2015/05/06 22:18] Tudor Berariu [Algoritmul MAC] |
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]] | * Responsabil: [[tudor.berariu@gmail.com|Tudor Berariu]] | ||
| * Deadline: 29.05.2015 23:59 | * 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 == | == Obiective == | ||
| Linia 15: | Linia 15: | ||
| == Probleme 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 una sau mai multe variabile din **V**. | + | 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 **V** cu valori ce satisfac toate restricțiile din **C**. | + | 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 == | == Algoritmul GAC3 == | ||
| Linia 23: | Linia 23: | ||
| 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ă. | 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 == | == Algoritmul MAC == | ||
| Linia 29: | Linia 42: | ||
| Î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}. | Î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 == | == Cerințe == | ||
| Linia 79: | Linia 93: | ||
| Solution = [3, 3, 1]. | Solution = [3, 3, 1]. | ||
| </code> | </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}}. | ||
15/teme/prolog-csp.1430939924.txt.gz · Ultima modificare: 2015/05/06 22:18 de către Tudor Berariu
