Lucrarea 3 Cutare i Selecie

Tehnici de Programare

Udritoiu tefan 7. Greedy

Stoica Spahiu Cosmin

Lucrarea 7 Greedy.

Introducere tehnica Greedy

Este greu de spus forma general a unei probleme rezolvabile cu tehnic Greedy. Algoritmii greedy (greedy=lacom) sunt n general simpli i sunt folosii la probleme de optimizare, cum ar fi: s se gseasc cea mai bun ordine de executare a unor lucrri pe calculator, s se gseasc cel mai scurt drum ntr-un graf etc. In cele mai multe situaii de acest fel avem: o mulime de elemente (lucrri de executat, vrfuri ale grafului etc) o funcie care verific dac o anumit mulime de candidai constituie o soluie posibil, nu neaprat optim, a problemei o funcie care verific dac pentru o mulime de candidai este posibil s o completm astfel nct s obinem o soluie posibil, nu neaprat optim, a problemei o funcie de selecie care alege la orice moment cel mai potrivit element, nc nefolosit o funcie soluie care spune cnd s-a ajuns la soluie. Pentru a rezolva problema o anumit problem, un algoritm greedy construiete soluia pas cu pas. Iniial, mulimea candidailor selectai este vid. La fiecare pas, ncercm s adugm acestei mulimi cel mai potrivit element, conform funciei de selecie. Dac, dup o astfel de adugare, mulimea de elemente obinut nu mai poate duce la soluie, se elimin ultimul element adugat; acesta nu va mai fi niciodat considerat. Dac, dup adugare, mulimea de elemente selectate poate duce la soluie, ultimul element adugat va rmne de acum ncolo n ea. De fiecare dat cnd lrgim mulimea elementelor selectate, verificm dac aceast mulime nu constituie o soluie posibil a problemei noastre. Dac algoritmul Greedy funcioneaz corect, prima soluie gsit va fi totodat o soluie optim a problemei. O ntrebare fireasc este aceea dac algoritmul Greedy duce totdeauna la soluie optim? Evident c nu Sunt situaii cnd soluia gsit nu este optim. Mai mult, pentru cele mai multe din probleme nu se cunosc algoritmi Greedy de rezolvare. Spre deosebire de Backtracking, algoritmul Greedy nu permite atunci cnd s-a oservat c nu se poate ajunge la soluie pentru o anumit secven de elemente, revenirea napoi, pe nivelele anterioare.

Pentru problemele care nu duc la soluia optim este necesar s se caute soluii, chiar dac nu optime, dar ct mai apropiate de acestea.

Descrierea n pseudocod al algoritmului de rezolvare este urmtoarea:

function greedy(C) {C este multimea candidatilor} S ( ( {S este multimea in care construim solutia} while not solutie(S) and C ( ( do x ( un element din C care maximizeaza/minimizeaza select(x) C ( C \ {x} if corect(S ( {x}) then S ( S ( {x}if solutie(S)then return S else return nu exista solutieLa fiecare pas, procedura alege cel mai bun candidat la momentul respectiv, far s-i pese de viitor i fr s se rzgndeasc. Daca un candidat este inclus n soluie, el rmne acolo; dac un candidat este exclus din soluie, el nu va mai fi niciodat reconsiderat. Asemenea unui ntreprinztor rudimentar care urmrete ctigul imediat n dauna celui de perspectiv, un algoritm Greedy acioneaz simplist. Totui, ca i n afaceri, o astfel de metod poate da rezultate foarte bune tocmai datorit simplitii ei.

ntre metoda Greedy i metoda Backtracking putem enumera urmtoarele diferene: ambele tehnici ofer soluii sub form de vector tehnica Backtracking ofer toate soluiile problemei, n timp ce Greedy ofer o singur soluie tehnica Greedy nu dispune de mecanismul ntoarcerii, specific tehnici Backtracking

Exemplu de problem rezolvat prin metoda Greedy

S presupunem c deinem un magazin de soft i dorim s dm restul unui client care ne-a dat o sum oarecare de bani, folosind un numr ct mai mic de monezi. Presupunem c avem urmtoare list de monede disponibile: 100lei, 50lei, 25lei, 1leu. Moneda unitate (1 leu) este obligatoriu s se regseasc printre ele. De asemenea din fiecare tip de moned avem un numr nelimitat de buci. void function Greedy(int suma)

//se primete ca parametru suma pe care trebuie s o dea rest

{ int nr_monezi;

//initial dam cat se poate din bani n moneda cea mai mare (de 100) Deoarece atat suma cat si 100 sunt numere ntregi, suma/100 va avea

ca rezultat un numar ntreg, partea de dup virgul ignorndu-se

nr_monezi = suma/100;

printf(s-au pltit %d monede de 100,nr_monezi);

//restul care mai este de achitat este de fapt restul mpririi

suma, la 100 suma = suma%100;

//se pltete ct este posibil n moneda urmtoare

nr_monezi = suma/50;

printf(s-au pltit %d monede de 50,nr_monezi);

suma = suma%50

nr_monezi = suma/25;

printf(s-au pltit %d monede de 100,nr_monezi);

suma = suma%25;

//Deoarece nu mai avem la dispoziie dect moneda unitate, acum se va

plti restul care mai este de dat n monede de 1 leu

printf(s-au pltit %d monede de 1,suma);}

Se poate demonstra c algoritmul Greedy va gsi n acest caz mereu soluia optim (restul cu un numr minim de monezi). Dac n schimb nu am avea moneda unitate, nu s-ar mai putea o obine soluie optim. Este posibil ca dup ce am pltit tot ce se poate n monedele disponibile, folosind algoritmul de mai sus, s ne rmn o sum mic (mai mic dect cea mai mic moned) pe care nu avem cu ce s o restituim. Cum algoritmul Greedy nu dispune de mecanismul ntoarcerii pentru a ncerca alt combinaie de monede pentru restituirea restului, acea sum. ne va rmne ca baci.

Probleme propuse

1. s se rescrie problema casierului n condiiile n care am avea un numr citit de la tastatur de tipuri de monede. (de asemenea trebuie citit pentru fiecare tip n parte valoarea acelei monede)2. ntr-o sal de teatru, ntr-o anumit zi trebuie planificate n spectacole. Pentru fiecare spectacol se cunoate intervalul n care se desfoar [inceptermin]. Se cere s se planifice un numr maxim de spectacole astfel nct s nu se suprapun. Indicaie: se folosete un vector bidimensional spectacol[i][j], unde i reprezint ora nceperii spectacolului, iar j ora terminrii lui. Se sorteaz spectacolele dup ora terminrii lui. Primul spectacol este programat cel care se termin cel mai devreme. Mai departe alegem primul spectacol care ndeplinete condiia c ncepe dup ce s-a terminat cel anterior lui. Acest algoritm gsete soluia optim? 3. O persoan are un rucsac cu care poate transporta o greutate maxim G. Persoana are la dispoziie n obiecte i cunoate pentru fiecare obiect greutatea i valoarea sa. Se pune problema ce obiecte trebuie s transport persoana n aa fel nct ctigul s fie maxim. Modificai rezolvarea astfel nct s corespund situaiei cnd persoana nu este obligat s ia un obiect ntreg, ci poate lua doar un fragment din el.4. Se dau n numere ntregi nenule b1, b2 bn i m numere ntregi nenule a1,a2 . am. S se determine o submulime a mulimii B= {b1, b2 bn} care s maximizeze valorile expresiei:E = a1x1 + a2x2 + . + amxm unde n > m i xi ( {b1, b2 bn}

5. Un comis-voiajor pleac dintr-un ora, trebuie s viziteze un numr de n orae i s se ntoarc n oraul de plecare cu efort minim. Se da matricea de vecinti a celor n orae, precizndu-se i distanele dintre ele.6. Se d o tabl de ah n(n. S se arate punctele prin care trece un cal care pornete din punctul 1,1 n ncercarea de a acoperi ct mai multe puncte posibile. Indicaie: la fiecare pas se alege acea mutare care plaseaz calul ntr-o poziie din care la pasul urmtor exist ct mai puine posibiliti de a muta din nou

PAGE 3