Tehnici de optimizare (interschimbare, greedy, divide et impera)

Pe scurt

Tehnicile de optimizare sunt strategii fundamentale în programare care ajută la obținerea unor soluții eficiente din punct de vedere al timpului de execuție și al utilizării memoriei. Cele trei tehnici principale studiate la nivel liceal sunt: interschimbarea (metoda schimbului), metoda greedy (lacomă) și divide et impera (divide și stăpânește). Înțelegerea acestor tehnici este esențială pentru rezolvarea eficientă a problemelor de concurs și a celor din viața reală.

Interschimbarea (Metoda schimbului)

Aceasta este o tehnică simplă, dar puternică, care constă în schimbarea valorilor a două variabile fără a utiliza o variabilă auxiliară (de exemplu, prin însumare sau prin XOR). Deși pare banală, interschimbarea este baza multor algoritmi de sortare (bubble sort, selection sort) și de permutare. În probleme de optimizare, interschimbarea poate fi folosită pentru a reordona elemente astfel încât să se minimizeze o anumită funcție cost (de exemplu, ordonarea după un criteriu de eficiență).

• Exemplu - Sortare prin selecție (selection sort): Se dă un vector de numere. La fiecare pas, se găsește minimul din partea nesortată și se interschimbă cu primul element din partea nesortată. Algoritmul este O(n²).

- Pentru vectorul [5, 3, 8, 1]

- Pasul 1: găsește minimul 1, îl schimbă cu 5 → [1, 3, 8, 5]

- Pasul 2: minimul din [3,8,5] este 3, rămâne pe loc

- Pasul 3: minimul din [8,5] este 5, schimbă cu 8 → [1,3,5,8]

- Se observă cum interschimbarea este operația centrală.

Metoda greedy (lacomă)

Această metodă presupune construirea unei soluții pas cu pas, alegând la fiecare pas cea mai avantajoasă opțiune locală, în speranța că aceasta va conduce la o soluție globală optimă. Exemple clasice sunt:

• Problema rucsacului fracționar
• Alegerea monedelor pentru o sumă dată
• Planificarea activităților (interval scheduling)
• Algoritmul lui Dijkstra pentru drumuri minime

Greedy nu funcționează întotdeauna (de exemplu, problema rucsacului 0/1 nu poate fi rezolvată greedy), dar atunci când funcționează, este extrem de eficientă (complexitate O(n log n) de obicei).

• Exemplu - Problema rucsacului fracționar (Fractional Knapsack): Avem un rucsac cu capacitatea W și obiecte cu greutate și valoare. Pentru a maximiza valoarea totală, alegem obiecte în ordinea descrescătoare a raportului valoare/greutate, putând lua fracțiuni din obiecte.

- Obiecte: (greutate: 10, valoare: 60), (20, 100), (30, 120), W=50

- Raporturi: 6, 5, 4

- Luăm integral primul (10,60), apoi al doilea (20,100), apoi din al treilea 20 unități (80) → total 240

- Acesta este optim global, iar algoritmul este O(n log n).

Divide et impera (Divide și stăpânește)

Această tehnică divide problema în subprobleme mai mici, independente, de același tip, le rezolvă recursiv și apoi combină rezultatele pentru a obține soluția problemei inițiale. Exemple reprezentative sunt:

• Quicksort
• Mergesort
• Căutarea binară
• Exponențierea rapidă
• Algoritmul lui Strassen pentru înmulțirea matricelor
• Problema turnurilor din Hanoi

Complexitatea tipică este O(n log n) sau O(n² log n), iar aplicarea corectă necesită identificarea punctului de divizare, a modului de combinare și a cazurilor de bază.

• Exemplu - Algoritmul Merge Sort: Pentru a sorta un vector, îl împărțim în două jumătăți egale, sortăm recursiv fiecare jumătate, apoi interclasăm cele două jumătăți sortate.

- Pentru [38, 27, 43, 3, 9, 82, 10]

- Se împarte în [38,27,43,3] și [9,82,10]

- Se sortează fiecare

- La final interclasarea produce [3,9,10,27,38,43,82]

- Complexitate O(n log n).

Verifică-te!

1. Care sunt cele trei tehnici principale de optimizare studiate la nivel liceal?
2. În ce constă diferența fundamentală dintre metoda greedy și divide et impera în modul de abordare a unei probleme?
3. Pentru ce tip de problemă (rucsac fracționar sau rucsac 0/1) funcționează metoda greedy și de ce nu funcționează pentru cealaltă?