probleme algoritmice ˆın studiul propriet˘at¸ilor ...acf/csp/teza.pdf · 3.2 backtracking ......

Facultatea de Informatica

Universitatea ”Al. I. Cuza” Iasi

Probleme algoritmice ın studiulproprietatilor ereditare pe

grafuri

Teza de doctorat

Doctorand: Cristian Frasinaru

Coordonator: Prof. Dr. Elefterie Olaru

Noiembrie, 2006

MultumiriMultumesc conducatorului meu de doctorat, domnul profesor doctor Elef-

terie Olaru, pentru sprijinul, ındrumarile si bunavointa acordate pe ıntreagaperioada ın care mi-a supervizat activitatea.

De asemenea, multumesc domnului profesor doctor Cornelius Croitorupentru sansa pe care mi-a oferit-o de a lucra alaturi de dumnealui si pentrutoate sfaturile acordate de-a lungul anilor, sfaturi care m-au ajutat sa madezvolt atat din punct de vedere profesional, dar si ca om.

Multumesc mult sotiei mele si ıntregii familii pentru faptul ca m-auıncurajat si m-au ajutat sa duc la bun sfarsit aceasta lucrare.

DeclaratieDeclar ca aceasta teza este scrisa de mine si toate rezultatele prezen-

tate sunt obtinute de mine, cu exceptia celor care sunt marcate cu referintebibliografice sau sunt declarate explicit ca fiind preluate de la alti autori.

Cristian Frasinaru, noiembrie 2006

Cuprins

1 Introducere 51.1 Continutul tezei . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Satisfacerea constrangerilor 112.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.2 Definitii de baza . . . . . . . . . . . . . . . . . . . . . . . . . . 14

2.2.1 Tuple, relatii . . . . . . . . . . . . . . . . . . . . . . . 142.2.2 Reprezentarea relatiilor . . . . . . . . . . . . . . . . . . 142.2.3 Operatii cu relatii . . . . . . . . . . . . . . . . . . . . . 15

2.3 Retele de constrangeri . . . . . . . . . . . . . . . . . . . . . . 182.3.1 Solutiile unei retele de constrangeri . . . . . . . . . . . 192.3.2 Echivalenta retelelor . . . . . . . . . . . . . . . . . . . 192.3.3 Reprezentarea retelelor . . . . . . . . . . . . . . . . . . 202.3.4 Rezolvarea retelelor de constrangeri . . . . . . . . . . . 222.3.5 Analiza complexitatii . . . . . . . . . . . . . . . . . . . 24

2.4 Satisfacerea partiala a constrangerilor . . . . . . . . . . . . . . 272.4.1 Instante specifice . . . . . . . . . . . . . . . . . . . . . 302.4.2 Operatii cu functia de cost . . . . . . . . . . . . . . . . 302.4.3 Cautarea solutiilor . . . . . . . . . . . . . . . . . . . . 312.4.4 Algoritmul ”branch-and-bound”(b-b) . . . . . . . . . . 322.4.5 Functii de marginire inferioara . . . . . . . . . . . . . . 342.4.6 Functii de marginire superioara . . . . . . . . . . . . . 372.4.7 Tehnici locale de cautare . . . . . . . . . . . . . . . . . 37

3 Rezolvarea retelelor de constrangeri 393.1 Algoritmi sistematici de cautare . . . . . . . . . . . . . . . . . 393.2 Backtracking . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

3.2.1 Structura generala a algoritmului . . . . . . . . . . . . 40

1

2 CUPRINS

3.2.2 Testarea consistentei unei instantieri partiale . . . . . . 403.3 Backjumping . . . . . . . . . . . . . . . . . . . . . . . . . . . 423.4 Backmarking . . . . . . . . . . . . . . . . . . . . . . . . . . . 443.5 Algoritmi de filtrare si propagare . . . . . . . . . . . . . . . . 453.6 Arc-consistenta . . . . . . . . . . . . . . . . . . . . . . . . . . 48

3.6.1 Algoritmul de proiectie . . . . . . . . . . . . . . . . . . 503.6.2 Constructia unei subretele cu doua variabile . . . . . . 503.6.3 Testarea arc-consistentei . . . . . . . . . . . . . . . . . 513.6.4 Procedura de reducere a domeniilor Revise . . . . . . . 523.6.5 Algoritmul de arc-consistenta AC-1 . . . . . . . . . . . 533.6.6 Algoritmul de arc-consistenta AC-3 . . . . . . . . . . . 543.6.7 Algoritmul de arc-consistenta AC-4 . . . . . . . . . . . 55

3.7 Constrangeri globale . . . . . . . . . . . . . . . . . . . . . . . 563.7.1 Exemple de constrangeri globale . . . . . . . . . . . . . 573.7.2 AllDiff . . . . . . . . . . . . . . . . . . . . . . . . . . . 583.7.3 Global Cardinality Constraint (GCC) . . . . . . . . . . 61

4 Crearea unui solver CSP 654.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 654.2 Nivelul de modelare . . . . . . . . . . . . . . . . . . . . . . . . 68

4.2.1 Reprezentarea problemei . . . . . . . . . . . . . . . . . 684.2.2 Definirea variabilelor . . . . . . . . . . . . . . . . . . . 704.2.3 Crearea domeniilor . . . . . . . . . . . . . . . . . . . . 724.2.4 Specificarea constrangerilor . . . . . . . . . . . . . . . 734.2.5 Reprezentarea tuplelor . . . . . . . . . . . . . . . . . . 75

4.3 Nivelul de control . . . . . . . . . . . . . . . . . . . . . . . . . 754.3.1 Conceptul general de solver . . . . . . . . . . . . . . . 764.3.2 Rezolvarea sistematica (completa) . . . . . . . . . . . . 784.3.3 Exemplu de implementare . . . . . . . . . . . . . . . . 814.3.4 Definirea strategiilor de explorare . . . . . . . . . . . . 85

4.4 Monitorizarea procesului de rezolvare . . . . . . . . . . . . . . 884.5 Crearea constrangerilor . . . . . . . . . . . . . . . . . . . . . . 92

4.5.1 Constrangeri explicite . . . . . . . . . . . . . . . . . . 924.5.2 Constrangeri binare . . . . . . . . . . . . . . . . . . . . 944.5.3 Constrangeri oarecare . . . . . . . . . . . . . . . . . . 944.5.4 Constrangeri globale . . . . . . . . . . . . . . . . . . . 97

4.6 Retele slabe de constrangeri . . . . . . . . . . . . . . . . . . . 994.6.1 Structuri de evaluare . . . . . . . . . . . . . . . . . . . 99

CUPRINS 3

4.6.2 Modelarea unei probleme de optimizare . . . . . . . . . 1014.6.3 Optimizare multi-criteriala . . . . . . . . . . . . . . . . 102

5 Explicatii 1055.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1055.2 Ce ınseamna o explicatie ? . . . . . . . . . . . . . . . . . . . . 106

5.2.1 Cum poate fi explicata inconsistenta ? . . . . . . . . . 1075.2.2 Multimi suport . . . . . . . . . . . . . . . . . . . . . . 109

5.3 Construirea unei explicatii . . . . . . . . . . . . . . . . . . . . 1115.3.1 Graful eliminarilor . . . . . . . . . . . . . . . . . . . . 1115.3.2 Arborele reducerilor . . . . . . . . . . . . . . . . . . . 114

5.4 Implementarea algoritmului . . . . . . . . . . . . . . . . . . . 119

6 Problema satisfiabilitatii 1216.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1216.2 Un nod model CSP pentru SAT . . . . . . . . . . . . . . . . . 1226.3 Graful asociat modelului CSP . . . . . . . . . . . . . . . . . . 1256.4 Arc consistenta . . . . . . . . . . . . . . . . . . . . . . . . . . 1276.5 Proprietati ale grafului . . . . . . . . . . . . . . . . . . . . . . 1286.6 Implementare si experimente . . . . . . . . . . . . . . . . . . . 1316.7 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133

7 Problema orarului 1357.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135

7.1.1 Activitati (Evenimente) . . . . . . . . . . . . . . . . . 1367.1.2 Domeniul temporal . . . . . . . . . . . . . . . . . . . . 1387.1.3 Participanti (Actori) . . . . . . . . . . . . . . . . . . . 1387.1.4 Resurse . . . . . . . . . . . . . . . . . . . . . . . . . . 140

7.2 Reteaua de constrangeri . . . . . . . . . . . . . . . . . . . . . 1407.2.1 Variabile si domenii . . . . . . . . . . . . . . . . . . . . 1417.2.2 Constrangeri . . . . . . . . . . . . . . . . . . . . . . . 1427.2.3 Complexitatea problemei . . . . . . . . . . . . . . . . . 149

7.3 Rezolvarea problemei orarului . . . . . . . . . . . . . . . . . . 150

8 Rezolvarea interactiva a problemelor 1538.1 Starea unui solver . . . . . . . . . . . . . . . . . . . . . . . . . 1548.2 Oprirea si reluarea executiei . . . . . . . . . . . . . . . . . . . 1558.3 Salvarea si restaurarea starii extinse . . . . . . . . . . . . . . . 158

4 CUPRINS

8.4 Extinderea starii curente . . . . . . . . . . . . . . . . . . . . . 1588.5 Anularea unor decizii . . . . . . . . . . . . . . . . . . . . . . . 1588.6 Inactivarea unor variabile . . . . . . . . . . . . . . . . . . . . 1598.7 Adaugarea de noi variabile . . . . . . . . . . . . . . . . . . . . 1618.8 Modificarea constrangerilor . . . . . . . . . . . . . . . . . . . . 1618.9 Concluzii . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162

9 Probleme de colorare 1639.1 Introducere . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1639.2 Colorarea grafurilor . . . . . . . . . . . . . . . . . . . . . . . . 1649.3 Rezolvarea unor probleme de colorare . . . . . . . . . . . . . . 167

9.3.1 Colorarea varfurilor unui graf . . . . . . . . . . . . . . 1679.3.2 Star-coloring . . . . . . . . . . . . . . . . . . . . . . . . 1679.3.3 Acyclic-coloring . . . . . . . . . . . . . . . . . . . . . . 1689.3.4 Harmonious-coloring . . . . . . . . . . . . . . . . . . . 169

9.4 Euristici de colorare . . . . . . . . . . . . . . . . . . . . . . . . 1709.5 Analizoare de problema . . . . . . . . . . . . . . . . . . . . . . 171

10 Concluzii 175

Capitolul 1

Introducere

Ideea de la care a pornit realizarea acestei teze poate fi redusa la urmatoareaıntrebare: ”Data o problema, cum putem sa o rezolvam ?”. Dezvoltareaindustriei si economiei, gradul de tehnologizare a societatii curente fac ca ıncadrul foarte multor procese de calcul sau sisteme integrate de analiza saintervina situatii complexe a caror rezolvare nu este deloc evidenta. Domeni-ile de activitate din care aceste probleme provin sunt extrem de diverse side multe ori aceeasi problema se poate ascunde sub o multitudine de forme,diferentele sintactice fiind date de modurile specifice de formulare ale fiecaruitip de activitate ın parte.

Asadar, data o problema, cum putem sa o rezolvam ? Primul pas este,evident, sa o reformulam ıntr-un mod abstract astfel ıncat particularitatiledomeniului din care provine sa devina transparente, ıncercand astfel inte-grarea ei ıntr-o clasa de probleme cunoscute. Daca acest lucru este posibil,putem apela la ”baza de date” a algoritmilor existenti pentru clasa respec-tiva de probleme si sa folosim unul din ei. In cazul ın care acest lucru nu esterealizabil, singura solutie ar fi dezvoltarea unui algoritm dedicat problemeirespective, abordare care ınsa poate fi anevoioasa si implica atat efort teo-retic pentru gasirea unei solutii eficiente cat si efort pentru implementareaei. Din punct de vedere practic, acest proces poate fi extrem de costisitor.Un alt aspect care trebuie luat ın calcul este urmatorul: chiar ın conditia ıncare am redus problema initiala la una deja cunoscuta, exista un algoritmeficient pentru ea ?

Conform teoriei complexitatii, problemele de decizie care pot fi rezolvatede o masina secventiala determinista ın timp polinomial relativ la dimen-siunea intrarii formeaza clasa de complexitate P. Acestea sunt considerate

5

6 CAPITOLUL 1. INTRODUCERE

”usoare”, ın sensul ca timpul de lucru creste proportional cu dimensiuneadatelor de intrare.

Clasa NP este reprezentata de probleme de decizie ale caror solutii potfi verificate ın timp polinomial sau care pot fi gasite ın timp polinomial de omasina nedeterminista. Asadar P ⊆ NP dar, dupa cum se stie, incluziuneastricta nu a fost demonstrata ınca. O clasa aparte este cea a problemelorNP-complete, sau a asa numitelor probleme ”dificile” din NP, ce are pro-prietatea ca daca una din ele ar putea fi rezolvata de un algoritm polinomial,atunci acel algoritm ar putea fi folosit pentru rezolvarea tuturor din aceastaclasa.

In 1979, Michael Garey si David Johnson ın lucrarea ”Computers andIntractability: A Guide to the Theory of NP-Completeness” [40] au realizatun compendiu al problemelor NP-complete astfel ıncat acestea sa poata fifolosite ca reper ın ıncercarea de a determina gradul de dificultate al uneiprobleme oarecare.

In conditiile ın care am ajuns la concluzia ca problema noastra este NP-dificila este de asteptat sa nu dispunem de nici un algoritm eficient pentrurezolvarea ei. Este momentul ın care trebuie sa decidem ın ce fel dorimsolutionarea ei: este necesar sa obtinem toate solutiile exacte, doar a uneiasingure sau este suficienta o solutie aproximativa ? Sigur ca raspunsul laaceste ıntrebari depinde foarte mult si de natura problemei. Astfel, prob-lema satisifiabilitatii nu lasa loc la aproximari ın timp ce colorarea unui grafpoate fi privita ca o problema de optimizare ın care nu vrem decat o colorare”suficient de buna”, nu neaparat ideala. In cazul din urma, putem apela ladiferite tehnici de programare bazate pe euristici care, desi nu garanteazareusita, sunt folosite cu succes ın multe situatii. Vom presupune ın contin-uare ca nu suntem interesati ın principal de eurisitici, ci cautam o rezolvarecare sa permita, chiar ın cazul problemelor dificile, obtinerea unei sau a tu-turor solutiilor exacte ın conditia ın care dimensiunile datelor de intrare suntrezonabile.

Avand ın vedere toate aceste lucruri, dorim sa identificam un mecanismde rezolvare care sa poata fi aplicat ın mod unitar la cat mai multe tipuri deprobleme, sa poata aborda situatii NP-dificile cat mai performant posibil sisa puna ın valoare existenta unor restrictii polinomiale ale problemei date.

O teorie care ofera solutii pentru cerintele de mai sus este cea a satis-facerii constrangerilor, ın care problemele sunt modelate ca instante CSP(Constraint Satisfaction Problems) iar apoi sunt utilizate diferite tehnici deprogramare cu constrangeri pentru rezolvarea lor.

1.1. CONTINUTUL TEZEI 7

Desi lucrari dedicate constrangerilor au aparut ınca din anii ’70 [41], [36],[16], domeniul CSP a devenit activ stiintific ıncepand cu 1980, astazi fiindidentificat de ACM (Association for Computing Machinery) ca o ”directiestrategica de dezvoltare a informaticii”. Eugene C. Freuder spunea ın 1997:

”Constraint programming represents one of the closest approachescomputer science has yet made to the Holy Grail of programming:the user states the problem, the computer solves it.”

Programarea cu constrangeri a intrat deplin si ın aria aplicativa prin aparitiaunor sisteme comerciale foarte performante de rezolvare automata a prob-lemelor modelate cu constrangeri, cum ar fi Ilog Solver [27], dar si a uneimultitudini de alte aplicatii de acest tip create pe diverse platforme de pro-gramare Java, C++, Prolog, etc. [30], [31], [18]. Un aport esential la dez-voltarea si la impunerea paradigmei de programare cu constrangeri l-a avutsi saltul remarcabil al performantelor dispozitivelor hardware de calcul dinultimii ani. Incepand cu anii ’90 au aparut si o serie de monografii [13], [1],[50], [2], [45] care ofera o imagine de ansamblu asupra ıntregii teorii.

1.1 Continutul tezei

Capitolul 2 ısi propune sa ofere o imagine generala asupra teoriei satis-facerii constrangerilor, introducand definitiile si rezultatele necesare pentruprezentarile ulterioare. Pentru a respecta terminologia actuala, ca sursa prin-cipala bibliografica a fost utilizata recenta monografie ”Constraint Process-ing”, scrisa de Rina Dechter [13].

Capitolul 3 abordeaza o serie de tehnici care pot fi utilizate pentru re-zolvarea retelelor de constrangeri, accentul fiind pus pe algoritmii sistematicide explorare ai spatiului solutiilor.

Capitolul 4 constituie o descriere ampla a tuturor aspectelor care trebuieanalizate ın implementarea unui sistem software capabil sa rezolve problememodelate cu ajutorul constrangerilor, fiind de fapt o prezentare detaliata asolverului OmniCS 1 care a fost creat de noi pentru a sustine din punct devedere practic ideile din aceasta lucrare. In acest capitol sunt oferite exempleconcrete care sa ajute la ıntelegerea modului de utilizare a aplicatiei precum sispecificatiile necesare pentru a controla procesul general de gasire a solutiilor,

1http://omnics.sourceforge.net


cum ar fi strategiile de explorare a spatiului solutiilor sau asocierea unor al-goritmi dedicati de filtrare constrangerilor. De asemenea, o componenta im-portanta a sistemului de rezolvare consta ın posibilitatea de integrare a unoralgoritmi eficienti dezvoltati pentru diverse restrictii ale problemei initiale ıncadrul algoritmului general, ın scopul cresterii performantelor.

Implementarea solverului OmniCS reprezinta contributia principala atezei, acesta aducand numeroase lucruri noi fata de alte produse similareexistente la ora actuala, cum ar fi: rezolvarea atat a retelelor clasice de con-strangeri cat si a celor slabe, implementarea unui mecanism de observarea procesului de cautare a solutiei, posibilitatea de a genera explicatii si dea aborda probleme dinamice, interactivitate, etc. Pe langa acestea, trebuiementionat faptul ca a fost gandit astfel ıncat ıntelegerea, utilizarea si extin-derea acestuia sa fie extrem de simple, putand fi astfel folosit cu usurinta ınactivitati didactice sau de cercetare.

Capitolul 5 este o extensie a capitolului 4, ın care se ıncearca gasirea uneimodalitati de a raspunde la ıntrebarea: ”De ce o problema nu are solutie?”. Pe baza metodei alese pentru implementarea solverului a fost creat unmecanism capabil sa extraga pe parcursul procesului de rezolvare informatiilenecesare pentru a genera, ın cazul ın care problema nu are solutie, o suc-cesiune de rationamente care sa explice ıntr-un mod cat mai apropiat deıntelegerea umana motivul esecului. Explicatiile, asa cum au fost introduseın cadrul solverului Choco [31] cu extensia PaLM (Propagation and Learn-ing with Move) [6], se refera la informatii care sa explice starea curenta asistemului. Ceea ce ne propunem noi este sa cream o modalitate simpla degenerare a unei structuri de date din care sa putem extrage un rationamentcomplet si clar care sa demonstreze inconsistenta unei probleme.

Capitolul 6 este un prim studiu de caz ın care este analizata problema sat-isfiabilitatii ın varianta restransa 3-SAT. Sunt prezentate doua solutii diferitede reprezentare a problemei cu ajutorul constrangerilor, una fiind cea clasicafolosita ın mod curent de catre solverele SAT existente, iar cea de a douaconstituind o abordare originala de modelare care sa ne ofere transformareaproblemei 3-SAT ıntr-una echivalenta de grafuri. Studiind structura grafu-lui obtinut, pot fi identificate cazuri particulare care sa fie utilizate pentrueficientizarea procesului de rezolvare.

Capitolul 7 analizeaza problema orarului care, dupa cum se stie, este deasemenea o problema NP-dificila. Pe langa dezvoltarea unui model foarteflexibil care sa permita abordarea unor probleme de planificare cat mai di-verse a fost creata si o librarie de constrangeri cu ajutorul careia sa poata

1.1. CONTINUTUL TEZEI 9

fi formalizate restrictiile generale precum si preferintele participantilor, ınvederea rezolvarii automate a problemei.

Capitolul 8 reia problema orarului si pune ın evidenta aspecte legatede necesitatea ca un solver CSP sa fie interactiv, ın sensul de a permiteutilizatorului sa directioneze procesul de cautare a solutiei prin extindereamanuala a solutiei curente sau revocarea unor decizii luate de solver precumsi de a oferi posibilitatea de a modifica dinamic problema rezolvata prinadaugarea/eliminarea de variabile sau constrangeri.

Capitolul 9 descrie o serie de tehnici de modelare a problemelor de colorarea grafurilor, scopul final fiind integrarea unor alogritmi polinomiali dezvoltatipentru diverse clase de grafuri ın algoritmul general de rezolvare. In acestcontext, este introdusa notiunea de analizor de problema si sunt prezentatemodalitati de utilizare ale acestora.

Capitolul 10 prezinta concluziile tezei precum si principalele directii decercetare ulterioara.

Capitolul 2

Satisfacerea constrangerilor

2.1 Introducere

Problemele de satisfacere a constrangerilor sunt utilizate ın orice situatie ıncare este necesar sa identificam o stare a unui sistem format dintr-o multimede obiecte care sa satisfaca o serie de restrictii, numite constrangeri. Obiecteleproblemei initiale sunt modelate cu ajutorul unor variabile care au asociateanumite domenii de valori iar o solutie reprezinta o atribuire de valori acestorvariabile astfel ıncat sa fie respectate toate constrangerile. Avand ın vederegeneralitatea acestei definitii si diversitatea problemelor ce pot fi ıncadrateın aceasta categorie este necesar sa clarificam, deocamdata informal, o seriede aspecte cum ar fi:

• Cum pot fi formulate ın mod unitar problemele ?

– Ce este o variabila ?

– Ce este o constrangere si cum putem sa o specificam ?

• Ce tehnici de rezolvare putem utiliza ?

Dupa cum am spus deja, o variabila formalizeaza o necunoscuta a proble-mei, fiind o reprezentare simbolica a unui obiect caruia trebuie sa-i atribuimo anumita valoare. Nu se impune nici o restrictie asupra tipului unei vari-abile, elementele acestuia putand fi ıntregi, logice, multimi sau orice altceva.De asemenea, nu este necesar ca toate variabilele sa aiba acelasi tip. Fiecareivariabile ıi este asociat un domeniu reprezentand multimea valorilor posibilepe care le poate primi acea variabila.

11

12 CAPITOLUL 2. SATISFACEREA CONSTRANGERILOR

O constrangere poate fi privita intuitiv ca o restrictionare a spatiuluiposibilelor solutii ale unei probleme. Ca si ın cazul variabilelor, nu se im-pune nici o modalitate de specificare a constrangerilor, orice informatie cepoate fi extrasa dintr-un set de specificatii corespunzatoare unei problemeputand fi privita ca o restrangere a domeniului solutiilor acesteia, deci ca oconstrangere.

Modul de definire a constrangerilor trebuie sa satisfaca urmatoarele pro-prietati [3]:

• Constrangerile pot specifica informatii partiale; cu alte cuvinte con-strangerile pot sa nu identifice ın mod unic valorile permise pentruanumite variabile.

• Constrangerile sunt ne-directionale, o constrangere definita pe vari-abilele x si y avand aceeasi semantica atat din perspectiva variabilei xcat si a lui y: x = y + 1 si y = x− 1 sunt echivalente.

• Constrangerile sunt declarative; ele definesc o restrictie ce trebuie sat-isfacuta fara a specifica un mod computational de impunere a acesteirestrictii.

• Constrangerile sunt aditive; ordinea ın care acestea sunt impuse nuconteaza din punctul de vedere al rezultatului final.

• Constrangerile pot avea variabile comune ceea ce ınseamna ca satisfac-erea lor trebuie privita ın ansamblu si nu individual, pentru fiecare ınparte.

Asadar, modelarea unei probleme presupune identificarea urmatoarelorcomponente:

• un set finit de variabile,

• o functie care mapeaza fiecare variabila la un domeniu finit,

• un set finit de constrangeri.

In sectiunea urmatoare vom prezenta notiunea de retea de constrangeri careformalizeaza modalitatea de reprezentare a unei instante CSP.

Gasirea unei solutii pentru respectiva problema consta ın atribuirea fiecareivariabile a unei valori din domeniul sau astfel ıncat nici o constrangere sanu fie ıncalcata. In functie de natura problemei, rezolvarea poate consta ınidentificarea :

2.1. INTRODUCERE 13

• unei singure solutii, indiferent care este aceasta;

• tuturor solutiilor;

• unei solutii optime, sau care se apropie cat mai mult de un optim stiut,ın cazul ın care este specificata o functie obiectiv definita pe variabileleproblemei.

Mai jos sunt doar cateva exemple de probleme care demonstreaza arialarga 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) [11]

• Probleme de rutare si explorare [10]

• Crearea interfetelor grafice [21]

• ...

”Problema celor n regine”Inainte de a formaliza notiunile prezentate pana acum, sa consideram unexemplu concret de problema pe care sa o modelam din perspectiva CSP.

Un exemplu clasic frecvent utilizat pentru a demonstra modalitatea deutilizare a constrangerilor este ”Problema celor n regine”. Problema cere safie plasate n regine pe o tabla de sah de dimensiuni n × n astfel ıncat nicio pereche de regine sa nu se gaseasca ıntr-o situatie de atac. O posibila for-mulare ca o problema cu constrangeri poate fi urmatoarea. Consideram cateo variabila pentru fiecare coloana a tablei de sah: x1, x2, ..., xn. Domeniilevariabilelor vor coincide cu multimea liniilor tablei de sah: 1, ..., n. Pefiecare coloana trebuie plasata cate o regina, asadar constrangerile vor im-pune ca nici o pereche de regine sa nu se gaseasca pe aceesi linie sau diagonala:∀i, j : xi 6= xj ∧ |xi − xj| 6= |i− j|.


2.2 Definitii de baza

2.2.1 Tuple, relatii

Un k-tuplu reprezinta o secventa de k elemente, notata prin (a1, ..., ak), nuneaparat distincte, fiecare element din tuplu fiind denumit si componenta.Atunci cand numarul k de elemente este subınteles, vom folosi doar termenulde tuplu.

Produsul cartezian al unor multimi D1, ..., Dk, notat D1 × ... × Dk estemultimea tuturor k-tuplelor (a1, ..., ak) cu proprietatea ca ∀i : ai ∈ Di.

Pentru a exemplifica, fie D1 = a, b si D2 = 0, 1, 2.

D1 ×D2 = a, 0, a, 1, a, 2, b, 0, b, 1, b, 2

Fiind data o multime de variabile X = x1, ..., xk, fiecare variabilaxi avand asociat un domeniu Di, definim o relatie de aritate k ca fiind osubmultime a produsului cartezian D1 × ... × Dk. Multimea variabilelorpe care este definita o relatie R o vom mai nota var(R). Daca notamS = var(R), relatia R mai poate fi scrisa si ca RS, pentru a pune ın evidentavariabilele acesteia. Pentru k = 1, 2, 3 relatiile se mai numesc unare, binare,respectiv ternare. Daca R = D1 × ...×Dk, atunci relatia este universala.

Fie D1 = a, b si D2 = 0, 1, 2. R = a, 0, a, 1, b, 2 este unexemplu de relatie, fiind o submultime a produsului D1 ×D2.

2.2.2 Reprezentarea relatiilor

Relatiile sunt multimi de tuple definite peste aceasi multime de variabile,ele putand fi reprezentate fie explicit, situatie ın care sunt enumerate efectivtuplele relatiei, fie implicit, prin expresii aritmetice sau alte functii. RelatiaR = 0, 1, 0, 2, 1, 2 definita sub forma ei explicita pe domeniile D1 =D2 = 0, 1, 2 poate fi scrisa implicit si astfel: R = (x1, x2)|x1 ∈ D1, x2 ∈D2, x1 < x2.

Sa notam ca tuplele unei relatii pot fi enumerate si sub forma unui tabel,ın care coloanele reprezinta variabilele relatiei iar fiecare linie este un tuplu.

x1 x2

0 10 21 2

2.2. DEFINITII DE BAZA 15

Reprezentarea explicita a unei relatii de aritate k poate fi facuta, mai com-pact, folosind tablouri k-dimensionale cu elementele 0 si 1. Astfel, o relatiebinara R cu variabile x1, x2, avand valori ın domeniile D1 = a1, ..., ansi D2 = b1, ..., bm poate fi definita folosind o (0, 1)-matrice de dimensiunin×m, ın care fiecare linie corespunde unui element din D1 si fiecare coloanacorespunde unui element din D2. Prezenta unui 1 in matrice la pozitia (i, j)semnifica faptul ca (ai, bj) ∈ R, ın timp ce valoarea 0 semnifica (ai, bj) 6∈ R.

Fie D1 = a, b, D2 = x, y, z. Relatia R = a, x, a, y, b, z poatefi reprezentata astfel:

x y za 1 1 0b 0 0 1

2.2.3 Operatii cu relatii

In primul rand, fiind multimi de tuple, asupra relatiilor pot fi aplicate operatiileuzuale de la multimi: reuniunea, intersectia si diferenta, acestea avand sensdoar ın situatia cand relatiile sunt definite pe aceeasi multime de variabile.Astfel, fie R,R′ doua relatii si var(R) = var(R′).

• R ∪R′ = t tuplu | t ∈ R ∨ t ∈ R′

• R ∩R′ = t tuplu | t ∈ R ∧ t ∈ R′

• R−R′ = t tuplu | t ∈ R ∧ t 6∈ R′

In toate cele trei operatii, relatia rezultata are aceeasi multime de variabileca si relatiile asupra carora au fost aplicate.

Structura speciala a elementelor unei relatii (tuple) permite ınsa definireasi a unor operatii specifice acestora, pe langa cele comune tuturor multimilor.Cele mai reprezentative sunt: selectia, proiectia si legarea (join). Sa leanalizam pe fiecare ın parte.

Selectia (σ) este un operator care creaza o noua relatie, eliminand dintuplele unei relatii pe cele care nu satisfac o serie de conditii ce impun anumitevalori asupra unor anumite variabile. In reprezentarea tabelara, selectia va


elimina linii, acestea fiind corespunzatoare tuplelor. Astfel, sa consideramo relatie R, x1, ..., xn variabilele acesteia si D1, ..., Dn domeniile pe caresunt definite acestea. Fie Y = xi1 , ..., xik o submultime a lui var(R) sit = ai1 , ..., aik un k-tuplu continand valori din domeniile corespunzatoare.Operatorul de selectie va pastra din tuplele relatiei R doar pe acelea cuproprietatea ca ∀j : xij = aij si vom nota acest lucru prin σxi1

=ai1,...,xik

=aik(R)

sau, mai simplu, σY =t(R).Fie R = 0, 1, 0, 2, 1, 2, var(R) = x1, x2, D1 = D2 = 0, 1, 2.

σx1=0(R) = 0, 1, 0, 2σx1=0,x2=1(R) = 0, 1

Proiectia (π) este un operator care creeaza o noua relatie, pastranddoar componentele unui anumit set de variabile din toate tuplele unei relatii.In reprezentarea tabelara, proiectia va elimina coloane ale tabelului, acesteafiind corespunzatoare variabilelor. Fie o relatie R, X = x1, ..., xn variabileleacesteia si Y = xi1 , ..., xik o submultime a lui X. Operatorul de proiectieva pastra toate tuplele relatiei R dar va elimina componentele variabilelorcare nu apartin multimii Y . Vom nota acest lucru prin πxi1

,...,xik(R) sau, mai

simplu, πY (R). Evident, πX(R) = R.Pentru relatia anterioara R = 0, 1, 0, 2, 1, 2:

πx1(R) = 0, 1πx2(R) = 1, 2

Atunci cand aplicam proiectia doar asupra unei tuple a = a1, ..., ak,pot fi folosite oricare din notatiile πY (a) sau a[Y ].

Legarea (./) a doua relatii RS si RT , notata cu RS ./ RT , va produce onoua relatie formata din combinarea tuplelor din RS si RT care au aceleasivalori pentru componentele corespunzatoare variabilelor comune (din S∩T ).Sa notam C = S ∩ T = x1, ..., xk si sa presupunem ca rescriem tuplelecelor doua relatii astfel ıncat componentele corespunzatoare variabilelor dinC sunt pe primele k pozitii. Un tuplu r ∈ RS ./ RT va fi construit astfel:

2.2. DEFINITII DE BAZA 17

1. luam un tuplu s = (s1, ..., sk, sk+1...sn) din RS

2. luam un tuplu t = (t1, ..., tk, tk+1, ..., tm) din RT cu proprietatea ca∀i = 1, k : si = ti

3. r = (s1 = t1, ..., sk = tk, sk+1...sn, tk+1, ..., tm).

Sa observam ca var(RS ./ RT ) = S∪T si ca legarea a doua relatii cu aceeasimultime de variabile este de fapt intersectia celor doua: RS ./ R′

S = RS∩R′S.

Fie S = x, y, z, T = x, a , fiecare variabila avand domeniul 0, 1, 2 sidoua relatii: RS = 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, RT = 0, 0, 0, 1.RS ./ RT va avea ca variabile pe S ∪ T = x, y, z, a si va fi:

RS ./ RT = 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1


2.3 Retele de constrangeri

O retea de constrangeri este un triplet (X,D,C) ın care:

• X = x1, ..., xn reprezinta o multime de variabile;

• D = D1, ..., Dn reprezinta domeniile finite ın care variabilele din Xpot lua valori;

• C = C1, ..., Ct reprezinta o multime de constrangeri.

Dupa cum am precizat deja, nu se impune nici o restrictie asupra tipuluivariabilelor: acestea pot fi ıntregi, logice, multimi sau orice altceva si, deasemenea, nu se impune nici o restrictie asupra modului ın care sunt definiteconstrangerile. Formal, o constrangere Ci ∈ C este o pereche < Si, Ri >,unde Ri denota o relatie definita pe o submultime Si de varibile din X,aceasta reprezentand atribuirile legale, simultane, permise respectivelor vari-abile. Cand multimea de variabile a relatiei este subınteleasa, vom identificaconstrangerea Ci cu relatia Ri. De asemenea, pentru claritate, Ci mai poatefi referita si sub notatia RSi

. Tot pentru claritate, multimea de variabilex1, ..., xk ale unei constrangeri va mai fi scrisa si sub forma x1...xk, astfelca o constrangere C =< x, y, z, R > va fi notata simplu Rxyz.

Multimea S = S1, ..., St a tuturor seturilor de variabile din retea pecare sunt definite constrangeri se numeste schema retelei. Fara a restrangegeneralitatea, putem presupune ca ∀i 6= j : Si 6= Sj, cu alte cuvinte nuexista constrangeri definite pe aceeasi multime de variabile. In cazul ın carear exista, putem reuni relatiile celor doua constrangeri, obtinand o reteaechivalenta.

Aritatea unei constrangeri coincide cu aritatea relatiei de care este definita,fiind cardinalul multimii sale de variabile. O retea este binara daca toate con-strangerile sale au cel mult doua variabile.

Pentru o multime de variabile S vom nota cu T (S) multimea tuturortuplelor ce pot fi formate cu variabilele respective si valori din domeniileacestora:

T (S) =∏xi∈S

Di

2.3. RETELE DE CONSTRANGERI 19

2.3.1 Solutiile unei retele de constrangeri

Instantierea unei variabile reprezinta atribuirea unei valori din domeniul aces-teia, ın timp ce instantierea unei multimi de variabile Y = xi1 , ..., xit pre-supune instantierea fiecareia dintre ele si vom nota acest lucru ca un tuplu,sub una din formele: (< xi1 , ai1 >, ..., < xik , aik >), (xi1 = ai1 , ..., xik = aik),sau chiar a = (ai1 , ..., aik) atunci cand multimea de variabile este subınteleasa;evident, ∀j ∈ i1, ...ik : aj ∈ Dj.

O instantiere a a variabilelor din Y = xi1 , ..., xit satisface o constrangereRS daca si numai daca proiectia tuplei a peste S apartine relatiei R:

a[S] ∈ R

O solutie a unei retele de constrangeriR = (X,D, C), unde X = x1, ..., xn,reprezinta o instantiere a tuturor variabilelor din X astfel ıncat toate con-strangerile retelei sunt satisfacute. Multimea tuplelor definite pe X carereprezinta solutii ale unei retele R formeaza relatia solutiilor lui R si va finotata cu sol(R) sau ρX . Mai spunem ca reteau exprima sau reprezintarelatia soltiilor sale.

sol(R) = a = (a1, ..., an) | ∀i : ai ∈ Di ∧ a[Si] ∈ Ri

O instantiere partiala a a unui set de variabile S ale unei retele esteconsistenta daca si numai daca satisface toate constrangerile definite doar pevariabile dintre cele carora le-au fost atribuite valori:

∀Si ∈ schema(R), Si ⊆ S ⇒ a[Si] ∈ RSi

O instantiere partiala consistenta a unor variabile se mai numeste si solutiepartiala. Vom nota cu sol(A) sau ρA relatia tuturor solutiilor partiale aleunei retele peste o submultime de variabile A.

2.3.2 Echivalenta retelelor

Doua retele de constrangeri sunt echivalente daca sunt definite pe aceeasimultime de variabile si au aceeasi multime de solutii. Tinand cont de aceastadefinitie, rezolvarea unei probleme modelata ca o retea de constrangeri pre-supune de multe ori modificarea retelei initiale ıntr-o noua retea, adaugandsau eliminand constrangeri, astfel ıncat reteaua obtinuta este echivalenta cuprima, dar mai ”usor” de rezolvat. Crearea de noi constrangeri pe baza celorexistente se numeste deducere sau inferenta.


O constrangere este redundanta daca eliminarea ei din retea nu afecteazacu nimic multimea solutiilor, cu alte cuvinte, reteaua obtinuta este echiva-lenta cu cea originala. Evident, ın urma procesului de inferenta constrangerilerezultate sunt redundante.

2.3.3 Reprezentarea retelelor

Unei retele ıi pot fi asociate diverse reprezentari prin intermediul carora sapoata fi identificate mai usor unele proprietati ale acesteia, care sa simplificeprocesul de gasire a solutiilor.

Reprezentarea ca hipergrafUn hipergraf este o structura H = (V,S) , unde V = v1, ..., vn reprezinta omultime de noduri iar S = S1, ..., Sm este o multime formata din submultimiale lui V , fiecare din ele purtand denumirea de hipermuchie. Un graf esteasadar un hipergraf ın care toate hipermuchiile contin exact doua noduri.

Unei retele de constrangeri R = (X,D, C) ıi poate fi asociat un hipergrafH = (V,S) ın care:

• Nodurile hipergrafului sunt variabilele retelei: V = X = x1, ..., xn.

• Hipermuchiile vor fi multimile de noduri corespunzatoare variabilelorpe care sunt definite constrangerile retelei:xi1 , ..., xik ∈ S(H)⇔ ∃Cj =< Sj, Rj >∈ C : Sj = xi1 , ..., xik.

Este evident ca pot exista retele diferite care sa aiba aceeasi reprezentareca hipegraf, acesta furnizand doar informatii despre dependenta variabilelorıntre ele si nu despre relatiile constrangerilor retelei.

Graful primal al constrangerilorGraful G = (V, E) al constrangerilor unei retele R = (X,D, C), numit siprimal, este construit astfel:

• Nodurile grafului sunt variabilele retelei: V = X = x1, ..., xn.

• Intre doua noduri ale grafului exista muchie daca si numai daca ın reteaexista o constrangere a carei multime de variabile le contine si pe cele


corespunzatoare nodurilor:

xixj ∈ E ⇔ ∃C =< S, R >∈ C : xi, xj ⊆ S

Asadar, acest graf pune ın evidenta dependenta variabilelor una de cealalta,prezenta unei muchii ıntre nodurile corespunzatoare a doua variabile in-dicand faptul ca valoarea uneia este constransa ıntr-un anumit fel de valoareaceleilalte, ın timp ce absenta muchiei semnifica faptul ca cele doua variabilepot fi instantiate independent, fara ca vreo constrangere sa fie ıncalcata - cualte cuvinte, cele doua variabile apartin relatiei universale care contine toatetuplele produsului cartezian al celor doua domenii.

Este evident ca pot exista retele diferite care sa aiba grafurile constrangerilorizomorfe. Practic, acest graf ne va fi de ajutor ın situatia ın care el nu estecomplet, pentru a putea identifica variabilele care nu depind una de cealalta.In situatia ın care el este complet, informatia transmisa nu simplifica ın niciun fel rezolvarea problemei.

Graful dual al constrangerilorGraful G = (V, E) dual al constrangerilor este construit astfel:

• Nodurile grafului corespund constrangerilor retelei: V = C = C1, ..., Cm.

• Intre doua noduri ale grafului exista muchie daca si numai daca ınretea multimile variabilelor pe care sunt definite constrangerile core-spunzatoare nodurilor au intersectia nevida:

∀Ci =< Si, Ri >,Cj =< Sj, Rj >∈ V, CiCj ∈ E ⇔ Si ∩ Sj 6= ∅

Practic, aceasta reprezentare ne ofera urmatoarea informatie: prezenta uneimuchii semnifica faptul ca doua constrangeri depind una de cealalta ın sensulca o instantiere consistenta a variabilelor uneia dintre ele poate fi inconsis-tenta pentru variabilele celeilalte, ın timp ce absenta unei muchii indica faptulca satisfacerea celor doua constrangeri este independenta una de cealalta. Casi ın cazul grafului primal, acest graf ne va fi de ajutor doar ın situatia ıncare el nu este complet.

Graful relatiilorIn continuare ne punem problema cum am putea reprezenta sub forma unui


graf atat variabilele unei retele cat si constrangerile acesteia, astfel ıncatproblema satisfacerii constrangerilor sa poata fi exprimata sub forma uneiprobleme pe grafuri.

Fie R = (X,D,S) o retea de constrangeri, X = x1, ..., xn variabilelesale si D1, ..., Dn domeniile corespunzatoare. Vom defini graful G = (V, E)al relatiilor lui R astfel:

• Nodurile grafului sunt toate perechile de forma (xi, aj), unde xi ∈ Xsi aj ∈ Di. Cu alte cuvinte, pentru fiecare variabila cream perechi cutoate valorile cu care poate fi instantiata aceasta. Numarul de nodurial grafului va fi |V | =

∑i=1,n |Di|.

• Intre doua noduri (x, a) si (y, b) ale grafului exista muchie daca si numaidaca

– x 6= y

– ın retea exista o constrangere definita pe o multime de variabile ceinclude pe x si y iar relatia sa contine o tupla ın care componentelecorespunzatoare lui x si y au valorile a, respectiv b.

– ın retea variabilele x si y sunt independente, cu alte cuvinte grafulprimal al constrangerilor nu contine muchia xy.

Graful astfel format este multipartit, avand |V | clase ale partitii, o clasa fiindmultimea stabila generata de o variabila a retelei.

Propozitie 1 [13] Orice solutie a retelei corespunde unui drum din grafulrelatiilor de lungime n, avand cate un nod din fiecare partitie.

2.3.4 Rezolvarea retelelor de constrangeri

Vom ıncheia aceasta sectiune cu o privire de ansamblu asupra metodelor pecare la putem folosi pentru a gasi una sau toate solutiile unei retele de con-strangeri. Avand ın vedere ca problemele modelate folosind constrangeri suntın general dificile, algoritmii pot aborda problema gasirii solutiilor fie sistem-atic, ın cazul ın care spatiul solutiilor nu este foarte mare, fie aproximativprin diverse euristici care ınsa nu garanteaza rezolvarea corecta a retelei.


Algoritmi sistematici de rezolvareIn principiu, algoritmii sistematici de cautare parcurg tot spatiul solutiilorproblemei ce trebuie rezolvata, atribuind pe rand variabilelor retelei toatevalorile din domeniul lor. In felul acesta, suntem siguri ca vom gasi toateposibilele solutii, daca exista vreuna, sau vom trage concluzia ca problema nuare rezolvare. In mod evident, dezavantajul abordarii sistematice a cautariiconsta ın faptul ca timpul de lucru al acestor algoritmi depinde strict dedimensiunea spatiului solutiilor, care poate fi foarte mare.

Generare si testCel mai simplist algoritm sistematic de rezolvare consta ın generarea secventialaa tuturor tuplelor din produsul cartezian al domeniilor variabilelor retelei sitestarea fiecareia dintre acestea pentru a vedea daca sunt satisfacute toateconstrangerile. Algoritmul se poate opri la gasirea unei solutii sau poatecontinua pana ce tot spatiul de cautare a fost analizat. Practic, metoda nuprezinta nici o importanta, ineficienta abordarii constand ın faptul ca nusunt exploatate informatiile continute de constrangeri ın pasul de generare aposibilelor solutii.

BacktrackingO metoda sistematica, dar mult mai eficienta decat cea anterioara, consta ınatribuirea succesiva de valori variabilelor retelei si testarea consistentei aces-tor instantieri partiale. In felul acesta, algoritmul de backtracking ıncearcaın permanenta sa extinda o solutie partiala catre una completa. In situatiaın care o solutie partiala este inconsistenta algoritmul nu va mai ıncerca saasigneze valori si celorlalte variabile ci va face un pas ınapoi, ultima variabilacare a fost instantiata va primi o alta valoare si asa mai departe. In felulacesta, spatii ıntregi din produsul cartezian al domeniilor variabilelor vor fiexcluse de la testare, sporind astfel eficienta cautarii sistematice a solutiilor.

Desi backtrackingul este un algoritm mult mai bun decat cel de generaresi test, ın cazul problemelor dificile aplicarea sa ın forma standard nu estefoarte eficienta, motivele care pot provoca acest lucru fiind:

• repetarea greselilor (thrashing) - deoarece la aparitia unei inconsistentenu sunt identificate variabilele care sunt ın conflict, acelasi conflict sepoate repeta si ın alte situatii fara ca el sa fie detectat ın prealabil.


• redundanta - consta ın efectuarea acelorasi teste pentru verificareaconsistentei de mai multe ori fara a retine rezultatul lor, lucru caresporeste nejustificat timpul de lucru al algoritmului.

• detectarea tarzie a conflictelor - semnifica faptul ca algoritmul stan-dard nu ısi poate da seama atunci cand se ındreapta cu siguranta catreun conflict, efectuand iarasi calcule inutile care pot fi extrem de costisi-toare din punctul de vedere al timpului total de lucru.

Plecand de la backtracking-ul standard, vom studia ın capitolele urmatoareo serie de tehnici care ıncearca sa elimine dezavantajele prezentate mai sus,ımbunatatind substantial comportarea generala algoritmului.

Euristici de rezolvareEuristicile de rezolvare renunta la cautarea sistematica a solutiilor, ıncercandsa ajunga la acestea prin metode aproximative care nu garanteaza reusitaınsa au un timp de lucru mult mai bun fata de algoritmii sistematici. Printremetodele care pot fi amintite aici sunt: algoritmii genetici, algoritmi stochas-tici, simulated annealing, etc. Uneori, combinarea unor algoritmi sistematicicu euristici de rezolvare poate produce algoritmi eficienti pentru diferite clasede probleme.

2.3.5 Analiza complexitatii

Analiza complexitatii unui algoritm prespune stabilirea resurselor necesareacestuia pentru realizarea calculului presupus de rezolvarea problemei careiaıi este destinat. Cele mai comune resurse care sunt luate ın considerare sunt:

• timpul - numarul de pasi necesari;

• spatiul - necesarul de memorie pentru reprezentarea datelor initiale siintermediare.

Pentru a compara performantele unor algoritmi diferiti dar care rezolvaaceeasi problema, au fost introduse masuri care sa cuantifice consumul deresurse al acestora, punandu-le astfel ın evidenta eficienta.

Complexitatea timp a unui algoritm reprezinta numarul de operatii atom-ice necesare rezolvarii unei instante a unei probleme, avand o intrare de o


anumita dimensiune n (uzual reprezentata ca un si de biti). Asadar, com-plexitatea timp poate fi vazuta ca o functie f avand ca intrare dimensiuneaintrarii n si ca iesire numarul necesar de operatii. Pentru a masura valo-rile acestei functii este folosita notatia Big-O, introdusa de germanul PaulBachmann ın 1892 ın cartea Analytische Zahlentheorie si popularizata apoide un alt german Edmund Landau, din acest motiv ea mai numindu-se sisimbolul Landau. Prin intermediul acestei notatii este oferit un mecanismcare sa descrie comportamentul asimptotic al unei functii, cu alte cuvinte, sapoata fi stabilita o limita superioara asimptotica a unei functii ın raport cualte functii mai simple, care pot fi luate ca reper.Sa consideram ca exemplu un algoritm care necesita T (n) = 2n2 + 3n + 4pasi pentru a rezolva o anumita problema de dimensiune n. Pe masura ce ncreste, valoarea lui T (n) se va apropia asimptotic de valoarea lui 2n2. Facandabstractie de coeficienti, putem scrie ca T (n) ∈ O(n2), cu alte cuvinte algo-ritmul are ordinul de complexitate n2.

Formal, fiind date doua functii reale f si g, spunem ca f(x) ∈ O(g(x))cand x → ∞ daca si numai daca exista o valoare reala x0 si o constanta Mpentru care are loc:

|f(x)| ≤M |g(x)|, ∀x > x0.

Prin abuz de notatie, faptul ca f(x) ∈ O(g(x)) va fi scris de cele maimulte ori f(x) = O(g(x)).

Cele mai comune clase de functii folosite pentru a exprima complexitateaalgoritmilor sunt:

Notatie DenumireO(1) constantaO(log(n)) logaritmicaO([log(n)]c) polilogaritmicaO(n) liniaraO(nlog(n)) supraliniaraO(n2) patraticaO(nc), c > 1 polinomialaO(cn), c > 1 exponentialaO(n!) factoriala

Dintre proprietatile pe care trebuie sa le avem ın vedere ın calculul com-plexitatii algoritmilor, cele mai utilizate sunt:


• O(f(n))O(g(n)) = O(f(n)g(n))

• O(f(n)) + O(g(n)) = O(maxf(n), g(n))

• O(cf(n)) = O(f(n)), unde c > 0 este o constanta.

• O(c + f(n)) = O(f(n)), unde c > 0 este o constanta.

Desi notatia O este cea mai folosita, mai exista si alte instrumente pentrua descrie asimptotic comportamentul unei functii. Acestea sunt prezentateın tabelul de mai jos:

Notatie Semnificatie Definitie

f(n) ∈ O(g(n)) limita superioara asimptotica lim supx→∞ |f(x)g(x)| <∞

f(n) ∈ o(g(n)) asimptotic neglijabila limx→∞f(x)g(x)

= 0

f(n) ∈ Ω(g(n)) limita inferioara asimptotica lim infx→∞ |f(x)g(x)| > 0

f(n) ∈ ω(g(n)) asimptotic dominata limx→∞g(x)f(x)

= 0

f(n) ∈ Θ(g(n)) asimptotic marginita f ∈ O(g) si g ∈ O(f)

Inainte de a prezenta diversi algoritmi pe retele de constrangeri, sa vedemcare sunt parametrii dupa care putem analiza complexitatea acestora. FieR = (X,D, C) o retea oarecare.

• n = |X| - numarul de variabile

• k = max|D||D ∈ D - cardinalul maxim al domeniilor de definitie.

• e = |C| - numarul de constrangeri

• t = max|R||C =< S,R >∈ C - numarul maxim de tuple al relatiilorce definesc constrangerile retelei.

Numarul maxim de constrangeri ce poate fi definit pe n variabile este:C1

n + C2n + ... + Cn

n = 2n − 1. Asadar O(e) = O(2n).Un exemplu simplu care sa ilustreze acest lucru este: X = x, y, z, C =Rx, Ry, Rz, Rxy, Rxz, Ryz, Rxyz.In cazul retelelor binare, e <= C1

n + C2n, ceea ce ınseamna ca O(e) = O(n2).

Numarul maxim de tuple dintr-o relatie este cardinalul produsului cartezianal domeniilor variabilelor relatiei, asadar parametrul t va depinde de numarul

2.4. SATISFACEREA PARTIALA A CONSTRANGERILOR 27

maxim de variabile si de dimensiunea maxima a domeniilor: t <= kn.Astfel, daca X = x, y, z, Dx = Dy = Dz = 0, 1, Rxyz poate fi(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1),avand asadar 23 = 8 tuple.In cazul retelelor binare t <= k2.

Intrucat algoritmii prezentati vor avea ca intrare retele de constrangerioarecare, nu vom face supozitii care sa limiteze valorile acestor parametri, ciıi vom folosi ca atare.

Din punct de vedere algoritmic, este important sa analizam complexi-tatea operatiunilor elementare pe care le vom efectua, deoarece acestea vor fiimplicate ın stabilirea complexitatii totale a acestora. Din acest motiv vomorganiza structurile de date astfel ıncat, cu pretul unui calcul mai costisitorinitial, sa optimizam efectuarea operatiilor de baza.

Astfel, vom presupune ca:

• testarea apartenentei unei variabile la multimea de variabile a uneiconstrangeri,

• determinarea constrangerilor ın care este implicata o anumita variabila

pot fi facute ın timp constant folosind structuri de date corespunzatoare.

2.4 Satisfacerea partiala a constrangerilor

Modelul clasic de definire a problemelor de satisfacere a constrangerilor pleacade la premiza ca identificarea unei solutii presupune satisfacerea tuturor con-strangerilor problemei. Din acest punct de vedere, singura diferentiere ıntredoua asignari ale variabilelor problemei este daca acestea sunt sau nu consis-tente. Exista ınsa multe situatii reale care modelate sub forma unei instanteCSP conduc la probleme a caror rezolvare nu poate fi facuta (folosind sol-vere clasice CSP) ıntr-un timp rezonabil datorita complexitatii lor, sau chiarcare nu au nici o solutie, asa numitele probleme supra-constranse (overcon-strained) [17], [5]. Un exemplu ın acest sens este problema orarului ın care,la restrictiile tari ale problemei care nu pot fi sub nici o forma violate (o salanu poate fi ocupata ın acelasi timp cu doua activitati) se adauga o multimede constrangeri care modeleaza, sa spunem, preferintele profesorilor. Intr-o


solutie ideala este de dorit respectarea tuturor acestor preferinte ınsa de celemai multe ori acest lucru nu este posibil, caz ın care trebuie sa alcatuim unorar care sa satisfaca partial dar ”cat mai bine” multimea acestor restrictiipersonale. Acest ”cat mai bine” poate reprezenta minimizarea numarului deconstrangeri care nu au fost satisfacute sau poate fi definit ın asa fel ıncatrespectarea preferintelor unui profesor sa aiba prioritate ın fata doleanteloraltora.

Asdar, ın situatii cum este cea prezentata mai sus, devine necesara oabordare care sa ne conduca ıntr-un mod eficient catre o solutie partialasatisfacatoare. In continuare vom formaliza notiunea de ”satisfacator” sivom prezenta diferite modele de lucru.

Definitie 1 O retea slaba de constrangeri [46] este un triplet (X, D,C),unde

• X = x1, ..., xn reprezinta o multime de variabile;

• D = D1, ..., Dn reprezinta domeniile finite ın care variabilele din Xpot lua valori;

• C = C1, ..., Ct reprezinta o multime de constrangeri slabe.O constrangere slaba C =< S, f >∈ C este definita ca o pereche for-mata dintr-o multime S ⊆ X de variabile si o functie f definita pemultimea tuplelor ce pot fi asignate variabilelor din S avand valori ıntr-o multime E ce denota nivele de preferinta. Formal, f :

∏xi∈S

Di → E.

Pentru simplitate, vom mai nota o astfel de constrangere prin fS.

Pentru o multime de variabile S vom nota T (S) =∏

xi∈S

Di.

Evident, pentru a putea spune ca o instantiere t a variabilelor dintr-omultime S este mai buna decat o alta t′ relativ la o constrangere fS, trebuieca pe multimea E sa fie definita o relatie de ordine totala , astfel ıncat teste mai buna decat t′ daca si numai daca fS(t) fS(t′).

De asemenea, deoarece dorim sa integram modelul clasic CSP ın acestnou model, trebuie sa existe doua elemente ın multimea E, sa le notam ⊥ si> cu semnificatiile de ”tupla permisa” (absenta oricarei interdictii), repectiv”tupla interzisa” din varianta clasica. Relativ la ordinea a elementelor dinE, ⊥ reprezinta minimul iar > maximul.


∀a ∈ E ⊥ a >Fie a, a′ doua instantieri ale tuturor variabilelor din X. Intrebarea pe care

ne-o punem este cum putem aprecia care din cele doua instatierei este maibuna, din perspectiva satisfacerii tuturor constrangerilor din retea. Pentru araspunde la aceasta ıntrebare, trebuie sa definim un operator ⊕ pe multimeaE care sa specifice cum se ”combina” nivelele de preferinta reprezentate deelementele lui E. Folosind acest operator, putem defini nivelul de satisfactieoferit de o instantiere a ca fiind functia F : T (X)→ E:

F (a) =⊕f(a[S]) | ∀C =< S, f >∈ C

Spunem ca o retea slaba de constrangeri are solutie daca ∃t ∈ T (X)astfel ıncat F (t) ≺ >. O astfel de solutie se numeste admisibila. O solutiea este optimala daca si numai daca ∀t′ ∈ T (X) F (t) F (t′). Daca ∀t ∈T (X) F (t) = >, spunem ca reteaua nu are nici o solutie.

In continuare vom extinde functia cost f astfel: f :⋃T (S)|S ∈ X,

f(t) =⊕f(a[S]) | ∀C =< S, f >∈ C : var(t) ∩ S 6= ∅

Definitie 2 [49] O structura de evaluare este o cvintupla (E,⊕,,⊥,>)astfel ıncat:

• E este o multime ale carei elemente sunt numite evaluari, total ordonatadupa , avand minimul ⊥ si maximul >.

• E este ınchisa dupa operatorul binar ⊕ ce satisface proprietatile de:

– comutativitate: ∀a, b ∈ E a⊕ b = b⊕ a.

– asociativitate: ∀a, b, c ∈ E (a⊕ b)⊕ c = a⊕ (b⊕ c).

– element neutru: ∀a ∈ E a⊕> = >⊕ a = a

– element de scufundare: ∀a ∈ E a⊕⊥ = ⊥⊕ a = ⊥– monotonie: ∀a, b, c ∈ Ea b⇒ (a⊕ c) (b⊕ c)

Definitie 3 O retea evaluata de constrangeri este o cvadrupla (X, D,C, S),unde (X, D,C) este o retea slaba de constrangeri iar S o structura de eval-uare.


2.4.1 Instante specifice

Prin particularizarea structurii de evaluare obtinem usor modele studiatedeja de reprezentare a problemelor folosind constrangeri.

• Modelul clasicIn modelul clasic multimea E este formata din cele doua valori logicepentru adevarat si fals, operatorul de compunere fiind cel de si logic.

• AditivIn modelul aditiv, nerespectarea unei constrangeri atrage dupa sine openalizare reprezentata sub forma unui numar ıntreg pozitiv, scopulfiind de a minimiza suma totala a penalizarilor.

• MAX-CSPMAX-CSP este o particularizare a modelului aditiv ın care ne intere-seaza doar minimizarea numarul de constrangeri care nu sunt sat-isfacute, asadar penalizarile pot fi doar 0 sau 1.

Sintetizam particularizarile de mai sus ın urmatorul tabel:

CSP E ⊥ > ⊕Clasic 0, 1 0 1 0 1 ∧Aditiv N ≤ 0 ∞ +

MAX-CSP 0, 1 ≤ 0 |C| +

2.4.2 Operatii cu functia de cost

Sa analizam ın continuare operatorii care pot fi aplicati functiilor ce definescconstrangerile unei retele.

RestrictiaFie fS o constrangere, xi ∈ S si a ∈ Di. Restrictia este un operator care,pentru asignarea xi = a, creeaza o noua constrangere fS−xi

= fS[xi = a]definita astfel:

∀t ∈ T (S − xi) fS−xi(t) = fS(t ./ (xi = a))

ProiectiaFie fS o constrangere si xi ∈ S. Proiectia este un operator care creaza onoua constrangere fS−xi

= fS[S − xi] =not. fS[−xi] definita astfel:

∀t ∈ T (S − xi) fS−xi(t) = mina ∈ Di | fS(t ./ (xi = a))


CombinareaFie fS, gS′ doua constrangeri. Functia hS∪S′ = fS ⊕ gS′ este definita astfel:

∀t ∈ T (S ∪ S ′) h(t) = fS(t[S])⊕ gS′(t[S ′])

Folosind aceasta notatie, o solutie a unei retele slabe de constrangeri este oasignare t a tuturor variabilelor astfel ıncat:

(⊕f∈C

f)(t) 6= >

ComparareaFie fS, gS′ doua constrangeri. Spunem ca f este mai tare decat g (si notamfS ≥ gS′) daca si numai daca:

∀t ∈ T (S ∪ S ′) fS(t[S]) gS′(t[S ′])

Daca f ≤ g si g ≤ f cele doua constrangeri sunt echivalente.

2.4.3 Cautarea solutiilor

In cazul retelelor slabe de constrangeri problema rezolvarii acestora poate fiprivita sub mai multe aspecte. Astfel, se poate cere:

• determinarea costului optimal al unei solutii;

• identificarea unei sau a tuturor solutiilor optimale;

• gasirea unei solutii suficient de buna (al carei cost nu depaseste o con-stanta specificata);

• determinarea tuplelor interzise (nu pot face parte din nici o solutieoptimala);

• transformarea retelei ıntr-una echivalenta din punctul de vedere al solutiilor,dar ”mai simpla” din punctul de vedere al rezolvarii.

In cazul modelului clasic, rezolvarea retelelor era realizata pe structuraunui algoritm sistematic de explorare a spatiului solutiilor, de tip backtrack,conditia fiind de satisfacere deplina a unei multimi de constrangeri. Pentrumodelul generalizat ınsa aceasta abordare nu mai este suficienta, acest lucru


fiind datorat diferentei conceptuale fata de CSP. Ceea ce ne intereseaza acumeste identificarea unei solutii care sa satisfaca ”cat mai bine” constrangerileimpuse, acest lucru traducandu-se prin necesitatea optimizarii unei functiiobiectiv.

Distingem urmatoarele categorii de algoritmi:

• sistematici - un astfel de algoritm (numit si complet) va garanta re-spectarea cerintelor impuse (cum ar fi identificarea unei solutii optimalesau ”suficient de buna”) sau va determina ca problema nu are nici osolutie admisibila.

• euristici - acestea ıncearca gasirea unei solutii optimale fara a garanta ınvreun fel reusita; scopul lor este de a oferi o modalitate de complexitatepolinomiala pentru a ”ıncerca” rezolvarea problemelor foarte dificile.

• hibrizi - sunt algoritmi sistematici care folosesc diverse euristici pentrueficientizarea procesului de cautare a solutiilor.

Trebuie observat ca rezolvarea retelelor slabe de constrangeri prin inter-mediul algoritmilor sistematici este mult mai dificila decat situatia similaradin modelul clasic, deoarece ın situatia ın care operatorul ⊕ nu este idem-potent - cum ar fi ın structurile de evaluare aditive - calitatea unei asignarinu este cunoscuta decat dupa ınsumarea tuturor penalizarilor generate deconstrangerile care nu sunt satisfacute. In modelul clasic, nerespectarea uneiconstrangeri conducea la oprirea procesului de evaluare a asignarii, aceastafiind evident inconsistenta.

2.4.4 Algoritmul ”branch-and-bound”(b-b)

In descrierea generala a algoritmului b-b vom porni de la urmatoarele ipoteze:

• P este o problema de optimizare, ın cazul nostru o retea slaba de con-strangeri: P = (X, D,C, S).

• Dimensiunea problemei este notata cu dim(P ) si este data de numarulvariabilelor retelei dim(P ) = |X|.

• f este functia obiectiv care trebuie minimizata (extensia functiei decost).


Rezolvarea va consta ın identificarea valorii fopt(P ) si unei tuple a∗ ∈ T (X)astfel ıncat:

fopt(P ) = f(a∗) = minf(t)|t ∈ T (X) ≺ >

[9] Metoda b-b este de tip divide-et-impera si poate fi descrisa astfel:

(a) Se descompune problema P ın problemele Pi (i = 1, k), instante aleproblemei P si dim(Pi) < dim(P ).

(b) fopt(P ) se construieste ın timp polinomial din fopt(Pi), i = 1, k.

(c) Pentru o problema P , daca dim(P ) este suficient de mic, nu este nevoiesa se mai realizeze descompunerea ci se determina ın timp constantsolutia fopt(P ) si a∗.

(d) In procesul recursiv de calcul descris de (a),(b) si (c) se dispune de ometoda de ”eliminare” a rezolvarii unei probleme Pi pe baza concluzieica la etapa (b) solutia problemei Pi, fopt(Pi) nu va afecta calculul luifopt(P ).

La nivel de implementare, vom avea nevoie de:

• O variabila fopt care va retine optimul curent si o tupla a∗ care vamemora instantierea optima curenta. fopt = f(opt).

• Un predicat de oprire care sa determine daca o problema P poate firezolvata fara a o mai descompune ın subprobleme. Acesta va fi ınsotitde algoritmi de rezolvare a cazurilor simple de oprire.

• O functie de ramificare responsabila cu descompunerea problemei.

• O functie de marginire inferioara capabila sa calculeze ıntr-un timprezonabil marginea inferioara a unei retele P , sub care nu poate coborıevaluarea nici unei solutii admisibile: m(P ) ≤ fopt(P ). Daca m(P ) estemai mare decat optimul curent, nu are rost sa mai rezolvam problemaP .

• O functie de marginire superioara - aceasta ne ofera informatia ca op-timul problemei P nu poate depasi o anumita valoare:fopt(P ) ≤M(P ).Daca m(P ) > M(P ) atunci problema nu are solutie.


• O strategie de cautare care va determina la fiecare ramificare modali-tatea ın care subproblemele generate vor fi selectate pentru rezolvare.

• O euristica de cautare locala a solutiei pornind de la o instantierepartiala a variabilelor.

• O ordine de instantiere variabilelor.

• O ordine de selectare a valorilor.

La apelul initial al algoritmului vom seta fopt = > si opt = ∅. O variantasimplista de marginire este:

upperBound(P ) = fopt

lowerBound(P ) = ⊥

2.4.5 Functii de marginire inferioara

Vom considera ın continuare modelul aditiv de tip WCSP (Weighted CSP) alretelelor slabe, ın care fiecare constrangere are asociata o penalizare pe careo atrage nerespectarea sa iar evaluarea unei asignari se face prin ınsumareatuturor penalizarilor induse.

Sa consideram arborele corespunzator executiei unui algoritm de tip b− bsi sa facem urmatoarele notatii:

• A = x1, ..., xi−1 - multimea variabilelor deja instantiate

• a = (x1 = a1, ..., xi−1 = ai−1) - asignarea curenta

• xi = ai atribuirea ce urmeaza a fi facuta si care reprezinta de fapt nodulcurent al arborelui de cautare.

• F = X − A - multimea variabilelor ramase de instantiat

• µbc - penalizarea curenta (backward checking cost):

µbc = f(a) =def∑f(a[S]) | fS ∈ C, A ∩ S 6= ∅

De asemenea, vom nota:

• lb - marginea inferioara ce semnifica penalizarea minima a unei solutiicomplete ce va fi construita pornind de la instantierea partiala curenta.


Algorithm 1 Structura generala a procedurii Branch-and-Bound

Intrare: O retea slaba de constrangeri P = (X, D,C, S). Consideramdefinite functiile isSimple, resolveSimple, branch, select, upperBound,lowerBound, localSearch cu semnificatiile descrise mai sus. Consideraminitializate variabilele opt si fopt.

Rezultat: O solutie optima a problemei P sau mesajul ca aceasta nu arenici o solutie admisibila.

ub = upperBound(P )lb = lowerBound(P )if ub < lb thenProblema nu are solutiereturn (>, ∅)

end if

if fopt < lb thenRezolvarea lui P este inutilareturn (>, ∅)

end if

if isSimple(P ) thenProblema poate fi rezolvata simplu, fara a o descompunereturn resolveSimple(P )

end if

branch(P )→ B = P1, ..., Pk

while B 6= ∅ doPi = select(B)B = B − Pi

(fi, opti) = Branch− and−Bound(Pi)if fi < fopt then

fopt = fi

opt = optiIncercam ımbunatatirea optimului local(fopt, opt) = localSearch(P, fopt, opt)

end ifend while


• ub - marginea superioara data de costul celei mai bune solutii gasitepana ın acest moment.

In mod evident, ın cadrul algoritmului b− b nu are rost sa continuam explo-rarea ın conditia ın care ub ≤ lb, deci este important sa gasim modalitati decalcul pentru lb care sa fie cat mai eficiente ın sensul de a maximiza aceastavaloare, fara ınsa a introduce un efort computational prea mare. In cazul ıncare, ın urma evaluarii marginilor ub si lb, vom avea relatia ub ≤ lb, atribuireaxi = ai nu va mai fi realizata, reducand astfel domeniul de cautare al solutieioptime. Cea mai simpla forma de evaluare a marginii inferioare este data depenalizarea curenta (backward checking cost):

lb = µbc

Partial Forward Checking (PFC)Metoda PFC ofera o modalitate simpla de a evalua costul minim al uneisolutii ce poate fi gasita mergand pe ramura curenta a arborelui prin ınsumareapenalizarilor constrangerilor ce vor fi violate de asignarea a′ = a · (xi = ai)(forward checking cost). Pentru aceasta va trebui sa inspectam doar aceleconstrangeri fS pentru care xi ∈ S si A ∩ S = ∅:

µpfc =∑f(a′[S]) | fS ∈ C, xi ∈ S ∧ A ∩ S = ∅

In aceste conditii, marginea inferioara va fi calculata astfel:

lb = µbc + µpfc

Sa observam ca ın evaluarea acestui cost nu sunt luate ın calcul interactiuniledintre variabilele din F − A− xi.

Russian Doll Search (RDS)Algoritmul RDS presupune ordonarea statica a variabilelor retelei si re-zolvarea a n probleme succesive P1, P2, ..., Pn = P obtinute din problemainitiala P prin restrictionarea multimii de variabile. Astfel prima problemava avea ca variabile doar pe xn, P2 pe xn−1, xn, ..., Pi va avea n − i + 1variabile iar Pn va fi chiar problema initiala. Rezolvarea problemei Pi se va


face pastrand ordinea stabilita a variabilelor si solutia obtinuta va fi folositapentru determinarea marginilor inferioare lb ın cadrul urmatoarei problemePi+1. Astfel, ın rezolvarea problemei curente, sa notam cu P ′ problema re-zolvata anterior. In evaluarea asignarii a′ = a · (xi = ai) ne vom folosi deoptimul obtinut pentru P ′ care era definita pe variabilele A = var(a).

µrds = fopt(P′)

Folosind si aceasta masura, marginea inferioara va fi calculata astfel:

lb = µbc + µpfc + µrds

2.4.6 Functii de marginire superioara

Functia de marginire superioara este optimul curent obtinut. Initial, aceastapoate fi obtinuta aplicand o euristica cu timp de lucru polinomial, cum ar fiun algoritm de tip greedy.

2.4.7 Tehnici locale de cautare

Tehnicile de cautare locala sunt metode extrem de folosite ın problemelede optimizare combinatoriala. Ideea generala este de a porni de la o solutieadmisibila t si de a o transforma ıntr-o alta solutie t′ ”apropiata” de t conformunei anumite metrici dar ”mai buna” din punctul de vedere al minimizariifunctiei obiectiv. Aceste transformari sunt repetate atat timp cat este posibil,rezultatul final fiind un optim local.

Spre deosebire de metodele complete de cautare a solutiilor, tehnicilelocale nu garanteaza obtinerea optimului ınsa au o complexitate redusa decalcul, de cele mai multe ori polinomiala si sunt foarte eficiente ın situatiileın care nu ne intereseaza neaparat obtinerea minimului ci doar a unei solutiicare este ”suficient” de buna, ın sensul ca penalizarea sa este sub un nivelprestabilit.

Dintre metodele cele mai des folosite amintim:

• simulated annealing

• tabu search

• greedy random adaptive search


• algoritmi genetici

• swarm optimization

In contextul retelelor de constrangeri, tehnicile locale de cautare pot fifolosite pentru a determina un optim initial sau pentru ımbunatati optimulcurent, reducat astfel marginea superiora a intervalului [lb, ub], lucru extremde important ın reducerea spatiului de cautare a solutiilor.

Capitolul 3

Rezolvarea retelelor deconstrangeri

3.1 Algoritmi sistematici de cautare

Data o retea de constrangeri oarecare, ne punem ın continuare problemagasirii uneia sau a tuturor solutiilor acesteia. Intrucat dorim sa facem o abor-dare cat mai generala a problemei, vom exclude deocamdata ideea folosiriiunor euristici sau a unor particularitati ale retelei date si vom descrie algo-ritmi care sa identifice ın mod exact solutiile problemei.

Un algoritm sistematic de cautare poate fi reprezentat ca un automatdefinit de:

• O multime finita S de stari, fiecare stare corespunzand unei instantieria unei submultimi de variabile a retelei. Multimea S poarta denumireasi de spatiul de cautare al algoritmului iar |S| va fi numita dimensiuneaspatiului de cautare.

• O multime O de operatori responsabili cu tranzitia automatului dintr-ostare ın alta;

• O stare initiala s0;

• O multime Sf ⊆ S de stari finale, reprezentand solutiile retelei.

Ne intereseaza ın mod deosebit algoritmii ai caror spatiu de cautarepoate fi reprezentat din punct de vedere grafic sub forma unui arbore, avand

39

40 CAPITOLUL 3. REZOLVAREA RETELELOR DE CONSTRANGERI

radacina s0 si un numar de noduri egal cu |S|. Trecerea dintr-o stare ınalta va reprezenta trecerea de pe un nivel al arborelui pe urmatorul, ceea ceınseamna ca o masura a eficientei algoritmului va fi si adancimea arborelui.

Exista doua clase de algoritmi sistematici:

• Generare si test - Spatiul de cautare este produsul cartezial al tutu-tor domeniilor variabilelor retelei, din fiecare stare putand fi executatatranzitia ıntr-o singura alta stare, numita succesor. Executia algorit-mului va consta astfel ın parcurgerea secventiala a tuturor starilor siverificarea consistentei acestora. Deoarece dimensiunea spatiului decautare este foarte mare, din punct de vedere practic aceasta clasa dealgoritmi nu prezinta importanta practica.

• Backtracking - In cazul algoritmilor de tip backtracking, o stare reprezintao instantiere partiala consistenta a unui set de variabile a retelei. Tre-cerea dintr-o stare ın alta se face prin extinderea instantierii partialea starii curente cu ınca o componenta. Starile finale vor reprezentasolutiile retelei.

3.2 Backtracking

3.2.1 Structura generala a algoritmului

Algoritmul 2 prezinta structura generala a procedurii de backtracking.

3.2.2 Testarea consistentei unei instantieri partiale

Singura procedura care a ramas nedezvoltata algoritmic este cea de testarea consistentei unei instantieri partiale a a unui set S ⊆ X de variabile aleretelei date R. Teoretic, aceasta presupune parcurgerea tuturor relatiilorcorespunzatoare constrangerilor retelei si testarea faptului daca proiectia tu-plei a este continuta ın vreuna dintre ele. Daca notam cu t numarul maximde tuple ale unei relatii si e = |C|, atunci complexitatea algoritmului ar fiO(et), presupunand ca testarea apartenentei unei tuple la o relatie se face ıntimp constant.

3.2. BACKTRACKING 41

Algorithm 2 Structura generala a algoritmului backtracking

Intrare: R = (X,D, C) o retea de constrangeri, avand |X| = n.Rezultat: O solutie a retelei R sau mesajul ca reteaua este inconsitenta.

for Di ∈ D doD′

i = Di Facem o copie a domeniului Diend fora = ∅ a va contine solutia partiala a reteleii = 1 i reprezinta indexul variabilei ce urmeaza a fi instantiatawhile 1 ≤ i ≤ n do

success = instantiate(xi, a)Incercam sa instantiem variabila xi astfel ıncat solutia partiala a ex-tinsa cu valoarea lui xi sa ramana consistentaif success thentrecem la pasul urmatori = i + 1

elsefacem pasul ınapoiDi = D′

i

i = i− 1a = a[x1, ..., xi−1]

end ifend whileif i = 0 then

return ”inconsistenta”else

return aend if

Procedura instantiate(xi, a)while Di 6= ∅ do

Alege ai ∈ Di o valoare oarecare din domeniul lui Di

Di = Di − ai

a′ = (a, xi = ai)if isConsistent(a′) then

a = a′

return trueend if

end whileNu s-a putut face instantierea lui xireturn false


3.3 Backjumping

Unul din motivele pentru care algoritmul general de backtracking, ın care pa-sul de ıntoarcere se face la ultimul nod instantiat ınaintea obtinerii inconsistentei,devine de multe ori ineficient este posibilitatea de a gresi din acelasi motivde mai multe ori (”thrashing”). Sa analizam mai concret aceasta situatie.

FieR = (X,D, C) o retea de constrangeri avand variabilele X = x1, ..., xnsi sa presupunem ca instantierea partiala curenta a algoritmului BT este(x1 = a1, ..., xk−1 = ak−1) iar urmatoarea variabila ce trebuie instantiata estexk. In cazul ın care 6 ∃b ∈ Dk astfel ıncat (x1 = a1, ..., xk−1 = ak−1, xk = b) safie consitenta suntem ıntr-o situatie de esec si trebuie sa facem pasul ınapoi.

Dupa cum am spus, algoritmul cronologic de BT s-ar intoarce in xk−1,ıncercand sa atribuie acestei variabile o noua valoare si va continua apoi dinnou cu xk, presupunand ca motivul esecului anterior a fost valoarea atribuitalui xk−1. Acest lucru nu este ınsa neaparat adevarat. Este posibil sa existeun index 1 ≤ i < k − 1 pentru care instantierea partiala (x1 = a1, ..., xi =ai) sa nu fie compatibila cu variabila xk, ceea ce ınseamna ca 6 ∃b ∈ Dk

astfel ıncat (x1 = a1, ..., xi = ai, xk = b) sa fie consistenta. In aceastasituatie algoritmul de BT va ıncerca fara nici un succes sa schimbe valorilevariabilelor xk−1, ..., xi+1 ın speranta ca va putea instantia pe xk, aceastadeoarece motivul esecului din xk este tocmai valoarea atribuita variabilei xi.

Spunem ca o instantiere partiala (x1 = a1, ..., xk−1 = ak−1, xk = ak) estetare inconsistenta daca si numai daca:

• este inconsitenta si

• exista un index index 1 ≤ i < k − 1 pentru care instantierea partiala(x1 = a1, ..., xi = ai) nu este compatibila cu variabila xk.

In mod evident, pentru a eficientiza algoritmul de backtracking trebuie saminimizam numarul instantierilor responsabile cu situatii de esec si, implicit,pe cele tare-inconsistente. O strategie simpla pentru a obtine acest lucrueste ınlocuirea pasului clasic de ıntoarcere la variabila anterioara cu un saltla variabila responsabila efectiv de aparitia esecului. Aceasta tehnica poartanumele de Backjumping.

3.3. BACKJUMPING 43

Algorithm 3 Structura generala a procedurii Backjumping

Rezultat: Variabila catre care va fi facut pasul de ıntoarcere, sau null dacareteaua este inconsistenta

ak = (x1 = a1, ..., xk−1 = ak−1) este solutia partiala curentaxk este urmatoarea variabila ce trebuie instantiatai = k indexul variabilei curente (xi−1 este candidatul la ıntoarcere)D este submultimea variabilelor din x1, ..., xk−1 cu care xk participamacar la o constrangerewhile true do

Restaureaza domeniul Di la valoarea initialai = i− 1if i = 0 then

return null Reteaua este inconsitentaend ifif xi 6∈ D then

continue Daca xi si xk sunt independente schimbarea valorii lui xi

nu influenteaza nimicend ifai = (x1 = a1, ..., xi = ai)if isCompatible(ai, xk) then

return xi

end ifend while


3.4 Backmarking

In sectiunea anterioara am abordat problema minimizarii situatiilor de tare-inconsistenta si am descris schema generala a algoritmilor de tip backjumping,ın care pasul de ıntoarcere se face la variabila a carei instantiere curenta esteresponsabila cu esecul obtinut. Prin acest tip de algoritm eliminam una dinproblemele algoritmului general de backtracking si anume cea de munca ıngol (”thrashing”), reducand astfel dinamic dimensiunea spatiului de cautarea solutiilor.

O alta tehnica de optimizare a algoritmilor sistematici de cautare estecea de creare a unei structuri de date de tip cache ın care sa fie memorateinformatii legate de incompatibilitatea unor anumite atribuiri de valori vari-abilelor retelei, astfel ıncat algoritmul sa evite munca redundanta, cu altecuvinte sa evite crearea unor instante inconsistente dintr-un motiv care afost identificat la un pas anterior. Aceasta tehnica se numeste backmarking.

FieR = (X,D, C) o retea de constrangeri, avand variabilele X = x1, ..., xn.Sa ne reamintim ca algoritmul general de backtracking ıncearca instantiereasuccesiva a variabilelor x1, ..., xn si, ın situatia ın care o solutie partiala(x1 = a1, ..., xk = ak) k < n nu mai poate fi extinsa, trebuie sa faca unpas ınapoi si sa atribuie alta valoare lui xk−1, continuand apoi ın aceeasimaniera. In cazul algoritmului de backjumping, revenirea se face la variabilacare a determinat efectiv esecul curent, ınsa acesata tehnica vine cu un costsi anume: identificarea variabilei responsabile. Folosind backmarking, vomretine situatia care a provocat conflictul ın asa fel ıncat la pasii urmatori aialgoritmului sa prevenim crearea instantierile care nu sunt consistente.

Sa presupunem ca am instantiat variabilele x1, ..., xk−1, solutia partialacurenta este (x1 = a1, ..., xk−1 = ak−1) si suntem ın situatia de a atribui ovaloarea variabilei xk, fie aceasta b. Este posibil ca aceasta sa nu fie primatentativa de a extinde o solutie partiala formata din variabilele x1, ..., xk−1si, ın tentativele anterioare o serie de incompatibilitati au fost memorate.Scopul algoritmului backmarking este de a preveni instantierea xk = b ınconditiile ın care din informatiile culese anterior putem deduce faptul ca eanu este consistenta.

Pentru aceasta vom folosi urmatoarele structuri de date:

low Pentru fiecare x ∈ X, vom nota low(x) cel mai mic index al uneivariabile care si-a schimbat valoarea de la ultima vizita ın variabila x.Initial low(x) = 0,∀x ∈ X.

3.5. ALGORITMI DE FILTRARE SI PROPAGARE 45

x1 -> x2 -> x3 -> x4 x5 x6

x3 <-

x2 <- x3 <-

low(x3)=low(x4)=2

mark Daca xk este variabila curenta, pentru fiecare valoare b ∈ Dxk, vom

nota mark(xk, a) cel mai mic index p al unei variabile pentru careinstantierea partiala (x1 = a1, ..., xp = ap, xk = b) nu este consis-tenta. Daca atribuirea xk = b este consistenta cu solutia curenta,atunci mark(xk, a) = k.

Revenind la situatia initiala si folosind structurile de date de mai sus, lainstantierea variabilei curente xk putem elimina din domeniul lui xk toatevalorile b ∈ Dk pentru care:

low(xk) > mark(xk, b)

Explicatia este simpla. Sa notam p = mark(xk, b), instantierea (x1 =a1, ..., xp = ap, xk = b) (conform definitiei lui mark) nu este consistenta,deci schimbarea valorii oricarei variabile din multimea xp+1, ..., xk−1 nu arecum sa afecteze consistenta intantierii (x1 = a1, ..., xp = ap, ..., xk = b). Sicum low(xk) > p, concluzia este evidenta.

x1..............xp............low(xk)..........xk

x1..............low(xk)........xp..............xk

3.5 Algoritmi de filtrare si propagare

In aceasta sectiune vom analiza o tehnica de reducere a spatiului de cautarea solutiilor.

Definitie 4 Spunem ca o retea R′ = (X,D′, C ′) este ”mai usor de rezol-vat” decat o retea echivalenta R = (X,D, C) si notam R′ R daca si numaidaca:

∀xi ∈ X |D′i| ≤ |Di|


Definitie 5 Un algoritm de filtrare este un algoritm care aplicat uneiretele de constrangeri R = (X,D, C) va reduce spatiul de cautare al acesteia,transformand-o ıntr-o retea echivalenta dar mai usor de rezolvat.

Deoarece un algoritm de filtrare determina transformarea retelei pentrucare a fost apelat, este natural sa ıncercam repetarea acestuia atat timp catsunt obtinute modificari asupra domeniilor sau constrangerilor acesteia. Dinacest motiv, precum si datorita faptului ca aplicarea lor este realizata dupaefectuarea unei schimbari a retelei (de exemplu, asignarea unei variabile cereduce domeniul acesteiea la valoarea atribuita), acestia mai sunt numitialgoritmi de propagare (a schimbarii efectuate). Denumirea de ”filtrare” estesugerata de faptul ca reducerea spatiului de cautare se face prin eliminareade valori din domeniile variabilelor. ”Propagare” se refera la faptul ca oriceschimbare a domeniilor sau constrangerilor retelei determina la randul ei, ınlant, alte schimbari ce pot fi facute si care reduc ın continuare spatiul decautare al problemei.

Definitie 6 Un algoritm de filtrare-propagare este un algoritm formatdin:

(F ) o componenta de filtrare F responsabila cu reducerea problemei.

(test) o componenta de evaluare a retelei care va analiza starea retelei curenteobtinuta ın urma unei operatiuni de filtrare;

(stop) un predicat de oprire care va specifica daca este necesara reluarea algo-ritmului de filtrare.

Componenta de evaluare trebuie sa distinga urmaoarele situatii:

• succes - a fost identificata o solutie a retelei, de exemplu ın situatia ıncare toate domeniile au fost reduse la un singur element.

• inconsistent - nu exista nici o solutie bazata pe instantierea partiala,acest lucru fiind uzual dedus din reducerea domeniului unei variabilela multimea vida;

• simplu - problema a fost redusa pana la un punct ın care exista al-goritmi simpli, polinomiali de rezolvare si acestia vor fi folositi pentrurezolvare;

3.5. ALGORITMI DE FILTRARE SI PROPAGARE 47

• insuficent - instantierea curenta nu ofera suficiente informatii pentrua trage concluzia daca ea poate conduce la o solutie sau nu, caz ın caretrebuie sa continuam algoritmul de cautare a solutiilor.

Aplicarea unui algoritm de propagare P = (F, test, stop) va fi realizataastfel:

Algorithm 4

Intrare: R = (X,D, C) o retea de constrangeri, P = (F, test, stop) un algo-ritm de propagare

Rezultat: O solutie a retelei sau R′ = (X,D′, C ′) o retea echivalenta cuproprietatea R′ R sau ∅ daca R este inconsistenta

stop = falsewhile stop = false doR′ ← Aplica algoritmul F retelei Rif R = R′ thenFiltrarea nu a modificat reteauareturn R

end ifif test(R′) = inconsistent then

return ∅end ifif test(R′) = succes then

return solutia lui R′

end ifif test(R′) = simplu then

return rezolvarea lui R′

end ifInsuficiente informatii - continuam algoritmulActualizeaza valoarea lui stopR = R′

end whilereturn R’

Asadar, ın urma executiei unui algoritm de propagare asupra unei reteleR poate fi obtinut unul din urmatoarele rezultate:

• o solutie a retelei;


• inconsistenta retelei; ın aceasta situatie este utila retinerea unei explicatiicare sa demonstreze inconsitenta instantierii curente.

• o retea R′ exchivalenta cu R dar mai usor de rezolvat - algoritmul decautare a solutiilor va continua folosind domeniile si constrangerile luiR′

Din punctul de vedere al momentului aplicarii lor, algoritmii de propagaresunt:

• statici - sunt aplicati problemei initiale o singura data, ınainte de re-zolvarea propriu-zisa

• dinamici - sunt aplicati ın timpul procesului de rezolvare asupra sub-problemei curente obtinuta din problema initiala ın urma instantieriiunor variabile.

Diferenta ıntre cele doua tipuri se refera la momentul ın care acestia suntapelati. De asemenea, ın cazul algoritmilor dinamici este necesar sa retinemstarea curenta a retelei astfel ıncat la executarea pasului de ıntoarcere aceastasa poata fi refacuta corespunzator.

Schematic vorbind, includerea propagarii ın cadrul unui algoritm sistem-atic de cautare a solutiilor este descrisa de algoritmul 5.

Distingem urmatoarele tipuri de algoritmi de filtrare:

• algoritmi bazati pe adaugarea de constrangeri deduse din multimeacelor existente;

• algoritmi generali de asigurare a arc-consistentei;

• algoritmi dedicati de filtrare, specifici fiecarei probleme ın parte.

3.6 Arc-consistenta

Fie R = (X,D, C) o retea de constrangeri oarecare, unde X = x1, ..., xn,D = D1, ..., Dn.

Definitie 7 Spunem ca o variabila xi ∈ X este arc-consistenta referitorla o variabila xj ∈ X daca si numai daca pentru orice valoare ai ∈ Di exista ovaloare aj ∈ Dj astfel ıncat instantierea partiala < xi, ai >,< xj, aj > este

3.6. ARC-CONSISTENTA 49

Algorithm 5 Includerea algoritmilor de propagare

Intrare: R = (X,D, C) o retea de constrangeri, PS o multime de algoritmistatici de propagare, PD o multime de algoritmi dinamici de propagare.

Rezultat: Solutia (solutiile) retelei R

for all P ∈ PS doR← Aplica algoritmul P retelei R

end for

while Sunt cautate solutii do

Pasul de ınaintare (Forward)Memoreaza starea reteleiA fost realizata o instantiere xi = aReducem domeniul lui xi: Di = afor all P ∈ PD doR← Aplica algoritmul P retelei R

end for

Pasul de ıntoarcere (Backward)Restaureaza starea retelei

end while


consistenta. Daca Di = ∅ vom considera ca xi este arc-consistenta relativ laorice alta variabila.

Cu alte cuvinte, din perspectiva executiei algoritmului de backtracking,atribuind valoarea ai variabilei xi nu vom produce o situatie de inconsistentacare sa necesite efectuarea pasului ınapoi.

O retea este arc-consistenta daca si numai daca ∀x, y ∈ X, x este arc-consistenta relativ la y si y este arc-consistenta relativ la x. In mod evident,daca o retea nu este arc-consistenta atunci ea nu are nici o solutie.

Asadar, arc-consistenta este o proprietate importanta pe care ar trebuisa o aiba o retea de constrangeri astfel ıncat algoritmii de explorare de tipbacktrack sa poata reduce numarul de atribuiri gresite.

Deoarece arc-consistenta analizeaza reteaua la nivelul subretelelor de catedoua variabile, ea mai este numita si 2-consistenta.

3.6.1 Algoritmul de proiectie

Algorithm 6 Construieste proiectia unei relatii pe o multime de variabile

Intrare: R o relatie peste multimea de variabile X = x1, ..., xn, S =xi1 , ..., xit o submultime a lui X

Rezultat: Proiectia lui R pe S: πS(R)πS(R) = ∅for all a = (a1, ...an) ∈ R do

πS(R) = πS(R) ∪ (ai1 , ..., aik)end forreturn πS(R)

Complexitatea algoritmului de proiectie este O(|S|t), unde t este numarulde tuple al relatiei.

3.6.2 Constructia unei subretele cu doua variabile

O retea de constrangeri avand doar doua variabile poate fi identificata curelatia peste cele doua variabile formata din reuniununea tuturor relatiilorconstrangerii retelei.

Folosind operatorii de la relatii, putem scrie:


Algorithm 7 Construieste o subretea cu doua variabile

Intrare: R = (X,D, C) o retea de constrangeri, xi, xj ∈ X doua variabiledistincte

Rezultat: Relatia Rij formata din perechile de valori admise pentru vari-abilele xi, xj.Rij = ∅for all C =< S, R >∈ C do

Rij = Rij ∪ πxixj(R)

end forreturn Rij

Rij =⋃πxixj

(R)|R ∈ C

Complexitatea algoritmului este O(et), unde e = |C| iar t este margineasuperioara a numarului de tuple din fiecare constrangere a retelei R.

3.6.3 Testarea arc-consistentei

Algorithm 8 AC-Test - Testeaza arc-consistenta unei retele

Intrare: R = (X,D, C) o retea de constrangeriRezultat: true daca reteaua este arc-consistenta, altfel false

for all xi ∈ X dofor all a ∈ Di do

for all C =< S, R >∈ C, xi ∈ S doif a 6∈ πxi

(R) thenreturn false

end ifend for

end forreturn true

end for

Propozitie 2 Complexitatea algoritmului de testare a arc-consistenteieste O(ek2t), unde k este marginea superioara a dimensiunilor domeniilor,e = |C| iar t este marginea superioara a numarului de tuple din fiecare con-strangere.


Demonstratia rezulta imediat din faptul ca numarul maxim de valori pecare le pot lua variabilele retelei este ek iar pentru fiecare instantiere < xi, a >efectuam e teste pentru a determina daca este satisfacuta arc-consistenta,fiecare dintre acestea apeland procedura de proiectie care se face ın O(t).

Vom descrie ın continuare o serie de algoritmi prin intermediul caroraputem obtine, plecand de la o retea oarecare, o retea echivalenta care sa aibaproprietatea de arc-consistenta, daca acest lucru este posibil. Ideea generalaa acestor algoritmi se bazeaza pe ”corectarea” domeniilor de definitie ale vari-abilelor prin eliminarea unor valori incompatibile ale acestora, reducandu-leastfel ıncat sa fie atinsa arc-consistenta.

3.6.4 Procedura de reducere a domeniilor Revise

Procedura Revise (corectare, revizuire) are ca intrare o retea de constrangeriR = (X,D, C) si doua variabile distincte xi, xj ∈ X, avand ca rezultat reduc-erea domeniului Di de definitie a lui xi astfel ıncat xi sa fie arc-consistentarelativ la xj.

Algorithm 9 Revise - Asigura arc-consistenta lui xi relativ la xj

Intrare: R = (X,D, C) o retea de constrangeri, xi, xj ∈ X, xi 6= xj

Rezultat: Reducerea domeniului Di astfel ıncat xi sa fie arc-consistentarelativ la xj; daca domeniul a fost redus, returneaza true, altfel false.

Rij =⋃πxixj

(R)|R ∈ CRij este relatia perechilor de valori permise pentru xi, xj

revised = falsefor all ai ∈ Di do

if 6 ∃aj ∈ Dj astfel ıncat (ai, aj) ∈ Rij thenDi = Di − airevised = true

end ifend forreturn revised

Folosind operatorii de la relatii, restrangerea lui Di poate fi scrisa sub


forma: Di = Di ∩ πxi(Rij)

Propozitie 3 Complexitatea algoritmului de corectie Revise este O(et +k2), unde k este marginea superioara a dimensiunilor domeniilor iar e = |C|.

Demonstratia consta ın faptul ca, ın cel mai defavorabil caz, fiecare val-oare din Di este testata ımpreuna cu fiecare valoare Dj, cee ce conduce lacel mult |Di||Dj| ≤ k2 operatii. La acestea se mai adauga complexitateaoperatorului de proiectie necesar calcularii relatiei Rij, care este O(et), fiindnecesara parcuregerea tuturor constrangerilor retelei.

In retelele binare, deoarece nu mai trebuie sa executam operatia de proiectie,complexitatea va fi O(k2).

3.6.5 Algoritmul de arc-consistenta AC-1

Algoritmul prezentat ın continuare consta ın satisfacerea bruta a arc-consistenteiunei retele prin aplicarea repetata a procedurii de reducere a domeniilor pen-tru fiecare pereche de variabile.

Algorithm 10 AC-1 - Asigura arc-consistenta unei retele

Intrare: R = (X,D, C) o retea de constrangeriRezultat: O retea arc-consistenta R′ echivalenta cu RR′ = Rrepeat

for all xi, xj ∈ X, xi 6= xj participa la o constrangere doRevise(R′, xi, xj)Revise(R′, xj, xi)

end foruntil nici un domeniu din R′ nu mai este modificatreturn R′

Trebuie observat faptul ca o singura aplicare a reducerilor pentru toateperechile de variabile nu este suficienta, motivatia fiind urmatoarea: dupaapelurile Revise(R′, xi, xj) si Revise(R′, xj, xi) variabilele xi si xj vor fi arc-consistente una relativ la cealalta, dar la un pas ulterior una din acestevariabile ısi poate schimba domeniul ca urmare a satisfacerii arc-consistenteicu o alta variabila, ceea ce ınseamna ca arc-consistenta lor nu mai este sigura.


In cazul ın care ın urma aplicarii algoritmului domeniul vreunei variabiledevine vid, atunci reteaua este inconsistenta.

Propozitie 4 Data o retea R = (X,D, C), avand |X| = n, |C| = esi dimensiunile domeniilor marginite de k, complexitatea algoritmului AC-1aplicat retelei R este O((et + k2)n2ek).

Justificarea complexitatii este urmatoarea: apelul procedurii Revise esterealizata ın O(et + k2) timp, acesta fiind executat de n(n − 1)/2 ori, deciın O(n2) timp. Cum, ın cel mai rau caz, la fiecare pas va fi eliminata cateo singura valoare a unui domeniu, bucla repetitiva se va executa de O(ek)ori (acesta fiind numarul maxim de valori), deci complexitatea totala va fiO((et + k2)(n2)(ek)).

In retelele binare, deoarece numarul perechilor de variabile este de or-dinul numarului de constrangeri si operatia de reducere se face ın O(k2),complexitatea algoritmului AC-1 va fi O(e2k3).

Algoritmul AC-1 nu este foarte eficient din cauza aplicarilor repetate aleprocedurii de reducere chiar ın situatia ın care acest lucru nu este necesar.Sa ne gandim doar la situatia ın care doar domeniul unei variabile a fostmodificat iar algoritmul este reluat si va executa revizuirea domeniilor, dinnou, pentru toate perechile de variabile. Asadar, AC-1 poate fi ımbunatatit.O prima varianta de ımbunatatire este algoritmul AC-2 pe care, datoritasimilitudinii cu AC-1 nu ıl vom mai prezenta.


Ideea pe care se bazeaza AC-3 este memorarea perechilor de variabile pecare este necesar sa le testam dupa executarea unui pas complet de reduceri.Astfel, vom folosi o structura de date de tip lista ın care vom plasa initialtoate perechile de variabile (xi, xj), (xj, xi) care urmeaza sa fie procesate,ıntocmai ca la primul pas din AC-1. Dupa procesarea unei perechi (xi, xj),aceasta va fi eliminata din stiva, fiind reintrodusa ulterior doar daca domeniullui xj a fost redus ın urma testarii unei perechi de forma (xj, xp), p 6= i

Propozitie 5 Data o retea R = (X,D, C), avand |X| = n, |C| = esi dimensiunile domeniilor marginite de k, complexitatea algoritmului AC-3


Algorithm 11 AC-3 - Asigura arc-consistenta unei retele

Intrare: R = (X,D, C) o retea de constrangeriRezultat: O retea arc-consistenta R′ echivalenta cu RR′ = Rqueue = ∅for all xi, xj ∈ X, xi 6= xj participa la o constrangere do

queue = queue ∪ (xi, xj), (xj, xi)end forwhile queue 6= ∅ do

Selectam o pereche (xi, xj) din lista queuequeue = queue− (xi, xj)revised = Revise(R′, xi, xj)if revised thenDomeniu D′

i a fost redusqueue = queue ∪ (xi, xk)|k 6= i

end ifend whilereturn R′

aplicat retelei R este O(max(n2, ek)ek2).

Pentru a demonstra acest lucru sa ne reamintim ca apelul proceduriiRevise este realizata ın O(ek2) timp. Ramane sa calculam numarul maximde iteratii al buclei while. Initial avem O(n2) perechi de variabile ın listaqueue. La fiecare pas, o pereche dintre acestea este eliminata, singura situatieın care aceasta ar putea fi reintrodusa fiind cea ın care domeniul unei variabileeste redus cu cel putin o valoare. Avand ın vedere faptul ca sunt maximek valori ın reuniunea tuturor domeniilor, iteratia va fi facuta de cel multO(max(n2, ek)).

In retelele binare, deoarece numarul perechilor de variabile este de or-dinul numarului de constrangeri si operatia de reducere se face ın O(k2),complexitatea va fi O(ek3).


Folosind eficient o serie de structuri de date pentru reprezentarea informatiilornecesare ın obtinerea arc-consistentei poate fi elaborat un algoritm avand


complexitatea O(ek2).Avand ın vedere ca doar pentru a verifica daca o retea este arc-consistenta

sunt necesare O(ek2) operatii, algoritmul AC-4 este optimal.Mai multe detalii legate de acest algoritm vor fi discutate ın capitolul

”Explicatii”.

3.7 Constrangeri globale

Definitie 8 Fie C = C1, ..., Ck o multime de constrangeri. Numim con-strangere globala constrangerea CG definita sub forma unei conjunctii ıntreconstrangerile multimii C:

CG = C1 ∧ C2 ∧ ... ∧ Ck

Daca notam cu X(C) multimea tuturor variabilelor constrangerilor din Csi D(C) familia tuturor domeniilor variabilelor din X(C), multimea tuplelorlui CG este egala cu solutia retelei (X(C),D(C), C1, ..., Ck).

ObservatieFie R = (X,D, C) o retea, unde X = x1, ..., xn, C = C1, ..., Cm si fie

CG = C1 ∧ C2 ∧ ... ∧ Cm. Retelele R si R′ = (X,D, CG) sunt echivalente.

Avantajele folosirii constrangerilor globale sunt:

• Expresivitate - este mai convenabil sa definim o singura constrangerecare sa reprezinte un anumit lucru, decat ca acesta sa reiasa ca o con-cluzie a mai multor constrangeri. De exemplu, o constrangere de tipalldiff ce specifica faptul ca toate variabilele unei retele trebuie sa iavalori diferite are o semnificatie si o implementare standard indiferentde tipul retelei.

• Filtrare superioara - introducerea constrangerilor globale poate aveaimpact asupra algoritmilor de filtrare, cum ar fi cel de arc-consistenta,reducand spatiul de cautare a solutiilor.Fie R = (X,D, C) o retea, unde X = x, y, z, Dx = Dy = Dz = 0, 1iar C = x 6= y, y 6= z, z 6= x. Aplicand algoritmul clasic de arc-consistenta nu vom obtine nici un rezultat deoarece oricum am alege

3.7. CONSTRANGERI GLOBALE 57

doua variabile, sa spunem x si y, pentru orice valoare a ∈ Dx exista ovaloare b = 1 − a ∈ Dy astfel ıncat instantierea partiala < x, a >, <y, b > este consistenta (cele doua variabile sunt arc-consistente unarelativ la cealalta). Daca adaugam ınsa si constrangerea CG = x 6=y∧y 6= z∧z 6= x algoritmul de filtrare va detecta imediat inconsistentaretelei. Singura problema care apare ın aceasta abordare este, ın modevident, complexitatea verificarii constrangerii globale.

• Descompunerea unei retele - gruparea unor constrangeri ıntr-o formaglobala presupune rezolvarea subretelei create astfel ıncat sa putemdetermina tuplele ce formeaza constrangerea globala. In urma acestuiproces putem determina inconsistenta retelei.

Pentru a exemplifica situatia de mai sus, sa consideram un alt exemplu,similare celui precedent. FieR = (X,D, C) o retea, unde X = x, y, z,Dx = Dy = Dz = 0, 1 iar C = x 6= y, y 6= z, z 6= x, fxy, fyz, fxz, ffiind o functie de tip oracol cu complexitate mare de calcul. Aplicandun algoritm sistematic de cautare vom fi nevoiti sa calculam functiaf cel putin o data, lucru inutil deoarece R este evident inconsistenta.Daca rescriem ınsa reteaua sub forma R = (X,D, CG, fxy, fyz, fxz),unde CG = x 6= y ∧ y 6= z ∧ z 6= x, atunci ın urma calculului tuplelorconstrangerii CG vom obtine ca ea este vida, ceea ce ınseamna evidentca reteaua este inconsistenta.

Definitie 9 FieR = (X,D, C) o retea de constrangeri, C = C1, C2, ..., Cmsi CG = C1∧C2∧ ...∧Cm constrangerea globala corespunzatoare. Spunem caun algoritm de filtrare este pertinent daca, aplicat retelei R′ = (X,D, CG),poate reduce mai mult spatiul de cautare al solutiilor fata de aplicarea lui peR.

3.7.1 Exemple de constrangeri globale

AllDiffConstrangerile de tip alldiff impun ca valorile uni multimi de variabilesa fie distincte doua cate doua. In cazul ın care se refera la toate variabileleretelei, o constrangere alldiff mai este referita sub numele de permutation.alldiff(X) ın orice solutie a retelei variabilele din X trebuie sa fie diferite.


AtLeast, AtMostatleast(X, #time, val) / atmost(X, #time, val) - ın orice solutie a reteleivariabilele din X trebuie sa aiba ca valoare pe val de cel putin / cel mult unnuma specificat de ori.

Global Cardinality Constraints (GCC)gcc(X, l, u) Fiecarei valori ai din D(X(C)) ıi sunt asociate valorile li si ui.In orice solutie, pentru orice valoare ai a unei variabile din X, numarul ei deaparitii trebuie sa fie ın intervalul [ui, li].

3.7.2 AllDiff

Fie X = x1, ..., xn. Complexitatea verificarii constrangerii alldiff(X) este(n− 1)+ ...+1 = O(n2). Un algoritmul de filtrare trebuie sa elimine valoriledin domeniile variabilelor lui X care sigur nu pot face parte dintr-o solutie.Exemplu: Dx = 1, 2, 3, 4, Dy = 1, 2, Dz = 1, 2. Un algoritm de filtrarecorespunzator pentru alldiff trebuie sa elimine valorile 1, 2 din domeniul luix.

Graful valorilor [33] asociat unei constrangeri C este un graf bipartitG = (X, Y, E) definit astfel:

• X = X(C) - variabilele care participla ın constrangerea C

• Y = D(X(C)) - valorile care pot fi atribuite variabilelor din X(C)

• (x, a) ∈ E ⇔ a ∈ D(x)

Teorema 1 [26] Fie G = (V, E) un graf bipartit, avand |V | = n si |E| = m.Exista un algoritm de complexitate O(

√nm) pentru determinarea unui cuplaj

maximal al grafului G.

Propozitie 6 Fie C o constrangere de tip alldiff si GV (C) graful valorilorasociat. Un cuplaj care acopera multimea X(C) corespunde unei tuple dinC.

Propozitie 7 O constrangere C de tip alldiff este consistenta daca sinumai daca ın graful valorilor GV (C) asociat exista un cuplaj care acoperamultimea X(C).


Propozitie 8 O variabila x ∈ X(C) este consistenta relativ la C daca sinumai daca exista o muchie (x, a) care sa apartina unui cuplaj care acoperamultimea X(C), din graful valorilor GV (C).

Propozitie 9 [4] O muchie apartine unor cuplaje maxime dar nu tuturorcuplajelor maxime daca si numai daca pentru un cuplaj maxim oarecare eaapartine unui drum alternat de lungime para care ıncepe ıntr-un nod libersau unui circuit alternat de lungime para.

Propozitie 10 Dat un graf bipartit G = (X, Y, E) si un cuplaj maxim Mcare acopera X. Fie A = a ∈ Y |a liber si A = Y −B = a ∈ Y |a saturat.Construim graful orientat O(G, M) = (X ∪Y ∪s, E ′) obtinut din G astfel:

• adaugam un nou varf s grafului G

• adaugam muchii ıntre toate nodurile din B si s

• adaugam muchii ıntre s si toate nodurile din A

• orientam muchiile din M de la nodul din Y catre cel din X

• orientam muchiile din E −M de la nodul din X catre cel din Y

• orientam muchiile de la B catre s

Fie (x, a) 6∈ M (a este nod liber ın Y ). Atunci (x, a) apartine unui drumalternat de lungime para care ıncepe ıntr-un nod liber daca si numai daca asi s apartin unei componente tare conexe a grafului orientat O(G, M).

Demonstratie(⇒) Toate nodurile din X fiind saturate, orice drum alternat de lungime

para care ıncepe ıntr-un nod liber este de tipul: D = (a, x1, b1, x2, b2, ..., xk, bk),unde a ∈ A, xi ∈ X, bi ∈ B, ∀i = 1, k, apartenenta muchiilor la cuplajul Mfiind: (a, x1) 6∈ M , (xi, bi) ∈ M, ∀i = 1, k, (bi, xi+1) 6∈ M, ∀i = 1, k. Tinandcont de orientarea arcelor ın O(G, M) se fa forma un drum de la a la s.Avand ın vedere ca (s, a) ∈ E ′, a si s fac parte din aceeasi componenta tareconexa a grafului O(G, M).


(⇐) Daca exista un drum de la a la s, atunci tinand cont de constructialui O(G, M) putem trage concluzia ca arcele drumului (exceptand ultimul)formeaza ın G un drum alternat de lungime para.

Fie G = (X, Y, E) un graf bipartit si un cuplaj maxim M care acopera X.Tinand cont de ultimele doua afirmatii si de faptul ca ın G nici un nod libernu poate face parte dintr-un circuit alternat obtinem urmatorul algoritm defiltrare pentru o constrangere C de tip alldiff:

1. Determinarea unui cuplaj maxim M ın G. Daca |M | < |X| atunciconstrangerea nu este consistenta. Daca notam |X| = n, |Y | = d, |E| =m, complexitatea acestui pas este O(

√nm).

2. Constructia grafului orientat O(G, M)

3. Determinarea componentelor tari conexe ale lui O(G, M). Complexi-tatea este O(m + n + d).

4. Pentru fiecare nod liber a, daca a si s nu sunt ın aceeasi componentatare conexa, elimina pe a din domeniile variabilelor constrangerii C.Complexitatea acestui pas este de asemenea O(m + n + d).

Sa analizam ın continuare eficienta algoritmului de filtrare pentru alldiff,cu alte cuvinte care este impactul aplicarii sale asupra domeniilor variabilelorconstrangerii. Fie X = x1, ..., x2k o multime de n = 2k variabile avandurmatoarele domenii:

• pentru 1 <= i <= k: D(xi) = 2[(i− 1)/2] + 1, 2[(i− 1)/2] + 2

• pentru k < i <= n: D(xi) = 1, ..., n

De exemplu, pentru n = 8 vom avea D(x1) = D(x2) = 1, 2, D(x3) =D(x4) = 5, 6, D(x5) = D(x6) = D(x7) = D(x8) = 1, ..., 8.

Aplicand algoritmul de filtrare, toate valorile din domeniile variabilelorde la x1 la xk vor fi eliminate din domeniile variabilelor xk+1, ..., xn, ceeace ınseamna O(k2) = O(n2) reduceri.


3.7.3 Global Cardinality Constraint (GCC)

O constrangere de tip gcc impune restrictii asupra numarului de asignari aleunei valori pentru variabile dintr-o anumita multime ın cadrul unei solutii.Sa exprimam formal acest lucru. Fie X = x1, ..., xn o multime de variabilesi l = l1, ..., lm, u = u1, ..., um o multime de valori asociate fiecarui ele-ment din reuniunea D(X) = a1, ..., am a domeniilor variabilelor din X. Oconstrangere C = gcc(X, l, u) impune ca ın orice solutie a retelei din care Cface parte, pentru orice valoare ai ∈ D(X), numarul ei de aparitii ca valoarea unei variabile din X trebuie sa fie ın intervalul [ui, li]. Daca notam cuT (X) = ×Dx|x ∈ X multimea tuplelor care pot fi asignate variabilelordin X, si #(a, t) numarul de aparitii a unei valori a ıntr-o tupla t ∈ T (X),putem scrie:

C = t ∈ T (X)|∀a ∈ D(X) : li ≤ #(ai, t) ≤ ui.

Dupa cum este usor de observat, constrangerea alldiff este o particu-larizare a gcc ın care limitele superioare si inferioare sunt egale cu 1.

Sa analizam cum putem aborda problema testarii consistentei unei con-strangeri gcc si a implementatii unui algoritm de filtrare.

Fie G = (V, E) un digraf. Asociem fiecarui arc ij al digrafului doua valorilij, respectiv uij, avand semnificatia de capacitate minima, respectiv maximaa arcului: l, u : E → R+, lij ≤ uij,∀ij ∈ E.

Definitie 10 ([9]) Se numeste circulatie ın G orice functie f : E → Rastfel ıncat:

∀i ∈ V∑

j:ji∈E

cji −∑

j:ij∈E

cij = 0

O circulatie c se numeste admisibila daca ∀ij ∈ E lij ≤ xij ≤ uij.

Fara a restrange generalitatea, vom presupune ın continuare ca ıntre ori-care doua varfuri ale digrafului exista cel mult un arc.

Teorema 2 (Hoffman-Gale) Fie G = (V, E) un digraf si l, u : E → R+, lij ≤uij,∀ij ∈ E. Exista o circulatie admisibila ın G daca si numai daca ∀(S, T )partitie a lui V avem: ∑

i∈S,j∈T

lij ≤∑

i∈T,j∈S

uij


(ın expresia de mai sus se subıntelege ij ∈ E)

Definitie 11 Fie C = gcc(X, l, u) o constrangere de tip gcc. Definimreteaua valorilor lui C ca fiind digraful N(C) obtinut din graful valorilorGV (C) astfel ([44]):

• orientam muchiile lui GV (C) de la valori catre variabile; pentru fiecareastfel de arc ax setam lax = 0 si uax = 1.

• adaugam un nod s si arce de la s catre fiecare nod valoare; pentrufiecare astfel de arc lsai

= li si usai= ui.

• adaugam un nod t si arce de la fiecare nod variabila catre t; pentrufiecare astfel de arc lxt = uxt = 1.

• adaugam un arc (t, s) avand lts = uts = |X|.

Propozitie 11 Fie C = gcc(X, l, u) si N(C) reteaua valorilor asociata.Urmatoarele doua proprietati sunt echivalente:

1. Constrangerea C este consistenta.

2. Exista un o circulatie admisibila ın N(C).

Demonstratie(1 ⇒ 2) In cazul ın care constrangerea C este consistenta, atunci exista

o tupla q = (< x1 = a1 >, ..., < xn = an >) ∈ T (X) cu proprietatea ca∀a ∈ D(X) : li ≤ #(ai, q) ≤ ui.Definim urmatoarea circulatie f : E(N(C))→ R+:

• f(aixi) = 1, ∀i = 1, n

• f(sai) = #(ai, q), ∀i = 1, n

• f(xit) = 1, ∀i = 1, n

• f(ts) = n


Dupa cum se poate usor observa, circulatia f este admisibila.

(2 ⇒ 1) In cazul ın care exista o circulatie f admisibila ın N(C) atuncitupla q = (< x1 = a1 >, ..., < xn = an >), unde ai sunt valorile pentru caref(aixi) = 1, satisface constrangerea C, deci C este consistenta.

In cazul general, folosind teorema lui Hoffman-Gale si algoritmul luiEdmonds-Karp de determinare a unui flux maxim ıntr-o retea, problematestarii existentei unei circulatii admisibile pentru un digraf poate fi rezol-vata ın O(m3n) [9]. Pentru structura speciala a digrafului N(C) poate fi ınsaconceput un algoritm care sa determine ın O(nm) existenta unei circulatiiadmisibile.

Definitie 12 Graful rezidual al unei circulatii f , notat cu R(f), este undigraf cu aceeasi multime de noduri ca si G = N(C) iar multimea arcelor estedefinita orientand muchiile grafului suport G al lui G astfel : ∀ij ∈ E(G)

• daca fij < uij atunci ij ∈ E(R(f)), avand capacitatea reziduala rij =uij − fij

• daca fij > lij atunci ji ∈ E(R(f)), avand capacitatea reziduala rji =fij − lij

Propozitie 12 Fie C o constrangere de tip gcc consitenta si f o circulatieadmisibila ın N(C). O valoare a din domeniul unei variabile x nu este con-sitenta relativ la C daca si numai daca fax = 0 si a si x nu fac parte dinaceeasi componenta tare conexa ın R(f).

Demonstratie [44]

Este binecunoscut ın teoria fluxurilor ca valoarea fluxului pentru un arcax este constanta daca nu exista nici un drum de la a la x ın R(f)−ax si nuexista nici un drum de la x la a ın R(f)−xa. Mai mult uax = 1, deci ax si xanu pot apartine simultan grafului rezidual R(f) ceea ce ınseamna ca valoareaf(ax) este constanta daca si numai nu exista un circuit continand ax si xaın R(f), cu alte cuvinte x si a sunt ın componente tare conexe diferite.


CorolarFie C = (X, u, l) o constrangere de tip gcc, n = |X|, d = |D(X)| si

m = |E(N(C)|.

• Testarea consitentei lui C poate fi facuta ın O(nm).

• Arc-consistenta relativ la C poate fi obtinuta ın O(m + n + d).

Capitolul 4

Crearea unui solver CSP

4.1 Introducere

In acest capitol vom analiza aspectele cele mai importante care trebuie luateın considerare ın implementarea unui sistem de rezolvare automata a prob-lemelor modelate cu ajutorul constrangerilor. La ora actuala exista o ofertaconsistenta de astfel de aplicatii, variata atat din punctul de vedere al plat-formei de programare folosite cat si din modul de specificare a problemelorce trebuie rezolvate, unele dintre ele fiind create ın scop academic, altele fiindcomerciale. Dintre cele mai cunoscute (ın ordine alfabetica) putem aminti:

• Choco (Java, free software)

• Disolver (C++, proprietary)

• Gecode (C++, free software)

• ILOG Solver (C++, proprietary)

• Koalog Constraint Solver (Java, proprietary)

• Minion (C++, GPL)

• Mozart (Oz, free software)

• SICStus (Prolog, proprietary)

65

66 CAPITOLUL 4. CREAREA UNUI SOLVER CSP

Din perspectiva acestei lucrari, existenta aplicatiilor mentionate ante-rior nu ınseamna ca abordarea domeniului CSP trebuie sa se rezume strictla aspecte legate de modelarea problemelor iar rezolvarea acestora sa fieıncredintata unui solver performant ci, dimpotriva, este necesara ıntelegereaın detaliu a comportamentului unui astfel de solver ın vederea identificariituturor punctelor cheie care pot influenta procesul de gasire a solutiei sau deoptimizare a acesteia. Rezolvarea problemelor dificile presupune nevoia depersonalizare a modului de cautare a solutiilor, fiind necesara integrarea ıncadrului algoritmului general de rezolvare a unor alti algoritmi dedicati unorrestrictii polinomiale sau a unor euristici.

Asadar, obiectivele urmarite ın crearea solver-ului OmniCS sunt:

• Rezolvarea retelelor de constrangeri modelate ın sistemul clasic (CSP)

• Rezolvarea probleme de optimizare reprezentate sub forma unor reteleslabe de constrangeri (WCSP)

• Intreg procesul de explorare a spatiului solutiilor sa poata fi parame-trizat

• Adaugarea, ın functie de problema, a unor algoritmi de filtrare si propa-gare care sa reduca problema dupa fiecare decizie luata de solver

• Definirea de constrangeri globale carora sa le poata fi atasati algoritmispecifici de filtrare.

• Integrarea ın cadrul algoritmului general a:

– unor alti algoritmi dedicati unor restrictii polinomiale ale proble-mei respective

– unor eurisitici de cautare locala a solutiei

• Generarea de evenimente la momentele definitorii ale explorarii, astfelıncat sa poata fi creati observatori ai procesului de rezolvare

• Generarea de explicatii - posibilitatea de a crea un rationament deduc-tiv care sa explice de ce o problema nu are solutie.

• Interactivitate - posibilitatea de a schimba comportamentul solveruluichiar ın timpul executiei prin luarea manuala (de catre utilizator) aunor decizii sau revocarea unora luate de solver.

4.1. INTRODUCERE 67

• Dinamism - posibilitatea de a rescrie problema prin adaugarea/eliminareade variabile sau constrangeri chiar ın timpul executiei solverului, faraa fi necesara repornirea acestuia.

• Simplitate - Modelarea problemelor sa fie simpla.

• Performanta comparabila cu alte solvere.

Incercarea de a oferi atat simplitate ın utilizare cat si posibilitati cat maiample de parametrizare poate induce o penalizare la nivelul performanteloralgoritmului general comparativ cu alte solvere de tip Model-and-Run care,din punctul de vedere al utilizatorului sunt ca niste ”cutii negre” oferindfoare putine optiuni ınsa, dupa cum vom vedea, aceasta penalizare este decele mai multe ori nesemnificativa.

Un alt lucru care trebuie stabilit este modul de descriere a algoritmilorcare vor defini comportamentul aplicatiei. Exista doua abordari posibile:

• Modelul bazat pe evenimenteEste bazat pe generarea de evenimente la fiecare modificare a proble-mei. Astfel, evenimente cum ar fi schimbarea valorii unei variabile saueliminarea unei valori dintr-un domeniu sunt interceptate de obiecte detip listener ce vor reactiona propagand respectiva schimbare.Un solver CSP construit pe acest model este choco ın care, spre ex-emplu, propagarea deciziilor luate de solver trebuie implementata ıncadrul fiecarei constrangeri ın parte.

• Modelul globalExecutia solver-ului presupune apelarea succesiva a unor algoritmi definitila nivelul ıntregii probleme sau la nivelul fiecarei constrangeri ın parte.Astfel, algoritmul general de arc-consistenta poate fi definit sub formasa generala, ceea ce constituie un avantaj din punctul de vedere alclaritatii sale. Folosirea modelului global nu exclude posibilitatea de agenera evenimente si de a folosi acest mecanism ınsa acest lucru nu vaface parte din comportamentul critic al solverului.

Datorita simplitatii sale si a modului natural ın sunt descrisi algoritmii, ınimplementarea pe care o vom crea va fi utilizat modelul global.

Pentru a fi usor de folosit sistemul a fost conceput pe baza sablonului deproiectare MVC (Model-View-Controller) [22], [51], fiind structurat astfel:

• Nivelul de modelare - permite definirea problemei ce trebuie rezolvata


• Nivelul de control - reprezentat de componentele responsabile cu re-zolvarea problemei; aici sunt incluse:

– solver-ul propriu-zis

– algoritmii de filtrare globali sau cei definiti de constrangeri

• Nivelul de prezentare - defineste interfata cu utilizatorul pentru afisarearezultatelor.

Toate aceste trei nivele pot fi parametrizate si extinse astfel ıncat sa seadapteze oricarei probleme reprezentata ca o retea de constrangeri.

4.2 Nivelul de modelare

Indiferent de tipul sau, un solver CSP trebuie sa puna la dispozitie o modal-itate cat mai simpla de modelare a problemei care trebuie rezolvata. Simpli-tatea poate fi ınsa ınteleasa ın mai multe feluri, dintre care cele mai semni-ficative ar fi: concizia reprezentarii sau usurinta asimilarii de catre utilizator,prima situatie concretizandu-se ın utilizarea unui limbaj dedicat pentru de-scrierea problemei, ın timp ce a doua se bazeaza pe un limbaj consacrat deprogramare cum ar fi Java, C++ sau Prolog.

Datorita flexibilitatii sporite, a elegantei si a popularitatii sale, pentruimplementarea lui OmniCS a fost aleasa platforma de programare Java.

4.2.1 Reprezentarea problemei

Modelarea unei probleme presupune descrierea elementelor constitutive aleretelei de constrangeri asociate, acest lucru fiind facut printr-o serie de clasesi interfete. O instanta CSP este descrisa de clasa Problem, aceasta trebuindın primul rand sa permita definirea variabilelor si constrangerilor sale, acesteafiind reprezentate prin multimi de tip VarSet, respectiv ConstraintSet.

public class Problem

...

VarSet variables;

ConstraintSet constraints;

...

4.2. NIVELUL DE MODELARE 69

Dupa cum am mentionat, unul din obiectivele propuse a fost creareaunui sistem unitar care sa poata fi utilizat atat pentru rezolvarea retelelorclasice ın care obiectivul este satisfacacerea tuturor constrangerilor cat sipentru retelele slabe (soft) ın care scopul este minimizarea unei functii decost calculata din penalitatile implicate de nesatisfacerea unor constrangeri.Din acest punct de vedere, trebuie sa concepem o modalitate de evaluare asolutiilor care sa poata fi folosita ın ambele modele. Acest lucru a fost realizatprin asocierea fiecarei probleme a unei structuri de evaluare, descrisa de unobiect de tip ValuationStructure, aceasta fiind responsabil cu evaluareasolutiei curente.


...

ValuationStructure valuation;

...

Rezolvarea unei probleme presupune crearea unei instante a unui algo-ritm de rezolvare si lansarea procesului de cautare a solutiei. Un algoritmgeneric pentru rezolvarea unei retele de constrangeri va fi modelat printr-unobiect de tip Solver. In problemele de optimizare, cautarea poate porni faranici o informatie apriorica sau poate utiliza un optim determinat anteriorsi sa ıncerce ımbunatatirea acestuia. Implicit, variabila optim asociata uneiretele este valoarea minima definita de structura de evaluare, ınsa este oferitaposibilitatea de a o schimba ın conditia ın care acest lucru este necesar.


...

Solver solver;

int optimum;

...

Pe parcursul rezolvarii, o problema se poate gasi ın diferite stari care potinfluenta procesul de cautare al solutiei. Acestea sunt:

• UNKNOWN - nu se cunoaste nimic despre problema, aceasta fiind stareainitiala.


• SIMPLE - algoritmul general de rezolvare a determinat ca aceasta prob-lema, presupusa a fi NP-dificila, este un caz particular pentru careexista un algoritm mai simplu (polinomial) de determinare a solutiei;ın aceasta situatie controlul va fi transferat catre solverul mai eficient.

• SOLVED - problema este rezolvata.

• INCONSISTENT - problema nu are nici o solutie.

Definitia completa a structurii interne a unei probleme este:


private String name;

private String description;

private VarSet variables;

private ConstraintSet constraints;

private ValuationStructure valuation;

private Solver solver;

private int optimum;

public final static int UNKNOWN = 0;

public final static int SIMPLE = 1;

public final static int SOLVED = 2;

public final static int INCONSISTENT = -1;

...

Prin dimensiunea problemei vom ıntelege numarul variabilelor acesteia.

4.2.2 Definirea variabilelor

Variabilele reprezinta modalitatea de a formaliza necunoscutele unei prob-leme. Pentru a pastra generalitatea, nu va fi facuta nici o ipoteza asupratipului acestora, ele putand fi ıntregi, reale, siruri de caractere, multimi, etc.Clasa care modeleaza notiunea de variabila este Var. Aceasta va avea caprincipala proprietate domeniul sau, cu alte cuvinte multimea valorilor pecare le poate lua. Intrucat pe parcursul rezolvarii domeniile variabilelor suntmodificate de solver este necesar sa retinem si domeniul initial.


public class Var

...

Domain domain;

Domain initialDomain;

...

Pe langa acesta, fiecare variabila poate contine ca informatie suplimen-tara obiectul pe care ıl modeleaza ın cadrul retelei (daca este necesar). Deexemplu, ın problema colorarii varfurilor unui graf, fiecarui varf al grafuluiıi va corespunde o variabila ın cadrul retelei asociate. La randul lor, vari-abilele pot pastra o referinta la varful corespunzator prin intermediul acesteiinformatii suplimentare.

public class Var

...

Object data;

...

Prototipul unei metode care sa modeleze problema colorarii varfurilor unuigraf planar cu patru culori sub forma unei retele de constrangeri ar puteaıncepe astfel:

public void color(Graph graph)

...

Problem problem = new Problem(); // reteaua

Domain domain = new Domain(1,2,3,4); // cele 4 culori

for(Node node : graph.nodes())

Var var = new Var();

var.setDomain(domain); // stabilim domeniul

var.setData(node); // referinta la varf

problem.addVariable(var); // adaugam la problema

...

Valoarea unei variabile trebuie ınteleasa ın contextul rezolvarii retelei deconstrangeri din care aceasta face parte, cu alte cuvinte nu va fi o propri-etate a obiectului Var ci va fi extrasa din solutia partiala curenta a solveru-lui. Din acest punct de vedere, o variabila poate fi ıntr-una din starile:


instantiata sau neinstantiata. Asadar, metodele getValue, setValue, re-spectiv isInstantiated sunt strans legate de solver:

public Object getValue()

Solver solver = problem.getSolver();

return solver.solution().get(this);

public void setValue(Object value)

Solver solver = problem.getSolver();

solver.solution().put(this, value);

public boolean isInstantiated()

return (getValue() != null);

In cadrul unei probleme, variabilele acesteia sunt considerate ordonatedupa indexul lor. Indexul unei variabile reprezinta o proprietate surogat,fiind calculat automat la adaugarea ei ın cadrul problemei, valoare sa fiindde fapt pozitia din colectia ın care sunt memorate variabiele retelei. Astfel,ın mod implicit, urmatoarele modalitati de iterare sunt echivalente:

// varianta 1

for(Var var : problem.getVariables())

int i = var.getIndex();

// varianta 2

for(int i=0; i<problem.size(); i++)

Var var = problem.variable(i);

4.2.3 Crearea domeniilor

Un domeniu asociat unei variabile reprezinta o multime de valori din careaceasta poate fi instantiata. Ca si ın cazul variabilelor, pentru a pastra gener-alitatea domeniile vor fi considerate multimi eterogene indexate. Clasa caremodeleaza notiunea de domeniu este Domain. Chiar daca elementele dome-niului nu sunt comparabile, este fortata ordonarea domeniului dupa modal-itatea interna de reprezentare a acestuia astfel ıncat sa aiba sens notiunile


de minim si maxim. Deoarece multe probleme sunt modelate cu variabileıntregi sau logice, exista metode care sa faciliteze crearea domeniilor de acesttip. Mai jos sunt date cateva exemple de domenii simple:

Domain d1 = new Domain(); // domeniul vid

Domain d2 = new Domain("a", "b", "c"); // "a", "b", "c"

Domain d3 = Domain.createIntEnum(0, 9); // 0,1,...,9

Domain d4 = Domain.createBoolean(); // true, false

4.2.4 Specificarea constrangerilor

Crearea constrangerilor unei retele va fi analizata pe larg ıntr-o sectiuneulterioara, deocamdata fiind trecute ın revista clasele si interfetele de bazafolosite ın modelare. Astfel, abstractiunea cea mai importanta este datade clasa Constraint. La modul abstract, constrangerea va fi specificataprin intermediul unei functii de tip oracol capabila sa evalueze o tupla sisa determine daca aceasta este permisa sau nu, eventual sa returneze costulnerespectarii ei. Acest lucru va fi realizat prin extinderea clasei Constraint.

Pe langa implementarile constrangerilor uzuale (operatii aritmetice, log-ice, etc.), a fost oferita si posibilitatea de a defini o constrangere explicitprin relatia asociata, cu alte cuvinte prin enumerarea efectiva a tuplelor per-mise, eventual cu penalizarile corespunzatoare ın cazul retelelor slabe, prinintermediul clasei ExplicitConstraint.

Sa consideram un exemplu simplu pe care sa-l modelam ın cele doua feluri.Reteaua pe care dorim sa o modelam esteR = (X, D,C), unde X = x, y, z,Dx = Dy = Dz = 1, 2, 3 iar constrangerile sunt C = x 6= y, y 6= z, z 6= x.In primul rand, sa cream problema, variabilele si domeniile corespunzatoare:

Problem pb = new Problem();

Domain d = new Domain(1, 2, 3);

Var x = new Var("x", d);

Var y = new Var("y", d);

Var z = new Var("z", d);

pb.setVariables(x, y, z);

Definirea explicita a relatiilor corespunzatoare constrangerilor va fi facutaastfel:

Integer[][] Rxy = 1,2, 1,3;


Integer[][] Ryz = 2,1, 2,3;

Integer[][] Rzx = 3,1, 3,2;

Constraint Cxy = new ExplicitConstraint(new VarSet(x,y), Rxy);

Constraint Cyz = new ExplicitConstraint(new VarSet(y,z), Ryz);

Constraint Czx = new ExplicitConstraint(new VarSet(z,x), Rzx);

pb.setConstraints(Cxy, Cyz, Czx);

Definirea constrangerilor folosind o functie de evaluare poate fi facuta prinextinderea clasei Constraint si implementarea metodei eval care primesteca argument o tupla si trebuie sa evalueze consistenta acestei din perspectivaconstrangerii modelate.

Constraint Cxy = new NotEqual(x,y);

Constraint Cyz = new NotEqual(y,z);

Constraint Czx = new NotEqual(z,x);

this.setConstraints(Cxy, Cyz, Czx);

class NotEqual extends Constraint

private Var x, y;

public NotEqual(Var x, Var y)

super(x, y);

this.x = x;

this.y = y;

public int eval(Tuple tuple)

Object a = tuple.get(x);

Object b = tuple.get(y);

if (a == null || b == null) return ALLOWED;

if (a.equals(b)) return FORBIDDEN;

return ALLOWED;

Presupunand ca exista implementata constrangerea AllDiff care impune cavalorile unui numar oarecare de variabile sa fie diferite, restrictiile problemeide mai sus ar putea fi exprimate extrem de concis astfel:

pb.addConstraint(new AllDiff(x,y,z));

4.3. NIVELUL DE CONTROL 75

Sigur ca existenta unui set predefinit de constrangeri implicite va simpli-fica extrem de mult modelarea problemelor. Astfel, sunt puse la dispozitieclase care modeleaza constrangeri de urmatoarele tipuri:

• aritmetice: x 6= y, x = y + c, x ≤ y, x = |y|, etc

• logice: x = y ∧ z,x = ¬y, etc.

• globale: x ∈ y1, ..., yn,∧

i6=j xi 6= xj, etc.

Mai multe detalii legate de definirea de noi constrangeri vor fi discutateıntr-o alta sectiune dedicata acestora.

4.2.5 Reprezentarea tuplelor

Clasa responsabila cu modelarea notiunii de tupla este Tuple, aceasta reprezentandde fapt insantierea unor variabile ale problemei.

• (x = a): new Tuple(x,a)

• (x1 = a1, ..., xk = ak):new Tuple(new VarSet(x1, ..., xk), new Object[](a1, ..., ak))

Sigur ca exista posibilitatea de a modifica continutul unei tuple prin metodecare sa permita adaugarea unei noi perechi x = a (tuple.put(x,a)) sau caresa elimine un anumit element (tuple.remove(x)). De asemenea, au fostimplementate metode pentru operatiile uzuale cu tuple: proiectie, reuniune,legare (join).

4.3 Nivelul de control

Dupa cum am precizat, nivelul de control este format din toate componentelecare contribuie la rezolvarea problemei. Aici includem:

• Nivelul solverului - responsabil cu parcurgerea sistematica a spatiuluisolutiilor. Acesta poate fi personalizat prin specificarea strategiilor deexplorare.

• Nivelul algoritmic - format din algoritmii de filtrare:


– globali, definiti la nivelul ıntregii probleme, cum ar fi algoritmulgeneral de arc-consistenta

– locali, specifici fiecarei constrangeri ın parte.

Si comportamentul acestui nivel poate fi modificat prin adaugarea denoi algoritmi de filtrare si propagare, independenti sau asociati unorconstrangeri.

In dezvoltarea nivelului de control am tinut cont de posibilitatea extinderiiacestuia dar ıntr-o maniera controlata, aderand la principiul ”Open-Closed”[38], [37] care afirma ca o clasa trebuie sa poata fi extinsa dar fara ca acestlucru sa-i afecteze comportamentul propus.

4.3.1 Conceptul general de solver

Abstractiunea de la care se pleaca ın definirea acestui nivel este interfataSolver care modeleaza notiunea generala de sistem responsabil cu rezolvareaunei retele de constrangeri. Nu exista nici o presupunere asupra modalitatiide cautare a solutiei, aceasta putand fi un algoritm sistematic sau o euristica.

Vom considera ca fiecarui solver ıi poate fi atasat un analizor de problemacapabil sa identifice situatii particulare si sa ofere solutii specifice de rezolvarea acestora. Un astfel de obiect trebuie sa implementeze interfata Analyzer

ce defineste urmatoarele metode:

public interface Analyzer

Problem getProblem();

void setProblem(Problem problem);

boolean isSolved();

boolean isInconsistent();

boolean isSimple();

Solver getSolver();

Asadar, un analizor de problema trebuie sa poata determina daca problemacurenta este ıntr-una din starile: SOLVED, INCOSNSISTENT sau SIMPLE, iarın ultima situatie trebuie sa ofere prin metoda getSolver o solutie mai efe-icienta de rezolvare. In mod firsc, analizorul implicit pus la dispozitie nu


poate identifica starea SIMPLE, aceasta fiind specifica fiecarei probleme ınparte. In privinta celorlalte doua stari, problema este considerata inconsis-tenta daca exista cel putin o variabila al carei domeniu este multimea vida sieste considerata rezolvata atunci cand domeniile tuturor variabilelor au unsingur element. Decuplarea modului de analiza de algoritmul de cautare asolutiei ofera flexibilitate sporita sistemului.

Pe parcursul rezolvarii, trebuie sa avem acces la solutia curenta si laoptimul curent (ın cazul retelelor slabe de constrangeri).

In concluzie, la nivelul cel mai general, un solver trebuie sa ofere metodepentru:

• Stabilirea problemei care trebuie rezolvata

• Setarea unui analizor de problema

• Configurarea parametrilor generali ai procesului de cautare a solutiei(solutiilor), cum ar fi timpul maxim de rulare permis, numarul dorit desolutii, etc.

• Rezolvarea propriu-zisa

Aceste lucruri sunt surprinse ın definitia interfetei Solver:

public interface Solver

Problem getProblem();

void setProblem(Problem problem);

Analyzer getAnalyzer();

void setAnalyzer(Analyzer analyzer);

int eval(Tuple tuple);

Tuple solve();

TupleSet solve(int solutionsLimit);

TupleSet solveAll();

Tuple solution();

TupleSet solutions();

int optimum();

...


4.3.2 Rezolvarea sistematica (completa)

Ne vom focaliza ın continuare asupra tipului de sistem pe care dorim sa-limplementam efectiv si anume de algoritm de rezolvare a retelelor de con-strangeri capabil sa exploreze ın mod sistematic si complet ıntreg spatiulde cautare al solutiilor problemei. Clasa care modeleaza aceasta notiuneeste SystematicSolver si ea ofera toate mecanismele necesare procesuluide explorare a arborelui. Intrucat implementarea ei este strans legata dealgoritmul clasic de backtracking, a fost creata si clasa Backtracking carepoate fi folosita cu aceeasi semnificatie. In principiu, tipul solverului utilizatimplicit la rezolvarea unei retele este ascuns de metoda createSolver dinclasa Problem, responsabila cu crearea unui obiect de tip Solver si legareaacestuia de problema.

// Modelarea problemei

Problem problem = new Problem();

...

// Crearea unui solver

Solver solver = problem.createSolver();

// Rezolvarea problemei

Tuple solution = solver.solve();

Un algoritm sistematic de cautare a solutiilor trebuie sa ofere urmatoareleposibilitati:

• Obtinerea informatiilor asupra situatiei curente a explorarii:

– multimea variabilelor care nu au fost instantiate ınca (candidates);

– variabila curenta careia trebuie sa i se asigneze o valoare (current);

– stiva ce contine variabilele care au fost deja instantiate precum sivariabila curenta (path);

– cel mai recent nod ın care algoritmul a efectuat o ıntoarcere (failed).

• Parametrizarea modului de explorare a spatiului solutiilor prin definireade strategii (euristici) privitoare la:

– Inaintare: defineste ordinea de instantiere a variabilelor;

– Intoarcere: ın cazul esecului, defineste care nod va deveni curent;


– Instantiere: defineste ordinea ın care vor fi asignate valori vari-abilei curente.

• Obtinerea de informatii statistice, cum ar fi:

– numarul de noduri explorate,

– numarul de esecuri,

– lungimea celui mai lung backtrack.

Principiul de functionare al unui solver sistematic este de tip: decizie-propagare-ıntoarcere. La un moment dat, algoritmul trebuie sa ia o de-cizie, cum ar fi instantierea unei variabile, sa propage aceasta decizie re-ducand problema la una echivalenta dar mai usor de rezolvat, dupa caretrebuie sa determine daca problema este rezolvata/inconsistenta si, dupacaz, sa ia o noua decizie sau sa se ıntoarca la o stare anterioara. Schematic,algoritmul general de rezolvare este schitat mai jos:


Algorithm 12 Algoritmul general de rezolvare

Intrare: R = (X, D,C) o retea de constrangeriRezultat: Rezolvarea lui R

Pas0 Filtreaza problema initialaif reteaua este rezolvata then

Proceseaza solutiareturn

end ifif reteaua este inconsistenta then

returnend if

Pas1 Memoreaza starea problemeiPas2 DeciziePas3 Propagareif reteaua este rezolvata then



Restaureaza problema de dinaintea decizieigoto Pas2

end ifgoto Pas1


4.3.3 Exemplu de implementare

Sa consideram un prim exemplu care sa puna ın evidenta lucrurile prezentatepana acum si anume o problema de cripto-aritmetica: SEND + MORE =MONEY . Scopul acestui tip de probleme consta ın atribuirea fiecareia dinliterele S, E, N, D,M,O, R, Y a unei cifre de la 0 la 9 astfel ıncat:

• SEND, MORE si MONEY reprezinta numere si nu trebuie sa ınceapacu 0

• suma numerelor SEND si MORE este MONEY

• S, E, N, D,M,O, R, Y sunt toate diferite

Este usor de observat ca aceasta problema poate fi modelata sub forma uneiretele de constrangeri ın care variabilele sunt cele 8 litere, domeniile acestorafiind formate din cele 10 cifre de la 0 la 9 iar constrangerile sunt cele descriseinformal ın enumerarea de mai sus. Desi formularea problemei este simpla, eanu este neaparat triviala deoarece dimensiunea spatiului ın care sunt cautatesolutiile este de 108 elemente. In mod cert, simpla enumerare a tuturorposibilitatilor si testarea corectitudinii acestora nu este o solutie viabila.

Sa vedem cum poate fi modelata si rezolvata aceasta problema cu ajutorulsolverului.

In primul rand trebuie sa cream problema, cele 8 variabile si domeniilecorespunzatoare fiecareia.

Problem pb = new Problem();

IntVar s = new IntVar("S", 1, 9);

IntVar e = new IntVar("E", 0, 9);

IntVar n = new IntVar("N", 0, 9);

IntVar d = new IntVar("D", 0, 9);

IntVar m = new IntVar("M", 1, 9);

IntVar o = new IntVar("O", 0, 9);

IntVar r = new IntVar("R", 0, 9);

IntVar y = new IntVar("Y", 0, 9);

IntVar[] vars = s,e,n,d,m,o,r,y;

pb.setVariables(vars);


Urmatoarea etapa consta ın definirea constrangerilor. Faptul ca s 6= 0 sim 6= 0 a fost specificat direct ın definitia domeniilor. Constrangerea ca toateliterele trebuie sa aiba valori diferite poate fi descrisa fie prin intermediul luiNotEqual:

for(int i=0; i<8; i++)

for(int j=i+1; j<8; j++)

pb.addConstraint(new NotEqual(vars[i], vars[j]));

fie folosind constrangerea globala AllDiff:

pb.addConstraint(new AllDiff(vars));

Cea de a doua constrangere va impune egalitatea SEND+MORE = MONEY .Explicitata, aceasta poate fi scrisa astfel:

1000 ∗ s + 100 ∗ e + 10 ∗ n + d + 1000 ∗m + 100 ∗ o + 10 ∗ r + e =

10000 ∗m + 1000 ∗ o + 100 ∗ n + 10 ∗ e + y

echivalent cu:

1000 ∗ s + 91 ∗ e− 90 ∗ n + d− 9000 ∗m− 900 ∗ o + 10 ∗ r − y = 0

Ultima constrangere va fi exprimata ca un produs scalar ıntre variabileleproblemei si coefientii calculati mai sus:

int coeffs[] = 1000, 91, -90, 1, -9000, -900, 10, -1;

pb.addConstraint(new ScalarProduct(vars, coeffs, 0));

In final, trebuie sa instantiem solverul si sa apelam metoda care determinatoate solutiile:

SystematicSolver solver = pb.createSolver();

solver.solveAll();

solver.printResult(System.out);

Presupunand ca au fost folosite constrangeri de tip NotEqual, rezultatul vacontine solutiile problemei precum si informatii statistice :


Variables : 8

Constraints : 29

Solutions : 1 (all)

S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2

Time : 60 ms

- Nodes : 4

- Backtracks : 1

Dupa cum vom vedea, unui solver ıi poat fi asociati diversi observatoricare sa monitorizeze activitatea acestuia. Pentru a arunca o prima privireasupra comportamentului acestuia sa-i atasam un observator simplu de tipulSolverObserver. Rezultatul va fi (ıntre paranteze rotunde sunt comentarii):

Solver started.

Problem status:

S: [1, 2, 3, 4, 5, 6, 7, 8, 9]

E: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

N: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

D: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

M: [1, 2, 3, 4, 5, 6, 7, 8, 9]

O: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

R: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Y: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

Filter and propagate removed 48 values.

Problem status:

S: [9]

E: [4, 5, 6]

N: [5, 6, 7]

D: [2, 3, 4, 5, 6, 7, 8]

M: [1]

O: [0]

R: [2, 3, 4, 5, 6, 7, 8]

Y: [2, 3, 4, 5, 6, 7, 8]

Decision: E=4

Solution extended: S=9, E=4, M=1, O=0


Problem status:


S: [9]

E: [4]

N: [5]

D: [8]

M: [1]

O: [0]

R: []

Y: [2]

Nogood : S=9, E=4, M=1, O=0

Solution restored: S=9, M=1, O=0

Decision: E=5



Problem status:

S: [9]

E: [5]

N: [6]

D: [7]

M: [1]

O: [0]

R: [8]

Y: [2]

Solution found: S=9, E=5, N=6, D=7, M=1, O=0, R=8, Y=2


Decision: E=6



Problem status:

S: [9]

E: [6]

N: [7]

D: [8]

M: [1]

O: [0]

R: []

Y: [4]


Nogood : S=9, E=6, M=1, O=0


Solver finished.

4.3.4 Definirea strategiilor de explorare

Algoritmul sistematic de cautare a solutiilor trebuie sa ia o serie de deciziiın vederea parcurgerii spatiului solutiilor. Astfel, la un moment dat trebuiesa aleaga din multimea variabilelor care nu au fost instantiate un candidatcaruia sa-i asigneze o valoare. Dupa selectarea variabilei, instantierea aces-teiea presupune atribuirea unei valori din domeniul sau. In final, atunci candse afla ın situatia de esec trebuie sa decida care este variabila de la care varelua cautarea solutiei.

Strategia de ınaintare este responsabila cu identificarea variabilei can-didat care urmeaza sa fie instantiata, definind de fapt o relatie de ordine to-tala asupra variabilelor retelei. Aceasta ordine nu este ınsa statica (stabilitaınainte de pornirea solverului) ci poate fi determinata dinamic, la executie,ın functie de starea curenta a sistemului. Interfata care descrie o strategie deınaintare este ForwardStrategy:

public interface ForwardStrategy

Var next();

Evident, la modul general, nu exista o strategie care sa fie mai buna decatalta, din acest motiv este important ca fiecare problema sa-si defineascapropria ordonare a variabilelor. Exista ınsa o serie de euristici care suntfiresti sau pentru care s-a observat, experimental, ca functioneaza bine pemulte categorii de probleme. Acestea sunt:

• SimpleForward - selecteaza variabilele ın ordinea ın care au fost definiteın cadrul problemei; aceasta este strategia implicita.

public class SimpleForward

extends AbstractStrategy

implements ForwardStrategy


public Var next()

List<Var> candidates = solver.candidates();

if (candidates.isEmpty())

return null;

Var var = candidates.get(0);

return var;

• MinDomainForward - alege variabila cu dimensiunea domeniului catmai mica, reducand astfel latimea arborelui de cautare; corespundeprincipiului first-fail.

• MostConstrainedForward - alege variabila implicata ın cele mai multeconstrangeri.

Strategia de instantiere este responsabila cu definirea unei relatii deordine asupra valorilor din domeniul unei variabile. Ca si ın cazul strate-giei de ınaintare, relatia nu este statica ea putand fi reordonata dinamicpe parcursul executiei. Interfata care descrie o strategie de instantiere esteAssignmentStrategy:

public interface AssignmentStrategy

Object assign(Var var);

Ca implementari au fost definite:

• SimpleAssignment - selecteaza valorile conform cu ordinea naturala adomeniului, aceasta fiind si strategia implicita.

public class SimpleAssignment extends AbstractStrategy

implements AssignmentStrategy

public Object assign(Var var)

Domain domain = var.getDomain();

Tuple solution = solver.solution();


while (!domain.isEmpty())

Object a = domain.first();

domain.remove(a);

solution.put(var, a);

if (solution.isConsistent(var))

return a;

solution.remove(var);

return null;

• MaxReductionAssignment - executa o operatie de forward-checking,calculand pentru ficare atribuire numarul de eliminari provocat prinpropagarea ei de catre algoritmii de filtrare, dupa care alege valoareacare a determinat cea mai semnificativa reducere.

Strategia de ıntoarcere defineste modul ın care va fi selectata variabilade unde va fi reluat procesul de cautare a solutiei ın caz de esec. Interfatacare descrie o strategie de ıntoarcere este BackwardStrategy:

public interface BackwardStrategy

Var back();

Implicit, algoritmul clasic de backtracking efectueaza ıntoarcerea cronologicacatre ultima variabila instantiata ınainte de obtinerea inconsistentei, acestafiind de fapt si comportamentul implicit al solverului, implementat de clasaSimpleBackward. Aceasta utilizeaza stiva ın care sunt memorate variabileleprocesate de solver, extragand de acolo pe ultima careia i-a fost atribuita ovaloare:

public class SimpleBackward extends AbstractStrategy

implements BackwardStrategy

public Var back()

Stack<Var> path = solver.path();

if (path.isEmpty()) return null;


Var current = path.pop();

Var var = null;

if (!path.isEmpty())

var = path.peek();

return var;

Insa acest tip de ıntoarcere cronologica poate provoca fenomenul de ”thrash-ing”, cu alte cuvinte apare posibilitatea de a gresi din acelasi motiv de maimulte ori. Din acest motiv pot fi implementati algoritmi de ıntoarcere maicomplecsi, cum ar fi cel de tip backjumping, care sa determine variabila re-sponsabila efectiv cu aparitia situatiei curente de esec si sa reia procesul deexplorare direct de acolo.

O alta tehnica de optimizare a algoritmilor sistematici de cautare estecea de creare a unei structuri de date de tip cache ın care sa fie memorateinformatii legate de incompatibilitatea unor anumite atribuiri de valori vari-abilelor retelei, astfel ıncat algoritmul sa evite munca redundanta, cu altecuvinte sa evite crearea unor instante inconsistente dintr-un motiv care afost identificat la un pas anterior. Aceasta tehnica se numeste backmarking sipoate fi de asemenea implementata prin redefinirea strategiilor de ıntoarceredar si de instantiere ın acelasi timp, ıntrucat folosesc date comune.

public class BackMarking extends AbstractStrategy

implements AssignmentStrategy, BackwardStrategy

public Var back() ...

public Object assign(Var var) ...

4.4 Monitorizarea procesului de rezolvare

Monitorizarea procesului de rezolvare a unei probleme a fost realizata prinimplementarea sablonului de proiectare Observer [22], [51]. Acesta definesteo relatie de tip one-to-many ıntre un subiect, ın cazul nostru solverul, siun numar oarecare de observatori astfel ıncat atunci cand starea subiectului

4.4. MONITORIZAREA PROCESULUI DE REZOLVARE 89

se modifica toti observatoii sunt notificati asupra schimbarii astfel ıncat sapoata reactiona corespunzator. In acest fel, pot fi create obiecte de tip solver,respectiv observator, independent unul de celalalt, aceasta decuplare sporindcu mult flexibilitatea ıntregului sistem.

Implementarea a fost realizata pe baza de evenimente corespunzatoaremomentelor definitorii ale solverului, cu posibilitatea de a adauga noi tipuride evenimente fara a afecta corectitudinea obiectelor observator create deja.Exista doua posibilitati de comunicare ıntre subiect si observatori:

• Push model : subiectul transmite informatii detaliate legate de schim-bare

• Poll model : subiectul transmite informatii minimale legate de schim-bare, urmand ca observatorul sa execute interogari suplimentare pentrua afla toate datele necesare.

Deoarece este de dorit impunerea unei ıncarcari minime asupra sistemului ınsituatia cand acesta este monitorizat, vom alege cel de-al doilea model. Inaceste conditii evenimente pot fi grupate astfel:

• SolverEvent - eveniment general ce notifica faptul ca solverul si-a schi-mat starea, fara a contine informatii suplimentare legate de schimbare.

• FilterEvent - eveniment derivat din SolverEvent ce va fi creat pentrua semnala faptul ca un algoritm de filtrare a redus problema initiala saua detectat o inconsistenta; acesta va contine ca informatie suplimentarao referinta la obiectul de tip Filter responsabil cu aceasta schimbare.

• EliminationEvent - eveniment derivat din FilterEvent va fi creatpentru a semnala eliminarea unei valori din domeniul unei variabileın timpul executiei unui algoritm de filtrare si propagare; acesta vacontine ca informatie suplimentara variabila, valoarea eliminata si de-clansatorul acesteia (daca este cazul).

Fiecarui tip de eveniment ıi poate fi asociat un tip de observator prinintermediul unei interfete dedicate ınsa, pentru simplitate, a fost definita osingura interfata si anume SolverListener care sa modeleze notiunea ınsens general. Pentru a pastra similaritatea cu platforma Java pe care acestsolver este construit, a fost preferat termenul de listener celui de observer.Metodele interfetei sunt intuitive asa ıncat nu le vom mai detalia.


public interface SolverListener

/**

* Called when the solver starts to solve the problem.

*/

void solverStarted(SolverEvent event);

/**

* Called when the solver is finished.

*/

void solverFinished(SolverEvent event);

/**

* Called when the solver extends the solution.

*/

void solutionExtended(SolverEvent event);

/**

* Called when the solver restores the solution.

*/

void solutionRestored(SolverEvent event);

/**

* Called when the solver finds a solution.

*/

void solutionFound(SolverEvent event);

/**

* Called after the problem has been filtered.

*/

void problemFiltered(FilterEvent event);

/**

* Called when a value is removed by a filter.

*/

void valueRemoved(EliminationEvent event);

/**

* Called when a nogood is found.

*/

void nogoodFound(FilterEvent event);

4.4. MONITORIZAREA PROCESULUI DE REZOLVARE 91

La nivel de implementare a solverului, trebuie creat mecanismul de ınregistrarea observatorilor precum si de notificare a acestora. Astfel, ınregistrareaobservatorilor va fi facuta ıntr-o lista simplu ınlantuita cu metode de tipaddListener, respectiv removeListener iar notificarea acestora va fi real-izata printr-un obiect de tip EventHandler care va contine metode speci-fice apelate de solver la momentele definitorii, fiind responsabil cu creareaevenimentelor si transmiterea acestora catre observatori. De exemplu, laidentificarea unei solutii actiunea executata de solver va fi:

if (firingEvents)

eventHandler.fireSolutionFound();

iar ın clasa EventHandler va exista metoda fireSolutionFound:

public void fireSolutionFound()

SolverEvent event = new SolverEvent(solver);

for(SolverListener listener : solver.getListeners())

listener.solutionFound(event);

Pentru a defini un observator, tot ceea ce trebuie sa facem este sa oferim oimplementare interfetei SolverListener sau, mai simplu, sa extindem adap-torul SolverAdapter si sa supradefinim metodele la care dorim sa interactionam.

Sa consideram ca exemplu un observator responsabil cu afisarea pe ecrana solutiilor chiar ın timpul executiei algoritmului, pe masura ce acestea suntgasite.

public class SolutionObserver extends SolverAdapter

public void solutionFound(SolverEvent event)

Tuple solution = event.getSolver().solution();

System.out.println("Solution found: " + solution);

Tot ceea ce mai trebuie sa facem este sa ınregistram observatorul, ca ınexemplul de mai jos.


Problem problem = new QueenProblem(8);

SystematicSolver solver = problem.createSolver();

solver.addListener(new SolutionObserver());

solver.solveAll();

4.5 Crearea constrangerilor

Constrangerile reprezinta un aspect fundamental al oricarui solver, imple-mentarea acestora fiind critica pentru performantele sistemului. Pe langaacest fapt, este necesar ca procesul crearii de noi constrangeri sa fie cat maisimplu, fara a presupune cunostinte despre functionarea interna a algorit-mului de rezolvare. Dupa cum am precizat deja ıntr-o sectiune anterioara,abstractiunea de baza este reprezentata de clasa Constraint care defineste:

• Modul de evaluare a unei tuple

• Care sunt tuplele admisibile

• Filtrul asociat constrangerii.

4.5.1 Constrangeri explicite

Constrangerile explicite sunt reprezentate de clasa ExplicitConstraint cedefineste o constrangere specificand efectiv relatia asociata, cu alte cuvinteprin enumerarea tuplelor permise, eventual cu penalizarile corespunzatoareın cazul retelelor slabe.

In modelul clasic aceasta va contine o structura de tip TupleSet, reprezentandtuplele permise:

public class ExplicitConstraint extends Constraint

private TupleSet tuples;

public boolean contains(Tuple tuple)

return tuples.contains(tuple);


return (contains(tuple) ? ALLOWED : FORBIDDEN);

...

4.5. CREAREA CONSTRANGERILOR 93

In modelul aditiv, este necesara o structura de tip HashMap care sa specificeatat tuplele admisibile cat si penalizarile asociate acestora. O tupla esteadmisibila daca evaluarea acesteia este mai mica decat maximul structuriide evaluare.

public class ExplicitConstraint extends Constraint

private Map<Tuple, Integer> valuationMap;

public boolean contains(Tuple tuple)

return (eval(tuple) < FORBIDDEN);


return valuationMap.get(tuple);

...

Constrangerile implicite - pot fi specificate prin intermediul unei functiide tip oracol capabila sa evalueze o tupla si sa determine daca aceasta estepermisa sau nu, eventual sa returneze costul nerespectarii ei. Dupa cum esteusor de observat, constrangerile explicite pot fi privite ca un caz particular alacestora, ınsa implementarile lor au fost create independent. Atat ın modelulclasic, cat si ın cel aditiv, constrangerile implicite sunt reprezentate de clasaabstracta Constraint, metoda care necesita a fi implementata fiind eval.Aceasta va returna:

• ValuationStructure.MIN, ValuationStructure.ALLOWED sau 0 dacatupla este permisa (nu are nici o penalizare)

• ValuationStructure.MAX sau ValuationStructure.FORBIDDEN dacatupla nu este admisibila

• un ıntreg ın intervalul deschis (MIN, MAX) pentru a specifica faptulca tupla este admisibila dar atrage dupa sine o anumita penalizare.


4.5.2 Constrangeri binare

Pentru comoditate si, tinand cont ca ın modelarea multor probleme inter-vin un numar mare de constrangeri binare, a fost creata o clasa specialapentru acestea si anume BinaryConstraint. Extinderea acesteia presupunesupradefinierea metodei eval care, spre deosebire de cazul general ın care ar-gumentul este o tupla, primeste ca parametri cele doua valori ale variabilelorconstrangerii. Astfel, implementarea unei constrangeri simple de tipul x 6= yva fi realizata astfel:

public class NotEqual extends BinaryConstraint

public NotEqual(Var x, Var y)

super(x, y);

setName(x + " != " + y);

public int eval(Object a, Object b)

return (a.equals(b) ? FORBIDDEN : ALLOWED);

Pentru constrangerile binare nu este necesara atasarea vreunui algoritm defiltrare si propagare, acest lucru fiind responsabilitatea algoritmului generalde arc-consistenta.

4.5.3 Constrangeri oarecare

Crearea unor constrangeri oarecare este putin mai complexa, ıntrucat numarulvariabilelor nu este neaparat acelasi (de exemplu ın cazul lui alldiff) iar,ın evaluarea tuplei primite ca argument trebuie sa se tina cont si de faptul caunele variabile pot sa nu fie instantiate. De asemenea, trebuie avut ın vederefaptul ca unei constrangeri ıi poate fi asociat un algoritm propriu de filtrarecare sa rezolve situatii de inconsistenta nedetectate de algoritmii generali.

Sa consideram un prim exemplu ın care dorim sa implementam o con-strangere de tipul:

∑i=1,k xi = c, unde c este o constanta ıntreaga. O abor-

dare simplista ar fi cea ın care verificam pur si simplu daca toate variableledin tupla primita ca argument sunt instantiate iar suma lor este cea dorita:


public class ConstantSum extends Constraint

private int sum;

public ConstantSum(Var[] variables, int sum)

super(variables);

this.sum = sum;


int total = 0;

boolean complete = true;

for(Var var : variables)

Object val = tuple.get(var);

if (val == null)

complete = false;

else

total += (Integer)val;

if (complete)

return (total == sum ? ALLOWED : FORBIDDEN);

return ALLOWED;

Fie reteau R = (X, D,C), unde X = x, y, z, Dx = Dy = Dz = 1, 2, 3iar C contine o singura constrangere: x + y + z = 9. Rezolvand aceastaproblema cu ajutorul implementarii de mai sus, vom observa ca algoritmulde arc-consistenta nu poate face nici o filtrare, ceea ce ınseamna ca ıntregspatiul solutiilor va fi explorat iar solverul va lua un numar inacceptabil (10)de decizii gresite ın urma carora trebuie sa faca pasul ınapoi.

Se observa ınsa ca o decizie x = a nu este valida ın situatiile: a +min(Dy) + min(Dz) > 9 sau a + max(Dy) + max(Dz) < 9. Generalizandaceasta idee, o implementare mai eficienta a metodei de evaluare pentru con-strangerea ConstantSum ar fi:


int total = 0, min = 0, max=0;


boolean complete = true;

for(Var var : variables)

Object val = tuple.get(var);

if (val == null)

complete = false;

Domain domain = (Domain) var.getDomain();

min += (Integer)domain.minimum();

max += (Integer)domain.maximum();

else

total += (Integer)val;

if (complete)

return (total == sum? ALLOWED : FORBIDDEN);

if (total + min > sum) return FORBIDDEN;

if (total + max < sum) return FORBIDDEN;

return ALLOWED;

Rezolvand din nou problema vom constata ca solverul va efectua 6 eliminaride valori, gasind solutia corecta fara a lua nici o decizie si evident, fara aefectua nici o ıntoarcere:

Solver started.

Elimination: x != 1

Elimination: x != 2

Elimination: y != 1

Elimination: y != 2

Elimination: z != 1

Elimination: z != 2

Solution found: x=3, y=3, z=3

Solver finished.

Asadar, implementarea corecta a constrangerilor are un impact foarte mareasupra comportamentului solverului, permitand algoritmilor de filtrare gen-erali asociati sa reduca ın mod eficient problema chiar de la ınceput ca ıncazul exemplului anterior sau dupa efectuarea unei decizii.


4.5.4 Constrangeri globale

Fie C = C1, ..., Ck o multime de constrangeri. Numim constrangere globalaconstrangerea CG definita sub forma unei conjunctii ıntre constrangerilemultimii C:

CG = C1 ∧ C2 ∧ ... ∧ Ck

Din punctul de vedere al implementarii lor, constrangerile globale diferadoar ın mod teoretic fata de cazul general, ın sensul ca sunt constrangeri cuun numar oarecare de parametri carora trebuie sa le implementam metodade evaluare a tuplelor. Diferenta notabila fata de cele obisnuite este ca,pe langa evaluarea unei tuple, constrangerile globale pot avea algoritmi defiltrare proprii, pertinenti care sa ımbunatateasca comportamentul generalal solverului detectand situatii de inconsistenta sau efectuand operatii defiltrare la nivelul ıntregii probleme.

Sa consideram ca exemplu constrangerea alldiff(x1, ..., xk) =∧

i6=j xi 6= xj

si sa vedem care ar fi avantajul utilizarii acestei constrangeri globale fata defolosirea individuala a celorlalte k constrangeri binare din care este formata.Fie R = (X, D,C), unde X = x, y, z o retea pe care este definita con-strangerea alldiff(x, y, z).

• Cazul 1 : Dx = 1, 2, Dy = 1, 2, Dz = 1, 2Luate ın particular constrangerile x 6= y, y 6= z, z 6= x nu pot de-termina algorimtul general de arc-consistenta sa elimine vreo valoaresau sa detecteze inconsistenta. Cu toate acestea, reteaua este evident,inconsistenta.

• Cazul 2 : Dx = 1, 2, 3, 4, Dy = 1, 2, Dz = 1, 2Valorile 1, 2 trebuie eliminate din Dx dar, doua cate doua, variabileleretelei sunt arc-consistente una relativ la cealalta, ceea ce ınseamna canici o filtrare nu va fi efectuata de algoritmul general.

Implementarea eficienta a unei constrangeri globale trebuie asadar sa ofereun algoritm propriu de filtrare care sa permita detectarea situatiilor deinconsistenta ce nu pot fi determinate de algoritmul general, oferind astfelputere de filtrare sporita ıntregului sistem.

Clasa AllDiff este definita cu o implementare normala a metodei de eval-uare, ın care sunt comparate doua cate doua valorile variabilelor instantiateale tuplei primite ca argument. Pe langa acesta este specificat ınsa un algo-rimt dedicat de filtrare AllDiffFilter.


public class AllDiff extends Constraint

public AllDiff(Var ... variables)

super(variables);

setFilter(new AllDiffFilter());


// Compara doua cate doua valorile

...

Clasa AllDiffFilter trebuie sa implementeze interfata Filter (sau sa ex-tinda AbstractFilter), oferind algoritmul propriu-zis. Mai jos este datao varianta simpla capabila sa rezolve situatii de inconsistenta folosind gra-ful valorilor. Reamintim ca graful valorilor GV = (X, Y, E) asociat uneiconstrangeri C este definit astfel:

• X = X(C) - variabilele care participla ın constrangerea C

• Y = D(X(C)) - valorile care pot fi atribuite variabilelor din X(C)

• (x, a) ∈ E ⇔ a ∈ D(x)

Consistenta lui alldiff este obtinuta daca si numai daca ın acest graf existaun cuplaj de cardinal maxim care acopera multimea X, satisfacand astfeltoate variabilele.

private class AllDiffFilter extends AbstractFilter

...

public boolean filter()

Graph graph = new Graph();

// Cream graful valorilor

...

BipartiteMaximumMatching alg =

new BipartiteMaximumMatching(graph);

Map<Node, Node> matching = alg.maximumMatching();

int n = variables.length;

boolean consistent = (matching.size() == n);

return consistent;

4.6. RETELE SLABE DE CONSTRANGERI 99

4.6 Retele slabe de constrangeri

Majoritatea sistemele existente de satisfacere a constrangerilor ofera posibil-itatea de a rezolva si probleme de optimizare. Acestea sunt definite ın moduzual sub forma unei retele clasice de constrangeri pentru care este specifi-cata si o anumita functie ce trebuie optimizata (minimizata sau maximizata)eventual sub forma unei meta-variabile. Procesul de rezolvare ın acest cazpresupune, pe langa identificarea unei solutii admisibile (care sa satisfacatoate constrangerile) si demonstrarea optimalitatii acesteia. Spre exemplu,choco [31] defineste metodele minimize si maximize asociate unei problemece au ca argument variabila obiectiv.

Un dezavantaj al acestei abordari ıl reprezinta faptul ca permite doar oabordare uni-criteriala a cazului general si nu poate fi usor folosita ın situatiacand suntem interesati de optimizare multi-criteriala ın care este cautata osolutie ”satisfacatoare” din mai multe puncte de vedere.

Ceea ce ne propunem este sa implementam exact modelul retelelor slabede constrangeri, ın care fiecarei constrangeri ıi este asociata o valoare cesemnifica nivelul sau de preferinta, cu alte cuvinte cat de importanta esterespectarea ei. Dupa cum am vazut ın capitolul dedicat modelelor CSP, uneiretele slabe de constrangeri ıi poate fi asociata o structura de evaluare cedefineste multimea elementelor care vor fi folosite pentru evaluari precum sioperatorul folosit pentru a specifica modul de combinare a acestora. Deoarecene-am propus sa putem folosi ın mod unitar atat modelul clasic cat si celaditiv, sa vedem cum putem realiza acest lucru.

4.6.1 Structuri de evaluare

Dupa cum am precizat, fiecarei probleme trebuie sa ıi asociem o structurade evaluare. Aceasta este descrisa de interfata ValuationStructure ce areurmatoarea definitie:

public interface ValuationStructure

// Extremitatile domeniului

int MIN=0;

int MAX=Integer.MAX_VALUE;

int ALLOWED=MIN;

int FORBIDDEN=MAX;


//Operatorul de combinare a preferintelor

int plus(int a, int b);

// Operatorul ce defineste ordinea totala

int compareTo(int a, int b);

Modelul clasic specifica un domeniu format doar din doua valori reprezentandsatisfacerea/nesatisfacerea, acestea fiind de fapt elementul neutru (ALLOWED =0) respectiv de scufundare // (FORBIDDEN =∞) al structurii de evalu-are.

public class ClassicalValuation implements ValuationStructure

// SI logic

public int plus(int a, int b)

return (a == FORBIDDEN ||

b == FORBIDDEN ? FORBIDDEN : ALLOWED);

// relatia de ordine: ALLOWED < FORBIDDEN

public int compareTo(int a, int b)

return a - b;

Modelul aditiv are ca domeniu multimea numerelor naturale, ALLOWED =0 semnificand satisfacerea deplina a unei constrangeri, FORBIDDEN =∞inadmisibilitatea iar valorile intermediare fiind nivele de preferinta.

public class AdditiveValuation implements ValuationStructure

// adunarea intregilor

public int plus(int a, int b)

return a + b;

// ordinea numerelor naturale

public int compareTo(int a, int b)

return a - b;


Folosind aceasta abordare, putem concepe o metoda de evaluare a uneituple care sa fie independenta de modelul CSP pe care se lucreaza, gener-alizand astfel mecanismul de rezolvare:


int cost = 0;

VarSet vars = tuple.variables();

ConstraintSet cs = problem.getConstraints(vars);

ValuationStructure valuation = problem.getValuationStructure();

for(Constraint c : cs)

int eval = c.eval(tuple);

if (eval == ValuationStructure.FORBIDDEN)

return eval;

cost = valuation.plus(cost, c.eval(tuple));

return cost;

4.6.2 Modelarea unei probleme de optimizare

Sa consideram un exemplu clasic de optimizare si anume ”problema rucsac-ului”: date un numar n de articole, fiecare avand o greutate si un profit, siun rucsac de capacitate c trebuie sa selectam un numar de articole care saıncapa ın rucsac si care sa maximizeze profitul. Pentru fiecare articol i = 1, nsa notam wi greutatea, pi profitul adus de acesta si xi variabila asociata, carepoate avea valorile 0 sau 1. Constrangerea care trebuie respectata este:∑

i=1,n

wixi ≤ c

Functia care trebuie maximizata este:

f(x1, ..., xn) =∑i=1,n

pixi

Pentru modelarea acestei problem vom calcula o limita maxima M =∑

i=1,n pi

a functiei obiectiv si vom introduce o constrangere slaba de tipul f(x1, ..., xn) =


M . Nivelul de preferinta al unei tuple a = (x1 = a1, ..., xk = ak) va fi|M − f(a)|, acesta avand semnificatia ca dorim sa ne ındepartam cat maiputin de la maximul posibil M care poate fi obtinut doar ın conditia ın caretoate articolele ıncap ın rucsac.

public class KnapsackProblem extends Problem

public KnapsackProblem()

setValuationStructure(new AdditiveValuation());

int n = 6;

int w[] = 100, 50, 45, 20, 10, 5;

int p[] = 40, 35, 18, 4, 10, 2;

int c = 100;

int m = 0;

for(int i=0; i<n; i++)

m += p[i];

Domain domain = Domain.createIntEnum(0,1);

Var[] x = createVariables(n, domain);

addConstraint(new ScalarProductLeq (x, w, c));

addConstraint(new SoftScalarProduct(x, p, m));

Rezolvand problema vom obtine solutia: x[0] = 0, x[1] = 1, x[2] = 1, x[3] =0, x[4] = 0, x[5] = 1, optimul fiind 35 + 18 + 2 = 55.

4.6.3 Optimizare multi-criteriala

In situatia ın care o problema clasica de satisfacere a constrangerilor nu aresolutie putem spune ca este supra-constransa. Spre deosebire de exemplulanterior ın care am modelat o problema clasica de optimizare ce definea ofunctie obiectiv, suntm acum ın situatia sa relaxam o serie de constrangeri,eventual toate, ceea ce ne conduce la o situatie de optimizare multi-criteriala.

Sa consideram un exemplu de echilibrare a raportului calitate/pret. Suntdate n materiale pe care dorim sa le achizitionam pentru executia unei lucrari.


Fiecare material poate fi procurat de la mai multe firme producatoare, fiecareiadintre acestea corespunzandu-i o anumita calitate si un anumit pret. Scopuleste sa achizitionam aceste materiale astfel ıncat:

• sa minimizam pretul si

• sa maximizam calitatea

Evident, ın acest caz optimizarile nu pot fi facute la modul absolut ci trebuiesa specificam ın ce masura punem accentul pe pret si ın ce masura pe calitate.Pentru fiecare material i = 1, n si fiecare firma producatoare j = 1, m sanotam qij calitatea oferita de respectiva firma si pij pretul iar xij variabilaasociata perechii (material, firma), care poate avea valorile 0 sau 1. Sapresupunem ca preturile sunt luate dintr-un domeniu [0, δ] iar calitatea vafi specificata procentual, valoarea de 100 reprezentand o calitate excelenta.Constrangerile slabe ale retelei vor fi:∑

i=1,n;j=1,m

pijxij = 0

si ∑i=1,n;j=1,m

cijxij = 100

Pe langa acestea va trebui sa specificam faptul ca vom cumpara un materialde la o singura firma:

∀i = 1, n∑

j=1,m

xij = 1

In cazul ın care dorim sa echilibram ponderea pe care au calitatea sipretul ın evaluarea finala ar trebui ca domeniile din care sunt alesi scalariipij si cij sa fie aceleasi: [0, 100]. Pentru aceasta poate fi determinat pretulcel mai mic al fiecarui material si exprimarea pretului sa o facem procentualın functie de acest minim: p′ij = ((mink=1,mpik) ∗ 100)/pij. Bineınteles, dacadorim sa punem accentul pe calitate sau pe pret, putem amplifica valorilepij, respectiv cij corespunzator.

Modelarea problemei va fi:

addConstraint(new SoftScalarProduct(x, q, 100));

addConstraint(new SoftScalarProduct(x, p, 0));


Optimizarea multi-criteriala ar putea fi rezolvata si printr-o modelarecorespunzatoare cu ajutorul unei singure functii obiectiv, ınsa ın cazul prob-lemelor complexe, cu multe tipuri de constrangeri slabe, aceasta abordare arfi ineficienta atat din punctul de vedere al formalizarii cat si al rezolvarii.

Capitolul 5

Explicatii

5.1 Introducere

Sistemele actuale de rezolvare automata a problemelor modelate cu ajutorulconstrangerilor sunt capabile ca, plecand de la o retea specificata de con-strangeri, sa ofere una sau toate solutiile problemei ın cazul ın care aceastaeste consistenta sau sa detecteze faptul ca nu exista nici o solutie, caz ın carecele mai multe dintre ele nu vor face altceva decat sa afiseze un mesaj infor-mativ de tipul ”Problema nu are solutie ...”. In situatia din urma ramanela latitudinea utilizatorului sa-si dea seama care este motivul pentru caresistemul nu a gasit nici o solutie: a fost o eroare de functionare, modelareaproblemei a fost gresita sau ıntr-adevar problema este inconsistenta ? Ex-ista asadar o serie de informatii suplimentare care ar trebui oferite de catresolverele CSP, cum ar fi:

• De ce problema nu are nici solutie ?

• De ce o variabila x nu poate lua valoarea a ?

Cu alte cuvinte, este necesar un mecanism care sa explice procesul de deter-minare a solutiei sau de stabilire a inconsistentei.

Unele solvere, cum ar fi choco [31] cu extensia PaLM (Propagation andLearning with Move) [6], ofera instrumente pentru generarea de explicatiiınsa acestea se refera ın special la informatii care sa explice starea curentaa sistemului. Ceea ce ne propunem ın continuare este sa cream o modali-tate simpla de generare a unei structuri de date din care sa putem extrage unrationament complet si clar care sa demonstreze inconsistenta unei probleme.

105

106 CAPITOLUL 5. EXPLICATII

Procesul de generare se va desfasura pe masura executiei aloritmului de re-zolvare, acesta fiind de fapt un observator asociat solverului si prin urmarepoate fi utilizat si ca modalitate de inspectare a starii curente a problemei.

5.2 Ce ınseamna o explicatie ?

Fie R = (X,D,C) o retea de constrangeri. O situatie de esec a unui algoritmsistematic de cautare este identificata de un nod al arborelui de cautare deunde explorarea nu mai poate continua si poate fi descrisa prin instantiereapartiala curenta: a = (x1 = a1, ..., xk = ak). O astfel de tupla va fi numitagresita (nogood) [42] si vom scrie:

C ` ¬(x1 = a1, ..., xk = ak)

Evident, nici o solutie nu poate include o tupla gresita. Expresia de mai suspoate fi scrisa folosind operatori logici si astfel:

¬(x1 = a1 ∧ ... ∧ xk = ak)

De asemenea, pentru oricare din variabilele xj, j ∈ [1..k] putem scrie:∧i∈[1..k]\j

(xi = ai)⇒ xj 6= aj

In acest context, problema pe care o vom aborda va fi determinarea mo-tivului pentru care o tupla este gresita. Vom numi explicatia esecului uneituple a si vom nota expl(¬a) un rationament deductiv ale carui premize suntreteaua data si tupla a = (x1 = a1, ..., xk = ak) iar concluzia trebuie sa fieca reteaua R′ obtinuta din R dupa reducerea domeniilor D1 = a1, ..., Dk =ak este inconsistenta. In cazul ın care tupla este de forma x = a vom notaexpl(¬(a)) = expl(x 6= a).

Determinarea unei modalitati de a construi explicatia unui esec ne vaoferi raspunsuri la ambele ıntrebari puse la ınceput:

• expl(x 6= a): de ce o variabila nu poate lua o anumita valoare,

•⋃

a∈Dxexpl(x 6= a): de ce problema nu are nici o solutie.

5.2. CE INSEAMNA O EXPLICATIE ? 107

Unitatea atomica a unui rationament (ın sensul ca nu mai necesita explicatiisuplimentare) va fi ın general constrangerea responabila cu violarea unei tu-ple. De exemplu, fie reteaua R = (X,D, C), X = x, y,Dx = Dy = 0, 1 siavand definita o singura constrangere x 6= y.Atunci expl(¬(x = 0, y = 0)) = x 6= y si acest lucru nu mai necesitaexplicatii suplimentare.

Trebuie sa avem ın vedere si situatia ın care algoritmii asociati uneiconstrangeri, de filtrare sau chiar de evaluare a unei tuple, se bazeaza perationamente nebanale. Fie reteau R = (X, D,C), unde X = x, y, z,Dx = Dy = Dz = 1, 2, 3 iar C contine o singura constrangere: x+y+z = 9.O explicatie de tipul expl(¬(x = 1)) = x + y + z = 9 nu satisface criteriulde claritate pe care dorim sa-l oferim, ıntrucat motivul pentru care respectivaconstrangere nu poate fi satisfacuta ascunde o serie de rationamente efectu-ate de algoritmii specifici ai constrangerii. Rezultatul pe care am dori sa-lvedem este:

x = 1 ∧max(Dy) = 3 ∧max(Dz) = 3⇒ x + y + z ≤ 7

Acesta este ınsa un rationament specific constrangerii impuse, deci trebuiesa avem ın vedere integrarea explicatiilor oferite de algoritmul sistematicde rezolvare a problemei, de algoritmii generali de filtrare precum si de ceispecifici constrangerilor.

In continuare, vom presupune data tupla care trebuie explicata si vomnota R = (X, D,C) reteaua de constrangeri obtinuta din cea initiala dupareducerea domeniilor. In acest fel, problema generala devine demonstrareainconsistentei retelei R.

5.2.1 Cum poate fi explicata inconsistenta ?

Obtinerea unei solutii a retelei R prin intermediul unui algoritm sistematicpoate fi vazuta ca o succesiune finita de transformari R = R0 → R1 → ...→Rf , unde Ri si Rj sunt echivalente iar Ri+1 ≺ Ri (ın sensul ca spatiul decautare al lui Ri+1 este mai mic decat al lui Ri) iar Rf are toate domeniileformate dintr-un singur element. Etapa de transformare Ri → Ri+1 esterealizata prin:

1. Luarea unei decizii de instantiere a unei variabile: x = a, actiune ceare ca efect reducerea domeniului lui x la Dx = a.


2. Propagarea deciziei luate la pasul 1, folosind algoritmi de filtrare caresa reduca ın continuare domeniile variabilelor problemei.

Ridecizie−−−−−−−−−−−→

propagare/filtrareRi+1

Dupa cum am vazut, algoritmii de filtrare pot fi globali (cum ar fi algorit-mul general de arc-consistenta) sau locali (cum ar fi cei asociati unor con-strangeri). Indiferent de tipul acestora, ın construirea unei explicatii trebuiesa retinem motivul pentru care o anumita tupla este gresita, respectiv de ceo anumita valoare este eliminata din domeniul unei variabile.

Fie a = (x1 = a1, ..., xk = ak) o instantiere partiala. Demonstrareafaptului ca aceasta este gresita poate fi obtinuta ın urmatoarele modalitati:

(E1) Exista o constrangere c care nu este satisfacuta de a.

(E2) Exista o variabila x pentru care: ∀a ∈ Dx a′ = (a, x = a) este gresita.

(E3) In urma aplicarii algoritmilor de filtrare si propagare a deciziilor xi = ai,domeniul unei variabile a devenit vid sau a fost detectata ın alt modinconsistenta.

Sa consideram ca prim exemplu problema reginelor pe o tabla de dimen-siuni 3×3 si sa explicam inconsistenta acesteia. In absenta oricarui algoritmde filtrare si propagare, demonstratia ar fi formata doar din reguli de tip(E1), respectiv (E2):

Explain problem is inconsistent

Explain x[0]=0 is inconsistent

x[0]=0 => x[1] != 0

x[0]=0 => x[1] != 1

Explain x[0]=0, x[1]=2 is inconsistent

x[0]=0, x[1]=2 => x[2] != 0

x[0]=0, x[1]=2 => x[2] != 1

x[0]=0, x[1]=2 => x[2] != 2


x[0]=1 => x[1] != 0

x[0]=1 => x[1] != 1

5.2. CE INSEAMNA O EXPLICATIE ? 109

x[0]=1 => x[1] != 2


x[0]=2 => x[1] != 1

x[0]=2 => x[1] != 2


x[0]=2, x[1]=0 => x[2] != 0

x[0]=2, x[1]=0 => x[2] != 1

x[0]=2, x[1]=0 => x[2] != 2

Dupa cum se observa, mecansimul de explicare afiseaza ın acest caz ıntregspatiul de cautare al problemei.

5.2.2 Multimi suport

Vom numi multime suport si notam support(x = a, y) ”sustinerea” pe care oofera variabila y atribuirii x = a, cu alte cuvinte:

support(x = a, y) = b ∈ Dy|(x = a, y = b) consistenta

Pentru x si a date, daca exista o variabila y astfel ıncat support(x = a, y) = ∅atunci valoarea a poate fi eliminata din domeniul lui x.

In cazul problemei anterioare multimile suport sunt:

support x[0] x[1] x[2]x[0] = 0 - 2 1x[0] = 1 - ∅ 0, 2x[0] = 2 - 0 1x[1] = 0 2 - 2x[1] = 1 ∅ - ∅x[1] = 2 0 - 0x[2] = 0 1 2 -x[2] = 1 0, 2 ∅ -x[2] = 2 1 0 -

Din tabelul de mai sus este simplu de observat ca x[0] = 1, x[1] = 1 six[2] = 1 nu sunt instantieri valide deoarece pentru fiecare dintre ele existacel putin o multime suport vida.

Folosind notiunea de multime suport, algoritmul general de arc-consistentapoate fi scris astfel (algoritmul 13):


Algorithm 13 Stabileste arc-consistenta unei retele (AC-4)

Intrare: R0 = (X, D,C) o retea de constrangeriR = R0

Construieste S multimea tuturor multimilor supportqueue = ∅queue este lista tuturor multimilor suport videfor all E = support(x = a, y) ∈ S do

if E = ∅ thenqueue = queue ∪ (x, y, a)

end ifend forwhile queue 6= ∅ do

Selectam un triplet (x, y, a) din lista queuequeue = queue− (x, y, a)Dx = Dx − aif Dx = ∅ thenReteaua este inconsistentareturn null

end iffor all A = support(z = c, x) ∈ S do

A = A− aif A = ∅ then

queue = queue ∪ (z, x, c)end if

end forend whilereturn R

5.3. CONSTRUIREA UNEI EXPLICATII 111

Din perspectiva acestui algoritm, motivul pentru care o valoare a esteeliminata din domeniul unei variabile x este pierderea ın ıntregime a sustineriidin partea unei anumite variabile y: ∃y ∈ X support(x = a, y) = ∅. Dacainitial support(x = a, y) = b1, ..., bt atunci:

expl(x 6= a) = expl(y 6= b1) ∪ expl(y 6= b2) ∪ ... ∪ expl(y 6= bt)

Revenind la exemplul anterior, putem explica inconsistenta problemeiastfel:

Explain problem is inconsistent

Explain x[2] != 0

- support(x[2]=0, x[0])=[1]

Explain x[0] != 1

- support(x[0]=1, x[1])=[]

Explain x[2] != 1

- support(x[2]=1, x[1])=[]

Explain x[2] != 2

- support(x[2]=2, x[0])=[1]

Explain x[0] != 1

- support(x[0]=1, x[1])=[]

5.3 Construirea unei explicatii

5.3.1 Graful eliminarilor

Fie a = (x1 = a1, ..., xk = ak) solutia partiala curenta si x = xk+1 urmatoareavariabila ce trebuie instantiata.

Numim eliminare explicita a valorii a din Dx existenta unei constrangeric cu proprietatea ca (x1 = a1, ..., xk = ak, x = a) nu satisface c.

Numim eliminarea dedusa a valorii a din Dx existenta unui algoritm defiltrare/propagare care, aplicat retelei curente rezultate ın urma deciziilorxi = ai, a determinat o situatie de tipul support(x = a, y) = ∅ si y 6∈x1, ..., xk. Variabila y va fi numita declansator (trigger) al eliminarii.

Multimea eliminarilor explicite si care pot fi deduse prin propagare dininstantierea curenta formeaza graful eliminarilor aferent tuplei a. Acesta vafi construit astfel:


• Varfurile grafului corespund eliminarilor efectuate. Pentru un varf u =elim(x, a) vom nota:

– var(u) = x

– val(u) = a

– context(u) = (x1 = a1, ..., xk = ak)

• Daca ınainte de aplicarea algoritmilor de filtrare support(x = a, y) =b1, ..., bt si ın urma propagarilor support(x = a, y) = ∅ atunci varfulcorespunzator eliminarii lui a din Dx va avea ca vecini cele t varfuricorespunzatoare eliminarilor lui bi din Dy.

Un graf de eliminari se numeste explicativ daca are proprietatea ca exista ovariabila x si o multime de varfuri u1, ..., uk astfel ıncat: ∀i = 1, k var(ui) = xsi

⋃i=1,k val(ui) = Dx. Intr-un graf explicativ, un varf u = elim(x, a) cu

proprietatea ca, ın urma acestei eliminari, Dx = ∅ se numeste final si, prinextensie, vom numi variabila sa finala ın conextul dat. Evident, constructiagrafului se va opri atunci cand a fost adaugat un nod final, ıntrucat acestamarcheaza determinarea inconsistentei instantierii curente.

Un graf explicativ normalizat este un graf explicativ din care au fosteliminate toate componentele conexe care nu contin o eliminare a unei valoridin domeniul variabilei finale. Cu alte cuvinte, acesta este subgraful indusde varfurile ce contin variabila finala.

Pentru simplitate, graful eliminarilor va mai fi numit reducere.

Sa analizam un alt exemplu ın care se doreste explicarea faptului ca nuexista nici o solutie ın problema reginelor pe o tabla 4× 4 ın care o regina safie plasata chiar ıntr-unul din cele patru colturi: explain(x[0] 6= 0).

Graful eliminarilor pentru tupla (x[0] = 0) este:


In situatia de mai sus putem deduce ca tupla (x[0] = 0) este gresitaıntrucat domeniul variabilei x[3] a devenit vid ın urma reducerilor efectuate.De asemenea, se observa ca eliminarea elim(x[2], 2) nu influenteaza ın niciun fel demonstratia inconsistentei, deci varful respectiv poate fi eliminat dingraf. Explicatia ce va fi construita din acest graf este:


<<< x[3] fails... >>> x[3] este finala

- x[0]=0 => x[3] != 0 explicita

Explain x[3] != 1 dedusa

- support(x[3]=1, x[2])=[3] (trigger x[2])


- support(x[2]=3, x[1])=[0, 1] (trigger x[1])

- x[0]=0 => x[1] != 0 explicita

- x[0]=0 => x[1] != 1 explicita


- support(x[3]=2, x[2])=[0] (trigger x[2])

- x[0]=0 => x[2] != 0 explicita

- x[0]=0 => x[3] != 3 explicita

In cazul ın care graful eliminarilor construit unei tuple este explicativ,putem construi un rationament al faptului ca tupla respectiva este gresita cuajutorul algoritmului 14.


Algorithm 14 explainSimple(¬a): Explica inconsistenta unei tuple

Intrare: Graful explicativ al eliminarilor pentru tupla a = x1 = a1, ..., xk =ak.

Rezultat: Explicatia faptului ca a este inconsistentaexpl = ∅ expl este explicatia ce va fi construita

if ∃c ∈ C : a nu satisface c thenreturn ”c⇒ ¬a”

end ifDx domeniul initial al variabilei xfor all a ∈ Dx do

expl = expl ∪ explainDel(x, a) Explicam eliminarea lui a din Dxend for

Algoritmul 15 explica eliminarea unei valori din domeniul unei variabile:

5.3.2 Arborele reducerilor

Arborele reducerilor asociat unei tuple este un arbore cu urmatoarele pro-prietati:

• Fiecare nod e va corespunde unei instantieri partiale a = (x1 = a1, ..., xk =ak), Vom nota tuple(e) = a.

• Fiecare nod va contine graful normalizat al eliminarilor care au fostdeduse direct sau prin propagare din deciziile xi = ai, i = 1, k.

• Pentru orice nod intern e exista o variabila xe astfel ıncat orice fiu alsau e′ are proprietatea var(tuple(e′)) = var(tuple(e))∪x. Vom notanextV ar(e) = x.

Numim explicatie un arbore de reduceri ın care toate frunzele sunt ex-plicative. Evident, ın aceasta situatie toate nodurile interne vor desemnasubarbori care sunt de asemenea explicatii, semnificatia fiecaruia fiind dedemonstrare a inconsistentei tuplelor corespunzatoare. Analizand acest ar-bore trebuie sa putem extrage o succesiune logica de rationamente care sane conduca la inconsistenta tuplei din radacina acestuia, respectiv a ıntregiiretele.


Algorithm 15 explainDel(x, a) : Explica eliminarea lui a din Dx

Intrare: G graful explicativ al eliminarilor pentru tupla a = x1 =a1, ..., xk = ak, x 6∈ x1, ..., xk o variabila si a ∈ Dx.

Rezultat: Explicatia faptului ca x = a este incompatibila cu tupla a.expl = ∅ expl este explicatia ce va fi construitaexplained = ∅ explained este multimea eliminarilor (x, a) deja explicateCautam varful u = elim(x, a) ın Gif u = null then

return nullend ifVerificam daca este o eliminare explicitaif trigger(u) ∈ context(u) then

return ”context ⇒ x 6= a”end ifVerificam daca nu a fost deja explicataif (x, a) ∈ explained then

return ”(∗) ⇒ x 6= a”end if

y = trigger(u)S = support(x = a, y)for all b ∈ S do

expl = expl ∪ explain(y, b)end forexplained = explained ∪ (x, a)return expl


Mergand pe linia exemplelor anterioare, sa explicam faptul ca nu existanici o solutie ın problema reginelor pe o tabla 8× 8 ın care: (x[0] = 0, x[1] =2). In aceasta situatie reducerea corespunzatoare tuplei (x[0] = 0, x[1] =2) nu este explicativa, ceea ce ınseamna ca va trebui sa continuam creareaarborelui de reduceri, pana la obtinerea explicatiei.


x[0]=0, x[1]=2 => x[2] != 0

x[0]=0, x[1]=2 => x[2] != 1

x[0]=0, x[1]=2 => x[2] != 2

x[0]=0, x[1]=2 => x[2] != 3

Explain x[0]=0, x[1]=2, x[2]=4 is inconsistent

<<< x[6] fails... >>>

...


<<< x[3] fails... >>>

...


<<< x[6] fails... >>>


<<< x[4] fails... >>>

...

Algoritmul 16 demonstreaza inconsistenta unei tuple, respectiv a a uneiprobleme.

Algoritmul 17 descrie crearea succesiunii de rationamente corespunzatoareunui nod explicatie.


Algorithm 16 explain(a): Explica inconsistenta unei tuple (a unei prob-leme)

Intrare: R0 = (X0, D0, C0) o retea de constrangeri, a este tupla care trebuieexplicata (poate fi ∅).

Rezultat: Explicatia faptului ca tupla (problema) este inconsistenta

if a 6= ∅ thenif ∃c ∈ C : a nu satisface c then

return ”c⇒ ¬a”end ifR reteau obtinuta din R0 dupa reducerea corespunzatoare tuplei a

elseR = R0

end if

Construim arborele explicatiilor pentru reteaua RFie e radacina acestui arboreConstruim recursiv succesiunea rationamentelorreturn create(e)


Algorithm 17 create(e): Crearea succesiunii de rationamente pentruexplicatia e

Intrare: e un nod de tip explicatie.Rezultat: O succesiune de rationamente ce demonstreaza e.

expl = ∅ expl este explicatia ce va fi construitat = tuple(e)x = nextV ar(e)Dx = domeniul initial al lui xif x 6= null thene nu este nod frunzafor all a ∈ Dx do

if ∃c ∈ C : (t, x = a) nu satisface c thenEliminare explicitaexpl = expl∪ ”t⇒ ¬x 6= a”

elser = explainDel(x, a)if r 6= null thenEliminare dedusa pentru x 6= aexpl = expl ∪ r

end ifend if

end forend ifE nodurile fiu ale explicatiei eif E = ∅ thene este o reducere explicativa pentru texpl = expl ∪ explainSimple(t)

elseRamura recursivafor all e′ ∈ E do

expl = expl ∪ create(e′)end for

end ifreturn expl

5.4. IMPLEMENTAREA ALGORITMULUI 119

5.4 Implementarea algoritmului

Arborele de explicatii va fi construit pe masura executiei algoritmului sistem-atic de cautare. Acesta va pastra o referinta catre nodul curent al acestuiarbore astfel ıncat sa ıl poata extinde sau sa poata naviga prin acesta.

• Initializare - la initializarea solverului este creat nodul radacina alarborelui corespunzator problemei a carei inconsistenta dorim sa odemonstram.

// solution este instantierea partiala curenta

// explanation este nodul curent

// al arborelui reducerilor ce va fi construit

explanation = new Explanation(solution);

• Inaintare - la pasul de alegere a unei noi variabile ın vederea instantiereii(conform strategiei de ınaintare) aceasta va fi retinuta ın nodul curent.

Var var = forwardStrategy.next();

explanation.setNextVar(var);

• Instantiere - la pasul de instantiere a variabilei curente, ın cazul ıncare acest lucru este posibil, va fi creat un nou nod al arborelui, core-spunzator noii solutii partiale. Parintele acestui nod este explicatiacorespunzatoare insantierii precedente.

Object val = assignmentStrategy.assign(var);

if (val != null)

solution.put(var, val);

...

// Start an explanation

if (explaining)

Explanation expl = new Explanation(solution);

expl.setParent(getExplanation());

setExplanation(expl);


• Intoarcere - cand algoritmul efectueaza pasul ınapoi ınseamna ca afost identificata o situatie de esec si cautarea va fi reluata conformstrategiei de ıntoarcere. Nodul curent al arborelui de explicatii va fi celcorespunzator instantierii partiale curente, fiind ın mod evident unuldin stramosii vechiului nod.

Explanation expl = getExplanation();

while (!expl.getTuple().equals(solution))

expl = expl.getParent();

setExplanation(expl);

• Filtrare - ın urma aplicarii unui algoritm de filtrare si propagare vorfi efectuate o serie de eliminari, acestea putand conduce ın final lastabilirea inconsistentei. Aceste eliminari trebuie memorate ın cadrulexplicatiei curente:

// La eliminarea lui a din D(x) datorita pierderii

// sustinerii din partea lui y

// (support(x=a,y) este vida)

explanation = solver.getExplanation();

Elimination elim = new Elimination(x, a, y, solution);

explanation.addElimination(elim);

Capitolul 6

Problema satisfiabilitatii

6.1 Introducere

In acest capitol ne propunem sa introducem un nou model pentru reprezentareaproblemei satisfiabilitatii unei formule propozitionale ın forma normala con-junctiva 3-CNF sub forma unei probleme de satisfacere a constrangerilor [11].Pe baza acestui model vom defini un graf care sa ne permita crearea uneilegaturi ıntre aspecte structurale ale formulei propozitionale si proprietaticorespunzatoare ale grafului.

Fie data o multime de variabile logice X = x1, x2, ..., xn. Un literal lreprezinta fie o variabila x ∈ X, fie negatia sa x. O clauza c este o expresieformata din operatii de tip sau logic ıntre mai multi literali, cum ar fi x1 ∨x2 ∨ x3. O formula propozitionala ın forma normala conjunctiva (CNF)este o expresie formata din operatii de tip si logic ıntre mai multe clauze:c1 ∧ c2 ∧ ... ∧ cp.

Problema satisfiabilitatii (SAT) este formulata astfel:Data o formula F ın forma normala conjunctiva, exista o atribuire a vari-abilelor sale cu valori de adevar 0 sau 1 astfel ıncat F sa fie adevarata ? Acestlucru presupune ca toate clauzele sa fie adevarate, ceea ce conduce la nece-sitatea ca ın fiecare clauza cel putin un literal sa aiba valoarea 1. In cazul ıncare raspunsul este afirmativ, spunem ca F este satisfiabila, iar ın caz contrarnesatisfiabila. Cand fiecare clauza din F are exact k literali problema estenotata k − SAT .

Este binecunoscut faptul ca SAT a fost prima problema demonstrata a fiNP-completa ın faimoasa teorema a lui Stephen Cook, publicata ın 1971 ın

121

122 CAPITOLUL 6. PROBLEMA SATISFIABILITATII

lucrarea ”The Complexity of Theorem Proving Procedures” [48]. Mai multdecat atat, problema ramane dificila chiar daca este restransa la cazul specialcand fiecare clauza contine exact 3 literali (3-SAT). Trebuie de asemenea samentionam ca, spre deosebire de cazul general, 2-SAT este NL-completa [43]si deci poate fi rezolvata ın timp polinomial.

Considerand dificultatea problemei satisfiabilitatii nu ne putem astepta saconcepem algoritmi eficienti pentru cazul general. Cu toate acestea, deoareceo multime de probleme modelate dupa situatii reale se pot reprezenta subforma de instante SAT s-a deovedit ca este necesara dezvoltarea de algoritmicare sa abordeze rezolvarea satisfiabilitatii ıntr-un mod cat mai performant.Acesti algoritmi pot fi completi, ceea ce ınseamna ca vor explora sistematictoate posibilitatile ıncercand sa gaseasca una sau toate solutiile, sau aproxi-mativi bazati pe euristici care nu garanteaza ınsa gasirea solutiei exacte, cumar fi de exemplu algoritmii genetici. Bineınteles, ın continuarea capitoluluivom analiza problema din prima perspectiva, utilizand tehnici de programarecu constrangeri pentru rezolvarea 3-SAT.

SAT poate fi exprimata usor ca o problema de satisfacere a constrangerilor,ın care variabilele sunt cele pe care este construita formula F ce trebuie re-zolvata, domeniile lor sunt 0, 1 iar constrangerile sunt derivate din clauzelec1, ...cp ale lui F .

In pofida simplitatii acestui model, la ora actuala el este utilizat de ma-joritatea algoritmilor sistematici de rezolvare dedicati problemei SAT, cumar fi: Satz, C-SAT, Tableau, POSIT. Acestia sunt bazati pe procedura Davis-Putnam, ın varianta Loveland, asa numita procedura DPL. Schematic, ea esteprezentata ın figura 18.

Pe baza acestei idei au fost creati algoritmi care integreaza diverse tehniciCSP cum ar fi forward-checking (propagarea unitatilor), look-back (backjump-ing) sau diverse euristici de alegere a ordinii ın care sunt instantiate variabile,scopul fiind minimizarea spatiului de cautare a solutiilor astfel ıncat sa poatafi abordare probleme cu un numar cat mai mare de variabile. La ora actualaacesti algoritmi sunt capabili sa rezolve ın timp rezonabil probleme avandchiar si 1000 de variabile.

6.2 Un nod model CSP pentru SAT

In primul rand trebuie mentionat faptul ca nu suntem interesati ın primulrand de crearea unui algoritm care sa depaseasca ın performante pe cele deja

6.2. UN NOD MODEL CSP PENTRU SAT 123

Algorithm 18 Structura generala a procedurii DPL

Intrare: F o formula proprozitionala CNFRezultat: 1 daca F este satisfiabila, 0 ın caz contrar

if F = ∅ thenreturn 1

end ifPropagarea clauzelor unitarewhile F contine o clauza c de lungime 1: c = x or c = x do

Atribuie valoarea corespunzatoare variabilei lui cSimplifica F

end whileDeterminarea situatiei de esecif F contine o clauza vida then

return 0end ifRecursiaSelecteaza x o variabila din F conform unei euristici Hif DPL(F ∪ x) = 1 then

return 1else

return DPL(F ∪ x)end if


existente. In schimb, dorim conceperea unui nou model pentru reprezentareaproblemei SAT sub forma unei instante CSP care sa ne permita rezolvareaacesteia cu orice solver CSP general si care sa fie cat mai potrivit pentruanaliza teoretica. Dupa cum am mentionat deja, majoritatea solverelor ex-istente sunt bazate pe procedura DPL, diferentele majore ıntre acestea fiindeuristicile utilizate si calitatea implementarii. In aceasta abordare orientatape euristica este evident ca unele dintre ele se vor comporta mai bine pe unanumit tip de date de intrare ın timp ce altele vor fi mai eficiente pe alt tipde date. De asemenea, unele implementari sunt optimizate pentru problemestructurate, adica probleme ce prezinta un anumit grad de simetrie si suntrezultate ın general din situatii reale, ın timp ce altele sunt concepute sa fieeficiente pe instante generate uniform aleator. Un alt criteriu care trebuieluat ın considerare este cat de bine se comporta un solver atunci cand formulaeste satisfiabila si cat de bine atunci cand este nesatisfiabila.

Avand ın vedere toate aceste aspecte, am considerat ca este interesantsa gasim o modalitate de a transforma problema 3-SAT ıntr-o problema degrafuri care sa ne ofere de asemenea si un model CSP. In felul acesta, diferiteproprietati structurale ale grafului construit pot fi utilizate ın implementareaeficienta a strategiilor ce controleaza procesul general de rezolvare a uneiinstante CSP.

Ne propunem sa rezolvam problema satisfiabilitatii unei formule propozitionale3-CNF F = c1∧c2∧...∧cp, definita pe multimea de variabile X = x1, ..., xn.Fara a restrange generalitatea, presupunem ca variabilele fiecarei clauze suntdiferite.

Definitie 13 Numim triplet o tupla (x = r, y = s, z = t) unde x, y, zsunt variabilele unei clauze iar r, s, t sunt 0 sau 1. Cand variabilele suntsubıntelese, vom scrie doar (r, s, t).

Daca u = (x = r, y = s, z = t) este un triplet si A ⊆ x, y, z, notamπA(u) proiectia lui u pe multimea A, constand din restrictia tuplei u pevariabilele din A: πx,y(x = 0, y = 1, z = 0) = (x = 0, y = 1).

Definitie 14 Spunem ca doua triplete u si v sunt compatibile daca sinumai daca variabilele lor comune au aceeasi valoare:πA(u) = πA(v)

6.3. GRAFUL ASOCIAT MODELULUI CSP 125

Vom construi o retea de constrangeri R = (S, D, C) care sa modelezesatisfiabilitatea problemei F astfel:

• Fiecarei clauze ci ıi vom asocia o variabila si: S = s1, ..., sp.

• Domeniul Di al unei variabile si va fi format din valorile(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1),reprezentand cele 8 instantieri posibile ale variabilelor din clauza core-spunzatoare ci, din care o eliminam pe cea care nu satisface clauza.Asadar |Di| = 7,∀i = 1, p.

• Constrangerile vor impune ca instantierile variabilelor retelei sa fie com-patibile (variabile comune din cele doua triplete au aceleasi valori). Pen-tru fiecare pereche de clauze care au cel puti o variabila comuna vomadauga o constrangere de acest tip.

Propozitie 13 Fie F = c1 ∧ c2 ∧ ... ∧ cp o formula propozitionala si R =(S, D, C) reteaua de constrangeri corespunzatoare. Problema satisfiabilitatiilui F este echivalenta cu gasirea unei solutii pentru R.

Demonstratie(⇒) Sa presupunem mai ıntai ca a = (x1 = a1, ..., xk = ak) este o solutie

pentru F . Fie ci o clauza definita pe variabilele xi1 , xi2 , xi3 si si variabila dinR corespunzatoare lui ci. Instantierea si = (ai1 , ai2 , ai3) ∀i = 1, p reprezintao solutie a retelei.

(⇐) Sa presupunem acum ca avem o solutie a lui R u = u1, ..., up.Fiecare triplet ui reprezinta o instantiere a variabilelor corespunzatoare clauzeisi, cum toate tripletele sunt compatibile, ele vor induce o instantiere a tuturorvariabilelor formulei ce satisface ın mod evident toate clauzele.

6.3 Graful asociat modelului CSP

Fie F o formula propozitionala si R reteaua de constrangeri definita ınsectiunea anterioara. Corespunzator luiR putem construi un graf G = (V, E)astfel:


• Nodurile grafului V vor fi valorile din toate domeniile D.Astfel, pentru fiecare clauza c = x ∨ y ∨ z vor fi create nodurile:(0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0), (1, 1, 1),reprezentand cele 8 instantieri posibile ale variabilelor din c. Evident,una dintre acestea nu va satisface clauza si nodul corespunzator nu vafi adaugat la graf. Fiecarei clauze ıi vor corespunde asadar 7 noduri,numarul lor total fiind de 7p. Ca o conventie, pentru un nod v ∈ Vvom scrie v ∈ c pentru a denota faptul ca respectivul nod corespundeclauzei c.

• Doua varfuri vor fi adiacente daca si numai daca tripletele corespunzatoaresunt compatibile.

Din perspectiva problemei satisfiabilitatii, muchiile grafului sunt createconform urmatoarelor doua reguli:

• Intre doua varfuri ale aceleiasi clauze nu exista muchie:

∀c ∈ F ∀u, v ∈ c⇒ uv 6∈ E

• Doua varfuri corespunzand unor clauze diferite vor fi adiacente dacasi numai daca tripletele corespunzatoare sunt compatibile: Fie ci si cj

doua clauze din F si fie A multimea variabilelor comune ale lui ci si cj:

∀u ∈ ci, ∀v ∈ cj : uv ∈ E ⇔ πA(u) = πA(v)

Este usor de observat ca graful construit este multipartit, fiecare clasaa partitie corespunzand unei clauze din formula si avand exact 7 varfuri.Muchiile grafului pun ın evidenta instantierile compatibile ale variabilelorclauzelor.

Propozitie 14 Fie F = c1∧c2∧...∧cp o formula propozitionala. Problemasatisfiabilitatii lui F este echivalenta cu gasirea unei clici maximale ın G dedimensiune p.

Demonstratie(⇒) Sa presupunem ca putem determina o solutie a = (x1 = a1, ..., xk =

ak) pentru F . Deoarece aceste valori satisfac toate clauzele din F , exista cate

6.4. ARC CONSISTENTA 127

un triplet ui din fiecare clasa a partitiei grafului astfel ıncat πvar(ui)(a) = ui,∀i = 1, p. Fie ui, uj doua varfuri si A multimea variabilelor comune. Faptulca πA(ui) = πA(uj) = πA(a) implica uiuj ∈ E. Asadar, varfurile u1, ..., upinduc ın G o clica de dimensiune p si cum G este p-multipartit, clica estemaximala.

(⇐) Sa presupunem acum ca avem o clica Q = u1, ..., up ın G. Fiecaretriplet ui reprezinta o instantiere a variabilelor corespunzatoare clauzei si,cum toate tripletele sunt compatibile, ele vor induce o instantiere a tuturorvariabilelor formulei ce satisface toate clauzele.

Este cunoscut faptul ca determinarea existentei unei clici de o anumitadimensiune ıntr-un graf oarecare este NP-completa, aceasta fiind una din cele21 de probleme NP-complete demonstrate de Richard Karp ın lucrarea sadin 1972 ”Reducibility Among Combinatorial Problems” [29]. Propozitia 14demonstreaza ca problema clicii ramane NP-completa chiar si pentru grafuriarc-consistente.

6.4 Arc consistenta

Fie F o formula propozitionala, R reteaua de constrangeri si G graful core-spunzator lui R. In aceasta sectiune vom examina cum arc-consisenta lui Rpoate fi interpretata ın graful G.

Definitie 15 Fie ci o clauza a lui F . Un nod u ∈ ci al grafului ıl vomnumi rau daca si numai daca ∃cj ∈ F astfel ıncat ∀v ∈ cj : uv 6∈ E.

Conform propozitiei 14, este usor de observat ca un nod rau nu poateface parte dintr-o solutie.

Definitie 16 Spunem ca graful G este arc-consistent daca si numai dacanu contine nici un nod rau.

Propozitie 15 Fie F o formula propozitionala,R reteaua de constrangerisi G graful corespunzator lui R. R este arc-consistenta daca si numai dacaG este arc-consistent.


Demonstratia este evidenta si va fi omisa.

6.5 Proprietati ale grafului

In sectiunile urmatoare vom presupune ca graful G este arc-consistent. FieS1, ..., Sp clasele partitiei grafului, p > 2. Este usor de observat ca, ıntr-ungraf arc-consistent, orice varf v ∈ V (G) are cel putin cate un vecin ın fiecaredin celelalte p − 1 clase ale partitiei grafului. Vom mai presupune, fara arestrange generalitatea, ca nici una din clasele partitiei nu este singleton,deoarece ın aceasta situatie am putea reduce problema la una mai simpla.In concluzie, graful G are urmatoarele proprietati:

(P1) 2 ≤ |Si| ≤ 7 ∀i = 1, p

(P2) dG(v) ≥ p− 1,∀v ∈ V (G)

(P3) dG(v) ≥ 2,∀v ∈ V (G)

O alta observatie pe care trebuie sa o facem este legata de numarul cro-matic al lui G. Daca ω(G) = p ⇒ χ(G) ≥ ω(G) ≥ p. Dar, graful fiindp-multipartit χ(G) ≤ p, ceea ce ınseamna ca χ(G) = p iar cele p multimistabile sunt chiar clasele de colorare ale lui G.

Algoritmul 19 ıncearca sa determine o clica maximala de cardinal p ıntr-un graf arc-consistent. Daca nu poate fi gasita o clica p-maximala, algoritmulva returna ∅, dar asta nu ınseamna ca o astfel de clica nu exista.

Intrebarea pe care ne-o putem pune este: exista posibilitatea ca algoritmulde mai sus sa nu identifice o clica p-maximala ? Raspunsul este ”da” si figura6.1 descrie o situatie care poate conduce la aceasta situatie: 3 partitii avandfiecare cate doua varfuri, ce formeaza un C6:

Propozitie 16 Fie F o formula propozitionala si G graful p-multipartitcorespunzator lui F , satisfacand P1-P3. Daca G este P4 − free atunci Gcontine o clica maximala de cardinal p.

6.5. PROPRIETATI ALE GRAFULUI 129

Algorithm 19 Un algoritm care ıncearca determinarea unei clici p-maximale

Intrare: G un graf arc-consistent, p-multipartit.Rezultat: Q o clica maximala de cardinal p sau ∅

Fie S1, ..., Sp clasele partitiei lui GQ = ∅for all i = 1, p do

if Si = ∅ thenreturn ∅

end ifFie ui ∈ Si

Q = Q ∪ ui

for all j = i + 1, p doSj = Sj −NG(ui)

end forend forreturn Q

Figure 6.1: O situatie minimala de esec

DemonstratieInductiv, sa presupunem caam construit o clica Q avand cate un elementdin primele t clase ale partitiei si fie S una din clasele ramase ale partitiei.Presupunem prin reducere la absurd ca ∀x ∈ S Q∪x nu este clica si fie x1

un element oarecare din S, ceea ce implica ∃q1 ∈ Q : x1q1 6∈ E(G). Deoareceın G orice varf are cel putin un vecin ın orice clasa a partitiei (mai putincea din care face parte) rezulta ca ∃x2 ∈ S : q1x2 ∈ E(G). Conform ipotezeiQ ∪ x2 nu este clica deci ∃q2 ∈ Q : x2q2 6∈ E(G). Deoarece graful este


P4 − free deducem ca x1q2 6∈ E(G) altfel x1q2q1x2 ar forma un P4.Sa presupunem ca am identificat varfurile Qk = q1, ..., qk ⊆ Q si Sk =

x1, ..., xk ⊆ S cu proprietatile:

(1) xiqj 6∈ E(G)∀j ≥ i si

(2) xiqj ∈ E(G)∀j < i.

Rationand ca mai sus, obtinem ca exista varfurile qk+1 si xk+1 iar multimileQk+1 = Qk ∪ qk+1, Sk+1 = Sk ∪ xk+1 respecta de asemenea proprietatile(1),(2). Cum acest algoritm nu este finit, am obtinut o contradictie cu pre-supunerea ca initiala ∀x ∈ S Q ∪ x nu este clica. Asadar, putem extindeclica Q ceea ce ınseamna ca ın final vom obtine o clica de cardinal maxim.

O analiza mai atenta a demonstratiei ne arata ca P4 − free poate fiınlocuit cu H−free, unde H este un P4 ce are ambele extremitati ın aceeasiclasa a partitiei.

Propozitie 17 Daca G contine un P4 indus atunci G contine un P4 ceare cel putin o pereche de varfuri ın aceesi clasa a partitie.

DemonstratieFie a1b1c1d1 un P4 avand varfurile ın partitiile distincte A, B, C,D.a1 are cel putin un vecin ın C ⇒ ∃c2 ∈ C : a1c2 ∈ E(G)c1 are cel putin un vecin ın A ⇒ ∃a2 ∈ A : a2c1 ∈ E(G)Daca a2c2 ∈ E(G) ⇒ a1c2a2c1 formeaza un P4 cu proprietatea dorita. Deciputem presupune ca a2c2 6∈ E(G).b1 are cel putin un vecin ın D ⇒ ∃d2 ∈ D : b1d2 ∈ E(G)c1 are cel putin un vecin ın A ⇒ ∃b2 ∈ B : b2d1 ∈ E(G)Daca b2d2 ∈ E(G) ⇒ b1d2b2d1 formeaza un P4 cu proprietatea dorita. Deciputem presupune ca b2d2 6∈ E(G).a1b1c1a2 6= P4 ⇒ b1a2 ∈ E(G),c2a1b1c1 6= P4 ⇒ b1c2 ∈ E(G),b1c1d1b2 6= P4 ⇒ c1b2 ∈ E(G),d2b1c1d1 6= P4 ⇒ c1d2 ∈ E(G),a1b1c1b2 6= P4 ⇒ a1b2 ∈ E(G),d1c1b1c2 6= P4 ⇒ d1c2 ∈ E(G),a1b2c1d2 6= P4 ⇒ a1d2 ∈ E(G),

6.6. IMPLEMENTARE SI EXPERIMENTE 131

d1c2b1a2 6= P4 ⇒ a2d1 ∈ E(G),In final, am obtinut faptul ca a1d2a2d1 este un P4 indus avand 2 varfuri ın Asi doua varfuri ın D.

6.6 Implementare si experimente

Sa ne reamintim arhitectura generala a unui solver CSP:

Algorithm 20 Algoritmul general de rezolvare

Intrare: R = (X, D,C) o retea de constrangeriRezultat: Rezolvarea lui R

Pas0 Filtreaza problema initialaif reteaua este rezolvata then



returnend if

Pas1 Memoreaza starea problemeiPas2 DeciziePas3 Propagareif reteaua este rezolvata then



Restaureaza problema de dinaintea decizieigoto Pas2

end ifgoto Pas1

Solverul OmniCS, pe care l-am utilizat ın implementare si experimente,are capacitatea de a controla pasul decizional al algoritmului general prinspecificarea urmatoarelor strategii:


• Strategia de ınaintare este euristica pentru selectarea variabilelor.Pentru aceasta problema am utilizat o euristica simpla care selecteazavariabila implicata ın cat mai multe clauze din cele care nu au fostsatisfacute ınca.

• Strategia de instantiere este euristica pentru alegerea valorilor.Strategia utilizata pentru aceasta problema a fost de a selecta valoarea(tripletul) care maximizeaza numarul de clauze care devin satisfacutedupa asignarea specificata de triplet. Pentru a beneficia de rezultatulpropozitiei 16 a fost inclus un mecanism de forward-checking care aplicaalgoritmii de filtrare si propagare pentru fiecare valoare posibila ınıncercarea de a determina daca graful corespunzator problemei redusedevine P4-free. Aceasta operatie nu ar trebui sa aiba un impact negativsimtitor asupra performantei ıntrucat recunoasterea cografurilor poatefi facuta ın timp liniar [39].

In experimente, numarul de clauze utilizat a fost p = 4.25 ∗ n, unde neste numarul de variabile. Empiric [34], s-a observat ca problemele generatealeator de acest tip sunt cel mai greu de rezolvat.

Pentru fiecare n de la 50 la 300 au fost rezolvate 10 instante 3-SAT gen-erate uniform aleator. Rezultatele aproximative sunt date ın tabelul de maijos:

Variabile Clauze Backtrack Timp50 213 < 2 < 100ms100 425 < 20 < 2sec150 628 < 500 < 1min200 850 < 800 < 2min250 1063 < 3000 < 10min300 1275 < 30000 < 3h

Trebuie remarcat faptul ca reteaua de constrangeri corespunzatoare are unnumar de variabile egal cu numarul clauzelor p iar numarul de constrangerieste egal cu numarul perechilor de clauze care au cel putin o variabila co-muna. De exemplu, daca n = 50, numarul variabilelor este 213 iar numarulconstrangerilor ar putea fi aproximativ 3500.

6.7. CONCLUZII 133

6.7 Concluzii

Chiar daca performantele obtinute de implementarea noastra nu sunt ıncacomparabile cu cele ale celor mai bune solvere dedicate problemei 3-SAT,scopul nostru principal a fost de a dezvolta un model teoretic care sa nepermita studierea satisfiabilitatii unei formule propozitionale ın termeni deproprietati ale grafului corespunzator si, pe baza acestor proprietati, sa dez-voltam strategii eficiente de explorare sistematica a spatiului de cautare asolutiilor pe care sa le integram ıntr-un solver CSP general, cum ar fi Om-niCS. Directia ulterioara de cercetare va fi o mai profunda analiza a grafuluiasociat formulei propozitionale pentru a vedea cum putem exploata structurasa specifica. In afara de acest lucru, intentionam sa integram ın acest modeldiverse euristici care si-au dovedit eficienta ın abordarile clasice, cum ar fiMom ([34], [28], [8]) (Maximum Ocurrences in Clauses of Minimum Size),ımbunatatind astfel comportamentul general al procesului de rezolvare.

Capitolul 7

Problema orarului

7.1 Introducere

Capitolul de fata ısi propune analiza problemei orarului folosind tehnici desatisfacere a constrangerilor, ıntr-un mod cat mai general care sa includadiverse situatii cu aplicabilitate practica. Informal, definim problema oraru-lui astfel: ”Data o multime de activitati supuse unor constrangeri naturalesau impuse, se cere plasarea optima a acestora ıntr-un spatiu temporal”. Inmod firesc, vom detalia fiecare element al acestei definitii pentru a ajungela o definitie formala a problemei pe care dorim sa o rezolvam. In final,rezultatele obtinute trebuie sa poata modela cel putin urmatoarele situatii:

• Crearea orarului unei institutii de ınvatamant superior (universitate)

• Crearea orarului unei scoli cu program normal

• Planificarea orelor ın cadrul programelor de ınvatamant la distanta

• Planificarea sesiunilor de examene

• Planificarea unor cursuri de pregatire intensive

Problemele de planificare, cum este si cea a orarului, sunt bine-cunoscuteprobleme de optimizare a caror rezolvare a fost ın atentia cercetatorilor demult timp, contributii la acest domeniu venind din mai multe directii cumar fi:

• Teoria grafurilor - probleme de colorare

135

136 CAPITOLUL 7. PROBLEMA ORARULUI

• Inteligenta artificiala

– algoritmi genetici

– simulated annealing

– tabu search

• Probleme de satisfacere a constrangerilor

In multe cazuri ınsa, abordarile erau mai mult teoretice si implementarealor ın situatii reale era dificil sau chiar imposibil de realizat.

7.1.1 Activitati (Evenimente)

Prin activitati sau evenimente vom numi elementele atomice care vor fi plan-ificate. Proprietatea de atomicitate specifica faptul ca vom lucra ın mod-elul ın care evenimentele sunt continue (non-preemptive), cu alte cuvinte nupot fi ıntrerupte, aceasta fiind situatia cea mai frecventa ın problemele deplanificare de tip orar. In cazul construiri orarului pentru conferinte sauworkshop-uri pot exista situatii ın care o activitate sa fie fragmentata peparcursul unei zile ınsa, de obicei, dimensiunile segmentelor sunt cunoscuteceea ce face posibila modelarea activitatii cu ajutorul mai multor evenimentecorespunzatoare ıntregului.

Evenimentele pot fi:

• Repetitive - situatia cea mai frecventa, un exemplu fiind situatia uneisectii la zi din cadrul unei facultati, ın care domeniul temporal esteuzual produsul cartezial al multimilor:

– luni, marti,miercuri, joi, vineri si

– 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19,

acestea reprezentand orele posibile de ıncepere a cursurilor sau lucrarilorpractice. Evenimentele plasate ıntr-un astfel de domeniu se vor repetade un numar specificat de ori, formand astfel orarul complet. Specifi-carea pe calendar a datei de ınceput si a numarului de repetari suntsuficiente pentru a identifica exact, ın timp, fiecare activitate.

• Unice - domeniul este format din date calendaristice si ore specificateexplicit: t1 = (data1 : ora1), t2 = (data2 : ora2), ..., tn = (datan :

7.1. INTRODUCERE 137

oran). Exemple de acest tip ar putea fi: recuperari de ore, examene,admitere, licenta, etc.

Facand abstractie de problema planificarii, caracteristicile generale aleunei activitati sunt:

• informatiile legate de identificarea sa

• durata (timpul necesar desfasurarii sale)

• domeniul temporal asociat

• numarul de repetitii (doar pentru cele repetitive)

• resursele necesare

Sigur ca la acestea se vor adauga o serie de constrangeri obligatorii sau nu,despre care vom discuta ın sectiunea dedicata lor.

Plasarea pe orar a activitatilor presupune:

• atribuirea unei valori din domeniul temporal; de exemplu, cursul x vafi tinut la momentul t.

• alocarea unor resurse specifice; cursul x va avea loc in sala s.

• satisfacerea constrangerilor tari ale problemei.

Daca notam cu start(e) momentul ınceperii unui eveniment si end(e)momentul terminarii sale, concurenta a doua evenimente poate fi scrisa subforma unei disjunctii C1 ∨ C2, unde:

(C1) start(e1) < end(e2) ∧ start(e2) < end(e1)

reprezinta conditia suprapunerii temporale ın cadrul unei saptamani iar

(C2) week(e1) = 0 ∨ week(e2) = 0 ∨ week(e1) = week(e2)

este conditia care verifica faptul ca evenimentele sunt ın aceeasi saptamana,utila ın cazul ın care evenimentele nu se repeta cu aceeasi frecventa.

Din punctul de vedere al tipului lor, evenimentele pot fi:

• obligatorii


• optionale

• facultative

Aceasta clasificare nu are doar rol informativ, deoarece exista situatii ıncare penalizarea asociata unui conflict poate tine cont de tipul evenimentelorimplicate.

Pentru a putea specifica comod restrictii la nivelul unei multimi de ac-tivitati acestea vor fi vazute ca facand parte din grupuri. Astfel, ın cazulorarului unei facultati, o anumita disciplina de studiu din planul de ınvatamantpoate fi vazuta ca un grup, evenimentele sale putand fi cursul asociat, labora-toarele sau seminariile aferente, etc. Aceasta organizare poate fi utila pentrudefinirea unor proprietati comune activitatilor, cum ar fi pachetul din careacestea fac parte.

7.1.2 Domeniul temporal

Prin domeniu sau spatiu temporal vom ıntelege o multime de elemente T =t1, ..., tn reprezentand momente fixate ıntr-un interval calendaristic speci-ficat.

In cadrul unei probleme pot fi definite mai multe domenii temporale,fiecarei activitati fiindu-i asignat un astfel de domeniu, din care va trebuiselectata o pozitie. Fiecare domeniu T va avea asociata o functie de maparecare sa transforme elementele lui t ın date calendaristice reale.

Cazul cel mai uzual este cel al orarelor ale caror activitati se desfasoaraın aceeasi structura saptamanal, ıntre anumite ore ale zilei. Considerandn numarul de ore din zi si m numarul de zile din saptamana elementelespatiului temporal pot fi considerate valori ıntregi din domeniul [0, n ∗ m],corespondenta cu momentele reale fiind facuta ın conditiile ın care suntspecificati parametrii h0 - ora de ınceput a activitatilor ın zi si , d - du-rata ın minute a unei ore. Astfel, pentru o valoare t ∈ [0, n ∗ m], ziuava fi day = 1 + [t/n], ora hrs = h0 + (t − [t/n] ∗ n) ∗ d/60 iar minutulmin = (t− [t/n] ∗ n)− (hrs− h0) ∗ 60

7.1.3 Participanti (Actori)

Desfasurarea unui eveniment presupune implicarea unor anumite entitati,unele dintre ele fiind prestabilite, altele alocate dinamic ın functie de diverseconditii. Vom numi actor orice participant la o activitate care este asignat

7.1. INTRODUCERE 139

acesteia independent de procesul de creare a orarului. Acesta poate fi opersoana anume, cum ar fi un cadru didactic sau un student, sau un grup depersoane cum ar fi, ın cazul unei facultatii, ani, semiani sau grupe de studiu.Dupa cum vom vedea, organizarea actorilor ıntr-o structura comuna de dateeste foarte importanta pentru determinarea relatiilor dintre acestia.

Din punctul de vedere al asocierii eveniment-actor, vom considera cafiecare eveniment poate avea oricati actori, dar cel putin unu, aceasta abor-dare permitand o flexibilitate sporita ın organizarea orarului. Pentru a ex-emplifica, ın cazul cursurilor optionale sau facultative, exista de multe orisituatii ın care acestea se desfasoara ımpreuna cu studenti din mai multiani de studiu, sau exista activitati care presupun participarea mai multorprofesori, cum ar fi sedinte sau seminarii stiintifice.

Arborele de incluziuneRevenind la organizarea participantilor, vom defini ın primul rand un ar-bore care sa surprinda relatia de incluziune a actorilor. Nodurile frunza aleacestuia vor fi formate din actorii de baza (persoane propriu-zise sau grupeindivizibile de cursanti), nodurile interne reprezentand reuniunea tuturor ac-torilor din nodurile fiu. Mai jos, este schematizat un exemplu de astfel dearbore:

-Facultatea de informatica

- Profesori

- Catedra de optimizare (OIA)

- Cornelius Croitoru

- Cristian Frasinaru

- ...

- Colaboratori

- ...

- Studenti

- Cursuri de zi (3 ani)

- Anul 1

- Semianul A

- Grupa 1

- Grupa 2

- ...

- Semianul B


- ...

- Invatamant la distanta

- ...

Evenimentelor le pot fi asignati actori de pe orice nivel din arbore.

Propozitie 18 Fie a1, a2 doi actori. a1 ∩ a2 6= ∅ ⇔ exista un drum de laradacina arborelui de incluziune la un nod frunza ce contine pe a1 si a2.

7.1.4 Resurse

Prin resurse vom ıntelege elementele necesare desfasurarii unei actiuni, cumar fi: videoproiectoare, laptop-uri, retroproiectoare, etc. ce vor fi alocatedinamic ın procesul de creare a orarului. Din punctul de vedere al identificariilor, resursele pot fi:

• simple (specifice) - identificate ın mod unic, cum ar fi un profesor sauo sala speciala; la un moment dat o resursa specifica executa cel multun eveniment.

• compuse - acestea sunt multimi formate din resurse simple, cum ar firesursa sali de laborator, formata din multimea resurselor specifice cereprezinta salile ın care pot fi tinute laboratoare.

• cumulative - reprezinta o resursa generica careia ıi este asociata o an-umita capacitate specificata printr-un numar ıntreg, cum ar fi resursavideoproiector, capacitatea acesteia fiind numarul de videoproiectoaredisponibile. O resursa cumulativa poate sustine mai multe activitati ınparalel, cu conditia sa nu fie depasita capacitatea acesteia.

Fiecare eveniment poate avea asignate anumite resurse simple si cantitatiprestabilite ale unor resurse cumulative; un exemplu ar fi un curs ce nece-sita o anumita sala (resursa simpla), un videoproiector si un laptop (resursecumulative).

7.2 Reteaua de constrangeri

Sa vedem ın continuare cum putem reprezenta problema orarului sub formaunei retele de constrangeri, acest lucru presupunand identificarea variabilelor,

7.2. RETEAUA DE CONSTRANGERI 141

domeniilor si a constrangerilor. Ca ın majoritatea situatiilor exista mai multevariante de modelare a problemei care, desi conceptual sunt echivalente, potavea un impact semnificativ asupra eficientei procesului necesar obtineriisolutiei. In cazul nostru, distingem cel putin doua variante:

a. variabilele retelei reprezinta evenimentele iar valorile vor fi alese dindomeniul temporal asociat.

b. variabiele retelei sunt reprezentate de elementele domeniilor temporale,valorile acestora fiind alese din multimea evenimentelor.

Intrucat, ın general, este de preferat ca dimensiunea maxima a domeniilor devalori ale variabilelor sa fie mai mici decat numarul de variabile, vom alegepentru modelare prima varianta.

7.2.1 Variabile si domenii

Pentru fiecare activitate e vom considera o singura variabila pe care o vomnota tot e.

Dupa cum am vazut, pentru desfasurarea unui eveniment sunt necesareo serie de resurse cum ar fi o sala sau un videoproiector. Acest lucru va fispecificat printr-un tablou de liste, fiecare intrare a tabloului fiind multimearesurselor disponibile din care va fi selectata una anume de tipul dorit. Astfel,o solicitare de tipul: ”cursul va fi ın una din salile C308 sau C309, am nevoiede videoproiector si ın paralel retineti una din salile de laborator C401,C409sau C412 pentru ultima parte a semestrului ın care se vor desfasura lucraripractice” va fi formalizata prin structura de date:

res[1] = C308, C309

res[2] = video

res[3] = C401, C409, C412

Din cele trei liste de resurse va fi ales si asignat evenimentului cate un singurelement.

Domeniul unei variabile trebuie sa surprinda atat momentele din spatiultemporal la care evenimentul poate fi plasat cat si variantele de resursedisponibile. Pentru o variabila e, daca notam cu T = t1, t2, ..., tk spatiulsau temporal si Ri|i = 1, p resursele dorite, domeniul lui e va fi format dinprodusul cartezia ıntre toate aceste multimi:

De = T ×R1 ×R2 × ...Rp


Revenind la exemplul anterior, daca T = Luni(10 − 12), Marti(12 − 14)atunci domeniul variabilei asociate va avea 12 valori si anume:

(L 10-12, C308, video, C401), (L 10-12, C308, video, C409),



(Ma 12-14, C308, video, C401), (Ma 12-14, C308, video, C409),

(Ma 12-14, C308, video, C412), (Ma 12-14, C309, video, C401),

(Ma 12-14, C309, video, C409), (Ma 12-14, C309, video, C412)

De cele mai multe ori, numarul de multimi de resurse nu este mare (1, 2) ceeace face ca domeniile variabilelor sa nu devina exagerat de mari.

De asemenea, trebuie tinut cont si de saptamana ın care va fi plasatevenimentul, ın cazul celor care se desfasoara la doua saptamani, caz ın caredomeniul va fi:

De = 1, 2 × T ×R1 ×R2 × ...Rp

Asadar, valorile variabilelor ce descriu evenimente vor avea urmatoareleatribute:

• start - momentul temporal la care ıncepe evenimentul,de exemplu: luni, ora 10 ;

• end - informatie redundanta ce semnifica momentul de terminare aevenimentului, de exemplu: luni, ora 12 ;

• week - saptamana ın care se va desfasura: 0 - toate, 1 - impare, 2 -pare;

• resources - lista de resurse asignate, de exemplu: C308, video, C401

7.2.2 Constrangeri

Constrangerile trebuie sa reflecte atat restrictiile tari ale problemei, cumar fi imposibilitatea desfasurarii a doua actiuni ın aceeasi sala, precum sicele slabe, reprezentate de preferintele actorilor. Intrucat solverul OmniCSabordeaza ın mod unitar ambele tipuri de constrangeri, ın clasificarea demai jos nu le vom diferentia ın mod explicit. Astfel, identificam urmatoarelerestrictii:

• evenimentele ce au actori comuni nu trebuie sa fie concurente;

• un eveniment trebuie sa se desfasoare doar ın anumite momente spec-ificate;

• o multime de evenimente poate fi dispusa doar ın anumite zile;

• o multime de evenimente poate fi dispusa doar ıntre anumite ore;

• o multime de evenimente trebuie sa se desfasoare consecutiv;

• o multime de evenimente trebuie sa se desfasoare concurent;

• un eveniment trebuie sa aiba loc neaparat ınainte sau dupa alt eveni-ment;

• o resursa specifica nu poate fi asignata la doua evenimente concurente;

• suma cantitatilor dintr-o o resursa cumulativa asignate unor eveni-mente concurente nu poate depasi capacitatea acesteia;

• o resursa este (nu este) disponibila ıntr-un anumit interval al domeni-ului temporal;

Intrucat restrictiile pot fi obligatorii sau nu, trebuie sa utilizam un sistemde reprezentare a preferintelor ın care acestora sa le asociem un anumit nivelcare sa indice masura ın care trebuie respectate.

Fiecarui tip de restrictie ıi vom crea o clasa ce defineste constrangerearespectiva precum si o modalitate de specificare descriptiva a sa. In moduzual, constrangerile tari sunt invariabile si trebuie adaugate oricum.

Fiecarui actor ıi vom pune ın corespondenta un fisier descriptor ın formatXML ce formalizeaza preferintele acestuia precum si necesarul de resursepentru evenimentele sale. Sa consideram un exemplu foarte simplu:



<prefs actor="cc">

<event id="Cgraf_A, Cgraf_B">

<res id="C112"/>


<res id="video"/>

<include day="1" hour="8"/>


</event>

<event id="S_consult1">

<res id="Cabinet"/>


</event>

<event id="S_consult2">

<res id="Cabinet"/>


</event>

</prefs>

Sa detaliem ın continuare tipurile de constrangeri implementate.

Constrangeri de compatibilitateSpunem ca doua evenimente instantiate sunt compatibile daca:

• nu au actori sau resurse simple comune sau

• au actori sau resurse simple comune dar nu se suprapun temporal.

O restrictie tare a orarului este ca oricare doua evenimente trebuie sa fiecompatibile, acest tip de constrangere trebuind sa fie impus obligatoriu pen-tru orice pereche de evenimente ce au potential de a intra ın conflict: auactori comuni sau multimile de resurse solicitate au intersectia nevida. Con-strangerile de compatibilitate reprezinta cea mai mare parte din multimeatuturor constrangerilor. Pentru a exemplifica, ın cazul orarului Facultatii deInformatica Iasi pentru semestrul 2 anul scolar 2005-2006, dintr-un total depeste 20.400 constrangeri mai mult de 20.000 au fost de compatibilitate.

Constrangeri legate de capacitatea resurselorAcest tip de constrangere impune ca numarul evenimentelor concurente careutilizeaza o resursa cumulativa sa nu fie mai mare decat capacitatea resurseirespective. Fie r o resursa si c(r) capacitatea acesteia. Sa notam cu e1, ..., ek

o multime de evenimente concurente, fiecare utilizand p(ei) unitati de tipul


resursei r. Constrangerea poate fi formulata astfel:∑i=1,k

p(ei) ≤ c(r)

Constrangerea este globala si trebuie impusa pe multimea tuturor vari-abilelor ce definesc evenimente care solicita resursa respectiva.

Restrictii asupra disponibilitatii resurselorUn alt tip de constrangere tare ce poate aparea se refera la faptul ca anumiteresurse nu sunt disponibile pe tot domeniul temporal asociat evenimentelor.Astfel, o situatie frecventa este cea ın care unele sali sunt partajate ıntremai multe facultati, fiecareia revenindu-i anumite zile si intervale orare ıncare poate desfasura activitati ın sala respectiva. Sigur ca aceasta restrictiepoate fi relaxata ın conditiile ın care se prefera ca o anumita resursa sa nu fieutilizata din diferite motive, cum ar fi starea sa precara sau distanta marefata de locul uzual de desfasurare a evenimentelor dar ın lipsa altor solutiifolosirea ei sa poata fi facuta.

Constrangerea este globala si trebuie impusa pe multimea tuturor vari-abilelor ce definesc evenimente care solicita resursa respectiva, avand ca ar-gument subspatiul temporal ce specifica disponibilitatea resursei respective.Acesta va fi reprezentat sub forma unui tablou a avand hd elemente, undeh este numarul orelor din zi iar d numarul orelor din saptamana, elementelesale avand urmatoarele valori:

• 0 - pozitia respectiva este permisa

• +∞ - pozitia respectiva nu este permisa

• 0 < c < ∞ - pozitia este permisa cu un anumit nivel de preferinta,utilizarea ei fiind penalizata cu valoarea c.

Restrictii asupra disponibilitatii actorilorMajoritatea participantilor implicati ın activitatile ce trebuie planificate im-pun anumite restrictii asupra momentelor ın care acestea se pot desfasura.Aceste restrictii se pot referi la multimea tuturor evenimentelor unui actorsau pot fi particularizate asupra fiecarui eveniment sau grup de evenimente

ın parte. Indiferent de modul de specificare a acestora, la nivel intern con-strangerea aferenta va fi unara, avand ca argumente variabila ce reprezintaun eveniment restrictionat si subspatiul temporal aferent, acesta din urmafiind reprezentat sub forma unui tablu, ca mai sus. La nivel descriptiv, im-plicit se presupune ca actorul este disponibil ın orice moment. La aparitiaunei intrari de tip include, spatiul temporal urmeaza sa fie restrictionat,presupunerea initiala este negata ceea ce ınseamna ca actorul nu mai esteconsiderat disponibil decat ın intervalele specificate. Includerea intervalelorse face extrem de simplu prin enumerarea zilelor si orelor permise, eventual apenalizarilor aferente (ın lipsa acestora constrangerea este considerata tare).



<prefs actor="a">

<event id="Lso1, Lso2">

<res id="sali-lab"/>

<include day="1,2" hour="8,10,12"/>

<include day="5"/>

</event>

</prefs>

Daca tagul include este subtag event atunci el se va referi la evenimentelespecificate de acesta, ın caz contrar va fi aplicat pentru toate evenimenteleactorului. Un exemplu de utilizare a penalizarilor:



<prefs actor="a">

<event id="Cso1">

<res id="sali-curs"/>

<include hour="10,12"/>

<include day="5" penalty="10" />

</event>

</prefs>

Este usor de remarcat ca, ın prezenta mai multor directive include carerestrictioneaza domeniul temporal prin tablourile a1, ...ak, tabloul a ce va ficreat ın final ca argument al constrangerii va avea valorile create dupa regula:

a[i] = max(a1[i], a2[i], ..., ak[i])

In cazul constrangerilor tari de acest tip, fiind unare, ele vor avea ca efectreducerea domeniului variabilelor respective dupa care pot fi eliminate dinreteaua de constrangeri ınainte de pornirea efectiva a algoritmului sistematicde rezolvare.

Secventialitatea si ordinea evenimentelorDe foarte multe ori se doreste ca o multime de evenimente sa se desfasoareın bloc compact, indiferent de ordine sau ıntr-o ordine oarecare. Acest lucrupoate fi specificat prin constrangerea linked care impune ca o multime deevenimente sa fie legate, respectiv order cu argumentele first si last caredefineste o relatie de ordine partiala asupra acestor evenimente.



<prefs actor="a">

<event id="curs">


<include day="1"/>

</event>

<event id="curs, seminar">

<res id="sali-sem"/>

<include day="1"/>

</event>

<linked events="curs,seminar"/>

<order events="curs,seminar"

first="curs" last="seminar"/>

<event id="lab1, lab2, lab3">

<res id="sali-lab"/>

<include day="2"/>

<linked/>

</event>

</prefs>

Concurenta evenimentelorAcest tip de constrangere se refera ın special la evenimente care au loc odata la doua saptamani si sunt formate dintr-un un numar par de grupe destudii diferite. Sa consideram exemplul unui curs facultativ tinut la fiecaredin semianii A, B ai anului 1, o data la doua saptamani. Din punctul devedere al profesorului si din punctul de vedere al eficientizarii utilizarii saliloreste de preferat ca ambele cursuri sa fie plasate ın acelasi moment, unul ınsaptamana para iar celalalt ın cea impara. Acest lucru poate fi realizat cudirectiva concurrent:

<prefs actor="a">

<event id="cursA, cursB">


<concurrent/>

</event>

</prefs>

Limitarea numarului de zile si oreCu ajutorul constrangerilor de tip days, respectiv hours ce au parametriimin si max pot fi limitate numarul zilelor ın care se desfasoara un grup deevenimente, respectiv numarul orelor din zilele ın care exista evenimenteplasate. Aceasta restrictie poate fi aplicata global pe multimea evenimentelortuturor actorilor pentru a limita numarul orelor dintr-o zi la maxim 8 deexemplu, sau individual doar pentru evenimentele unui singur actor:



<prefs actor="a">

...

<hours max="6"/>

<hours min="4" penalty="1"/>

</prefs>

Restrictionarea numarului de zile poate fi facuta ca ın exemplul de maijos:



<prefs actor="b">

...

<days max="1"/>

</prefs>

7.2.3 Complexitatea problemei

Sa consideram problema de decizie asociata unui caz particular al problemeide constructie a orarului formulata ın capitolul anterior:

(TTP)Instanta: O multime A = a1, ..., an de activitati ce partajeaza resursecomune (ce pot fi actori sau resurse propriu-zise) si un domeniu temporalT = t1, ...tp.Intrebare: Exista o asignare a evenimentelor din A cu valori din T astfelıncat oricare doua evenimente ce au actori comnuni sa nu fie concurente ?

Vom arata ca aceasta problema este NP-completa demonstrand ca poate fiobtinuta prin transformarea ın timp polinomial a unei probleme a carei NP-completitudine a fost demonstrata. In lucrarea [7] autorii Tim B. Coopersi Jeffrey H. Kingston pun ın evidenta cinci metode diferite de a realizaacest lucru, scotand astfel ın evidenta complexitatea problemei din mai multeperspective.

Fara a ne propune sa intram ın detalii, prezentam mai jos echivalentadintre problema orarului si problema colorarii varfurilor unui graf. Aceastadin urma este formulata astfel:


(COL)Instanta: G = (V, E) un graf si p un numar natural pozitiv.Intrebare: Exista o p-colorare a varfruilor lui G ?

Urmatorul rezultat este binecunoscut:

Teorema 3 (Karp, 1972) [29] COL este NP-completa.

Teorema 4 TTP este NP-completa.

Vom reduce problema colorarii la problema orarului: COL α TTP . Fie Gun graf oarecare si p un numar de culori datele unei probleme COL. Vomconstruim ın timp polinomial urmatoarea problema de orar:

• fiecarui varf vi ıi cream o activitate ai; initial presupunem ca activitatilenu au nici o resursa asociata.

• pentru oricare doua varfuri adiacente a1 si a2, daca acestea nu au nicio resursa comuna, le adaugam una ambelor.

• cream un domeniu temporal oarecare cu p elemente

In mod evident am obtinut o instanta TTP, ceea ce demonstraza ca problemaorarului este NP-completa.

7.3 Rezolvarea problemei orarului

Dupa formalizarea problemei, urmatorul pas ın rezolvarea acesteia este uti-lizarea unui solver CSP pentru obtinerea unei solutii optime. Dupa cum ammentionat deja solverul utilizat (OmniCS) permite particularizarea strategi-ilor de ınaintare si instantiere a variabilelor lucru util din punct de vederepractic ıntrucat o serie de euristici desprinse din experienta practica se potdovedi extrem de utile.

Strategia de ınaintareEuristica de selectare a variabilelor folosita este de tip ”domeniu minimal”care alege ca urmatoare variabila pe cea cu domeniul cel mai mic. In cazulnostru, am considerat mai important aspectul temporal al domeniului si,pentru fiecare eveniment a fost calculat un coeficient tightness ce reprezintagradul de restrictivitate temporala extras din preferintele acestuia. Valorileacestui coeficient sunt numere reale din intervalul [0, 1], 1 avand semnificatia

7.3. REZOLVAREA PROBLEMEI ORARULUI 151

de foarte restrictiv iar 0 de foarte relaxat. Alegerea variabilelor se va face de-screscator ıncepand cu cele de coeficient maxim. In cazul unor valori egale alerestrictivitatii, va fi folosita tehnica ”adiacentei maximale”, care selecteazaca urmatoare variabila pe cea cu cele mai multe ”adiacente” ın multimeavariabilelor instantiate deja; ın cazul nostru adiacenta are semnificatia deactori comuni.

Strategia de instantiereEuristica de instantiere a variabilelor impune ca alegerea unei valori sa sefaca astfel ıncat orarul rezultat aferent actorilor implicati ın eveniment safie:

• minimal din punct de vedere temporal : aceasta conditie ne asigura ca,ın conditiile ın care o serie de evenimente pot fi suprapuse (cursurioptionale, la doua saptamani, etc.) acestea vor fi suprapuse.

• compact : fragmentarea zilnica a participantilor sa fie cat mai mica.

Utilizand aceste euristici, ın conditiile ın care problema creata pe bazatuturor preferintelor nu a fost supra-constransa, solverul OmniCS a determi-nat o solutie ıntr-un timp de ordinul minutelor, cu un numar extrem de redusde backtracking-uri. Numarul evenimentelor a fost de peste 300 iar numarulconstrangerilor de peste 20.000, solutia gasita fiind apropiata de cea generatamanual ın prealabil, proces care a durat 4-5 zile de munca.

In aceste conditii, singura activitate consumatoare de timp ramaneoperatiunea de formalizare a preferintelor participantilor la orar si de identifi-care a eventualelor conflicte ıntre acestea. In viitor, ne propunem sa realizamo interfata grafica Web [20] prin intermediul careia sa poata fi colectate siformalizate automat preferintele participantilor si, ın acelasi timp, sa asigureconsistenta problemei la un anumit nivel.

Exista ınsa o serie de limitari legate de rezolvarea problemei orarului subforma unui tot unitar, indiferent de modul ın care aceasta este abordata.Aceste neajunsuri survin din faptul ca enuntul problemei ın cele mai multecazuri nu este static, specificatiile fiind ın permanenta schimbare. Cu altecuvinte, este posibil ca dupa construirea orarului sa apara elemente noi caretrebuie luate ın calcul cum ar fi introducerea unor activitati suplimentare,


schimbarea de ultim moment a preferintelor unor profesori sau indisponi-bilizarea unor resurse, schimbari ce pot intra ın conflict cu solutia finalagenerata de solverul CSP. Reluarea ıntregului proces de construire a oraruluipoate fi o rezolvare dar, ın situatii complexe, ea poate fi totusi de durata sinu este firesc sa se piarda ıntregul efort de procesare anterior.

Pentru a oferi o solutie efectiv practica ar trebui ca solverul responsabilcu rezolvarea problemei sa poata face fata la situatiile enumerate anterior ınmod eficient, exploatand cat mai mai mult din rezultatul obtinut anteriorın ıncercarea de generarea a unei noi solutii care sa satisfaca specificatiileactuale ale problemei.

In capitolul urmator vom analiza aspectele construirii unui solver CSPinteractiv.

Capitolul 8

Rezolvarea interactiva aproblemelor

La ora actuala rezolvarea problemelor modelate cu constrangeri a fost abor-data prin prisma faptului ca reteaua obtinuta ın urma etapei de modelareeste ın forma sa finala, fiind astfel statica pe durata procesului de rezolvare.Intr-o serie de lucrari din domeniul inteligentei artificiale [32], [23] E. Lamma,M. Gavanelli si altii propun un cadru de lucru interactiv pentru problemele desatisfacere a constrangerilor (ICSP) ın care domeniile variabilelor sunt popu-late dinamic pe masura executiei algoritmului de obtinere a solutiei. In acestearticole dedicate ın special sistemelor de recunoastere vizuala, datele proble-mei sunt obtinute printr-un mecanism de ”achizitionare a informatiilor” carese desfasoara concurent cu procesul de rezolvare.

In capitolul dedicat problemei orarului a fost pusa ın evidenta necesitateainteractivitatii si din alte perspective derivate din faptul ca structura prob-lemei se poate schimba chiar pe parcursul executiei sau ulterior rezolvariiacesteia, caz ın care ar fi de preferat reutilizarea efortului computationaldepus pentru obtinerea solutiei anterioare ıntr-o masura cat mai mare.

In lucrarea lui M. Sergot, ”A query-the-user facility of logic program-ming” [47], acest lucru este sintetizat astfel: ”Este nerezonabil si nerealistsa fortam utilizatorul sa anticipeze si sa furnizeze ın avans toate informatiilenecesare rezolvarii unei probleme”. Un sistem de lucru eficient trebuie saofere posibilitatea schimbarii datelor problemei cu un efort minim de calcul.

Astfel, un solver CSP interactiv trebuie sa permita urmatoarele lucruri:

• Oprirea temporara a executie si reluarea acesteia la un moment ulterior

153

154CAPITOLUL 8. REZOLVAREA INTERACTIVA A PROBLEMELOR

• Salvarea si restaurarea starii ın forma persistenta

• Extinderea starii curente prin decizii externe (manuale)

• Anularea manuala a unor decizii luate de solver

• Eliminarea (inactivarea) unor variabile

• Adaugarea de noi variabile

• Adaugarea, eliminarea sau modificarea constrangerilor.

8.1 Starea unui solver

Fie R = (X,D, C) o retea de constrangeri corespunzatoare unei problemeoarecare, unde X = x1, ..., xn si D = D1, ..., Dn. Dupa cum am mai spus,obtinerea unei solutii a retelei R prin intermediul unui algoritm sistematicpoate fi vazuta ca o succesiune finita de transformari R = R0 → R1 → ...→Rf , unde Ri si Rj sunt echivalente iar Ri+1 ≺ Ri (ın sensul ca spatiul decautare al lui Ri+1 este mai mic decat al lui Ri) iar Rf are toate domeniileformate dintr-un singur element, etapa de transformare Ri → Ri+1 fiindrealizata prin luarea unor decizii de instantiere si propagarea acestora asupradomeniilor variabilelor.

Ridecizie−−−−−−−−−−−→

propagare/filtrareRi+1

Deoarece este posibil ca procesul de rezolvare sa aiba ıntoarceri este necesar caınainte de trecerea de la Ri la Ri+1 ca urmare a instantierii x = a sa memorampe Ri astfel ıncat daca Ri+1 se dovedeste a fi inconsistenta sa putem refaceproblema la momentul deciziei x = a si sa continuam atribuindu-i lui x oalta valoare.

Definitie 17 Vom numi stare sau stare simpla a unui solver CSP o struc-tura S = (α, δ, π, ω) unde:

• α reprezinta variabilele neinstantiate ale problemei (candidatii)

• δ(x) reprezinta domeniul variabilei x, ∀x ∈ X.

8.2. OPRIREA SI RELUAREA EXECUTIEI 155

• π este stiva deciziilor strategiei de ınaintare, cu alte cuvinte multimeavariabilelor carora le-au fost atribuite valori dispuse ıntr-o structura detip stiva, baza fiind prima variabila aleasa de solver iar varful variabilacurenta aflata ın proces de instantiere.

• ω este o tupla reprezentand solutia curenta.

Reteaua initiala ce urmeaza a fi rezolvata va avea starea:

(S0) : α0 = X, δ0(xi) = Di ∀i = 1, n, π0 = ∅, ω0 = ∅

O stare este finala daca:

(Sf ) : αf = ∅, |δf (xi)| = 1 ∀i = 1, n, πf = X, var(ωf ) = X

In definitia de mai sus am presupus ca nu exista o dinamica a con-strangerilor ın trecerea de la o stare la alta. Modelul ın care constrangerilepot fi activate sau nu ın functie de starea solverului introduce un grad sporitde complexitate si nu ıl vom analiza ın continuare.

Definitie 18 Un solver S asociat unei retele consistente R este corectdaca si numai daca exista o succesiune de stari S0 → ...→ Sf cu proprietateaca Sf este finala si ωf este consistenta.

Definitie 19 Un solver S asociat unei reteleR este complet daca si numaidaca oricare ar fi ω o solutie a luiR exista o succesiune de stari S0 → ...→ Sf

cu proprietatea ca ωf = ω.

Definitie 20 Fie S un solver asociat unei retele R si S0 → ...→ Si starilesimple corespunzatoare subproblemelor generate de deciziile luate pana lamomentul curent. Multimea S∗i = S0, ..., Si o vom numi starea extinsa asolverului S.

8.2 Oprirea si reluarea executiei

Pentru a obtine interactivitatea, o conditie esentiala pe care trebuie sa oındeplineasca un solver CSP este posibilitatea de a-i opri temporar executia


ın vederea interogarii sau schimbarii starii sale, dupa care aceasta sa poatafi reluata ulterior. Acest lucru poate fi relizat:

• manual, la momente arbitrare, ın cazul ın care este oferita si interfatagrafica cu utilizatorul

• programatic, la momente prestabilite, cum ar fi: solverul urmeaza sainstantieze o anumita variabila, sau o anumita valoare a fost atribuitaunei variabile sau la anumite intervale de timp.

Deoarece, din punct de vedere teoretic, a doua situatie este un caz particularal primei, vom analiza varianta opririi manuale.

Fara a detalia deocamdata implicatiile alterarii starii solverului, sa vedemcum poate fi implementat din punct de vedere practic un mecanism de oprire-pornire a procesului de rezolvare.

O prima conditie esentiala este lansarea algoritmului ıntr-un fir de executiepropriu, de tip daemon (worker) care sa depinda si sa poata fi accesat de unalt fir de tip controller [19].

Thread worker = new Thread(new Runnable()

public void run()

// pornim solverul

solver.solve();

);

worker.setDaemon(true);

worker.start();

In al doilea rand trebuie sa existe o metoda care sa notifice firul de executieal algoritmului ca se doreste ıntreruperea temporara a sa. OmniCS ofera osolutie simpla bazata pe o variabila de control paused si mecanismul wait -

notify de sincronizare a firelor concurente. Variabila de control este accesataprin metoda setPaused care va genera si evenimentele corespunzatoare ıncazul ın care sunt ınregistrati observatori.

public synchronized void setPaused(boolean paused)

this.paused = paused;

if (paused)

if (firingEvents)

eventHandler.fireSolverPaused();

8.2. OPRIREA SI RELUAREA EXECUTIEI 157

System.out.println("Solver paused.");

else

notify();

if (firingEvents)

eventHandler.fireSolverResumed();

System.out.println("Solver resumed.");

Metoda principala a solverului trebuie doar sa verifice valoarea variabileide control paused si sa opreasca temporar executia daca este cazul:

while (running)

synchronized(this)

while (paused)

try

wait();

catch(InterruptedException e)

System.err.println(e);

if (!running) break;

...

Plasarea secventei de oprire este importanta deoarece trebuie sa garantezeurmatorul invariant: ”toate variabilele din π sunt instantiate”.

Astfel, oprirea solverului se va face prin apelul solver.setPaused(true),iar reluarea acestuia prin solver.setPaused(false). Intre aceste apeluriobiectul solver este disponibil si expune starea sa curenta precum si metodepentru actualizarea ei respectiv revenirea la una din starile anterioare.

In cazul ın care se intervine din exterior asupra unei stari a solveruluiacesta ısi poate pierde proprietatile de completitudine si corectitudine.


8.3 Salvarea si restaurarea starii extinse

In situatiile ın care rezolvarea unei probleme este de lunga durata (ore, sauchiar zile) exista riscul ca unitatea de calcul sa devina indisponibila si sis-temul de operare sa nu fie capabil sa asigure automat persistenta procesuluirespectiv. Pentru a rezolva aceasta problema, ar fi de dorit ca solverul saofere un mecanism propriu de persistenta care sa salveze la cerere sau au-tomat la intervale de timp prestabilite starea sa extinsa astfel ıncat, dacaeste cazul, executia sa poata fi reluata de la un anumit punct.

OmniCS utilizeaza algoritmul standard de serializare a obiectelor pentrua salva starea extinsa a procesului de rezolvare. Utilizarea optiunilor desalvare-restaurare este extrem de simpla si se face astfel:

// Crearea unui solver pentru problema initiala

solver = problem.createSolver();

...

// Salvarea starii intr-un fisier extern

solver.save(filename);

...

// Crearea unui solver care preia

// starea celui salvat in fisier

solver = problem.createSolver(filename);

8.4 Extinderea starii curente

Extinderea manuala a starii curente semnifica efectuarea unei decizii care nurespecta regulile definite de strategiile de ınaintare si instantiere. Aceastaoperatiune nu afecteaza ın nici un fel comportamentul solverului, actiunileefectuate fiind descrise ın algoritmul 21.

Solverul OmniCS ofera metoda instantiate(Var x, Object a) careefectueaza extinderea starii curente prin instantierea x = a.

8.5 Anularea unor decizii

Dupa cum stim rezolvarea sistematica a unei probleme presupune explorareaarborelui corespunzator spatiului solutiilor. Determinarea rapida a subar-borilor ale caror frunze nu sunt consistente reprezinta un factor important

8.6. INACTIVAREA UNOR VARIABILE 159

Algorithm 21 Extinderea starii curente (instantiate)

Intrare: Si = (αi, δi, πi, ωi) starea curenta a solverului si x = a o instantiere,a ∈ δi(x)

Rezultat: Si+1 starea obtinuta dupa efectuarea deciziei x = a.Actualizam multimea candidatilorαi+1 = αi − xActualizam stiva variabilelor instantiateπi+1 = πi ∪ xActualizam solutia partialaωi+1(x) = aDomeniul variabilei x devine singletonδi+1(x) = aAplica algoritmii de filtrare si propagare

ın eficientizarea algoritmului general, dar acest lucru nu este simplu. Inconditiile ın care exista ınsa o reprezentare vizuala, interactiva a procesu-lui de rezolvare, acesta poate fi ”ajutat” din exterior sa evite parcurgereaunor portiuni din arbore care nu contin solutii si pe care nu le-a identificatautomat ın mod corespunzator datorita complexitatii constrangerilor. Un ex-emplu sugestiv este oferit de problema orarului ın care operatorul uman poatesa observe anumite decizii care nu sunt viabile si sa le anuleze, directionandsolverul catre alt spatiu de cautare.

Anularea unei decizii x = a a solverului presupune urmatoarele etape:

1. Identificarea starii simple anteriore deciziei

2. Anularea tuturor deciziilor care au urmat lui x = a, inclusiv

3. Reefectuarea deciziilor anulate, cu exceptia lui x = a

Solverul OmniCS ofera metoda revoke(Var x) care efectueaza anulareainstantierii variabilei x.

8.6 Inactivarea unor variabile

Inactivarea unor variabile este echivalenta cu eliminarea acestora din proce-sul de rezolvare. Acest lucru se realizeaza prin simpla eliminare a lor dinmultimea candidatilor si instantierea lor cu valoarea null.


Algorithm 22 Anularea unei decizii (revoke)

Intrare: Si = (α, δ, π, ω) starea curenta a solverului si x = a o instantierecare trebuie anulata

Rezultat: S ′i+1 starea obtinuta dupa anularea deciziei x = a.if x ∈ π thenx face parte din solutia initialaα = α ∪ xω = ω − xδ(x) = Dx Refacem domeniul initial al lui xreturn

end ifx e o variabila instantiata de solverA = ∅ A este multimea instantierilor de dupa x = ay = peek(π)k = iwhile x 6= y do

b = ω(y)A = A ∪ (y = b)π = π − yy = peek(π)k = k − 1

end whileRefacem starea solveruluiS = Sk

Anulam deciziaα = α ∪ xω = ω − xEfectuam din nou celelate instantierifor (y = b) ∈ A do

S =instantiate(S, y, b)end for

8.7. ADAUGAREA DE NOI VARIABILE 161

Algorithm 23 Inactivarea unor variabile

Intrare: S∗k = S0, ..., Sk starea extinsa a unui solver si x o noua variabila.Rezultat: S∗

′

k starea obtinuta dupa inactivarea lui x.for i = 0, k do

αi = αi − xωi(x) = null

end for

Solverul OmniCS detecteaza daca metoda removeVariable a clasei Problemeste apelata ın timpul executiei si inactiveaza respectiva variabila prin inter-mediul apelului setActive(false), dupa care actualizeaza starile sale.

8.7 Adaugarea de noi variabile

Adaugarea sau reactivarea unor variabile presupune actualizarea multimiicandidatilor pentru fiecare stare a solverului.

Algorithm 24 Adaugarea de noi variabile

Intrare: S∗k = S0, ..., Sk starea extinsa a unui solver si x o noua variabilasau o variabila inactiva.

Rezultat: S∗′

k starea obtinuta dupa adaugarea/reactivarea lui x.for i = 0, k do

αi = αi ∪ xωi = ωi − x

end for

Solverul OmniCS detecteaza daca metoda addVariable a clasei Problemeste apelata ın timpul executiei si realizeaza actualizarea starilor sale. Incazul ın care variabila exista dar era inactiva, ea va fi reactivata prin apelulsetActive(false).

8.8 Modificarea constrangerilor

Modificarea constrangerilor initiale ale problemei presupune urmatoarele etape:

1. Anularea tuturor deciziilor


3. Reefectuarea tuturor deciziilor, atat timp cat acest lucru este posibil.

Algorithm 25 Modificarea constrangerilor

Intrare: S∗k = S0, ..., Sk starea extinsa a unui solver asociat retelei R =(X,D, C) si C ′ un set de constrangeri.

Rezultat: S ′ starea aferenta retelei R = (X,D, C ′) cu proprietatea ω(x) =ω′(x), ∀x ∈ var(ω′)S ′0 = S0

i = 1for (y, b) ∈ ωk do

if b ∈ δ′i(y) thenS ′i = instantiate(Si, y, b)

end ifend for

8.9 Concluzii

Introducerea mecanismelor care sa asigure interactivitatea s-a dovedit extremde importanta ın procesul de rezolvare a problemei orarului, aceasta fiind unexemplu elocvent de situatie ın care definitia problemei este dinamica iarrezolvarea ei se poate face mult mai eficient daca este permisa si interventiautilizatorului.

Capitolul 9

Probleme de colorare

9.1 Introducere

Colorarea grafurilor [9], [25], [14], [35], are o importanta deosebita ın dome-niul optimizarii combinatoriale deoarece numeroase probleme pot fi mod-elate sub aceasta forma. Problemele de colorare sunt ın cazurile generaleNP-dificile, ceea ce a determinat dezvoltarea de numeroase tehnici de re-zolvare a acestora, specializate pe diferite tipuri de colorari sau grafuri. Inaceast capitol este prezentata o solutie generala de abordare a algoritmilorde colorare sub forma unor probleme de satisfacere a constrangerilor, caresa poata fi folosita pentru cazul general dar si pentru diverse tipuri special-izate de colorari, atat ın varianta explorarii sistematice a grafului cat si subforma de euristici. Sunt descrise situatii concrete de implementare pentrulist-coloring, star-coloring, acyclic-coloring si harmonious-coloring precum simodalitatea de integrare a unor algoritmi clasici ın acest cadru de lucru.

Prin colorarea unui graf se ıntelege ın general procesul de asignarea a unor”culori”, reprezentate uzual sub forma unor numere ıntregi, elementelor de unanumit tip din respectivul graf cum ar fi varfuri, muchii, fete sau combinatiiale acestora, astfel ıncat sa fie satisfacute o serie de conditii. Problemele decolorare au numeroase aplicatii atat teoretice cat si practice, fiind de multeori rezultatul formalizarii unor probleme concrete de optimizare ınsa, datoritadificultatii de rezolvare a acestora, gasirea de algoritmi eficienti si de tehnicigenerale de lucru formeaza ın continuare un domeniu activ de cercetare.

Ne propunem ın continuare sa descriem un cadru general de rezolvare aproblemelor de colorare folosind paradigma de programare cu constrangeri.

163

164 CAPITOLUL 9. PROBLEME DE COLORARE

In cadrul acestei abordari este necesar sa analizam urmatoarele aspecte im-portante:

• Gasirea unei solutii generale de modelare a problemele de colorare subforma unor instante CSP.

• Implementarea unei strategii cat mai flexibile de cautare a solutiilorcare sa poata fi parametrizata si adaptata fiecarui tip de colorare ınparte.

9.2 Colorarea grafurilor

Problema colorarii poate fi definita pe diferite tipuri de elemente constitu-ive ale grafurilor dar, uzual, ne referim la colorarea varfurilor, acesta fiindcazul cel mai important si din perspectiva faptului ca majoritatea celorlaltetipuri de colorari pot fi transformate ıntr-o forma echivalenta de colorare avarfurilor. Astfel, colorarea muchiilor unui graf G poate fi rezolvata prin col-orarea nodurilor line-grafului L(G) iar colorare fetelor unui graf planar esteechivalenta cu colorarea varfurilor grafului dual.

Desi ın continuare vom analiza doar probleme de colorare a varfurilor,acest lucru nu trebuie privit ca o restrictie pe care o vom impune sistemuluipe care dorim sa-l prezentam. Dimpotriva, unul din scopurile acestei lucrarieste de a gasi modalitati de a specifica si rezolva probleme de diferite tipuricare sa pastreze cat mai mult specificatiile initiale astfel ıncat, pe parcur-sul procesului de cautare a solutiilor sa poata fi puse ın evidenta diferiteproprietati ale grafului analizat cu impact asupra colorarii finale.

Fie G = (V, E) un graf. O p-colorare proprie [9] a lui V , unde p ∈ N∗

poate fi definita ca o functie c : V → 1, 2, ..., p cu proprietatea ca c(vi) 6=c(vj) ∀vivj ∈ E. Cu alte cuvinte, functia c defineste o partitie a varfurilorgrafului ın p multimi stabile. Numarul minim de culori necesare unei colorariproprii a unui graf G va fi numit numarul cromatic al grafului si va fi notatχ(G).

χ(G) = minp ∈ N∗ | G admite o p-colorare

Evident, se pune problema determinarii lui χ(G) pentru un graf oarecare G,lucru echivalent cu a raspunde la urmatoarea problema de decizie (COL):

9.2. COLORAREA GRAFURILOR 165

COL: ”Fie G = (V, E) si p ∈ N∗. Exista o p-colorare a lui G ?”

Este binecunoscut faptul ca problema COL este NP-completa si, mai mult,ea ramane NP-completa si ın varianta simplificata ın care p = 3, ceea ce puneın evidenta dificultatea rezolvarii problemelor de colorare a varfurilor unuigraf.

Datorita acestei dificultati au fost elaborate numeroare modalitati deabordare a problemelor de colorare, majoritatea sub forma de euristici alcaror scop este nu sa gaseasca solutia exacta ci sa se apropie cat mai mult deea, exemple de astfel de tehnici incluzand tehnici de programare evolutiva, al-goritmi genetici, algoritmi stochastici, etc. Cu toate acestea, ın unele situatiieste necesara gasirea exacta a solutiei asa ıncat trebuie analizate modalitatieficiente de rezolvare si ın aceste cazuri; amintim aici programarea semi-definita si algoritmii sistematici de cautare ımbunatatiti cu diferite tehnicide reducere a spatiului solutiilor. Eventual, metodele sistematice de cautarepot fi combinate cu diferite euristici pentru a obtine rezultate optime ın pro-cesul de colorare.

Un alt aspect care trebuie luat ın calcul este acela ca multi dintre algorit-mii care au fost propusi pana ın prezent sunt dedicati fie cazului general alproblemei colorarii varfurilor unui graf, fie unor cazuri specializate, adaptareaacestora la alte situatii fiind dificil sau chiar imposibil de realizat. Multe prob-leme de optimizare care ın final sunt modelate sub forma unei probleme decolorare impun ınsa diferite restrictii pe care trebuie sa le satisfaca colorareafinala, ceea ce ınseamna ca multi dintre algoritmii implementati deja nu potfi folositi. Astfel de variatiuni includ:

• List coloring - fiecare varf are asociata o lista de culori disponibile,numai acestea putand fi folosite pentru a-l colora.

• Harmonious, Complete, Exact coloring - fiecare pereche de culori poateaparea cel mult / cel putin / exact o data pentru varfurile unei muchii.

• Acyclic coloring - ın colorarea finala orice subgraf 2-cromatic trebuiesa fie aciclic (nici un circuit nu trebuie sa fie bicolor).

• Star coloring - ın colorarea finala nici un drum de lungime 3 nu poatefi bicolor.

• On-line coloring - instanta problemei nu este cunoscuta complet de laınceput ci ea devine disponibila treptat pe parcursul executiei algorit-mului.


• ...Lista poate continua oricat, restrictiile putand fi de orice tip ca rezul-tat al modelarii problemelor concrete de optimizare.

In concluzie, ın analiza pe care o vom face trebuie sa gasim o solutie care sapoata fi adaptata cat mai usor tuturor situatiilor care pot aparea.

Problemele de colorare a varfurilor unui graf se ıncadreaza ın mod firescın domeniul CSP, modelarea unei probleme de colorare prin intermediul uneiretele de constrangeri fiind, ın general, destul de naturala. Sa vedem ıncontinuare cateva cazuri. Fie G = (V, E) un graf oarecare avand varfurileV = v1, ..., vn.

a. p-Colorarea unui grafX = v1, ...vnDi = 1, ..., p, ∀i ∈ 1, ..., nCvivj

= c(vi) 6= c(vj), ∀(vi, vj) ∈ E(G)

b. List-coloringX = v1, ...vnDi = Lista de culori asociata varfului vi , ∀i ∈ 1, ..., nCvivj

= c(vi) 6= c(vj), ∀(vi, vj) ∈ E(G)

c. Star-coloring (nici un P3 nu trebuie sa fie bicolor)X = v1, ...vnDi = 1, ..., p, ∀i ∈ 1, ..., nCvivj

= c(vi) 6= c(vj), ∀i 6= jCvivjvk

= |c(vi), c(vj), c(vk)| = 3, ∀vi, vj, vk = P3

d. Acyclic-coloring (Nici un circuit nu trebuie sa fie bicolor)C =? (exprimarea constrangerii nu mai e evidenta)

Dupa cum se observa ın situatiile de mai sus, specificarea retelei de con-strangeri poate fi extrem de usor de realizat ın cazul unor probleme, con-strangerile fiind obtinute direct din structura grafului analizat (situatiile asi b). In cazul c), este necesara o procesare initiala a grafului pentru deter-minarea varfurilor care formeaza drumuri induse cu 3 varfuri (P3) si, pe baza

9.3. REZOLVAREA UNOR PROBLEME DE COLORARE 167

acestora, vor fi adaugate corespunzator noi constrangeri. In ultimul caz ınsadescrierea constrangerilor prin expresii simple ıntre varfuri este mai greu derealizat, ceea ce ne determina la reconsiderarea modalitatii de exprimare aconstrangerilor fata de cea clasica.

9.3 Rezolvarea unor probleme de colorare

9.3.1 Colorarea varfurilor unui graf

Colorarea unui graf presupune definirea conditiei prin care doua noduri nupot avea aceeasi culoare. Aceasta va fi folosita si ın celelalte tipuri de colorare,decuplarea modului de specificare a constrangerilor de problema propriu-zisapermitand asadar reutilizarea codului. Specificarea acestei conditii poate fifacuta utilizand constrangerea predefinita NotEqual: pentru fiecare perechede varfuri adiacente ale grafului impunem ca valorile variabilelor asociate sanu fie egale:

for((x,y) in E(G))

problem.addConstraint(new NotEqual(x,y));

9.3.2 Star-coloring

O abordare similara va fi folosita si ın aceast tip de colorare, cu deosebirea catrebuie sa facem o procesare initiala prin intermediul carei sa identificam dru-murile de lungime 3 ale grafului si sa cream constrangerile corespunzatoare:

// Nici un P3 nu trebuie sa fie bicolor

class StarColoring extends Constraint

Var x, y, z;

StarColoring(Var x, Var y, Var z)

this.x = x;

this.y = y;

this.z = z;


if (!tuple.contains(x, y, z)) return ALLOWED;


int xColor = (Integer)tuple.get(x);

int yColor = (Integer)tuple.get(y);

int zColor = (Integer)tuple.get(z);

if (xColor != yColor &&

xColor != zColor &&

yColor != zColor)

return ALLOWED;

return FORBIDDEN;

...

for((x,y) in E(G))


for((x,y,z) P3 indus in G)

problem.addConstraint(new StarColoring(x,y,z));

9.3.3 Acyclic-coloring

In aceasta situatie colorarea finala trebuie sa satisfaca conditia ca nici uncircuit sa nu fie bicolor. Exprimarea acestei conditii sub forma unor expresiiıntre variabile este dificil de realizat deoarece ar presupune aflarea ın prealabila tuturor circuitelor si impunerea tuturor constrangerilor folosind variabilelecorespunzatoare acestora. Alegerea unei strategii corecte de ınaintare nepoate reduce ın acest caz semnificativ complexitatea procesului de descriere aconditiei. Astfel, ınaintand conform strategiei ConnectedComponents putemidentifica circuitele grafului pe masura ce acestea se formeaza ıntre nodurileinstantiate deja si doar ın momentul formarii sa testam conditia impusa.

// Nici un circuit nu trebuie sa fie bicolor

class AcyclicColoring extends UnaryConstraint

Var x;

AcyclicColoring(Var x)

this.x = x;


9.3. REZOLVAREA UNOR PROBLEME DE COLORARE 169

/*

Daca x este adiacent cu un alt nod din tupla,

conform strategiei de inaintare s-a format un circuit.

Determinam circuitul format si verificam daca este bicolor.

*/

...

...

for((x,y) in E(G))


for(x in V(G))

problem.addConstraint(new AcyclicColoring(x));

...

solver.setForwardStrategy(new ConnectedComponents());

9.3.4 Harmonious-coloring

Colorarea ”armonioasa” impune ca o pereche de culori sa nu poata apareadecat la cel mult extremitatile unei muchii. In acest caz, tehnica de rezolvareeste aceea de a mentine o structura globala, externa algoritmului propriu-zisdar accesibila strategiilor de ınaintare si ıntoarcere, ın care sa fie retinuteperechile de culori folosite deja ın colorare.

Map<Integer,List<Integer>> globalPairs;

...

class HarmoniousColoring extende BinaryConstraint

Var x, y;

HarmoniousColoring(Var x, Var y)

this.x=x;

this.y=y;


if (!tuple.contains(x, y)) return ALLOWED;

int xColor = (Integer)tuple.get(x);

int yColor = (Integer)tuple.get(y);


boolean ok = globalPairs.get(xColor).contains(yColor);

return (ok ? ALLOWED : FORBIDDEN);

...

// La inaintare adaugam noi perechi de culori in globalPairs

solver.setForwardStrategy(

new HarmoniousForward(globalPairs));

// La intoarcere eliminam perechi de culori din globalPairs

solver.setBackwardStrategy(

new HarmoniousBackward(globalPairs));

9.4 Euristici de colorare

Folosind acest sistem de lucru, o serie de euristici clasice de colorare cumar fi colorarea ”Greedy” a unui graf pot fi implementate doar prin simplaparametrizare a algoritmului general. Astfel, pentru a implementa o colorarede tip greedy, este suficient sa definim o strategie de ıntoarcere care sa nu facade fapt o ıntoarcere propriu-zisa ci sa rescrie dinamic domeniile variabilelorramase de instantiat adaugandu-le o noua culoare disponibila si continuandapoi algoritmul general.

public class Greedy extends AbstractStrategy

implements BackwardStrategy

...

public Var back()

// Nodul in care ne-am blocat

Var current = solver.current();

// Crestem nr de culori

nc ++;

// Rescriem dinamic domeniile

solver.solution().put(current, nc);

for(Var var : candidates)

var.getDomain().add(nc);

9.5. ANALIZOARE DE PROBLEMA 171

// Nu facem nici o intoarcere

return current;

9.5 Analizoare de problema

Pentru a eficientiza procesul de cautare a unei solutii, un solver CSP tre-buie sa permita integrarea unor algoritmi dedicati unor cazuri particulareale problemei ın cadrul algoritmului general de rezolvare astfel ıncat atuncicand subproblema ramasa de rezolvat face parte dintr-o astfel de clasa sapoata fi utilizati respectivii algoritmi. De exemplu, ın cazul colorarii grafu-rilor, putem utiliza algoritmi eficienti de recunoastere a unor clase specifice degrafuri [12], dupa care sa folosim proprietatile acestora pentru a crea strategiiımbunatatite de explorare a spatiului solutilor.

Un analizor de problema este o componenta a solverului CSP dedicataunei anumite probleme responsabila cu:

1. Identificarea unor cazuri speciale ale problemei care se ıncadreaza ınclase pentru care exista algoritmi eficienti de rezolvare.

2. Determinarea inconsistentei problemei folosind tehnici specifice respec-tivei clasei speciale.

3. Punerea la dispozitia solverului CSP a unui algoritm dedicat de re-zolvare care sa poata fi utilizat ın mod automat pentru extindereasolutiei curente.

Solverul OmniCS ofera o modalitate extrem de simpla de definire a unuianalizor de problema prin intermediul interfetei Analyzer care descrie lamodul abstract comportamentul unui analizor, respectiv a clasei DefaultAnalyzercare implementeaza comportamentul standard si poate fi folosita prin extin-dere pentru diverse cazuri particulare.

Dupa cum am vazut la ınceputul capitolului, modelarea unei probleme decolorare a varfurilor unui graf ın cazul general este realizata foarte simplu,printr-o secventa de tipul celei de mai jos:

for((x,y) in E(G))



Fara a oferi solverului posibilitatea de a identifica situatii particularecomportamentul general poate fi extrem de ineficient si fara modalitati simplede ımbunatatire. Sa consideram cazul ın care graful de intrare este complet,avand 10 varfuri si cerem solverului sa realizeze o colorare cu 9 culori:

Graph g = GraphFactory.createComplete(10);

OmnicsGraphColoring col = new OmnicsGraphColoring(g, 9);

Desi rezolvarea problemei este evidenta, solverul va efectua nu mai putinde 260.650 backtrack-uri pentru a ajunge la aceasta concluzie, lucru carenu este deloc multumitor. Evident, ın cazul ın care am fi identificat cazulparticular si adaugam o constrangere de tipul AllDiff inconsistenta ar fi fostdeterminata imediat. De asemenea, prezenta unui mecanism de identificaresi eliminare a simetriilor (Symetry Breaking During Search) [24], [15] ar firedus numarul de esecuri ale algoritmului.

O prima solutie care se contureaza din exemplul de mai sus ar fi creareaunui analizor responsabil cu identificarea grafurilor complete ın procesul derezolvare. Acesta va realiza urmatoarele actiuni:

1. Determina daca subgraful G1 indus de varfurile deja colorate este com-plet si, ın caz afirmativ, adauga o constrangere AllDiff pentru ele.

2. Determina daca subgraful G2 indus de varfurile ramase de colorat estecomplet si, ın caz afirmativ, adauga o constrangere AllDiff pentru ele.

3. In cazul ın care G2 este complet, determina numarul de culori k folositepentru colorarea varfurilor adiacente celor din G2 si verfica daca nucumva k + |V (G2| depaseste numarul de culori pe care le avem ladispozitie; ın caz afirmativ, semnaleaza inconsistenta subproblemei.

4. In cazul ın care G2 este complet si problema nu este inconsistenta, oferaun algoritm liniar pentru problema de list-colorare a grafului completG2.

Implementarea doar a primelor trei puncte din cele de mai sus, corelata cuo strategie de ınaintare ın care sunt alese mai ıntai varfurile cu grad mai mic,a adus la ımbunatatiri spectaculoase ın colorarea grafurilor dense, reducandnumarul de backtrack-uri cu factori de ordinul 103 sau chiar 104. Clasa caredescrie analizorul pentru grafuri complete este prezentata partial mai jos:

9.5. ANALIZOARE DE PROBLEMA 173

public class CompleteGraphAnalyzer extends DefaultAnalyzer

SystematicSolver solver;

Graph graph;

int nc; //numarul de culori cu care efectuam colorarea

public CompleteGraphAnalyzer(Graph graph, int nc)

this.graph = graph;

this.nc = nc;

public void init()

solver = (SystematicSolver)problem.getSolver();

public boolean isInconsistent()

if (super.isInconsistent())

return true;

Graph g1 = currentSubgraph();

Graph g2 = remainingSubgraph();

if(g1.isComplete() && g1.N() > 2)

insertAllDiff(solver.solution().variables());

if (g2.isComplete() && g1.N() > 2)

NodeSet adj = g2.nodes().neigbors();

// Numar culorile folosite in adj

Set<Integer> colors = new HashSet<Integer>();

for(Node u : adj)

Var var = (Var) u.getData();

colors.add((Integer)var.getValue());

int used = colors.size();

if (g2.N() + used > nc)

// problema nu este consistenta

return true;

AllDiff alldiff = insertAllDiff(new VarSet(solver.candidates()));

if (alldiff.eval(solver.solution()) == FORBIDDEN)

return true;


return false;

...

Adaugarea analizorului de problema se face extrem de simplu:

SystematicSolver solver = pb.createSolver();

solver.addAnalyzer(

new CompleteGraphAnalyzer(graph, nbOfColors));

Din pacate, ın cele mai multe situatii problema colorarii subgrafului indusde variabilele neinstantiate este o problema de list-colorare care, ın cele maimulte cazuri, sunt NP-complete. Pentru a da doar doua exemple:

• grafuri bipartite (Hujter si Tuza (1993))

• cografuri (Jansen si Scheffler (1997))

Analiza modalitatilor de integrare a unor algoritmi eficienti ın procesulgeneral de colorare ramane ın continuare una din directiile principale decercetare pe aceasta tema.

Capitolul 10

Concluzii

Lucrarea de fata ısi propune ca principala directie de cercetare crearea unuicadru de lucru care sa permita modelarea cu ajutorul constrangerilor a unorprobleme din domenii diverse si rezolvarea automata, eventual interactiva aacestora. Pentru eficientizarea procesului de determinare a solutiei ın cazulproblemelor NP-dificile s-a avut ın vedere posibilitatea de integrarea a unoralgoritmi dedicati unor cazuri particulare ale problemei ın cadrul algoritmuluigeneral.

In prima parte au fost analizate atat din punct de vedere teoretic cat sidin perspectiva implementarii aspecte generale legate de tehnici de rezolvarea instantelor CSP, cum ar fi algoritmii de arc-consistenta AC-3, AC-4 saumecanisme de ıntoarcere controlata (backjumping).

Contributia proprie a tezei consta ın crearea solverului CSPOmniCS 1 (Omni Constraint Solver), prezentarea acestuia fiind partea cen-trala a lucrarii. Elementele de noutate constau ın:

• Crearea unei arhitecturi originale care sa permita modelarea si re-zolvarea atat a problemelor clasice de satisfacere a constrangerilor catsi a celor slabe (Soft CSP).

• Realizarea implementarii pe baza unor sabloane de proiectare softwareconsacrate, precum si utilizarea celor mai noi tehnici de programareorientata-obiect oferite de platforma de lucru Java. Acestea fac dinOmniCS un solver extrem de simplu de folosit si de ınteles, fiind usorde integrat ın activitati didactice sau de cercetare.

1http://omnics.sourceforge.net

175

176 CAPITOLUL 10. CONCLUZII

• Nivelul algoritmic al solver-ului propriu-zis este foarte flexibil, putandfi parametrizat atat din punctul de vedere al strategiilor de explo-rare cat si din punctul de vedere al algoritmilor de reducere a prob-lemei. Abordarea originala consta ın faptul ca pot exista algoritmi defiltrare-propagare globali dar si locali, asociati fiecarei constrangeri ınparte. Desi aceasta parametrizare poate induce o penalizare la nivelulperformantei, testele comparative cu solutii similare existente pe piataau aratat ca OmniCS este comparabil cu acestea, chiar mai rapid ınunele situatii.

• In abordarea problemelor supra-constranse a fost conceputa o solutieproprie de generare a unor structuri de date din care sa poata fi extraseinformatii necesare explicarii insatisfiabilitatii.

• Introducerea mecanismelor de interactivitate permit integrarea solveru-lui ın cadrul unor interfete cu utilizatorul cu ajutorul carora sa poata ficontrolat procesul de rezolvare sau chiar modificat enuntul problemeifara repornirea solverului. In acest context, sunt studiate proprietatilede corectitudine si completitudine ale unui solver CSP.

• A fost introdusa si notiunea de analizor de problema capabil sa iden-tifice ın procesul de rezolvare a unei instante NP-dificile subproblemerezolvabile polinomial, sa ofere solutii dedicate acestora si sa integrezerezultatul obtinut ın algoritmul general.

In partea a doua a lucrarii sunt prezentate trei studii de caz ın utilizareasolverului OmniCS, care sa puna ın evidenta caracteristicile si performanteleacestuia:

• Problema satisfiabilitatii (3-SAT), ın care este descrisa o nouatehnica de abordare a acesteia sub forma unei probleme de clica de car-dinal maxim ıntr-un graf corespunzator. Desi modelul teoretic rezultateste complex, flexibilitatea oferita de OmniCS a permis rezolvarea cusucces a problemei, tinand cont de toate proprietatile rezultate ın urmaanalizei grafului.

• Problema orarului, care pune ın evidenta aspectele dinamice si in-teractive ale solverului precum si moduri de definire a constrangerilorglobale care au algoritmi proprii de filtrare. Introducerea unor strate-gii eficiente de explorare a spatiului solutiilor a permis rezolvarea unor

177

probleme cu peste 300 de evenimente si 20.000 de constrangeri ıntr-untimp de ordinul minutelor.

• Probleme de colorare a grafurilor, ın care sunt prezentate ın modunitar diverse tipuri de colorare a grafurilor, modelarea lor folosindOmniCS precum si asocierea unor analizori de problema care sa sim-plifice procesul de rezolvare. Testele facute pe colorarea grafurilor densedemonstreaza eficienta acestei solutii.

Ca directii viitoare de cercetare ne propunem:

• Definirea unei modalitati declarative de specificare a constrangerilor,prin intermediul unui limbaj dedicat;

• Crearea unei librarii extinse de constrangeri, care sa includa algoritmidedicati de filtrare specifici constrangerilor globale;

• Crearea unei librarii de analizoare dedicate pentru diverse clase derestrictii polinomiale ale unor probleme NP-complete;

• Crearea unui mecanism de ınvatare cu ajutorul caruia sa poata fi creatao baza de date cu explicatii pentru diferite probleme, care sa poata ficonsultata de solver ın procesul de rezolvare.

Fiecare din aceste aspecte presupune provocari complexe atat din punctde vedere teoretic cat si practic, ınsa importanta domeniului si interesul gen-eral de care se bucura sunt motivatii suficiente pentru a le aborda, continuandsi rafinand rezultatele obtinute pana acum.

178 CAPITOLUL 10. CONCLUZII

Bibliografie

[1] Krzysztof Apt. Principles of constraint programming. Cambridge Uni-versity Press, 2003.

[2] Roman Bartak. On-line guide to constraint programming.http://kti.ms.mff.cuni.cz/ bartak/constraints/index.html.

[3] Roman Bartak. Constraint propagation and backtracking-based search.First International Summer School on Constraint Programming Italy,September 11-15 2005.

[4] Claude Berge. Graphes et Hypergraphes. Dunod, Paris, 1970.

[5] Stefano Bistarelli. Semirings for Soft Constraint Solving and Program-ming. Springer, 2004.

[6] Yves Caseau and Francois Laburthe. Palm. http://www.e-constraints.net/palm.

[7] Tim B. Cooper and Jeffrey H. Kingston. The complexity of timetableconstruction problems. In Proceedings of the First International Con-ference on the Practice and Theory of Automated Timetabling (ICPTAT’95), pages 511–522, 1995.

[8] Auton L.D. Crawford J.M. Experimental results on the crossover pointin random 3sat. Artificial Intelligence, No. 81, 1996.

[9] Cornelius Croitoru. Tehnici de baza in optimizarea combinatorie. Edi-tura Universitatii ”Al. I. Cuza” Iasi, 1992.

[10] Cornelius Croitoru and Cristian Frasinaru. Exploring unknown undi-rected graphs. Scientific Annals of Al.I.Cuza Iasi University, 8:67–76,1998.

179

180 BIBLIOGRAFIE

[11] Cornelius Croitoru and Cristian Frasinaru. A new approach for solv-ing satisfiability problems. International Conference on Mathematics &Informatics ICMI 45 Bacau, Romania, September 18-20 2006.

[12] Cornelius Croitoru, Cristian Frasinaru, Elefterie Olaru, and Mihai Tal-maciu. Hardly perfect graphs. Scientific Annals of Al.I.Cuza University,14:12–22, 2004.

[13] Rina Dechter. Constraint Processing. Morgan Kaufmann, 2003.

[14] Reinhard Distel. Graph Theory. Springer, 1997.

[15] Torsten Fahle, Stefan Schamberger, and Meinolf Sellmann. Symmetrybreaking. Lecture Notes in Computer Science, 2239:93, 2001.

[16] Eugene C. Freuder. Synthesizing constraint expressions. Communica-tions of the ACM, 21(11):958966, 1978.

[17] Eugene C. Freuder. Partial constraint satisfaction. In Proceedings ofthe Eleventh International Joint Conference on Artificial Intelligence,IJCAI-89, Detroit, Michigan, USA, pages 278–283, 1989.

[18] Cristian Frasinaru. Omnics. http://omnics.sourceforge.net.

[19] Cristian Frasinaru. Curs practic de Java. Matrix Rom Bucuresti, 2005.

[20] Cristian Frasinaru. Dezvoltarea modulara si extensibila a interfetelorweb. RoCHI 2005. A doua Conferinta de Interactiune Om-Calculator.Universitatea Babes-Blyai, Cluj-Napoca., 2:61–66, 2005.

[21] Cristian Frasinaru. Crearea interfetelor grafice folosind constrangeri.RoCHI 2006. A treia Conferinta de Interactiune Om-Calculator. Acad-emia de Studii Economice Bucuresti, 21-22 Septembrie 2006.

[22] Erich Gamma, Richard Helm, Ralph Johnson, and John Vlissides. De-sign Patterns: Elements of Reusable Object-Oriented Software. Addison-Wesley Professional, 1995.

[23] M. Gavanelli, E. Lamma, P. Mello, and M. Milano. Performance mea-surement of interactive CSP search algorithms. In Giornata di LavoroRCRA su “Analisi sperimentale di algoritmi per l’Intelligenza Artifi-ciale”, Rome, Italy, Dec 16 1999.

BIBLIOGRAFIE 181

[24] I. Gent and B. Smith. Symmetry breaking during search in constraintprogramming. Ian P. Gent and Barbara Smith. Symmetry breakingduring search in constraint programming. Report 99.02, University ofLeeds, January 1999.

[25] Frank Harary. Graph Theory. Addison-Wesley, Reading, MA, 1969.

[26] J.E. Hopcroft and R.M. Karp. A n5/2 algorithm for maximum match-ings in bipartite graphs. SIAM Journal on Computing, 2:225–231, 1973.

[27] Ilog. Ilog solver. http://www.ilog.com.

[28] Freeman J.W. Improvements to propositional satisfiability search algo-rithms. Ph.D. Thesis, Department of computer and Information science,University of Pennsylvania, Philadelphia, PA, 1995., 1995.

[29] R. Karp. Reducibility among combinatorial problems. In In R. Millerand J. Thatcher, editors, Complexity of Computer Communications,pages pages 85–103. Plenum Press, 1972.

[30] Koalog. Koalog constraint solver tutorial. http://www.koalog.com.

[31] Francois Laburthe and Narendra Jussien. Choco.http://choco.sourceforge.net.

[32] Evelina Lamma, Paola Mello, Michela Milano, Rita Cucchiara, MarcoGavanelli, and Massimo Piccardi. Constraint propagation and valueacquisition: Why we should do it interactively. In IJCAI, pages 468–477, 1999.

[33] J.-L. Lauriere. A language and a program for stating and solving com-binatorial problems. Artificial Intelligence. An International Journal,10(1):29–127, 1978.

[34] Chu Min Li. Look-ahead versus look-back for satisfiability problems. InProceedings of Third International Conference on Principles and Prac-tice of Constraint Programming (CP97), LNCS, 341-355. Springer Ver-lag., 1997.

[35] Laszlo Lovasz. Combinatorial Problems and Exercises. Elsevier, Horth-Holland, 1993.

182 BIBLIOGRAFIE

[36] Alan K. Mackworth. Consistency in networks of relations. ArtificialIntelligence, 8(1):99118, 1977.

[37] Robert C. Martin. The open-closed principle. C++ Report, SIGS Pub-lications, 1996.

[38] Bertrand Meyer. Object-Oriented Software Construction. Prentice-Hall,1997.

[39] C.Paul M.Habib. A simple linear time algorithm for cograph recognition.Discrete Applied Mathematics, 145:183 197, 2005.

[40] David S. Johnson Michael R. Garey. Computers and Intractability; AGuide to the Theory of NP-Completeness. W.H. Freeman and Company,1979.

[41] Ugo Monatanari. Networks of constraints: Fundamental properties andapplication to picture processing. Information Science, 7(2):95132, 1974.

[42] P. Boizumault N. Jussien, R.Debruyne. Mantaining arc-consistencywithin dynamic backtracking. In Sixth international conference on prin-ciples and practice of constraint programming (CP’2000), 2000.

[43] Christos H. Papadimitriou. Computational Complexity. Addison-Wesley,1994.

[44] Jean-Charles Regin. Global constraints. First International SummerSchool on Constraint Programming Acquafredda di Maratea – Italy,September 11-15 2005.

[45] F. Rossi, P. van Beek, and T. Walsh (editors). Handbook of ConstraintProgramming. Elsevier, 2006.

[46] Thomas Schiex. Soft constraint processing. First International SummerSchool on Constraint Programming, July 2005.

[47] M. Sergot. A query-the-user facility of logic programming. In In Degano,P., Sandwell, E., eds.: Integrated Interactive Computer Systems, NorthHolland, pages 27–41, 1983.

BIBLIOGRAFIE 183

[48] Cook Stephen. The complexity of theorem prooving procedures. Pro-ceedings of 3rd ACM Symp. on Theory of Computing, pages 151–158,1971.

[49] G. Verfaille T. Schiex, H. Fargier. Valued constrained satisfaction prob-lems: hard and easy problems. Proc. of the 14th IJCAI, -:631637, 1995.

[50] Edward Tsang. Foundations of Constraint Satisfaction. Academic Press,1993.

[51] James W.Cooper. The Design Patterns Java Companion. Addison-Wesley, 1998.

probleme algoritmice ˆın studiul propriet˘at¸ilor ...acf/csp/teza.pdf · 3.2 backtracking ......

Documents