Metoda Trierii

Definiție

Metoda trierii reprezintă o metodă care cercetează toate cazurile posibile introduse astfel selectînd soluțiile care ar îndeplini condiția problemei.
Astfel, soluţia unei probleme poate fi găsită analizînd consecutiv elementele Si ale unei mulţimi finite S = {s1, s2, …, si , …, sk}, denumită mulţimea soluţiilor posibile.

Aplicații alte tehnicilor de programare

Aceste tehnici de programare sunt folosite într-un mare număr de probleme și aplicații, printre care se numără:

• Minimizarea timpului mediu de așteptareț
• Interclasarea optimă a șirurilor ordonate
• Coduri Huffman
• Cele mai scurte drumuri care pleacă din același punct
• Problema comis-voiajorului

Problemă din cotidian: O statie de benzinarie trebuie sa satisfaca cerearea a n clienti. Se cunoaste timpul de servire necesar fiecarui client. Realizati un program care stabileste o ordine de servire a clientilor astfel incat timpul total de asteptare sa fie minim.

Program p2;

Type benz=record

ins, sfs:integer;

ord:integer; end;

Var v:array [1..100] of benz;

n, ultim, nr:integer;

Procedure citire_clienti;

Var hh, mm, i:integer;

begin

Write (‘n= ‘); Readln (n);

for i:=1 to n do begin

Write (‘Clientul cu nr. ‘,i,’cand este servit? (ora si minutul)’);

Readln (hh, mm);

v[i].ins:=hh*60+mm;

Write (‘clientul cu nr ‘, i, ‘ cand a terminat alimentarea ? ‘);

Readln (hh, mm);

v[i].sfs:=hh*60+mm;

v[i].ord:=i; end; end;

Procedure afisare_clienti;

Var i:integer;

Begin

Write (‘ cand incepe sa fie servit si cand a terminat alimentarea: ‘);

for i:=1 to n Do

Write (‘(‘v[i].ins,’,’,v[i].sfs, ‘,’,v[i].ord’)’);

Writeln;  end;

Procedure sortare_clienti;

Var i,j:integer;

t:benz;

Begin

for i:=1 to n-1 Do

for j:=i+1 to n Do

if (v[j].sfs

Begin

t:=v[i]; v[i]:=v[j];

v[j]:=t; end; end;

Procedure alg_greedy;

var i:integer;

Begin

Write (‘posibilii clienti, in ordine: ‘);

ultim:=1;

nr:=1;

Write (v[i].ord, ‘ ‘);

for i:=2 to n do

if (v[i].ins>v[ultim].sfs) then

begin

Write (v[i].ord, ‘ ‘);

ultim:=i;

nr:=nr+1;

end;

Writeln (‘in total se pot alege maxim’,nr, ‘clienti’);

begin

citire_clienti;

afisare_clienti;

sortare_clienti;

afisare_clienti;

alg_greedy;

END.

Concluzii

Beneficiul metodei trierii constă în faptul că programele care folosesc această metodă sunt simple, iar la verificarea este necesar de introdus multe date. Viteza acestui algoritm depinde de cîte elemente k (cele căutate) sunt în mulțimea S (toate elementele posibile). 

Tehnica Greedy nu are o structură standard pentru toate tipurile de algoritmi, de aceea nu se poate standardiza.
›