• Responsabil: Tudor Berariu
• Deadline: 29.05.2015 23:59
• Data publicării: 07.05.2015 00:00
• Data ultimei modificări: 07.05.2015 00:00
• Data arhivei: 07.05.2015 00:00

• înțelegerea problemelor de satisfacere a restricțiilor și a mecanismelor de rezolvare a acestora
• înțelegerea conceptului de arc-consistență și implementarea unui algoritm de propagare a constrângerilor: AC3
• utilizarea limbajului Prolog pentru a implementa un mecanism general de rezolvare a problemelor 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

Să se scrie un predicat gac3/5 pentru revizuirea domeniilor de valori ale unor variabile folosind algoritmul GAC3 descris mai sus.

gac3(+Vars, +Domains, +Constraints, +HyperArcs, -RevisedDomains)

unde:

• Vars reprezintă mulțimea tuturor variabilelor problemei (o listă de variabile Prolog
• Domains reprezintă lista domeniilor de valori pentru variabilele Vars
• 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)]