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 23:00] Tudor Berariu |
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 25: | Linia 25: | ||
| **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. | **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. | ||
| - | {{:teme15:prolog-csp:algoritmul1.png|}} | + | {{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//. | 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//. | ||
| - | {{ :teme15:prolog-csp:algoritmul2.png |}} | + | {{ 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. | 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. | ||
| Linia 96: | Linia 96: | ||
| === Cerința 3 (BONUS 0.2p): Reprezentarea unei probleme cu ajutorul restricțiilor === | === 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 și rezolvarea acesteia cu programul scris anterior. Trebuie identificate variabilele, domeniile acestora, precum și constrângerile problemei. | + | 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. | 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. | ||
| Linia 118: | Linia 118: | ||
| • Fumătorul de Blend are un vecin a cărui băutură favorită este apa. | • Fumătorul de Blend are un vecin a cărui băutură favorită este apa. | ||
| - | Scrieți o regulă care să afle naționalitatea celui care crește pești. | + | 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> | <code prolog> | ||
| - | ?- einstein(Nationality). | + | ?- einstein(Vars, FishNationality, Domains, Constraints). |
| - | Nationality=... | + | |
| </code> | </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.1430942447.txt.gz · Ultima modificare: 2015/05/06 23:00 de către Tudor Berariu
