• 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 una sau mai multe variabile din V.

O soluție pentru o astfel de problemă este reprezentată printr-o instanțiere a variabilelor din V cu valori ce satisfac toate restricțiile din C.

Arc-consistența reprezintă o metodă pentru propagarea restricțiilor (eliminarea din domeniile variabilelor a acelor valori care nu pot face parte dintr-o soluție a problemei). Arc-consistența este obținută atunci când pentru fiecare valoare din domeniul unei variabile și pentru orice restricție care implică acea variabilă există o instanțiere a tuturor variabilelor implicate care conține acea valoare astfel încât restricția să fie satisfăcută.

Una dintre tehnicile clasice de rezolvare a problemelor de satisfacere a restricțiilor o reprezeintă algoritmul backtracking, algoritm complet (găsește soluțiile problemei, dacă acestea există). De cele mai multe ori se dorește o optimizare a algoritmului backtracking prin reducerea spațiului de căutare chiar în timpul rulării algoritmului. O metodă de optimizare o reprezintă impunerea și menținerea arc-consistenței la fiecare pas al algoritmului (atât timp cât există variabile neinstanțiate). Metoda a fost propusă de Gasching, iar algoritmul este cunoscut după acronimul MAC (Maintaining Arc Consistency).

Înainte de începerea căutării se aplică un algoritm pentru obținerea arc-consistenței verificându-se toate hiperarcele posibile. Apoi, la fiecare nod al arborelui de căutare, se impune arc-consistența pentru acele restricții corespunzătoare variabilei instanțiate în acel nod. Mai precis, dacă variabila x este cea insanțiată la pasul curent, se va impune arc-consistența pentru toate hiperarcele (y, c), unde c ∈ C este o constrângere cu x ∈ Vars( c ), iar y ∈ Vars( c )\{x}.

Pentru reducerea spațiului de căutare (a domeniilor variabilelor) la rularea algoritmului backtracking se pot impune restricții locale de consistență mai puternice decât arc-consistența, dar, în general, MAC reprezintă un compromis bun între costul propagării restricțiilor și dimensiunea spațiului efectiv explorat.

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)

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 hiperarcelor ce trebuie verificate. Un hiperarc 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

De 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.

Să se scrie un predicat solve_csp/4 pentru rezolvarea problmelor de satisfacere a restricțiilor:

solve_csp(+Vars, +Domains, +Constraints, -Solution)

Argumentele Vars, Domains și Constraints reprezintă aceleași lucruri precum în cazul predicatului gac3/5.

Prin satisfacerea unui scop solve_csp, variabila Solution va fi legată la o listă de valori pentru variabilele Vars care compun o soluție a problemei.

De exemplu:

?- solve_csp([X,Y,Z],
             [[1,2,3], [1,2,3], [1,2,3]],
             [constraint([X], X > 2), constraint([X, Y, Z], X < Y + Z)],
             Solution).
Solution = [3, 1, 3];
Solution = [3, 2, 2];
Solution = [3, 3, 1].