Dinamično programiranje, osnovna načela

Če želite izbrati optimalno rešitev za programsko opravilo, je včasih treba iti skozi veliko število kombinacij podatkov, ki nalagajo pomnilnik osebnega računalnika. Takšne metode vključujejo, na primer, metodo "razdeliti in osvojiti". V tem primeru algoritem določa ločitev naloge v posameznih majhnih podizdelkih. Ta metoda se uporablja le v primerih, ko so majhne podrednosti medsebojno neodvisne. Da bi se izognili neupravičenim delom, če so medsebojne odvisnosti medsebojno odvisne, se uporablja metoda dinamičnega programiranja, ki jo je predlagal ameriški R. Bellman leta 1950.

Bistvo metode

Dinamično programiranje sestavlja določitev optimalne rešitve n-dimenzionalnega problema, ki ga razdeli v n ločene korake. Vsak od njih je podizvajalec glede na eno spremenljivko.

Glavno prednost tega pristopa je mogoče šteti, da se razvijalci ukvarjajo z enodimenzionalnimi optimizacijskimi nalogami podprogramov namesto n-dimenzionalnega problema in rešitev glavne naloge se zbira "od spodaj navzgor".

Priporočljivo je, da uporabite dinamično programiranje v tistih primerih, kjer so podreditve medsebojno povezane, npr. imajo skupne module. Algoritem ponuja rešitev za vsako od podizdelkov enkrat in odgovori se shranijo v posebno tabelo. To omogoča, da se pri odgovoru na podobno podprojekte ponovno ne izračuna odgovor.

Naloga dinamičnega programiranja rešuje problem optimizacija. Avtor te metode R. Bellman je oblikoval načelo optimalnosti: ne glede na začetno stanje na vsakem koraku in rešitev, določena na tem koraku, so vse naslednje izbrane kot optimalne glede na stanje, ki ga sistem vzame na koncu koraka.

Metoda izboljša učinkovitost nalog, ki jih rešujejo iskalne različice ali rekurzije.

Izgradnja algoritma problema

Dinamično programiranje predpostavlja konstrukcijo takega algoritma problemov, v katerem se naloga deli na dva ali več podizdelkov, tako da se njegova rešitev oblikuje iz optimalne rešitve vseh podtak nih, ki so vanj vključene. Nadalje postane potrebno, da napišemo ponovitveno razmerje in izračunamo optimalno vrednost parametra za celotno težavo.

Včasih se morate v tretjem koraku dodatno spomniti nekaterih pomožnih informacij o napredku vsake podizvedbe. To se imenuje obratno.

Uporaba metode

Dinamično programiranje se uporablja, če obstajajo dve značilni funkciji:

• optimalnost za podizvedbe;
• prisotnost prekrivnih podomestij v problemu.

Rešitev problema optimizacije z metodo dinamičnega programiranja je najprej potrebno opisati strukturo rešitve. Problem je optimalen, če rešitev problema sestavljajo optimalne rešitve njegovih podizdelkov. V tem primeru je priporočljivo uporabljati dinamično programiranje.

Druga lastnost problema, ki je bistvena za to metodo, je majhno število podizdelkov. Rekurzivna rešitev problema uporablja enake prekrivne podizlove, katerih število je odvisno od velikosti prvotnih informacij. Odgovor je shranjen v posebno tabelo, program pa prihrani čas, s temi podatki.

Še posebej je učinkovito uporabljati dinamično programiranje, kadar je v bistvu naloge treba sprejeti po stopnjah. Na primer, upoštevajte preprost primer naloge zamenjave in popravila opreme. Predpostavimo, da se na livnici naprave za proizvodnjo pnevmatik hkrati porazdelijo pnevmatike v dveh različnih oblikah. V primeru, da eden od obrazcev ne uspe, morate stroj razstaviti. Jasno je, da je včasih bolj ugodno nadomestiti drugo obliko, da ne bi razstavili stroja v primeru, in ta oblika bo v naslednji fazi neučinkovita. Poleg tega je lažje zamenjati oba delovna obrazca, preden začneta z odpovedjo. Metoda dinamičnega programiranja določa najboljšo strategijo pri vprašanju zamenjave takih obrazcev ob upoštevanju vseh dejavnikov: koristi nadaljevanja delovanja obrazcev, izgube s prostega teka, stroškov zavrnjenih pnevmatik in še več.