Dinamičko programiranje, osnovni principi

Da biste izabrali optimalno rešenje za programske zadatke, ponekad je neophodno proći kroz veliki broj kombinacija podataka, koji učitavaju memoriju na ličnom računaru. Takve metode uključuju, na primjer, metod "programiranja i osvajanja". U ovom slučaju, algoritam omogućava razdvajanje zadatka u pojedinačne male podzakone. Ovaj metod se koristi samo u slučajevima kada su mali potezovi nezavisni jedni od drugih. Kako bi se izbjeglo raditi nepotrebnim radom u slučaju da su posljedice međuzavisne, korišten je metod dinamičkog programiranja koji je američki R. Bellman predložio 1950-ih.

Suština metode

Dinamičko programiranje se sastoji u određivanju optimalnog rešenja n-dimenzionalnog problema, deljavajući n n odvojene korake. Svaka od njih je podtaga u odnosu na jednu varijablu.

Glavna prednost ovakvog pristupa može se smatrati da su se programeri bavili jednodimenzionalnim zadacima optimizacije zadataka umjesto n-dimenzionalnog problema, a rješenje glavnog zadatka ide "odozdo naviše".

Preporučljivo je primijeniti dinamičko programiranje u onim slučajevima gdje su posljedice međusobno povezane, tj. Imaju zajedničke module. Algoritam daje rješenje svakom od zadataka jednom, a odgovori se čuvaju u posebnoj tabeli. Ovo omogućava neprekidno izračunavanje odgovora prilikom sastanka sličnog podtaga.

Zadatak dinamičkog programiranja rešava problem optimizacije. Autor ove metode R. Bellman formulirao je princip optimalnosti: bez obzira na početno stanje na svakom koraku i rješenje određeno na ovom koraku, sve što sledi biće optimalno u odnosu na stanje koje sistem uzima na kraju koraka.

Metoda poboljšava performanse zadataka koji se rešavaju pretražujući varijante ili rekurzije.

Izgradnja algoritma problema

Dinamičko programiranje podrazumijeva konstrukciju takvog algoritma zadataka, u kojem je zadatak podijeljen na dva ili više pod-zadataka, tako da se njegovo rješenje formira iz optimalnog rješenja svih zadataka uključenih u njega. Dalje, javlja se potreba za pisanjem relativnog odnosa i izračunavanje optimalne vrednosti parametra za problem u cjelini.

Ponekad, na trećem koraku, dodatno se trebate pamtiti neke pomoćne informacije o napretku svake podtaskove. Ovo se zove obrnuto.

Primjena metode

Dinamičko programiranje se koristi kada postoje dve karakteristične osobine:

• Optimality for subtasks;
• Prisustvo podložnih preklapanja u problemu.

Rešavanje problema optimizacije metodom dinamičkog programiranja, prvo je potrebno opisati strukturu rešenja. Problem je optimalan ako se rješenje problema sastoji od optimalnih rješenja njegovih podtaga. U ovom slučaju, preporučljivo je koristiti dinamičko programiranje.

Druga svojina problema, koja je od suštinskog značaja za ovu metodu, je mali broj zadataka. Rekurzivno rešenje problema koristi iste pod-zadatke koji se preklapaju, čiji broj zavisi od veličine početnih informacija. Odgovor se čuva u posebnoj tabeli, program štedi vreme, koristeći ove podatke.

Posebno je efikasna upotreba dinamičkog programiranja kada su u suštini zadaci potrebni korak po korak. Na primer, razmotrite jednostavan primjer zadatka zamjene i popravke opreme. Pretpostavimo da se na livnici fabrike gume gume izrađuju istovremeno u dva različita oblika. U slučaju da neki obrazac ne uspije, morate rastaviti mašinu. Jasno je da je ponekad povoljnije zamijeniti drugi oblik kako ne bi rastavljali mašinu u slučaju, a ovaj oblik će biti neefikasan u sljedećoj fazi. Štaviše, lakše je zameniti oba operativna obrasca pre nego što počnu da pada. Metod dinamičkog programiranja određuje najbolju strategiju u pitanju zamjene takvih oblika, uzimajući u obzir sve faktore: korist od nastavka rada formi, gubitka od neaktivnih mašina, troškova odbijenih guma i tako dalje.