Creati un prototip functional de solver CSP, pe platforma de programare Java si expuneti functionalitatea acestuia sub forma unui serviciu Web.

O serie de probleme deosebit de importante din punct de vedere stiintific si economic, cum ar fi problemele de planficare sau rutare se dovedesc de o complexitate prea mare pentru a fi abordate cu tehnici matematice uzuale, cum ar fi programarea liniara.

Pornind de la aceasta premiza, in ultimii ani s-a dezvoltat teoria satisfacerii constrangerilor care defineste un model pentru reprezentarea problemelor sub forma unei retele de constrangeri si o serie de tehnici de programare pentru rezolvarea acestora. Din punct de vedere stiintific, programarea cu constrangeri imbina aspecte legate de logica, teoria grafurilor si inteligenta artificiala.

Problemele de satisfacere a constrangerilor sunt utilizate in orice situatie in care este necesar sa identificam o stare a unui sistem format dintr-o multime de obiecte care sa satisfaca o serie de restrictii, numite constrangeri. Obiectele problemei initiale sunt modelate cu ajutorul unor variabile care au asociate anumite domenii de valori iar o solutie reprezinta o atribuire de valori acestor variabile astfel incat sa fie respectate toate constrangerile.

O variabila formalizeaza o necunoscuta a problemei, fiind o reprezentare simbolica a unui obiect caruia trebuie sa-i atribuim o anumita valoare. Nu se impune nici o restrictie asupra tipului unei variabile, elementele acestuia putand fi intregi, logice, multimi sau orice altceva. De asemenea, nu este necesar ca toate variabilele sa aiba acelasi tip. Fiecarei variabile ii este asociat un domeniu reprezentand multimea valorilor posibile pe care le poate primi acea variabila.

O constrangere poate fi privita intuitiv ca o restrictionare a spatiului posibilelor solutii ale unei probleme. Ca si in cazul variabilelor, nu se impune nici o modalitate de specificare a constrangerilor, orice informatie ce poate fi extrasa dintr-un set de specificatii corespunzatoare unei probleme putand fi privita ca o restrangere a domeniului solutiilor acesteia, deci ca o constrangere.

Asadar, modelarea unei probleme presupune identificarea urmatoarelor componente:

• un set finit de variabile,
• o functie care mapeaza fiecare variabila la un domeniu finit,
• un set finit de constrangeri.

Gasirea unei solutii pentru respectiva problema consta in atribuirea fiecarei variabile a unei valori din domeniul sau astfel incat nici o constrangere sa nu fie incalcata. In functie de natura problemei, rezolvarea poate consta in identificarea : fie a unei singure solutii, indiferent care este aceasta, fie a tuturor solutiilor.

Mai jos sunt doar cateva exemple de probleme care demonstreaza aria larga de aplicabilitate a acestui tip de reprezentare:

• Problema celor 8 regine;
• Probleme cripto-aritmetice (SEND+MORE=MONEY);
• Patratul magic, Patratul latin, Sudoku, etc.;
• Colorarea grafurilor;
• Problema satisfiabilitatii (SAT).

Resurse online: On-Line Guide to Constraint Programming.

Exemplu de solver CSP: Choco.

Echipa: maxim 4 studenti.

Bonus: maxim 10 puncte (dintr-un total de 24 )  la laboratorul din cadrul disciplinei “Tehnici Avansate de Programare” (anul II, semestrul II).

Proiect propus de: domnul profesor, lector, doctor, Cristian Frasinaru.