Programare dinamică

Programarea dinamică în teoria controlului și teoria sistemelor informatice este o modalitate de a rezolva probleme complexe prin împărțirea lor în subsarcini mai simple. Se aplică problemelor cu substructură optimă, care arată ca un set de subprobleme suprapuse, a căror complexitate este puțin mai mică decât cea originală. În acest caz, timpul de calcul, în comparație cu metodele „naive”, poate fi redus semnificativ.

Ideea cheie în programarea dinamică este destul de simplă. De regulă, pentru a rezolva problema, este necesar să rezolvați părți separate ale problemei (subproblemă), apoi să combinați soluțiile subsarcinilor într-o singură soluție comună. Adesea, multe dintre aceste subsarcini sunt aceleași. Abordarea de programare dinamică este de a rezolva fiecare subproblemă o singură dată, reducând astfel numărul de calcule. Acest lucru este util în special în cazurile în care numărul de sarcini secundare recurente este exponențial mare.

Metoda de programare dinamică de sus este o simplă memorare a rezultatelor rezolvării acelor subprobleme care pot fi întâlnite din nou în viitor. Programarea dinamică de jos implică reformularea unei probleme complexe ca o secvență recursivă de subprobleme mai simple.

Istorie

Expresia „programare dinamică” a fost folosită pentru prima dată în anii 1940 de Richard Bellman pentru a descrie procesul de găsire a unei soluții la o problemă, în care răspunsul la o problemă poate fi obținut numai după rezolvarea problemei care o „precedă”. În 1953, el a rafinat această definiție la cea modernă. Domeniul a fost fondat inițial ca analiză și inginerie de sisteme, care a fost recunoscut de IEEE . Contribuția lui Bellman la programarea dinamică a fost imortalizată în numele ecuației Bellman , un rezultat central al teoriei programării dinamice care reformulează o problemă de optimizare într-o formă recursivă .

Cuvântul „programare” din sintagma „programare dinamică” nu are de fapt aproape nimic de-a face cu programarea „tradițională” (codul de scriere) și are sens ca în sintagma „ programare matematică ”, care este sinonimă cu cuvântul „optimizare”. Prin urmare, cuvântul „program” în acest context înseamnă mai degrabă succesiunea optimă de acțiuni pentru a obține o soluție la problemă. De exemplu, un program specific de evenimente la o expoziție este uneori denumit program. Programul în acest caz este înțeles ca o secvență validă de evenimente.

Ideea de programare dinamică

O substructură optimă în programarea dinamică înseamnă că o soluție optimă pentru subprobleme mai mici poate fi utilizată pentru a rezolva problema inițială. De exemplu, calea cea mai scurtă dintr-un grafic de la un vârf (notat cu s) la altul (notat cu t) poate fi găsită după cum urmează: mai întâi, considerăm calea cea mai scurtă de la toate vârfurile adiacente lui s la t și apoi, luând ținând cont de greutățile muchiilor care leagă s cu vârfurile adiacente, alegem calea cea mai bună către t (prin care vârf este cel mai bine să parcurgem). În cazul general, putem rezolva o problemă care are o substructură optimă făcând următorii trei pași.

Împărțirea unei sarcini în subsarcini mai mici.
Găsirea soluției optime pentru subprobleme recursiv, făcând același algoritm în trei pași .
Utilizarea soluției obținute de subsarcini pentru a construi o soluție la problema inițială.

Subproblemele se rezolvă împărțindu-le în subprobleme și mai mici, și așa mai departe, până ajung la cazul banal al unei probleme care poate fi rezolvată în timp constant (răspunsul poate fi spus imediat). De exemplu, dacă trebuie să găsim n!, atunci 1! = 1 (sau 0!=1).

Suprapunerea subproblemelor în programarea dinamică înseamnă subprobleme care sunt folosite pentru a rezolva un număr de probleme (nu doar una) de dimensiuni mai mari (adică facem același lucru de mai multe ori). Un exemplu izbitor este calculul șirului Fibonacci și - chiar și într-un caz atât de banal, am numărat deja calculele a doar două numere Fibonacci de două ori. Dacă continuați mai departe și numărați , atunci va fi numărat încă de două ori, deoarece din nou și va fi necesar pentru calcul . Rezultă următoarele: o abordare recursivă simplă va petrece timp calculând o soluție pentru problemele pe care le-a rezolvat deja. $F_{3}=F_{2}+F_{1}$ $F_{4}=F_{3}+F_{2}$ $F_{2}$ $F_{5}$ $F_{2}$ $F_{5}$ $F_{3}$ $F_{4}$

Pentru a evita un astfel de curs de evenimente, vom salva soluțiile subproblemelor pe care le-am rezolvat deja, iar când vom avea din nou nevoie de soluția subproblemei, în loc să o recalculăm, pur și simplu o vom obține din memorie. Această abordare se numește memorare . De asemenea, puteți efectua optimizări suplimentare - de exemplu, dacă suntem siguri că nu mai trebuie să rezolvăm o subsarcină, o putem arunca din memorie, eliberând-o pentru alte nevoi, sau dacă procesorul este inactiv și știm că soluția a unor subsarcini care nu au fost încă calculate, avem nevoie în viitor, le putem rezolva în avans.

Rezumând cele de mai sus, putem spune că programarea dinamică folosește următoarele proprietăți ale problemei:

subsarcini suprapuse;
substructură optimă;
capacitatea de a memora soluția subsarcinilor care apar frecvent.

Programarea dinamică urmează în general două abordări pentru rezolvarea problemelor:

programare dinamică de sus în jos: problema este împărțită în subprobleme mai mici, acestea sunt rezolvate și apoi combinate pentru a rezolva problema inițială. Memorarea este folosită pentru rezolvarea subsarcinilor deja rezolvate.
programare dinamică de jos în sus: toate sarcinile secundare care sunt necesare ulterior pentru a rezolva problema inițială sunt calculate în avans și apoi utilizate pentru a construi o soluție la problema inițială. Acest mod este mai bun decât programarea de sus în jos în ceea ce privește dimensiunea stivei necesare și numărul de apeluri de funcții, dar uneori nu este ușor să ne dăm seama în avans ce subprobleme trebuie să rezolvăm în viitor.

Limbajele de programare își pot aminti rezultatul unui apel de funcție cu un anumit set de argumente ( memorizare ) pentru a accelera „calculul după nume”. Unele limbi au această capacitate încorporată (de exemplu Scheme , Common Lisp , Clojure , Perl , D ), în timp ce altele necesită extensii suplimentare ( C++ ).

Cunoscute sunt programarea dinamică în serie, care este inclusă în toate manualele de cercetare operațională , și programarea dinamică non-serială (NSDP), care este în prezent puțin cunoscută, deși a fost descoperită în anii 1960.

Programarea dinamică convențională este un caz special de programare dinamică non-serială, în care graficul relației variabile este doar o cale. NSDP, fiind o metodă naturală și generală de luare în considerare a structurii unei probleme de optimizare, consideră un set de constrângeri și/sau o funcție obiectivă ca o funcție computabilă recursiv. Aceasta permite găsirea unei soluții pas cu pas, la fiecare etapă folosind informațiile obținute în etapele anterioare, iar eficiența acestui algoritm depinde direct de structura graficului relației variabile. Dacă acest grafic este suficient de rar, atunci cantitatea de calcul în fiecare etapă poate fi menținută în limite rezonabile.

Una dintre principalele proprietăți ale problemelor rezolvate folosind programarea dinamică este aditivitatea . Problemele non-aditive sunt rezolvate prin alte metode. De exemplu, multe sarcini de optimizare a investițiilor unei companii sunt non-aditive și sunt rezolvate prin compararea valorii companiei cu și fără investiții.

Probleme clasice de programare dinamică

Problemă cu cea mai lungă subsecvență comună : Având în vedere două secvențe, trebuie să găsiți cea mai lungă subsecvență comună.
Sarcina de a găsi cea mai mare subsecvență crescătoare : dată fiind o secvență, este necesar să se găsească cea mai lungă subsecvență crescătoare.
Problemă de distanță de editare (distanța Levenshtein) : având în vedere două șiruri, este necesar să se găsească numărul minim de ștersături, înlocuiri și adăugiri de caractere care transformă un șir în altul.
Problema calculării numerelor Fibonacci
Problema ordinului înmulțirii matricelor : date matrice , …, , se cere minimizarea numărului de operații scalare pentru înmulțirea lor. $A_{1}$ $Un}$
Problema alegerii unei traiectorii
Problemă de decizie secvențială
Problema folosirii muncii
Provocarea managementului stocurilor
Problema rucsacului : dintr-un set nelimitat de articole cu proprietățile „cost” și „greutate”, este necesară selectarea unui anumit număr de articole în așa fel încât să se obțină costul total maxim cu o greutate totală limitată.
Algoritmul Floyd-Warshall : găsiți cele mai scurte distanțe dintre toate nodurile unui grafic direcționat ponderat.
Algoritmul Bellman-Ford : găsiți cea mai scurtă cale într-un grafic ponderat între două vârfuri date.
Setul maxim independent de vârfuri dintr-un arbore : dat fiind un arbore, găsiți setul maxim de vârfuri dintre care două nu sunt conectate printr-o muchie.
Sarcina de programare a transportorului : există două transportoare, fiecare cu locuri de muncă. Sunt date timpii de lucru pe fiecare transportor, de așezare pe acesta și de scoatere, precum și timpul de mutare într-un loc învecinat. Doriți să determinați cel mai rapid mod de a asambla o piesă folosind ambele transportoare. $n$

Literatură

Bellman R. Programare dinamică. - M. : Editura de literatură străină , 1960.
Kormen, T. , Leizerson, C. , Rivest, R. , Stein, C. Capitolul 15. Programare dinamică // Algoritmi: Construcție și analiză = Introducere în algoritmi / Ed. I. V. Krasikova. - Ed. a II-a. - M. : Williams, 2005. - 1296 p. — ISBN 5-8459-0857-4 .
Sanjoy Dasgupta, Christos H. Papadimitriou, Umesh Vazirani. algoritmi . - McGraw-Hill Science / Engineering / Math, 2006. - 336 p. — ISBN 0073523402 .
Akulich I. L. Capitolul 4. Probleme de programare dinamică // Programarea matematică în exemple și probleme. - M . : Şcoala superioară , 1986. - 319 p. — ISBN 5-06-002663-9 .
Bertele U., Brioshi F. Programare dinamică non-serială. - NY: Academic Press, 1972. - 235 p.
Gabasov R. , Kirillova F. M. Fundamentele programării dinamice. -Mn. : Editura BSU, 1975. - 262 p.

Link -uri

Prelegeri video despre programarea dinamică
Teorie, sarcini, sistem de testare .

Dicționare și enciclopedii

În cataloagele bibliografice
BNE : XX543843 BNF : 11978098s GND : 4125677-3 J9U : 987007567971605171 LCCN : sh85040313 NDL : 00571739