Revizia anterioară Revizia următoare
Programare dinamica
(Categoria Tehnici de programare, autor Catalin Tiseanu)
Plan de atac (probleme-candidat):
1. http://www.main.edu.pl/user.phtml?op=showtask&task=wie&con=PA2009&lang=en
Reducerea complexitatii, transformarea problemei intr-una de construire a unui arbore binar.
2. http://code.google.com/codejam/contest/dashboard?c=32001#s=p0&a=3
3. http://code.google.com/codejam/contest/dashboard?c=32001#s=p3&a=3
4. http://code.google.com/codejam/contest/dashboard?c=32015#s=p1&a=1
5. http://code.google.com/codejam/contest/dashboard?c=32010#s=p3&a=3
Sugestii Silviu
- poate ca nu trebuie sa spunem tot despre programare dinamica intr-un singur articol; spre exemplu putem facem doua articole: PD basic si PD advanced
- cred ca era si ceva prin Cartea lui Francu' despre programare dinamica; ar merge incorporat (eventual in pd_basic).
Introducere
Programarea dinamică este o metodă utilă pentru a rezolva probleme care pot fi obţinute prin compunerea a mai multor bucăţi, a căror soluţie poate fi apoi determinată optim. Se bazează în principal pe proprietatea unei probleme de a putea fi rezolvată optim dacă se cunosc soluţii optime la sub-problemele ei.
De menţionat că 'programare' nu se referă aici la scrierea de cod într-un limbaj de programare, ci la 'programare matematica', care constă în optimizarea unei funcţii prin alegerea de valori dintr-o mulţime anume.
Scopul acestui articol nu este să ofere o introducere in programare dinamică (pentru aceasta poate fi consultat excelentul tutorial de pe TopCoder Dynamic Programming : From novice to advanced). În schimb, acest articol îşi propune să ofere nişte 'smenuri' mai avansate de rezolvare a problemelor cu programare dinamică.
Programare dinamică cu reducerea loop-ului interior
Să considerăm următoarea problema:
Problema 1: Drilling
Se da un şir de N numere naturale (a1, a2, ..., aN). Se ştie că un prefix al acestui şir (posibil chiar prefixul nul) este prost. Se ştie de asemenea că se poate testa orice poziţie i în timp ai dacă este proastă. Să se determine timpul minim în cazul cel mai defavorabil pentru aflarea lungimii maxime a prefixului şirului care este prost.
Exemplu:
Pentru secvenţa de numere (8 24 12 6), răspunsul ar fi 42. Astfel, se testează mai întâi poziţia 2. Dacă nu este proastă, mai rămâne de testat poziţia 1. Altfel, în cel mai rău caz mai trebuie testate poziţiile 3 şi 4, aducând timpul total la 24 + 12 + 6 = 42.
Rezolvare:
O să începem prin a da altă îmbrăcăminte problemei. Astfel, să ne imaginăm că am construi un arbore binar de căutare pe şirul dat, având drept chei poziţiile din şir, şi drept valori auxiliare valorile poziţiilor respective din şir (un nod cu cheia i va avea valoarea auxiliara ai.
Acum, există mulţi arbori binari de căutare posibile pentru şirul iniţial. Totuşi, să presupunem că am construit unul. Atunci, strategia noastra de testare a elementelor din şir se va desfăşura conforma arborelui. Astfel, testăm mai întâi în poziţia din rădăcină. Dacă poziţia respectivă este proastă, ne ducem în fiul drept. Altfel, mergem in fiul stâng. În ambele cazuri se reia procedeul. Căutarea se termină cand nu mai putem merge într-un fiu.
Acum, să observăm că dacă considerăm costul unui drum în arbore să fie suma
Programare dinamica folosind bitmask
In continuare vom vedea un exemplu de programare dinamica unde vom folosi un bitmask (codificat pe un intreg) pentru a tine spatiul starilor.
Astfel sa presupunem ca avem nevoie sa tinem un vector caracteristic pentru o multime.
Daca cardinalul acesteia este suficient de mic putem folosi un intreg pentru a codifica aceasta informatie astfel:
Fie multimea A = { x1, x2, ... xn }.
Atunci bitmaskul unei partitii a lui A, MASK, va avea bitul i egal cu 1 numai si numai daca xi apartine partitiei.
Desigur, aceasta reprezentare duce la o complexitate direct proportionala cu 2 card(A).
Exemplu
Programare dinamica folosind vectori de numere intregi
To be continued ...
