Tehnici de programare

Aprofundarea metodelor algoritmice avansate pentru rezolvarea problemelor complexe de programare.

Metoda Greedy — alegerea local optimă

Greedy (lacom) construiește soluția pas cu pas, alegând la fiecare pas varianta care pare cea mai bună la momentul respectiv (optimul local), fără a reveni vreodată asupra alegerilor făcute. De aici vin cele două trăsături care se cer la examen:

• nu revine asupra deciziilor — spre deosebire de backtracking;
• este rapidă (de regulă complexitate polinomială, adesea dominată de o sortare inițială — O(n log n)), dar nu garantează optimul global pentru orice problemă.

Schema generală: se sortează sau se ordonează candidații după un criteriu de selecție, apoi se parcurg în ordine și fiecare candidat se adaugă la soluție doar dacă nu strică validitatea acesteia.

Exemple clasice unde Greedy dă optimul: problema spectacolelor (selectarea numărului maxim de activități care nu se suprapun — criteriul corect este ora de terminare, nu durata), problema rucsacului fracționar (obiectele pot fi tăiate — se aleg în ordinea descrescătoare a raportului valoare/greutate), plata unei sume cu număr minim de bancnote pentru sisteme monetare canonice, algoritmii Kruskal și Prim pentru arborele parțial de cost minim.

Confuzia clasică: la rucsacul 0/1 (obiectele nu pot fi fracționate) Greedy poate rata optimul — acolo se folosește programarea dinamică. La examen, când se cere să justifici de ce merge Greedy, argumentul este că optimul local conduce la optim global pentru acea problemă anume, nu în general.

Divide et Impera — împarte și stăpânește

Divide et Impera rezolvă o problemă prin trei etape care se enunță exact așa la examen:

• Divide: problema se împarte în subprobleme de același tip, de dimensiuni mai mici (de regulă două jumătăți);
• Impera (cucerește): subproblemele se rezolvă recursiv; când dimensiunea devine suficient de mică (cazul de bază), se rezolvă direct;
• Combină: soluțiile subproblemelor se asamblează în soluția problemei inițiale.

Condiția esențială: subproblemele trebuie să fie independente — nu se suprapun. Dacă aceleași subprobleme apar de mai multe ori (de exemplu la șirul lui Fibonacci), Divide et Impera devine ineficientă și se trece la programare dinamică.

Exemple canonice: căutarea binară (O(log n)) — la fiecare pas se elimină jumătate din interval; MergeSort (O(n log n)) — împarte vectorul în două, sortează recursiv și interclasează; QuickSort — partiționează în jurul unui pivot (elementele mai mici la stânga, mai mari la dreapta), apoi sortează recursiv cele două zone; turnurile din Hanoi.

Capcană frecventă la scrierea recursivității: lipsa sau formularea greșită a cazului de bază duce la recursivitate infinită și depășirea stivei (stack overflow). La căutarea binară, condiția de oprire corectă este st > dr (interval vid), iar mijlocul se calculează cu m = (st + dr) / 2 pe indici întregi.

Backtracking — parcurgerea sistematică cu revenire

Backtracking generează toate soluțiile posibile ale unei probleme construind soluția ca un vector x[1..n], element cu element. Pentru fiecare poziție k se încearcă pe rând toate valorile candidate; o valoare este acceptată doar dacă trece de condițiile de continuare (validare). Dacă nicio valoare nu mai e validă pe poziția k, algoritmul revine (se întoarce) la poziția k-1 și încearcă acolo următoarea valoare — de aici numele.

Elementele care se cer la examen:

• soluțiile se construiesc în ordine lexicografică atunci când candidații se încearcă în ordine crescătoare;
• condițiile de continuare taie din start ramurile care nu pot duce la soluție — fără ele, algoritmul degenerează în generare exhaustivă;
• complexitatea este de regulă exponențială (de exemplu O(n!) la permutări), motiv pentru care backtracking se aplică doar pe dimensiuni mici.

Probleme standard: generarea permutărilor (x[k] diferit de toate valorile anterioare), aranjamente și combinări (la combinări se impune suplimentar x[k] > x[k-1], ca să nu se genereze aceeași mulțime de mai multe ori), problema celor n regine (regine pe linii diferite, coloane diferite și diagonale diferite — diagonala se verifică prin |x[i] - x[k]| diferit de k - i), colorarea hărților, parcurgerea labirintului.

Greșeala tipică de raționament: backtracking NU se oprește la prima soluție decât dacă i se cere explicit; implicit el explorează tot spațiul soluțiilor.

Programarea dinamică — subprobleme care se suprapun

Programarea dinamică se aplică problemelor de optimizare care au două proprietăți — amândouă se pot cere ca justificare:

• substructură optimă: soluția optimă a problemei conține soluțiile optime ale subproblemelor;
• subprobleme suprapuse: aceleași subprobleme apar de mai multe ori în descompunerea recursivă.

Ideea centrală: fiecare subproblemă se rezolvă o singură dată, iar rezultatul se memorează într-un tablou (tabelul de programare dinamică), de unde se refolosește. Astfel o recursivitate exponențială devine algoritm polinomial.

Cele două abordări: bottom-up (se completează tabelul de la cazurile mici spre problema mare, iterativ) și top-down cu memoizare (recursivitate plus tablou în care se rețin rezultatele deja calculate).

Exemplul didactic standard este Fibonacci: recursiv pur are complexitate exponențială pentru că F(n-2) se recalculează de multe ori; cu un vector completat de la stânga la dreapta devine O(n). Alte probleme de examen: numărul de drumuri într-o matrice (fiecare celulă se obține din suma vecinilor de sus și din stânga), subșirul crescător de lungime maximă, rucsacul 0/1 (tabel cu linii pentru obiecte și coloane pentru capacități), triunghiul de sumă maximă.

Distincția față de Divide et Impera este întrebare de teorie: ambele descompun problema, dar la Divide et Impera subproblemele sunt independente, pe când programarea dinamică tratează exact cazul în care ele se suprapun. Distincția față de Greedy: Greedy face o singură alegere pe pas și nu o mai schimbă; programarea dinamică evaluează toate alegerile și o reține pe cea optimă.

Branch and Bound și alegerea tehnicii potrivite

Branch and Bound (ramifică și mărginește) este o rafinare a explorării spațiului de soluții pentru probleme de optimizare: spațiul stărilor se organizează ca un arbore, iar pentru fiecare ramură se calculează o margine (bound) — o estimare optimistă a celui mai bun rezultat care se mai poate obține pe acea ramură. Dacă marginea este mai slabă decât cea mai bună soluție găsită deja, întreaga ramură se taie fără a fi explorată.

Diferențe care se cer în comparațiile de la examen:

• Backtracking parcurge arborele în adâncime și taie ramuri doar pe baza condițiilor de validitate; se folosește tipic pentru a genera toate soluțiile.
• Branch and Bound poate parcurge arborele și pe lățime sau după cea mai promițătoare margine (best-first) și caută o singură soluție optimă, folosind funcția de mărginire pentru tăieri.

Aplicații clasice: problema comis-voiajorului, rucsacul 0/1 pe date mari, jocul de tip puzzle glisant (taquin).

Cum alegi tehnica la o problemă de examen — ghid rapid:

• se cer toate soluțiile / configurațiile valide → backtracking;
• problema se sparge în jumătăți independente → Divide et Impera;
• optimizare cu subprobleme care se repetă → programare dinamică;
• optimizare unde un criteriu local simplu dă mereu optimul (și poți justifica) → Greedy;
• optimizare pe spațiu uriaș, cu estimări care permit tăieri → Branch and Bound.

Capcana de punctaj: a numi „Greedy” un algoritm care de fapt reține toate variantele într-un tabel — acela este programare dinamică; Greedy nu păstrează decât alegerea curentă.

Test — 6 întrebări ca la examen