PROGRAMARE DINAMICĂ: CARACTERISTICI, EXEMPLU, AVANTAJE, DEZAVANTAJE - TEHNOLOGIE - 2025

Programare dinamică este un model de algoritm care rezolvă o problemă complexă prin împărțirea - l în subprobleme, stocarea rezultatelor acestora pentru a evita să recalculeze rezultatele.

Acest program este utilizat atunci când aveți probleme care pot fi împărțite în subprobleme similare, astfel încât rezultatele acestora să poată fi reutilizate. În mare parte, acest program este utilizat pentru optimizare.

Programare dinamică. Subprobleme suprapuse în secvența Fibonacci. Sursa: Wikimedia commons, en: Utilizator: Dcoatzee, urmărit de Utilizator: Stannered / Public domain

Înainte de a rezolva subproblemele disponibile, algoritmul dinamic va încerca să examineze rezultatele subproblemelor rezolvate anterior. Soluțiile la subprobleme sunt combinate pentru a obține cea mai bună soluție.

În loc să calculezi aceleași subprobleme de mai multe ori, poți stoca soluția ta într-o oarecare memorie, când întâlnești pentru prima dată acest subproblem. Când apare din nou în timpul soluției unui alt subproblem, se va lua soluția deja stocată în memorie.

Aceasta este o idee minunată pentru fixarea timpului de memorie, unde utilizarea unui spațiu suplimentar poate îmbunătăți timpul necesar pentru a găsi o soluție.

Caracteristici ale programării dinamice

Următoarele caracteristici esențiale sunt cele cu care trebuie să aveți o problemă înainte de a putea aplica programarea dinamică:

Substructura optimă

Această caracteristică exprimă faptul că o problemă de optimizare poate fi rezolvată combinând soluțiile optime ale problemelor secundare care o includ. Aceste substructuri optime sunt descrise prin recursivitate.

De exemplu, într-un grafic va fi prezentată o substructură optimă pe cea mai scurtă cale r care merge de la un vertex s la un vertex t:

Adică, în această cale cea mai scurtă, orice vârf intermediar i poate fi luat. Dacă r este cu adevărat cea mai scurtă rută, atunci poate fi împărțită în sub-rutele r1 (de la s la i) și r2 (de la i la t), astfel încât acestea să fie, la rândul lor, cele mai scurte rute între vârfurile corespunzătoare.

Prin urmare, pentru a găsi cele mai scurte căi, soluția poate fi formulată cu ușurință recursiv, ceea ce face algoritmul Floyd-Warshall.

Subprobleme suprapuse

Spațiul subproblem trebuie să fie mic. Adică, orice algoritm recursiv care rezolvă o problemă va trebui să rezolve aceleași subprobleme de mai multe ori, în loc să genereze noi subprobleme.

De exemplu, pentru a genera seria Fibonacci, putem considera această formulare recursivă: Fn = F (n - 1) + F (n - 2), luând ca caz de bază că F1 = F2 = 1. Atunci vom avea: F33 = F32 + F31, și F32 = F31 + F30.

După cum puteți vedea, F31 este rezolvat în subtreadurile recursive atât ale F33 cât și ale F32. Deși numărul total de subprobleme este într-adevăr mic, dacă adoptați o soluție recursivă ca aceasta, veți ajunge să rezolvați din nou aceleași probleme.

Acest lucru este luat în considerare de programarea dinamică, astfel încât rezolvă fiecare subproblem o singură dată. Acest lucru poate fi realizat în două moduri:

Abordare de sus în jos

Dacă soluția la orice problemă poate fi formulată recursiv folosind soluția subproblemelor sale și dacă aceste subprobleme se suprapun, atunci soluțiile pentru subprobleme pot fi ușor memorate sau stocate într-un tabel.

De fiecare dată când este căutată o nouă soluție de subproblem, tabelul va fi verificat pentru a vedea dacă a fost rezolvată anterior. În cazul în care o soluție este stocată, aceasta va fi utilizată în loc să o calculeze din nou. În caz contrar, subproblema va fi rezolvată, stocând soluția în tabel.

Abordarea de jos în sus

După ce soluția unei probleme este formulată recursiv în termenii subproblemelor sale, se poate încerca reformularea problemei într-o manieră ascendentă: în primul rând, vom încerca să rezolvăm subproblemele și să folosim soluțiile lor pentru a ajunge la soluții pentru subproblemele mai mari.

Acest lucru se face, de asemenea, în general, sub formă de tabel, generând iterativ soluții pentru subprobleme mai mari și mai mari prin utilizarea soluțiilor pentru subprobleme mai mici. De exemplu, dacă valorile F31 și F30 sunt deja cunoscute, valoarea F32 poate fi calculată direct.

Comparație cu alte tehnici

O caracteristică semnificativă a unei probleme care poate fi rezolvată prin programare dinamică este aceea că ar trebui să aibă suprapuneri care se suprapun. Acesta este ceea ce distinge programarea dinamică de tehnica de împărțire și cucerire, unde nu este necesar să stocați cele mai simple valori.

Este similar cu recursul, deoarece la calcularea cazurilor de bază, valoarea finală poate fi determinată inductiv. Această abordare de jos în sus funcționează bine atunci când o valoare nouă depinde doar de valorile calculate anterior.

Exemplu

Pași minimi pentru a ajunge la 1

Pentru orice număr întreg pozitiv "e" se poate efectua oricare dintre următoarele trei etape.

- Reduceți numărul 1 din număr. (e = e-1).

- Dacă este divizibil cu 2, se împarte la 2 (dacă e% 2 == 0, atunci e = e / 2).

- Dacă este divizibil cu 3, se împarte la 3 (dacă e% 3 == 0, atunci e = e / 3).

Pe baza etapelor de mai sus, ar trebui găsit numărul minim de acești pași pentru a aduce e la 1. De exemplu:

- Dacă e = 1, rezultă: 0.

- Dacă e = 4, rezultă: 2 (4/2 = 2/2 = 1).

- Când e = 7, rezultă: 3 (7-1 = 6/3 = 2/2 = 1).

concentra

S-ar putea să ne gândim să alegem întotdeauna pasul care face n cât mai jos și să continuăm astfel, până când ajunge la 1. Cu toate acestea, se poate vedea că această strategie nu funcționează aici.

De exemplu, dacă e = 10, pașii ar fi: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 pași). Cu toate acestea, forma optimă este: 10-1 = 9/3 = 3/3 = 1 (3 trepte). Prin urmare, trebuie să se încerce toate etapele posibile care pot fi făcute pentru fiecare valoare a n găsite, alegând numărul minim al acestor posibilități.

Totul începe cu recurs: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} dacă e> 1, luând ca bază: F (1) = 0. Având ecuația de recurență, puteți începe să codați recursiunea.

Cu toate acestea, se poate observa că are subprobleme suprapuse. Mai mult, soluția optimă pentru o intrare dată depinde de soluția optimă a subproblemelor sale.

Ca și în memorare, unde soluțiile subproblemelor rezolvate sunt stocate pentru utilizare ulterioară. Sau la fel ca în programarea dinamică, pornești de jos, lucrându-te până la e. Apoi ambele coduri:

memorizare

Programare dinamică de jos în sus

Avantaj

Unul dintre avantajele principale ale utilizării programării dinamice este acela că grăbește procesarea, deoarece se folosesc referințele care au fost calculate anterior. Deoarece este o tehnică de programare recursivă, reduce liniile de cod din program.

Algoritmi vorați vs programare dinamică

Algoritmii lacomi sunt similari cu programarea dinamică prin faptul că sunt ambele instrumente de optimizare. Cu toate acestea, algoritmul lacom caută o soluție optimă la fiecare pas local. Adică se caută o alegere lacomă în speranța de a găsi un optim global.

Prin urmare, algoritmii lacomi pot face o presupunere care pare optimă la momentul respectiv, dar devine scumpă în viitor și nu garantează un optim global.

Pe de altă parte, programarea dinamică găsește soluția optimă pentru subprobleme și apoi face o alegere în cunoștință, combinând rezultatele acelor subprobleme pentru a găsi de fapt cea mai optimă soluție.

Dezavantaje

- Este necesară multă memorie pentru a stoca rezultatul calculat al fiecărui subproblem, fără a putea garanta că valoarea stocată va fi folosită sau nu.

- De multe ori, valoarea de ieșire este stocată fără a fi niciodată folosită în următoarele subprobleme în timpul executării. Aceasta duce la utilizarea inutilă a memoriei.

- În programarea dinamică, funcțiile sunt numite recursiv. Aceasta menține memoria stivei în continuă creștere.

Recursiune și programare dinamică

Dacă aveți memorie limitată pentru a rula codul dvs. și viteza de procesare nu este o problemă, puteți utiliza recursiv. De exemplu, dacă dezvoltați o aplicație mobilă, memoria este foarte limitată pentru a rula aplicația.

Dacă doriți ca programul să ruleze mai repede și să nu aibă restricții de memorie, este de preferat să utilizați programarea dinamică.

Aplicații

Programarea dinamică este o metodă eficientă de rezolvare a problemelor care ar putea părea extrem de dificil de rezolvat într-un timp rezonabil.

Algoritmele bazate pe paradigma dinamică a programării sunt utilizate în multe domenii ale științei, inclusiv în numeroase exemple în inteligența artificială, de la planificarea rezolvării problemelor până la recunoașterea vorbirii.

Algoritmi bazate pe programare dinamică

Programarea dinamică este destul de eficientă și funcționează foarte bine pentru o gamă largă de probleme. Mulți algoritmi pot fi văzuți ca aplicații de algoritmi lacomi, cum ar fi:

- seria numerelor Fibonacci.

- Turnurile Hanoiului.

- Toate perechile de rute mai scurte prin Floyd-Warshall.

- Problema rucsacului.

- Planificarea proiectului.

- Cel mai scurt drum prin Dijkstra.

- Controlul zborului și robotica.

- Probleme de optimizare matematică.

- Timeshare: programați treaba pentru a maximiza utilizarea procesorului

Serie de numere Fibonacci

Numerele Fibonacci sunt numerele găsite în următoarea secvență: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 etc.

În terminologia matematică, secvența Fn a numerelor Fibonacci este definită prin formula de recurență: F (n) = F (n -1) + F (n -2), unde F (0) = 0 și F ( 1) = 1.

Abordare de sus în jos

În acest exemplu, un tablou de căutare cu toate valorile inițiale este inițializat cu -1. Ori de câte ori este nevoie de soluția unui subproblem, această matrice de căutare va fi căutată mai întâi.

Dacă valoarea calculată există, atunci această valoare va fi returnată. În caz contrar, rezultatul va fi calculat pentru a fi stocat în tabloul de căutare, astfel încât să poată fi reutilizat ulterior.

Abordarea de jos în sus

În acest caz, pentru aceeași serie Fibonacci, mai întâi se calculează f (0), apoi f (1), f (2), f (3) și așa mai departe. Astfel, soluțiile subproblemelor sunt construite de jos în sus.

Referințe

1. Vineet Choudhary (2020). Introducere în programarea dinamică. Dezvoltator Insider, preluat de la: developerinsider.co.
2. Alex Allain (2020). Programare dinamică în C ++. C Programare. Preluat de la: cprogramming.com.
3. După Academie (2020). Idee de programare dinamică. Luat de la: afteracademy.com.
4. Aniruddha Chaudhari (2019). Programare dinamică și recursiune - diferență, avantaje cu exemplu. Pila CSE. Luate de la: csestack.org.
5. Chef de cod (2020). Tutorial pentru programare dinamică. Luat de la: codechef.com.
6. Programiz (2020). Programare dinamică. Luat de la: programiz.com.