Programare dinamică, principii de bază

Pentru a selecta soluția optimă pentru sarcini de programare, uneori este necesar să treceți printr-un număr mare de combinații de date, care încarcă memoria calculatorului personal. Astfel de metode includ, de exemplu, metoda de "divizare și cucerire". În acest caz, algoritmul prevede separarea sarcinii în submăsuri individuale mici. Această metodă este utilizată numai în cazul în care submăsurile mici sunt independente una de cealaltă. Pentru a evita munca inutilă în cazul în care subtascurile sunt interdependente, se folosește metoda de programare dinamică propusă de americanul R. Bellman în anii 1950.

Esența metodei

Programarea dinamică constă în determinarea soluției optime a unei probleme n-dimensionale, împărțind-o în n etape separate. Fiecare dintre ele este o sub-sarcină cu privire la o variabilă.

Principalul avantaj al acestei abordări poate fi considerat că dezvoltatorii implicați în problema de optimizare unidimensională Subactivități în loc de o problema n-dimensional, iar obiectivul nostru principal este de a merge la „bottom-up“.

Este recomandabil să se aplice programarea dinamică în acele cazuri în care subtaskele sunt interdependente, adică au module comune. Algoritmul furnizează o soluție pentru fiecare dintre sub-tastele o singură dată, iar răspunsurile sunt salvate într-un tabel special. Acest lucru face posibil să nu se calculeze din nou răspunsul când se întâlnește o subtasmă similară.

Sarcina programării dinamice rezolvă problema optimizare. Autorul acestei metode a fost formulată de R. Bellman Principiul optimalității: oricare ar fi starea inițială a fiecărei etape și soluția definită în această etapă, toate următoarele pentru a alege optimă în raport cu statul, care primește sistemul la sfârșitul etapei.

Metoda îmbunătățește performanța sarcinilor care sunt rezolvate prin căutarea variantelor sau recurențelor.

Construcția algoritmului problemei

Algoritmul de programare dinamică presupune construirea unor astfel de sarcini pe care sarcina, astfel este împărțit în două sau mai multe subactivități la soluția sa este compus dintr-o soluție optimă pentru toate subactivități, aceasta include. Mai mult, devine necesar să se scrie o relație de recurență și să se calculeze valoarea optimă a parametrului pentru problema ca un întreg.

Uneori, în al treilea pas, trebuie să vă amintiți suplimentar câteva informații auxiliare despre progresul fiecărei submăsuri. Aceasta se numește inversă.

Aplicarea metodei

Programarea dinamică este utilizată atunci când există două caracteristici caracteristice:

• optimitate pentru sub-sarcini;
• prezența suprapusurilor suprapuse în problemă.

Rezolvarea problemei de optimizare prin metoda programării dinamice este mai întâi necesară descrierea structurii soluției. Problema este optimă dacă soluția problemei constă în soluțiile optime ale subtaskelor sale. În acest caz, se recomandă utilizarea programării dinamice.

A doua proprietate a problemei, care este esențială pentru această metodă, este un număr mic de subtascuri. Soluția recursivă a problemei utilizează aceleași subtascuri suprapuse, numărul cărora depinde de dimensiunea informațiilor originale. Răspunsul este stocat într-un tabel special, programul economisește timp, utilizând aceste date.

Este deosebit de eficient să se utilizeze programarea dinamică atunci când, în esență, sarcinile trebuie luate în etape. De exemplu, luați în considerare un exemplu simplu al sarcinii de înlocuire și reparare a echipamentelor. Să presupunem că, în turnătoria unei fabrici de fabricare a anvelopelor, anvelopele sunt realizate simultan în două forme diferite. În cazul în care una dintre formulare eșuează, trebuie să dezasamblați mașina. Este clar că uneori este mai avantajos să înlocuiți al doilea formular pentru a nu dezasambla mașina în cazul în care această formă va fi ineficientă în etapa următoare. În plus, este mai ușor să înlocuiți ambele forme de lucru înainte de a începe să eșueze. Metoda de programare dinamică determină cea mai bună strategie în ceea ce privește înlocuirea unor astfel de formulare, luând în considerare toți factorii: beneficiul continuării funcționării formularelor, pierderea din mașinile în gol, costul anvelopelor respinse și multe altele.