clasa XI-B, 28.04-30.04. Tema: Metoda Greedy.

Această metodă se aplică la rezolvarea problemelor, care au următoarea structură:

§Se dă o mulţime A={a₁,a_a,…,a_n} formată din n elemente;

§Se cere să se determine o submulţime B, B A, care îndeplineşte anumite condiţii pentru a fi acceptată ca soluţie.

Pentru a evita trierea tuturor submulţimilor , în metoda Greedy se utilizează un criteriu care asigură alegerea directă a elementelor necesare din mulţimea A. De obicei criteriul nu este indicat explicit în enunţul problemei şi determinarea lui revine programatorului.

     Metoda Greedy ne propune o strategie de rezolvare a problemelor de optim în care se poate cauta optimul global prin alegeri succesive ale optimului local, ceea ce permite rezolvarea problemei fără nici o revenire la deciziile deja luate.

Problema spectacolelor.

     Într-o sală, într-o zi, trebuie planificate N spectacole. Pentru fiecare spectacol se cunoaşte intervalul în care se desfăşoară: [st, sf]. Se cere să se planifice un număr maxim de spectacole astfel încât sa nu se suprapună.

Algoritmul:

     Fie o planificare optimă a spectacolelor (un număr maxim k de spectacole i1, i2...ik. unde i1, i2,... ik aparţine {1,2,...N } şi spectacolul ij, are loc înaintea  spectacolului ij+1. O astfel de planificare îndeplineşte condiţia: spectacolul ij+1 începe după terminarea spectacolului ij.

=> 0 consecinţă imediată a condiţiei de mai sus este: spectacolul i, ia sfârşit înaintea terminării spectacolului tj+1 (consecinţa nu implica un efort de gândire deosebit).

     Vom construi o soluţie după următorul algoritm:

P1. sortăm spectacolele după ora terminării lor;

P2. primul spectacol programat este cel care se termină cel mai devreme;

P3. alegem primul spectacol dintre cele care urmează în sir ultimului spectacol programat care îndeplineşte condiţia că începe după ce s-a terminat ultimul spectacol programat;                              
P4. dacă tentativa de mai sus a eşuat (nu am găsit un astfel de spectacol) algoritmul se termină, altfel se programează spectacolul găsit şi algoritmul se reia de la pasul 3.

Acest program se încadrează in tehnica Greedy pentru că: la un pas se alege un spectacol (cu ora de terminare mai mare decât ora de terminare a ultimului spectacol programat iar dacă este posibil (dacă are ora de început după ora de sfârşit a ultimului spectacol programat) este adăugat soluţiei. Odată adăugat (programat) un spectacol, acesta rămâne in cadrul soluţiei.

Programul în limbajul Pascal.

Program Spectacole; Uses CRT;

Type Timp=Record

          O,M:Integer

          End;

     Spectacol=Array[1..2,1..10] Of Timp;

     Ordine=Array[1..10] Of Integer;

Var S:Spectacol;    O:Ordine;    N,I,H1,M1,H2,M2,K:Integer;

Procedure Sortare;

Var V:Boolean;    M,I:Integer;

Begin

  Repeat    V:=True;

  For I:=1 To N-1 Do

  If (S[2,O[I]].O>S[2,O[I+1]].O) Or

     ((S[2,O[I]].O=S[2,O[I+1]].O) And (S[2,O[I]].M>S[2,O[I+1]].M))

     Then Begin

            M:=O[I]; O[I]:=O[I+1];O[I+1]:=M;

            V:=False

          End

  Until V  End;

Begin  ClrScr;  Write ('Numarul de spectacole=') ; ReadLn (N);

  For I:=1 To N Do

      Begin        O[I]:=I;

    Write('Ora de inceput pentru spectacolul ',I, ' (hh min)=') ;

      ReadLn(H1,M1);

      S[1,I].O :=H1;  S[1,I].M :=M1;

    Write('Ora de sfirsit pentru spectacolul ', I , ' (hh min =') ;

      ReadLn(H2,M2);

      S[2,I].O :=H2;  S[2,I].M :=M2

      End;

      Sortare;

WriteLn('Ordinea spectacolelor este');

    WriteLn(O[1]) ;K:=1;

For I:=2 To N Do

If (S[1,O[I]].O>S[2,O[K]].O) Or

   ((S[1,O[I]].O=S[2,O[K]].O) And (S[1,O[I]].M>=S[2,O[K]].M))

   Then Begin

          WriteLn (O[I]);     K:=I

        End;

   ReadLn End.

Sarcini pentru rezolvare;

1. de citit par. 5.3, pag. 122
2. de rez. pr. 6,7 pag. 125
Problemele rezolvate le transmiteti la adresa: toloaca.svetlana@gmail.com pina la data de 30.04.2020.

Succese!!!