🐍 Python de la zero — Partea 8

🎯 Obiective

1. Recapitulare: ce știm deja?

În părțile anterioare am învățat să lucrăm cu variabile, condiții și repetări, apoi cu șiruri, liste și matrice. Am învățat funcții, recursivitate, programare dinamică și grafuri.

2. Ce înseamnă optimizare?

Într-o problemă de optimizare există mai multe soluții posibile și vrem una cât mai bună.

• minimizare — alegem o valoare cât mai mică;
• maximizare — alegem o valoare cât mai mare.

Exemplu: avem activități și vrem să alegem cât mai multe fără să se suprapună.

3. Ideea algoritmului Greedy

Greedy înseamnă să construim soluția pas cu pas, alegând la fiecare pas o variantă care pare cea mai bună în acel moment.

O schemă generală este:

solutie = ...

pregatim datele

cat timp mai avem alegeri:
    alegem varianta cea mai buna local
    daca alegerea este permisa:
        o pastram

4. Greedy cu sortare

Multe probleme Greedy devin simple după ce sortăm elementele după un criteriu.

a.sort()

for x in a:
    # analizăm x
    ...

Sortarea trebuie făcută după criteriul care susține strategia. Nu există o singură ordine corectă pentru toate problemele.

5. Problema activităților

Avem activități cu moment de început și sfârșit. Vrem să alegem cât mai multe activități care nu se suprapun.

Strategia Greedy corectă: alegem activitatea care se termină cel mai devreme, apoi căutăm următoarea activitate care începe după terminarea celei alese.

activitati.sort(key=lambda x: x[1])

ultima = -1
numar = 0

for activitate in activitati:
    inceput = activitate[0]
    sfarsit = activitate[1]

    if inceput >= ultima:
        numar = numar + 1
        ultima = sfarsit

print(numar)

6. Problema monedelor

Avem valori de monede și vrem să obținem o sumă folosind cât mai puține monede. Strategia „aleg mereu cea mai mare monedă posibilă” funcționează pentru anumite sisteme de monede, dar nu pentru orice sistem.

monede = [10, 5, 1]
suma = 28
numar = 0

for moneda in monede:
    while suma >= moneda:
        suma = suma - moneda
        numar = numar + 1

print(numar)

7. Greedy și programarea dinamică

8. Greedy în grafuri

În partea 7 am introdus grafurile și drumurile. Unele probleme de grafuri au soluții Greedy.

Dijkstra

Pentru muchii cu costuri nenegative, Dijkstra alege repetat vârful nevizitat cu distanța cunoscută cea mai mică și încearcă să îmbunătățească distanțele vecinilor.

distanta[start] = 0

repetam:
    alegem v care are distanta minima
    il marcam

    pentru fiecare vecin u al lui v:
        nou = distanta[v] + cost(v, u)
        daca nou < distanta[u]:
            distanta[u] = nou

9. Arbore de acoperire de cost minim

Un graf neorientat conex poate avea un arbore care leagă toate vârfurile fără cicluri. Dacă vrem cost total minim, căutăm un arbore de acoperire minim.

Kruskal — ideea

1. Sortăm muchiile crescător după cost.
2. Luăm muchia cea mai ieftină care nu formează un ciclu.
3. Continuăm până când avem suficiente muchii pentru a lega toate vârfurile.

10. Cum verificăm o strategie Greedy?

1. Definim clar ce alegere facem.
2. Arătăm că alegerea este permisă.
3. Explicăm de ce alegerea nu ne strică posibilitatea de a obține o soluție optimă.
4. Repetăm argumentul pentru pașii următori.

Nu este suficient să spunem „pare cea mai bună”. Trebuie să existe un motiv matematic sau algoritmic.

11. Exerciții rezolvate

activitati = [(1, 3), (2, 5), (4, 7), (6, 8), (8, 9)]
activitati.sort(key=lambda x: x[1])

ultima = -1
numar = 0

for a in activitati:
    if a[0] >= ultima:
        numar = numar + 1
        ultima = a[1]

print(numar)

monede = [25, 10, 5, 1]
suma = 63
numar = 0

for moneda in monede:
    while suma >= moneda:
        suma = suma - moneda
        numar = numar + 1

print(numar)

a = [7, 2, 9, 4, 6]
maxim = a[0]

for x in a:
    if x > maxim:
        maxim = x

print(maxim)

nou = distanta[v] + cost

12. Exerciții propuse

13. Greșeli frecvente

• A presupune că orice problemă de minimizare este Greedy.
• A alege „cea mai mare” sau „cea mai mică” valoare fără justificare.
• A sorta după criteriul greșit.
• A confunda o soluție validă cu o soluție optimă.
• A folosi Dijkstra când există muchii cu cost negativ.
• A trece direct la cod fără să testezi strategia pe exemple mici.

14. Checklist final

15. Legătura cu următoarea parte

După Greedy, următorul pas natural este aprofundarea algoritmilor avansați: complexitate, tehnici de căutare și optimizare, structuri de date mai eficiente și implementări mai rapide ale algoritmilor pe grafuri.