Slide 1

Proiectarea algoritmilor

DIVIDE ET IMPERA

Backtraking

Turnurile din Hanoi

Problema Turnurilor din Hanoi a fost introdus n1883 de matematicianul francez Edouard Lucas.

Problema are la baz o legend hindus conform creia zeul Brahma a aezat n templul dinBenares o stiv de 64 de discuri din aur cu diame-tre diferite, aezate n ordine descresctoare adiametrelor.

Clugrii templului au sarcina mutrii discurilor de pe o tij pe alta, folosind o tij auxiliar astfel nct:

Turnurile din Hanoi

Doar un disc aflat n vrful unei tijepoate fi mutat pe alt tij;

Nu este permis aezarea unui disc de dimensiune mai mare peste unul de dimensiune mai mic;

Conform legendei lumea se va sfri cndclugrii i vor termina treaba!

Turnurile din Hanoi

Algoritmul mut n discuri de pe tija A pe tija C folosind tija B.Pentru asta, trebuie mutate n-1 discuri de pe A pe B prin C, ultimuldisc de pe A pe C i apoi n-1 discuri de pe B pe C prin A.

HANOI (n, A, C, B)if n>=1 thenHANOI (n-1, A, B, C) PRINT (AC)HANOI (n-1, B, C, A)Hanoi.cpp

Turnurile din HanoiExemplu (n=2)

Complexitatea algoritmuluiHanoi

Complexitate

7

Metoda greedy

Algoritmii greedy aleg la fiecare moment cel mai bun candidat posibil. Metoda greedy face optimizri locale, cu speranta c acestea vorconduce la un optim global.Aceti algoritmi sunt de obicei rapizi si furnizeaz o solutie relativ bun, car nu ntotdeauna cea mai bun. Forma general a unui algoritm greedy:

GREEDY (C)S=0 while C0 dox = BEST (C) C = C- {x}if FEASIBLE (S U {x}) thenS = S U {x}

Greedy- Problema rucsacului

Se consider c dispunem de un rucsac cu o anumit capacitate G (greutate maxim) i de n obiecte, definite prin greutate g i pre p. S se umple rucsacul cu obiecte, astfel nct valoarea total s fie maxim. Pot fi introduse i fraciuni din obiecte.

Greedy rucsac.cpp

Algoritmul greedy pentru rezolvarea problemei rucsacului const n urmtorii pai:1. v[i] = p[i]/g[i], i = 1,..n;2. sorteaz vectorii v, p, g n ordinea descresctoare a valorilor din v;3. caut k a..

Timpul de execuie al algoritmului este O(n*lg n), deoarece sortarea se execut n O(n* lg n), iar complexitatea operaiei de cutare din pasul 3 este O(n).

Algoritmi obinui prin metoda

Greedy

Arborele de acoperire de cost minim

Se d un graf neorientat, n care fiecrei muchii i se asociaz un cost al parcurgerii acesteia.

Se numete arbore de acoperire de cost minim acel arbore de acoperire, pentru care suma costurilor laturilor este minim.

Construirea arborelui de acoperire de cost minimse poate face prin metoda Greedy.

Obinerea arborelui de acoperire de cost minim prin algoritmul lui Kruskal

Algoritmul lui Kruskal selecteaz prin metoda Greedy muchiile grafului, n ordinea strict cresctoare a costului lor.

Sunt incluse n arborele de acoperire numai acele muchii, a cror adugare la arbore nu produce formarea unor circuite.

Fie, de ex., graful din figura 1, n care nodurile sunt etichetate cu litere, iar pentru fiecare muchie este specificat costul parcurgerii acesteia.

Figura 1

13

Selectarea muchiilor care intr n componenaarborelui de acoperire de cost minim

Se face n ordinea cresctoare a costurilor,dup cum urmeaz:se selecteaz muchia D-E de cost 0.8, formnd astfel primul arborele nr. 1;se selecteaz muchia A-D de cost 1.2, care are nodul D comun cu muchia precedent, astfel c este ataat arborelui nr 1, deja format;se selecteaz muchia G-H de cost 1.4, ale crei noduri nu fac parte din arborele 1, astfel c se constituie arborele nr. 2;se selecteaz muchia E-F de cost 1.9, la care nodul E face parte din arborele 1, iar nodul F este liber; n consecin, muchia E-F se ataeaz la arborele 1;

Selectarea muchiilor care intr n componenaarborelui de acoperire de cost minim

se selecteaz muchia E-G de cost 2.1, care are nodul E n arborele1, iar nodul G n arborele 2; n consecin, muchia reunete cei doiarbori n unul singur, fie acesta arborele 1;se selecteaz muchia A-E de cost 2.3, dar nu poate fi adugat, deoarece ambele noduri exist deja n arborele 1, astfel c s-ar forma un circuit;se selecteaz muchia B-C de cost 2.7, ale crei noduri nu sunt nc cuprinse n arbori; n consecin se formeaz un arbore nou, fie acesta arborele 3; se selecteaz muchia B-D de cost 2.9, care are nodul B n arborele3 si nodul D n arborele 1, deci aceast muchie unete cei doiarbori n unul singur, fie el arborele 1; Cu aceasta construirea arborelui de acoperire de cost minim s-a ncheiat, deoarece numarul de muchii pe care le conine este n-1, unde n este numrul de noduri din graf.

ncercrile de a selecta celelalte muchii (C-D, E-H, D-H, C-H, F-G, A-F, A-B) eueaz, deoarece toate au ambele nodurin arborele 1, deci adugarea lor ar formacircuite.

Arborele de acoperire de cost minim astfel construiteste reprezentat n figura 2.

Arborele de acoperire de costminim figura 2

Din exemplul de mai sus constatm c, n procesul de construire a arborelui de acoperire de cost minim prin aceast metod, se creeaz mai muli arbori care, treptat, dac graful este conex, se unesc ntr-un singur arbore de acoperire.

Pentru fiecare nou muchie selectat (de cost minim) exist urmtoarele posibiliti:a) nici unul din nodurile de la capetele muchiei nu existn arborii deja creai anterior; n acest caz, se creeaz unarbore nou, care conine numai aceast muchie;b) unul din nodurile muchiei exist deja ntr-un arborecreat anterior, iar al doilea nod este liber; n acest caz,muchia se ataeaz la arborele cruia i aparine unul dinnoduri;

c) ambele noduri ale muchiei aparin aceluiai arbeore, dintre cei existeni; n acest caz, adugarea muchiei ar creea un circuit, deci muchia se elimin;

d) cele dou noduri ale muchiei se regsesc n doi arbori diferii; n acest caz, prin adugarea noii muchii, cei doi arbori se contopesc n unul singur.

Acest nou arbore primete numrul de ordine cel mai mic dintre cei doi, fcndu-se n mod cores- punztor modificarea cmpului nrArbore la toate muchiile care le aparin.

Dac graful este conex, arborele de acoperire conine toate cele n noduri alegrafului i n-1 muchii.

n consecin, dac numrul de muchii dinarbore a ajuns la valoarea n-1, cutarea se ncheie.

Obinerea arborelui de acoperire decost minim prin algoritmul lui Prim

Spre deosebire de algoritmul lui Kruskal, care construieste o "pdure" (care se poatecontopi pe parcurs ntr-un singur arbore), algoritmul lui Prim pornete de la unnod dat al grafului i construiete un singur arbore, avnd acest nod ca rdci- n.

Obinerea arborelui de acoperire decost minim prin algoritmul lui Prim

La fiecare parcurgere a ciclului Greedy din acest algoritm,la arborele deja existent se adaug un singur nod.n acest scop, dintre muchiile candidate care au unul din noduri n arborele deja creat, iar celalalt nod liber, se alege muchia de cost minim.

Dac graful este conex, algoritmii lui Kruskal i lui Prim dau acelai rezultat: arborele de cost minim care acoper toate nodurile grafului.

Dac ns graful nu este conex, algoritmul lui Kruskal genereaz pdurea care contine cte un arbore de acope- rire de cost minim pentru fiecare component conex a grafului, n timp ce algoritmul lui Prim genereaz numai arborele de acoperire de cost minim al componentei cone- xe n care se gsete nodul de pornire.

De exemplu, pentru a construi arborele de acoperire de cost minim al grafului conex din figura 1, pornind de la nodul E, se adaug muchiile n ordinea urmtoare:

E-D, D-A, E-F, E-G, G-H, D-B, B-C.

Dac se pornete din vrful B, ordinea va fiurmtoarea:

B-C, B-D, D,E, D-A, E-F, E-G, G-H.

Algoritmul Prim poate fi

formulat n pseudocod astfel:

Se iniializeaz graful G i nodul de pornire np.Se iniializeaz arborele de acoperire T, care conine iniial numai nodul np.Ct timp((numrul de noduri din T este mai mic dect cel din G) i (exist n G cel puin o muchie m care are un nod n T)) {se extrage din G muchia de cost minim m care are un nod n T;Dac (ambele noduri ale muchiei m sunt n T)Atunci muchia m se elimin din GAltfel muchia m se adaug la T}

Algoritmul lui Dijkstra

Este destinat aflrii celor mai scurte ci de la unnod dat la toate celelalte noduri ale grafului;

Se creeaz astfel un arbore de acoperire, care are ca rdcin nodul iniial dat (numit i surs), iar fiecare ramur reprezint cea mai scurt cale de la surs la toate nodurile pe care le conine.

Acest arbore, n general, difer de arborele decost minim.

Algoritmul lui Dijkstra

Pentru aplicarea acestui algoritm, se folosescdou structuri de date auxiliare:- Arborele S, care conine cile cele mai scurtectre noduri; iniial, acest arbore conine numainodul surs, dar el se completeaz cu un nou nodla fiecare parcurgere a ciclului Greedy;- coada de prioriti Q, care conine nodurilecare nu sunt n S, dar ctre care conduc legturide la nodurile din S; la extragerea din coad,prioritatea maxim aparine nodului pentru caredistana de la surs este cea mai mic.

Algoritmul lui Dijkstra

Iniial, se creeaz structurile vide S i Q, dup care sepune nodul surs n Q.Fiecrui nod din Q i se ataeaz ca informaie distana de la nodul surs pn la nodul dat. Se intr apoi ntr-un ciclu Greedy. La fiecare parcurgere a ciclului se extrage din Q nodul de prioritate maxim (deci cel pentru care distana de la nodul sursa este minim) i se pune n S.

Pentru a se putea reconstitui arborele, n structurile S i Q fiecare element va conine i o referin la tatl acestuia, deci va fi reprezentat prin urmtorul triplet:( < nod_curent> )

S considerm ca exemplu graful dinfigura 1 i s adoptm ca surs nodul A.

- Iniial, S va fi vid, iar Q va coninenumai elementul (null, A, 0).

- La prima parcurgere a ciclului Greedy, seextrage din Q unicul nod existent i se pune n S, iar n Q se pun elementele

(A, D, 1.2), (A, E, 2.3), (A, F, 5.1) i (A,B, 7.3).

La urmtoarea parcurgere a ciclului Greedy, din Q se extrage nodulD (pentru care distana la sursa A este minim), dup care se pun nQ nodurile legate prin muchii de acesta, cu distanele de la nodurilerespective la A calculate ca distana de la D la A plus distana de lanodul respectiv la D.Exist posibilitatea ca unele din aceste noduri s exist deja n Q, cum sunt B i E, pentru care exist deja o distan la A calculat anterior, si alta calculat acum pentru calea care trece prin D. Dintre acestea doua se va alege cea mai mic.Observm, deci, c n Q nu trebuie s existe de mai multe ori acelai nod i nici nu se pun noduri care exist deja n S.Ca urmare, S conine acum elementele (null, A, 0) i (A, D, 1.2), iar Q conine elementele (D, E, 2.0), (D, B, 4.1), (D, C, 4.3), (A, F, 5.1) i(D, H, 5.4), n ordinea cresctoare a prioritilor.

La fiecare din parcurgerile urmtoare aleciclului Greedy se procedeaz similar:

se extrage din Q nodul cu cea mai mic distan la A, iar nodurile adiacente acestuia se pun n Q, calculndu-se pentru fiecare distana la A actualizat.

Iat cum evolueaz mulimile

de noduri din S i Q:

S={ }, Q={(null, A, 0, 0)} S={(null, A, 0.0)}, Q={(A, D, 1.2), (A, E, 2.3), (A, F, 5.1), (A, B, 7.3)} S={(null, A, 0.0), (A, D, 1.2)}, Q={ (D, E, 2.0), (D, B, 4.1), (D, C, 4.3), (A, F,5.1), (D, H, 5.4)} S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0)},Q={ (E, F, 3.9), (D, B, 4.1), (E, G,4.1), (D, C, 4.3), (D, H, 5.4) } S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9)}, Q={ (D, B, 4.1), (E, G,4.1), (D, C, 4.3), (D, H, 5.4) } S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B, 4.1)}, Q={(E, G,4.1), (D, C, 4.3), (D, H, 5.4) } S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B, 4.1), (E,G,4.1)},Q={ (D, C, 4.3), (D, H, 5.4) }S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B, 4.1), (E, G, 4.1), (D, C, 4.3)}, Q={(D, H, 5.4) }S={(null, A, 0.0), (A, D, 1.2), (D, E, 2.0), (E, F, 3.9), (D, B, 4.1), (E, G, 4.1), (D, C, 4.3), (D, H, 5.4)}, Q={ }

Algoritmul se oprete cnd mulimea Q devinevid.

Dac graful este conex, numrul de parcurgeri ale ciclului Greedy este egal cu n-1, unde n este numrul de noduri din graf. Arborele de acoperire astfel obinut cuprinde,deci, toate nodurile grafului.

Dac graful nu este conex, arborele dat de algoritmul Dijkstra acoper numai componenta conex din care face parte nodul surs.

Arborele astfel obinut este cel din figura 3 i difer de cel de cost minim din figura 2.

n figur s-au reprezentat prin numere negre lungimile muchiilor i prin numere roii,puse lng noduri, distanele de la surs la nodurile respective.

Arborele de acoperire minim-Dijkstra Fig.3

Tabele de hashing (Hash

Tables)

Fie o mulime de elemente pstrat n memoriacalculatorului ca o list neordonat.

A afla dac o valoare anume este inclus n aceast mulime nseamn a parcurge secvenial lista i a testa element cu element.

Dac se folosesc diveri algoritmi de sortare a mulimii, cutarea se poate face mult mai rapid. Dac nici astfel viteza nu este suficient de mare,se va mbina sortarea cu hashing-ul.

Hash Table

Ideea de baz n hashing este de a ncerca s mprim elementele mulimii ntr-un numr oarecare de clase de echivalen (avnd fiecare cam acelai numr de elemente).

Dac se reuete acest lucru, nseamn c la cutarea unui element n cadrul mulimii vom stabili n prima faz crei clase de echivalen i aparine, iar apoi l vom cuta doar n cadrul acelei submulimi. n cazul n care clasele de echivalen vor fi sor-tate, viteza crete i mai mult.

Implementarea unei agende telefonice n care cutarea numerelor de telefon s se fac printr-o tabel de hashing

Criteriul mpririi n clase de echivalen va fi cifra finala numrului de telefon.

n consecin vom avea 10 clase de echivalen, avnd aprox. acelai numr de elemente.

Tabela de hashing este constituit dintr-un ir de 10 elem., fiecare coninnd un pointer la o list simplu nlnuit. Toate elementele ce aparin aceleiai liste au n comunfaptul c se sfresc cu aceeai cifr. Deoarece acest ex. are doar un scop didactic, clasele deechivalen nu vor fi sortate.

Hashtab.cpp

Deci a cuta n agend un numr de telefon ce se termin cu cifra i nseamn a-l cuta secvenial n cadrul listei la care pointeaz al i- lea element din tabela de hashing.

Exerciiu: Ordonarea claselor de echivalen cutarea (inserarea) n cadrul acestora prini

metoda divide et impera metoda

njumtirii intervalului. De asemenea, v

propunem scrierea unui destructor al clasei

hash_array.

Tehnica Forei brute

n situaii practice, n care trebuie s se aleag dintre mai multe variante posibile soluiacare satisface anumite condiii (de exemplusoluia de cost minim, sau de profitmaxim i care ndeplinete eventual ianumite restricii) se poate aplica principiul "forei brute"

Tehnica Forei brute

Se genereaz toate variantele posibile, dintre care se selecteaz numai acele variante care indeplinesc restriciile impuse i, n final, dintre variantele astfel selectate se alege cea optim. Avantajul acestei tehnici este simplitatea, celpuin la nivel conceptual.

Marele dezavantaj este c, odat cu cresterea dimensiunii n (a numrului de elemente din mulimile de date asupra crora se aplic algoritmul), numrul de variante posibile crete foarte rapid.

Tehnica Forei brute

n consecin, tehnica "forei brute" nu este convenabilpentru cazul cnd numrul de elemente este mare.

ntotdeauna cnd exist pentru o anumit problem un algoritm mai eficient, trebuie folosit acesta.

Totui, cnd astfel de algoritmi nu exist sau nu se cunosc, la nevoie se poate recur- gei la "fora brut.

Tehnica Forei brute

Exist algoritmi prin care se pot genera toatesoluiile posibile pentru diferite probleme tipice.

Dac dorim s aplicm "fora brut" pentru rezolvarea unei probleme particulare, stabilim mai nti n care din cazurile menionate se ncadreaz variantele de soluii, generm soluiile respective i apoi o selectm pe cea corespunztoare condiiilor problemei.

Exemplu

S considerm c la o conferin, n jurul unei mese rotunde, trebuie asezate n persoane, astfel nct s nu fie aezate alturi 2 persoane rivale, (este dat pentru fiecare persoan lista rivalilor acesteia).

Remarcm imediat c soluia, dac exist, se gsete printre permutrile celor n persoane.

n consecin, generm toate permutrile de n obiecte i le selectm pe acelea n care, pentru fiecare persoan n parte, cei doi vecini nu se gsesc n lista de rivali.