Metode si Tehnici de programare - limbajul C++
Adrian Runceanu
Capitolul 9 - METODA GREEDY
A.Consideratii teoretice
Pentru a exemplifica aceasta metoda consideram o multime A cu n elemente. Si problema care ar trebui rezolvata consta din determinarea unei submultimi B a lui A. Aceasta trebuie sa indeplineasca anumite conditii pentru a fi acceptata ca solutie. Dintre toate submultimile acceptate (numite solutii posibile), se va alege una singura numita solutie optima.
Dintre solutiile posibile trebuie aleasa cea optima tinand cont de proprietatea urmatoare: Daca B este solutie posibila si C inclusa in B atunci si C este solutie posibila.
Multimea vida este intotdeauna solutie posibila.
Initial se porneste de la multimea vida. Se alege intr-un anumit fel un element din A, neales la pasii precedenti. Daca aceasta adaugare la solutia partial construita conduce la o solutie posibila atunci construim noua solutie posibila prin adaugarea elementului - procedura Greedy1.
procedure Greedy1(A, n, B)
Begin
B<-vida
for i=1 to n do
begin
ALEGE(A, i, x)
POSIBIL(B, x, v)
if v=1 then ADAUG(B, x)
end
end
Procedura ALEGE selecteaza un element x = aj apartine { aI, . . ., an } si efectueaza interschimbarea ai<=aj. Procedura POSIBIL verifica daca B reunit cu {x} este solutie posibila, caz in care variabila booleana v va lua valoarea 1, altfel ea va lua valoarea 0. Procedura ADAUG inlocuieste pe B cu B reunit cu {x}. Procedura ALEGE nu precizeaza deloc cum se selecteaza un element x, de aceea trebuie stabilita o procedura de prelucrare PREL), care va preciza ordinea in care vor fi introduse elementele lui A in solutie - procedura Greedy2 .
procedure Greedy2(A, n, B)
begin
PREL
B<-vida
for i=1 to n do
begin
POSIBIL(B, ai, x )
if v=1 then ADAUG(B, ai)
end
end
1. Suma maxima
Se da o multime X= { x1, x2, . . ., xn } cu elemente reale. Sa se determine o submultime a lui X astfel incat suma elementelor submultimii sa fie maxima.
Aplicam metoda Greedy selectand din multime toate elementele pozitive. Sa presupunem ca rezultatul il construim in vectorul S = { s1, s2, . . . , sk } unde k<=n si exista j apartine { 1, 2, . . .,n } astfel incat si=xj pentru orice i=1, … , k.
program submultime(X, n, S, k)
begin
k<-0
for i=1 to n do
if xI>0 then
begin
k<-k+1
sk<-xi
end
end
2. K divizori naturali
Fiind dat numarul natural k > 1, se cere sa se determine cel mai mic numar natural n avand exact k divizori naturali proprii (diferiti de 1 si n).
procedure VERFI(n, k, v)
begin
i<=0
for j=2 to n-1 do
if n mod j = 0 then i<=i+1
if i=k then v<-true
else v<=false
end
program divizori(k,n)
begin
read k
n<-k+2
s<-0
while s=0 do
begin
VERIF(n,k,v)
If v=true then
begin
write n
s<-1
end
n<-n+1
end
end.
B.Exemple de programe
1. SUMA MAXIMA
Se da o multime X= { x1, x2, . . ., xn } cu elemente reale. Sa se determine o submultime a lui X astfel incat suma elementelor submultimii sa fie maxima.
(Ioan Odagescu, Felix Furtuna - METODE SI TEHNICI DE PROGRAMARE)
2. K DIVIZORI NATURALI
Fiind dat numarul natural k > 1, se cere sa se determine cel mai mic numar natural n avand exact k divizori naturali proprii (diferiti de 1 si n).
(Ioan Odagescu, Felix Furtuna - METODE SI TEHNICI DE PROGRAMARE)
3. PROBLEMA COMIS-VOIAJORULUI
Se considera un graf G neorientat in care oricare doua varfuri distincte sunt unite intre ele. Un comis-voiajor pleaca dintr-un oras (reprezentat de nodurile grafului), si trebuie sa viziteze toate orasele astfel incat costul deplasarii sa fie minim.(fiecare muchie dintre doua noduri are asociat un cost reprezentand distanta dintre cele doua orase).
Solutia data este generalizata astfel incat se reiau pe rand calculele pentru fiecare nod de pornire {1,2,...,n}.
4. PROBLEMA CONTINUA A RUCSACULUI
O persoana are un rucsac cu care poate transporta o greutate maxima G. Persoana are la dispozitie n obiecte si cunoaste pentru fiecare greutatea si castigul care se obtine in urma transportului sau la destinatie.
Se cere sa se precizeze ce obiecte trebuie sa transporte persoana a.i. castigul sa fie maxim.
Precizare : obiectele pot fi taiate.
Astfel se obtine o incarcare mai eficienta a rucsacului.
C.Exercitii si teme
1. Sa se ruleze programele prezentate anterior, executand mai multe exemple de test pentru a vedea valorile obtinute in situatii diferite.
2. Se dau n orase si costul conectarii anumitor perechi de orase. Se cere sa se aleaga acele muchii care asigura existenta unui drum intre oricare doua orase astfel incat costul total sa fie minim. (se poate folosi algoritmul lui Prim)
3. Problema spectacolelor. Intr-o sala de spectatcole, intr-o zi, trebuie planificate n spectacole Pentru fiecare spectacol se cunoaste intervalul in care se desfasoara: [st,sf). Se cere sa se planifice un numar maxim de spectacole astfel incat sa nu se suprapuna.