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:44] Tudor Berariu [Prolog: CSP] |
15:teme:prolog-csp [2016/02/26 18:21] (curent) 199.119.124.44 ↷ Links adapted because of a move operation |
||
|---|---|---|---|
| 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 128: | Linia 128: | ||
| == Testare == | == Testare == | ||
| - | Pentru testare folosiți fișierul {{:teme15:prolog-csp:tests.pl|tester}}. | + | Pentru testare folosiți fișierul {{15:teme:prolog-csp:tests.pl|tester}}. |
| - | Puteți începe implementarea de la fișierul {{:teme15:prolog-csp:tema3.pl|skel}}. | + | Puteți începe implementarea de la fișierul {{15:teme:prolog-csp:tema3.pl|skel}}. |
15/teme/prolog-csp.1431380682.txt.gz · Ultima modificare: 2015/05/12 00:44 de către Tudor Berariu
