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/12 00:29] Tudor Berariu [Cerința 3 (BONUS 0.2p): Reprezentarea unei probleme cu ajutorul restricțiilor] |
15:teme:prolog-csp [2016/02/26 18:21] (curent) 199.119.124.44 ↷ Links adapted because of a move operation |
||
|---|---|---|---|
| Linia 4: | Linia 4: | ||
| * Deadline: 29.05.2015 23:59 | * Deadline: 29.05.2015 23:59 | ||
| * Data publicării: 07.05.2015 | * Data publicării: 07.05.2015 | ||
| - | * Data ultimei modificări: 07.05.2015 | + | * Data ultimei modificări: 12.05.2015 |
| - | * Data arhivei: 07.05.2015 | + | * 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 125: | Linia 125: | ||
| ?- einstein(Vars, FishNationality, Domains, Constraints). | ?- einstein(Vars, FishNationality, Domains, Constraints). | ||
| </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.1431379794.txt.gz · Ultima modificare: 2015/05/12 00:29 de către Tudor Berariu
