Scrigroup - Documente si articole

Username / Parola inexistente      

Home Documente Upload Resurse Alte limbi doc  

CATEGORII DOCUMENTE





AccessAdobe photoshopAlgoritmiAutocadBaze de dateCC sharp
CalculatoareCorel drawDot netExcelFox proFrontpageHardware
HtmlInternetJavaLinuxMatlabMs dosPascal
PhpPower pointRetele calculatoareSqlTutorialsWebdesignWindows
WordXml


Metoda „greedy”

algoritmi

+ Font mai mare | - Font mai mic







DOCUMENTE SIMILARE

Trimite pe Messenger
Proiect - dispozitivul de comanda pentru un automat de schimbat bani (monede)
Grafuri - Parcurgerea DF a grafurilor neorientate
Metoda „greedy”
Liste - Arbori
AUTOMATE FINITE IMPLEMENTATE IN VERILOG
SYSAMO-SISTEM EXPERT PENTRU AMORTIZAREA IMOBILIZARILOR CORPORALE
Descrierea structurala
Limbaje de prezentare a algoritmilor ( pseudocod )
Algoritmi definire
REPREZENTAREA SI PRELUCRAREA INFORMATIEI IN CALCULATOARELE NUMERICE

Metoda „greedy”

            Metoda „greedy” este o metoda ce permite determinarea unei singure solutii care corespunde unui anumit criteriu de optim, in cazul problemelor in care solutia se construieste ca o submultime a unei multimi date. Ordinul de complexitate al unui astfel de algoritm este redus considerabil prin faptul ca se incearca obtinerea solutiei printr-o singura parcurgere a multimii din care se construieste solutia optima, cu toate ca in practica, inainte de aplicarea metodei, se fac prelucrari asupra acestei multimi care maresc ordinul de complexitate.



Problema. Se da o multime A de cardinal n (n³0) si o functie f: P(A) ® R. Sa se determine o submultime BI P(A) de cardinal k, B = , (1£k£n), astfel incat k-uplul (b1,b2,,bk) sa optimizeze functia f.

Solutie. Familia partilor multimii finite A, notata P(A) se numeste spatiul solutiilor problemei. Conditia de optim pe care trebuie sa o indeplineasca o solutie este exprimata printr-un set de relatii intre anumite elemente ale multimii A, relatii exprimate prin functia f. O solutie care poate conduce la obtinerea unei solutii optime se numeste solutie posibila. Pot exista mai multe solutii care satisfac conditiile de optim, dar se doreste obtinerea macar a uneia dintre acestea.

            Construirea unei solutii optime consta din determinarea unei succesiuni de solutii posibile care imbunatatesc progresiv valoarea functiei f, conducand catre optim. Solutiile posibile au proprietatea ca orice submultime a unei solutii posibile este o solutie posibila. Prin urmare si multimea vida poate fi considerata ca o solutie posibila.

 

Descriere metoda:

- consideram submultimea B, multimea vida

Pas 1.

- se alege un element aIA, neales la un pas anterior

- verificam daca submultimea B È   conduce la o solutie posibila

- daca da, atunci adaugam elementul ales la multimea B (B := BÈ ).

- se continua cu Pas 1 pana cand nici un element al multimii A nu mai poate fi adaugat la B sau adaugarea lui nu mai poate imbunatati valoarea functiei f.

            Algoritmul prezentat mai sus conduce la obtinerea unei solutii (macar o solutie exista intotdeauna), pornind de la multimea vida si cautand in fiecare pas sa imbunatatim solutia deja obtinuta. Aceasta tehnica de obtinere a solutiei, care a dat si denumirea, oarecum ironica, a metodei (greedy = lacom), in cele mai frecvente cazuri  conduce la indepartarea involuntara de optim, cunoscut fiind faptul (plastic exprimat prin „lacomia pierde optimalitatea”), ca optimul local nu atrage optimul global.

            Acest aspect al tehnicii „greedy” a condus la disocierea algoritmilor elaborati prin metoda „greedy” in:

-          algoritmi cu atingerea optimului global;

-          algoritmi  ale caror solutii converg catre optimul global (evident, fara atingerea acestuia in toate situatiile). Aceasta din urma categorie de algoritmi genereaza solutii 'multumitoare' in majoritatea cazurilor, dar si solutii 'catastrofale' in alte cazuri.

            Disocierea in cele doua categorii se realizeaza prin modalitatea de alegere a elementelor din multimea A. De aceea, este frecvent folosita o prelucrare (reordonare) prealabila a elementelor multimii A care sa modifice ordinea alegerii elementelor submultimii B.

 

procedura greedy

       k := 0                                - k este numarul de elemente din B

       B := Æ                             

       repeta

            alege a I A

            daca B È este solutie posibila atunci

                  k::=  k + 1

                  B := B È

            sfdaca

       pana cand nu se mai pot alege elemente din A

sfarsit

            Exemplul care urmeaza scoate in evidenta cele doua aspecte ale metodei: atingerea optimului sau numai apropierea de acesta.

Exemplu (functiagreedy”). Se da o submultime A a lui R, cu n elemente si o functie f de forma f(x1,x2,,xk) = c1x1 + c2x2 + + ckxk, (ciIR, 0£k£n). Sa se gaseasca o submultime BÍA de cardinal k pentru care functia f ia valoare maxima.

In programul Pascal:

·         fisierul de intrare 'multime.txt' va avea forma:

a1, a2, , an                     - multimea A

c1, c2, , cn                      - coeficientii functiei f

·         iesirea va fi:

Solutia : x = ( b1, b2, , bk)

Valoarea maxima a functiei este v.

Solutie. Aceasta problema constituie un exemplu ilustrativ complet, pentru cazul in care prin aplicarea metodei 'greedy' se obtine valoarea optima a functiei f. Algoritmul necesita o pregatire prealabila a multimii A in vederea aplicarii procedurii de alegere succesiva a elementelor submultimii B:

-          se va ordona crescator multimea A;

-          pornind de la B := Æ vom selecta elementele din A astfel:

-          cat timp printre coeficientii ci ai functiei f exista numere negative (carora nu li s-a asociat un element din A, ca valoare pentru xi  - ul corespunzator), executam: celui mai mic coeficient neasociat unui element din A, ii atasam cel mai mic numar din A inca neselectat;

-          pentru ceilalti coeficienti (pozitivi) ai functiei f carora nu li s-a asociat un element din A (ca valoare pentru xi), se alege, pentru cel mai mare coeficient neasociat unui element din A, cel mai mare numar din A inca neselectat.




            Vom ilustra algoritmul cu un exemplu numeric.

Exemplu. Fie multimea de numere A =   (deja ordonata) si functia f de forma f(x1,x2,x3,x4,x5,x6,x7) = 3x1 + 6x2 - x3 - 9x4 - 9x5 + 3x6 + 8x7. Solutia problemei va fi un vector x = (b1,b2,b3,b4,b5,b6,b7) ale carui componente sunt elemente din A. Succesiunea alegerii valorilor componentelor vectorului x pune in evidenta „tehnica greedy”:

            - corespunzator celui mai mic element negativ dintre coeficientii functiei f alegem primul element din A, deci b4 = -8;

            - corespunzator celui mai mic element negativ dintre coeficientii functiei f pentru care nu s-a ales inca o valoare pentru elementul vectorului x, alegem urmatorul element din A, deci b5 = -7;

            - continuam alegerea elementelor lui x pana cand tuturor coeficientilor negativi ai functiei f li s-a asociat componenta corespunzatoare in vectorul x. Obtinem x = (b1,b2,-5,-8,-7,b6,b7);

            - corespunzator celui mai mare element pozitiv dintre coeficientii functiei f alegem ultimul element din A, deci b7 =  8;

            - corespunzator celui mai mare element pozitiv dintre coeficientii functiei f pentru care nu s-a ales inca o valoare pentru elementul vectorului x, alegem elementul anterior celui ales la pasul precedent, deci b2 = 7;

            - continuam alegerea elementelor lui x pana cand tuturor coeficientilor functiei f li s-a asociat componenta corespunzatoare in vectorul x.

            Obtinem in final x = (5,7,-5,-8,-7,3,8). Valoarea maxima a functiei  este

 f(5,7,-5,-8,-7,3,8) = 270.

            Programul Pascal care implementeaza algoritmul este urmatorul:

program functie_greedy;

var a,c,x : array [1..15]  of shortint;

    i,j,k,n,r,l : byte;

    h : shortint;

    s : integer;

    t : boolean;

    f : text;

    procedure min(var val : shortint; var poz : byte);

    var minim : shortint;

        i : byte;

    begin

       minim := 127;

       poz := 0;

       for i := 1 to k do

           if (c[i] < minim) and (c[i] <> 0) then

              begin

                 minim := c[i] ;

                 poz := i;

              end;

       val := minim;

    end;

    procedure max(var val : shortint; var poz:byte);

    var maxim : shortint;

        i:byte;

    begin

       maxim := -128;

       poz := 0;

       for i := 1 to k do

           if (c[i] > maxim) and (c[i] <> 0) then

              begin

                 maxim := c[i] ;

                 poz := i;

              end;

       val := maxim;

    end;

begin

   assign (f,'multime.txt');

   reset(f);

   i := 0;

   while not eoln(f) do

      begin

         i := i + 1;

         read(f,a i );

      end;

   n := i;

   readln(f);

   i := 0;

   while not eoln(f) do

      begin

         i := i + 1;

         read(f,c i );

      end;

   k := i;

   close(f);

   repeat

      t := true;

      for i := 1 to n-1 do

          if ( a[i] >a[i + 1]  then

             begin

                h := a[i] ;

                a[i] := a[i + 1] ;

                a[i + 1] := h;

                t := false;

             end;

   until t;

   write ('Multimea A :  ');

   for i := 1 to n do

       write (a[i] ,',');

   writeln (chr(8),' ');

   i := 1;

   r := 1;

   s := 0;

   min(h,l);

   while (h<0) and (r< k) do

      begin

         x[l] := a[i] ;

         s := s +  c[l] *x[l] ;

         c[l] := 0;

         i := i + 1;

         r := r + 1;

         min(h,l);

      end;

   if ( r < k ) then

      begin

         i := n;

         max(h,l);

         while ( r <  k ) do

            begin

               x[l] := a[i] ;

               s := s + c[l]  * x[l] ;

               c[l] := 0;

               i := i - 1;

               r := r + 1;

               max(h,l);

            end;

      end;

   write ('Solutie : x (');

   for i := 1 to k do

       write (x[i] ,',');

   writeln (chr(8),')');

   write (' Valoarea maxima a functiei este ',s);

   readln;

end.

Pentru fisierul de intrare „multime.txt”:

8 -7 3 -1 5 7 -8 -5 2 3                       

3 6 -1 -9 -9 3 8

iesirea va fi: x = (5,7,-5,-8,-7,3,8) si valoarea maxima a functiei este 270.








Politica de confidentialitate

DISTRIBUIE DOCUMENTUL

Comentarii


Vizualizari: 584
Importanta: rank

Comenteaza documentul:

Te rugam sa te autentifici sau sa iti faci cont pentru a putea comenta

Creaza cont nou

Termeni si conditii de utilizare | Contact
© SCRIGROUP 2019 . All rights reserved

Distribuie URL

Adauga cod HTML in site