programare dinamică este un model de algoritm care rezolvă o problemă complexă împărțind-o în subprobleme, stocând rezultatele acestora pentru a evita să fie nevoie să recalculeze aceste rezultate.
Acest program este utilizat atunci când aveți probleme care pot fi împărțite în subprobleme similare, astfel încât rezultatele lor să poată fi reutilizate. În cea mai mare parte, această programare este utilizată pentru optimizare.
Înainte de a rezolva subproblema disponibilă, algoritmul dinamic va încerca să examineze rezultatele subproblemelor rezolvate anterior. Soluțiile de subproblemă sunt combinate pentru a obține cea mai bună soluție.
În loc să calculați aceeași subproblemă de mai multe ori, vă puteți stoca soluția în memorie când întâlniți prima dată această subproblemă. Când apare din nou în timpul soluției unei alte subprobleme, va fi luată soluția deja stocată în memorie.
Aceasta este o idee minunată pentru a rezolva timpul de memorie, unde folosind spațiu suplimentar puteți îmbunătăți timpul necesar pentru a găsi o soluție..
Indice articol
Următoarele caracteristici esențiale sunt cele cu care trebuie să aveți o problemă înainte ca programarea dinamică să poată fi aplicată:
Această caracteristică exprimă faptul că o problemă de optimizare poate fi rezolvată prin combinarea soluțiilor optime ale problemelor secundare care o compun. Aceste substructuri optime sunt descrise prin recursivitate.
De exemplu, într-un grafic o substructură optimă va fi prezentată pe cea mai scurtă cale r care merge de la un vârf s la un vârf t:
Adică, pe această cale cea mai scurtă r, poate fi luat orice vârf intermediar i. Dacă r este într-adevăr cel mai scurt traseu, atunci acesta poate fi împărțit în subrutele r1 (de la s la i) și r2 (de la i la t), în așa fel încât acestea să fie la rândul lor cele mai scurte trasee între vârfurile corespunzătoare.
Prin urmare, pentru a găsi cele mai scurte rute, soluția poate fi ușor formulată recursiv, ceea ce face algoritmul Floyd-Warshall..
Spațiul subproblemă trebuie să fie mic. Adică, orice algoritm recursiv care rezolvă o problemă va trebui să rezolve aceleași subprobleme repetate, în loc să genereze noi subprobleme..
De exemplu, pentru a genera seria Fibonacci, această formulare recursivă poate fi considerată: 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 subarborii recursivi ai F33 și F32. Deși numărul total de subprobleme este cu adevărat mic, dacă adoptați o soluție recursivă de acest gen, veți ajunge să rezolvați aceleași probleme de nenumărate ori..
Acest lucru este luat în considerare de programarea dinamică, deci rezolvă fiecare subproblemă o singură dată. Acest lucru poate fi realizat în două moduri:
Dacă soluția la orice problemă poate fi formulată recursiv folosind soluția subproblemelor sale și dacă aceste subprobleme se suprapun, atunci soluțiile la subprobleme pot fi memorate cu ușurință sau stocate într-un tabel.
De fiecare dată când se caută o nouă soluție de subproblemă, tabelul va fi verificat pentru a vedea dacă a fost rezolvată anterior. Dacă este stocată o soluție, aceasta va fi utilizată în loc să o calculeze din nou. În caz contrar, subproblema va fi rezolvată, stocând soluția în tabel.
După ce soluția unei probleme este formulată recursiv în termeni de subprobleme, va fi posibil să încercăm să reformulăm problema într-un mod ascendent: mai întâi vom încerca să rezolvăm subproblemele și vom folosi soluțiile lor pentru a ajunge la soluții la subproblemele mai mari..
Acest lucru se face, de asemenea, în general sub formă de tabel, generând în mod iterativ soluții pentru subprobleme din ce în ce mai mari, utilizând soluții pentru subprobleme mai mici. De exemplu, dacă valorile F31 și F30 sunt deja cunoscute, valoarea F32 poate fi calculată direct.
O caracteristică semnificativă a unei probleme care poate fi rezolvată dinamic este că ar trebui să se suprapună subprobleme. Acesta este ceea ce distinge programarea dinamică de tehnica de divizare și cucerire, unde nu este necesar să se stocheze cele mai simple valori.
Este similar cu recursivitatea, 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 nouă valoare depinde doar de valorile calculate anterior.
Pentru orice număr întreg pozitiv „e”, se poate efectua oricare dintre următorii trei pași.
- Scădeți 1 din număr. (e = e-1).
- Dacă este divizibil cu 2, împarte la 2 (dacă e% 2 == 0, atunci e = e / 2).
- Dacă este divizibil cu 3, împarte la 3 (dacă e% 3 == 0, atunci e = e / 3).
Pe baza pașilor de mai sus, trebuie găsit numărul minim al acestor 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).
S-ar putea gândi să alegeți întotdeauna pasul care face ca n să fie cât mai mic posibil și să continuați 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 pași). Prin urmare, trebuie încercate toate etapele posibile care pot fi făcute pentru fiecare valoare de n găsită, alegând numărul minim al acestor posibilități.
Totul începe cu recursivitate: 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 recurenței, putem începe codificarea recursiunii.
Cu toate acestea, se poate vedea că are subprobleme suprapuse. În plus, 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 ca și în programarea dinamică, începeți de jos, mergând până la e-ul dat. Apoi ambele coduri:
Unul dintre principalele avantaje ale utilizării programării dinamice este că accelerează procesarea, deoarece sunt utilizate referințele care erau calculate anterior. Deoarece este o tehnică de programare recursivă, reduce liniile de cod ale programului.
Algoritmii lacomi sunt similari cu programarea dinamică în sensul că sunt ambele instrumente de optimizare. Cu toate acestea, algoritmul lacom caută o soluție optimă la fiecare pas local. Adică, 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 costisitoare î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ță de cauză prin combinarea rezultatelor acelor subprobleme pentru a găsi de fapt cea mai optimă soluție..
- Este necesară multă memorie pentru a stoca rezultatul calculat al fiecărei subprobleme, neputând garanta că valoarea stocată va fi folosită sau nu.
- De multe ori, valoarea de ieșire este stocată fără a fi folosită vreodată în următoarele subprobleme în timpul execuției. Acest lucru duce la utilizarea inutilă a memoriei.
- În programarea dinamică funcțiile sunt numite recursiv. Acest lucru menține memoria stivei în continuă creștere.
Dacă aveți memorie limitată pentru a vă rula codul și viteza de procesare nu este o problemă, puteți utiliza recursivitatea. 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 nu aveți restricții de memorie, este de preferat să utilizați programare dinamică.
Programarea dinamică este o metodă eficientă de rezolvare a problemelor care altfel ar putea părea extrem de dificil de rezolvat într-un timp rezonabil..
Algoritmii bazați pe paradigma de programare dinamică sunt folosiți în multe domenii ale științei, inclusiv multe exemple în inteligența artificială, de la rezolvarea problemelor de planificare până la recunoașterea vorbirii..
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 Hanoi.
- Toate cele mai scurte perechi de rute de Floyd-Warshall.
- Problema rucsacului.
- Programarea proiectului.
- Cea mai scurtă cale prin Dijkstra.
- Controlul zborului și controlul roboticii.
- Probleme de optimizare matematică.
- Partajare temporară - Programați lucrarea pentru a maximiza utilizarea procesorului.
Numerele Fibonacci sunt numerele găsite în următoarea succesiune: 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ă de formula recurenței: F (n) = F (n -1) + F (n -2), unde F (0) = 0 și F (1) = 1.
În acest exemplu, o matrice de căutare cu toate valorile inițiale este inițializată cu -1. Ori de câte ori este necesară soluția la o subproblemă, această matrice de căutare va fi căutată mai întâi.
Dacă valoarea calculată este acolo, atunci acea valoare va fi returnată. În caz contrar, rezultatul va fi calculat pentru a fi stocat în matricea de căutare, astfel încât să poată fi reutilizat ulterior.
În acest caz, pentru aceeași serie Fibonacci, se calculează mai întâi f (0), apoi f (1), f (2), f (3) și așa mai departe. Astfel, soluțiile subproblemelor vor fi construite de jos în sus.
Nimeni nu a comentat acest articol încă.