Note de curs, clasele 11-12, 20 februarie 2014

From Algopedia
Jump to navigationJump to search

Programare dinamică

Această lecție rezumă tot ce consider că merită povestit despre programarea dinamică. Probabil nu vom acoperi chiar tot în această lecție.

Exemple introductive

Vom începe cu exemple pe care să putem studia proprietățile programării dinamice (numerele lui Fibonacci, distanța Levenshtein).

Generalități

Clasificarea soluției unei probleme ca „programare dinamică” necesită două condiții:

  1. Substructura optimă a subproblemelor. Aceasta înseamnă că soluția optimă problemei poate fi construită din soluțiile optime ale subproblemelor.
  2. Suprapunerea subproblemelor. Aceasta înseamnă că problema poate fi descompusă în subprobleme, dar numărul subproblemelor este relativ mic.

Comparați această definiție cu proprietățile altor două metode:

  • greedy: substructură optimă, proprietatea alegerii greedy
  • divide et impera: subprobleme care nu se suprapun

În ce categorie se încadrează următorii algoritmi?

  • mergesort
  • quicksort
  • Dijkstra
  • Kruskal
  • Prim
  • Floyd-Warshall
  • problema rucsacului
  • calculul diametrului unui arbore
  • problema cu ouăle și zgârie-norii

În general, subproblemele pot fi sistematizate într-un tabel. Pentru a le calcula, există două abordări:

  • Top-down, numită și memoizare. Aceasta se implementează, de obicei, recursiv. La fiecare intrare în funcția recursivă, algoritmul verifică dacă nu cumva a rezolvat deja această subproblemă. La sfârșitul funcției recursive, algoritmul salvează rezultatul subproblemei pe care tocmai a rezolvat-o.
  • Bottom-up. Aceasta își alege ordinea rezolvării subproblemelor astfel încât, la rezolvarea unei subprobleme, toate sub-subproblemele de care depinde ea să fi fost deja rezolvate.

Abordarea top-down are câteva dezavantaje:

  • este „leneșă” (lazy), deci ordinea rezolvării subproblemelor este mai impredictibilă;
  • poate avea probleme cu stiva;
  • completează matricea într-o ordine aleatoare, ceea ce distruge cache-ul procesorului;
  • are nevoie de întregul tabel (pe când abordarea bottom-up poate reține, în unele cazuri, doar anumite subtabele)

În general numai abordarea bottom-up este considerată programare dinamică. Abordarea top-down este mai mult o abordare recursivă cu memoizare.

Probleme

Vom insista numai acolo unde este cazul.

  • cel mai lung subșir crescător; rezolvări O(n2) și O(n log n)
  • distanța Levenshtein (discutată la început, dar o trec ca să fie pe listă)
  • numărul de parantezări corecte pentru un șir de 2 * n caractere '(' și ')'
  • Se dă un vector cu 2 * n elemente. Doi jucători aleg pe rând câte un număr de la capete. La final, jucătorul cu suma mai mare câștigă.
    • să se demonstreze că primul jucător câștigă sau face remiză întotdeauna
    • să se determine scorul maxim pe care îl poate obține
  • dându-se n, să se tipărească un număr în baza 10 care folosește doar cifrele 0 și 1 și care se divide cu n
    • dacă se cere cel mai mic număr -- programare dinamică
    • dacă se cere orice număr -- principiul lui Dirichlet (generăm maxim n numere de forma 111...1 și facem diferența)
  • Se dă un vector cu n elemente. Să se tipărească o submulțime cu sumă maximă, divizibilă cu n
  • Se dă o rețea Manhattan de 4 x n noduri. Să se afle câte cicluri hamiltoniene există.
  • produs optim de matrice
  • programare dinamică pe arbore: planificarea petrecerii companiei
  • programare dinamică pe arbore: pomul de Crăciun. Un arbore are câte un bec și câte un buton în fiecare nod. La apăsarea butonului, becul din nod și din toți vecinii își schimbă starea. Să se găsească o modalitate de a aprinde toate becurile.
  • Floyd-Warshall
  • problema rucsacului (timp pseudo-polinomial)
    • variațiuni: problema restului cu număr minim de monede
  • ouăle și zgârie-norii
  • cel mai lung subșir comun (pe sărite) între două șiruri de caractere
  • cea mai mare clică într-un graf-permutare
  • Să se transforme un string în palindrom printr-un număr minim de inserări în string

Optimizări

Generalități despre reconstituirea soluției dându-se tabelul de subprobleme. Exemple.

De multe ori se cere doar valoarea (costul) soluției optime, nu și soluția însăși. Atunci putem stoca doar o parte din tabelul cu valorile subproblemelor. Exemple.

Uneori ni se cere și soluția însăși, dar nu avem la dispoziție destulă memorie pentru a stoca întreg tabelul de subprobleme. Există un truc care dublează timpul de rulare, dar reduce memoria folosită cu un ordin de O(sqrt(n)). Exemple.