• 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)
  • de exemplu: [X, Y, Z]

• Domains reprezintă lista domeniilor de valori pentru variabilele Vars
  • de exemplu: [[1,2,3], [3,4], [1,4,7]]

• 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)]

• HyperArcs reprezintă lista hiper-arcelor ce trebuie verificate. Un hiper-arc va fi reprezentat astfel: hypeararc(X, Ys, Constraint), unde
  • X reprezintă variabila al cărei domeniu trebuie verificat pentru consistență
  • Ys reprezintă lista celorlalte variabile implicate în restricție
  • Constraint reprezintă un scop Prolog ce va putea fi verificat după instanțierea lui X și a celorlalte variabile Ys
  • exemplu: [hyperarc(X,[], X>0), hyperarc(Z, [X, Y], X =:= Y + Z)]

• RevisedDomains reprezintă lista domeniilor variabilelor problemei după impunerea arc-consistenței

Observație: listele Vars, Domains și RevisedDomains vor avea același număr de elemente.