Metode de elaborare a algoritmilor

Metode de elaborare a algoritmilor

Metoda Greedy

Se aplica problemelor in care se da o multime A continand n date de intrare si se cere sa se determine o submultime a sa (B) care satisface anumite conditii pentru a fi acceptata. Aceasta submultime se numeste solutie posibila. Se cere sa se determine o solutie posibila care fie sa maximizeze fie sa minimizeze o anumita functie obiectiv data. Aceasta solutie posibila se numeste solutie optima.

Obs: Metoda Greedy nu cauta sa determine toate solutiile posibile ( care ar putea fi prea numeroase) si apoi sa aleaga din ele pe cea optima, ci cauta sa in 838g68i troduca pe rand un element x (il "inghite") in solutia optima.

Metoda Greedy lucreaza in pasi astfel:

se initializeaza multimea solutiilor (B) cu multimea vida (B=F

se alege un anumit element xI A

se verifica daca elementul ales poate fi adaugat la multimea solutiilor, daca da atunci va fi adaugat (B=BÈ

procedeul continua astfel, repetitiv, pana cand au fost determinate toate elementele din multimea solutiilor.

Exemplul nr. 1

Se da o multime X = cu elemente reale. Se cere sa se determine o submultime Y X astfel incat sa fie maxima.

Observam ca o solutie posibila Y X va fi o submultime Y X cu toate elementele pozitive.

#include<iostream.h> 

int n, k, x[100], y[100];  void main ( )

void citire ( ) 

}

Exemplul nr.2

Problema platii unei sume cu bancnote(monezi) de valoare data: sa se efectueze plata unei sume S utilizand un numar minim de bancnote (monezi). Valorile lor se cunosc.

Metoda Greedy se poate aplica astfel:

Fie suma care a mai ramas de platit X=S

Se alege moneda de valoare maxima M_i (astfel incat M_i<=X)

Se calculeaza nr. maxim de monezi M_i ce pot fi date (n = X div M_i )

Repetam pana cand restul sumei de plata e zero

Presupunem ca avem urmatoare lista de bancnote disponibile: 100lei, 50lei, 10lei, 1leu. De asemenea, din fiecare tip de moneda avem un numar nelimitat de bucati.

	se primeste ca parametru suma pe care trebuie sa o dea rest

void Greedy(int suma)

initial dam cat putem bani in bancnota cea mai mare (de 100). Deoarece suma si 100 sunt numere intregi, suma/100 va avea ca rezultat un numar intreg.

Exemplul nr.3

Se da o multime de n numere pozitive, P si un numar M. Se cere determinarea unui subset a lui P a carui suma a elementelor sa fie cel mult M.

#include<iostream.h>

void main()

k = 0; sum = 0;

for (i=1; i<=n; i++)

;

else break;

}

cout<<"submultimea rezultat: ';

for (i=0; i<k; i++) cout<< rez[i]<<" " ;

Exemplul nr.4

Problema rucsacului: Se da un rucsac in care se poate incarca o greutate maxima g admis si mai multe obiecte de greutati g₁, g₂,., g_n ce au costurile de transport c₁, c₂,., c_n. Se cere sa se incarce rucsacul la greutatea maxima realizand un profit maxim.

Se observa ca cea mai buna metoda de incarcare a rucsacului ar fi sa introducem obiectele in ordine descrescatoare a eficientei acestora.

Deci vom calcula eficientele obiectelor:

ef_i c_i/ g_i

si vom sorta obiectele in ordine descrescatoare a eficientei.

Notam cu g1 greutatea curenta ce mai poate fi incarcata, iar in vectorul x memoram ordinea obiectelor (initial x[i] = i).

Acestea fiind realizate aplicam metoda Greedy:

La inceput g1 (greutatea curenta ce mai poate fi incarcata) = g_admis (greutatea maxima ce se poate incarca in rucsac).

Se alege un obiect (in ordine descrescatoare a eficientei)

Verificam daca putem adauga obiectul ( daca prin adaugare nu se depaseste volumul admis)

Repetam pana cand s-au terminat obiectele sau s-a atins volumul dorit

Algoritmul in pseudocod:

for i=1,n castig = 0; g1 = g admis;

read (c_i , g_i ); for i=1,n

ef_i c_i/ g_i ; if g1 > g_i

x_i = i ; write("obiectul", x_i , "in cantitatea", 1);

repeat  g1 = g1 - g_i

for i=1,n -1 castig = castig + c_i

for j = i+1,n endif

if ef_i < ef_j if g1 <= g_i

ef_i ef_j write("obiectul", x_i , "in cantitatea", g₁/ g_i );

c_i c_j castig = castig + c_i* g₁/ g_i

g_i g_j g1 = 0

x_i x_j  endif

endif repeat

repeat write ("castig total", castig)

repeat

Exemplul nr.5

Minimizarea timpului mediu de asteptare: o singura statie de servire (procesor, pompa de benzina etc) trebuie sa satisfaca cererile a n clienti. Timpul de servire necesar fiecarui client este cunoscut in prealabil: pentru clientul i este necesar un timp t_i, 1 ≤ i ≤ n. Dorim sa minimizam timpul total de asteptare:

T=

(t_i = timpul de asteptare pentru clientul i)

De exemplu, daca avem trei clienti cu t1 = 5, t2 = 10, t3 = 3, sunt posibile sase ordini de servire. In primul caz, clientul 1 este servit primul, clientul 2 asteapta pana este servit clientul 1 si apoi este servit, clientul 3 asteapta pana sunt serviti clientii 1, 2 si apoi este servit. Timpul total de asteptare a celor trei clienti este 38.

Ordinea T

5+(5+10)+(5+10+3) = 38

5+(5+3)+(5+3+10) = 31

10+(10+5)+(10+5+3) = 43

10+(10+3)+(10+3+5) = 41

3+(3+5)+(3+5+10) = 29 optim

3+(3+10)+(3+10+5) = 34

Algoritmul greedy este foarte simplu: la fiecare pas se selecteaza clientul cu timpul minim de servire din multimea de clienti ramasa. Prin metoda greedy obtinem deci intotdeauna planificarea optima a clientilor.

Problema poate fi generalizata pentru un sistem cu mai multe statii de servire.

Exemplul nr.6

Problema planificarii activitatilor: se considera un set de n prelucrari ce trebuie executate de catre un procesor. Durata executiei prelucrarilor este aceeasi (se considera egala cu 1). Fiecare prelucrare i are asociat un termen final de executie, ti <=n si un profit, pi. Profitul unei prelucrari intervine in calculul profitului total doar daca prelucrarea este executata (daca prelucrarea nu poate fi planificata inainte de termenul final de executie profitul este nul). Se cere sa se planifice

activitatile astfel incat sa fie maximizat profitul total (acesta este corelat cu numarul de prelucrari

planificate).

O soluttie consta in stabilirea unui 'orar' de executie a prelucrarilor S = (s1, s2,.., sn), s_iIfiind indicele prelucrarii planificate la momentul i.

Pentru rezolvarea problemei se poate aplica o tehnica de tip greedy caracterizata prin:

se sorteaza activitatile in ordinea descrescatoare a profitului;

fiecare activitate se planifica intr-un interval liber cat mai apropiat de termenul final de

executie.

Exemplul nr.7

Pe o banda magnetica sunt n programe, un program i de lungime li fiind apelat cu probabilitatea pi, 1 ≤ i ≤ n, p1+p2+.+pn = 1. Pentru a citi un program, trebuie sa citim banda de la inceput.

In ce ordine trebuie sa memoram programele pentru a minimiza timpul mediu de citire a unui program oarecare?

Indicatie: Se pun in ordinea descrescatoare a rapoartelor pi / li.

Exemplul nr.8

Problema celui mai lung subsir comun a doua siruri: fie A = (a1, a2,., am) si B = (b1,b2, ., bn)

doua siruri. Sa se determine cel mai lung subsir comun al celor doua siruri, adica (c1, c2,., cl) cu proprietatea ca exista i1 < i2 < .. < il si j1 < j2 < .. < jl astfel incat c_k = a_ik = b_jk pentru

k = 1. l.

Rezolvare. De exemplu pentru sirurile a = (2 1 4 3 2) si b = (1 3 4 2) exista doua subsiruri comune de lungime maxima (3) si anume: (1 4 2) si (1 3 2).