Dinamičko programiranje, osnovna načela

Da biste odabrali optimalno rješenje za programske zadatke, ponekad je potrebno proći velik broj kombinacija podataka koji učitava memoriju osobnog računala. Takve metode uključuju, primjerice, "program podjele i osvajanja". U ovom slučaju, algoritam omogućuje razdvajanje zadatka u pojedinačne male podzadatke. Ova se metoda koristi samo u slučajevima kada su male podzadatke neovisne jedna od druge. Kako bi se izbjeglo nepotrebno raditi u slučaju da su subtasks međusobno ovisni, koristi se dinamičko programiranje metode koju je predložio američki R. Bellman u 1950-ima.

Bit metode

Dinamičko programiranje sastoji se u određivanju optimalnog rješenja n-dimenzionalnog problema, podjelom u n zasebne korake. Svaki od njih je podzadatak u odnosu na jednu varijablu.

Glavna prednost ovog pristupa može se smatrati da se programeri bave jednodimenzionalnim zadacima optimizacije podzadataka umjesto n-dimenzionalnog problema, a rješenje glavnog zadatka prikupljeno je "odozdo prema gore".

Preporučljivo je primijeniti dinamičko programiranje u slučajevima u kojima su podzaslovi međusobno povezani, tj. imaju zajedničke module. Algoritam daje rješenje za svaku od podzadataka jednom, a odgovori se spremaju u posebnu tablicu. To znači da nećete ponovno izračunati odgovor prilikom sličnog podzadataka.

Zadatak dinamičkog programiranja rješava problem optimizacija. Autor ove metode R. Bellman je formulirao princip optimalnosti: bez obzira na početno stanje u svakom koraku i rješenje određeno u ovom koraku, sve sljedeće se izabire da budu optimalne s obzirom na stanje koje sustav uzima na kraju koraka.

Metoda poboljšava rad zadataka koji se rješavaju pretraživanjem varijanti ili rekurzija.

Izgradnja algoritma problema

Dinamičko programiranje pretpostavlja izgradnju takvog algoritma problema, u kojem je zadatak podijeljen u dvije ili više podzadataka tako da je njegovo rješenje oblikovano od optimalnog rješenja svih subtaskula uključenih u njega. Nadalje, postaje neophodno napisati relaciju recidiva i izračunati optimalnu vrijednost parametra za problem u cjelini.

Ponekad, u trećem koraku, morate dodatno zapamtiti neke pomoćne informacije o napretku svakog podzadatka. To se zove obrnuto.

Primjena metode

Dinamičko programiranje se koristi kada postoje dvije karakteristike:

• optimalnost za podzadatke;
• prisutnost preklapajućih podzadataka u problemu.

Rješavanje problema optimizacije metodom dinamičkog programiranja prvo je potrebno opisati strukturu rješenja. Problem je optimalan ako se rješenje problema sastoji od optimalnih rješenja svojih podzadataka. U ovom slučaju, poželjno je koristiti dinamičko programiranje.

Druga svojstva problema, koja su neophodna za ovu metodu, predstavljaju mali broj podzadataka. Rekurzivno rješenje problema koristi iste preklapajuće podzadatke, čiji broj ovisi o veličini izvornih podataka. Odgovor se pohranjuje u posebnu tablicu, program štedi vrijeme, koristeći ove podatke.

Posebno je djelotvorno koristiti dinamičko programiranje kada se, u biti, zadaci moraju poduzeti u fazama. Na primjer, razmislite o jednostavnom primjeru zadatka zamjene i popravljanja opreme. Pretpostavimo da se na ljevaonici pogona za proizvodnju guma istodobno izrađuju dvije gume u dva različita oblika. U slučaju da jedan od oblika ne uspije, morate rastaviti uređaj. Jasno je da je ponekad povoljnije zamijeniti drugi oblik kako ne bi rastavili stroj u slučaju, a taj će oblik biti neučinkovit u sljedećoj fazi. Štoviše, lakše je zamijeniti oba oblika rada prije nego što počnu propadati. Metoda dinamičkog programiranja određuje najbolju strategiju u pitanju zamjene takvih oblika, uzimajući u obzir sve čimbenike: prednost nastavka rada oblika, gubitak od neaktivnih strojeva, trošak odbijenih guma i još mnogo toga.