DINAMIČKO PROGRAMIRANJE: KARAKTERISTIKE, PRIMJER, PREDNOSTI, NEDOSTACI - TEHNOLOGIJA - 2026

Dinamičko programiranje je model algoritma koji rješava složen problem tako podijeli ga u subproblems, spremanje rezultate o tome kako bi se izbjeglo da se preračunati rezultate.

Ovaj se raspored koristi kada imate problema koji se mogu podijeliti u slične podprobleme, tako da se njihovi rezultati mogu ponovo upotrijebiti. Taj se raspored uglavnom koristi za optimizaciju.

Dinamičko programiranje. Potproblemi složeni u Fibonaccijevom nizu. Izvor: Wikimedia commons, hr: Korisnik: Dcoatzee, trag Korisnik: Stannered / Public domain

Prije rješavanja dostupnog podproblema, dinamički algoritam će pokušati ispitati rezultate ranije riješenih potproblema. Rješenja potproblema kombiniraju se kako bi se postiglo najbolje rješenje.

Umjesto da se isti podproblem izračunava iznova i iznova, možete pohraniti svoje rješenje u neku memoriju kada prvi put naiđete na ovaj podproblem. Kad se ponovo pojavi tijekom rješenja drugog podprograma, uzet će se rješenje već pohranjeno u memoriji.

Ovo je divna ideja za utvrđivanje vremena memorije, gdje se pomoću dodatnog prostora može poboljšati vrijeme potrebno za pronalazak rješenja.

Značajke dinamičkog programiranja

Sljedeće su bitne karakteristike s čime morate imati problema prije primjene dinamičkog programiranja:

Optimalna podstruktura

Ova karakteristika izražava da se problem optimizacije može riješiti kombiniranjem optimalnih rješenja sekundarnih problema koji ga čine. Ove optimalne podstrukture su opisane rekurzijom.

Na primjer, na grafu će biti prikazana optimalna podstruktura u najkraćem putu r koji ide od vrha s do vrha t:

Odnosno, u ovom najkraćem putu može se uzeti bilo koji intermedijarni vrh. Ako je r stvarno najkraći put, tada ga možemo podijeliti na pod-rute r1 (od s do i) i r2 (od i do t), tako da su oni zauzvrat najkraći ruti između odgovarajućih vrhova.

Stoga, za pronalaženje najkraćih putova, rješenje se lako može formulirati rekurzivno, što čini algoritam Floyd-Warshall.

Preklapanje podproblema

Prostor podproblema mora biti mali. To jest, svaki rekurzivni algoritam koji rješava problem morat će rješavati iste podprobleme iznova i iznova, umjesto da generira nove podprobleme.

Na primjer, da bismo generirali Fibonaccijev niz možemo razmotriti ovu rekurzivnu formulaciju: Fn = F (n - 1) + F (n - 2), uzevši za osnovni slučaj da je F1 = F2 = 1. Tada ćemo imati: F33 = F32 + F31, i F32 = F31 + F30.

Kao što vidite, F31 se razrađuje u rekurzivne potkoljenice i F33 i F32. Iako je ukupan broj potproblema vrlo mali, ako usvojite rekurzivno rješenje poput ovog, na kraju ćete rješavati iste probleme iznova i iznova.

To se uzima u obzir dinamičkim programiranjem, pa se svaki podproblem rješava samo jednom. To se može postići na dva načina:

Pristup odozdo prema gore

Ako se rješenje bilo kojeg problema može rekurzivno formulirati korištenjem rješenja njegovih potproblema, a ako se ovi podproblemi preklapaju, tada se rješenja podproblema mogu lako upamtiti ili pohraniti u tablicu.

Svaki put kada se traži novo rješenje podproblema, tablica će se provjeravati je li prethodno riješena. U slučaju da se rješenje pohrani, upotrijebit će se umjesto da se ponovno izračuna. U protivnom, podproblem će biti riješen, spremanje rješenja u tablicu.

Pristup odozdo prema gore

Nakon što se problem problema formulira rekurzivno u smislu njegovih potproblema, moguće je pokušati problem preformulirati nagore: prvo ćemo pokušati riješiti potprobleme i koristiti njihova rješenja kako bismo došli do rješenja za veće podprobleme.

To se općenito provodi u obliku tablice, iterativno generirajući rješenja za veće i veće podprobleme pomoću rješenja za manje podprobleme. Na primjer, ako su vrijednosti F31 i F30 već poznate, vrijednost F32 može se izračunati izravno.

Usporedba s drugim tehnikama

Jedna značajna značajka problema koji se može riješiti dinamičkim programiranjem je ta što se trebaju nalaziti podproblemi koji se preklapaju. Ovo razlikuje dinamičko programiranje od tehnike dijeljenja i osvajanja, gdje nije potrebno pohranjivati ​​najjednostavnije vrijednosti.

Slično je s rekurzijom, jer se pri izračunavanju osnovnih slučajeva konačna vrijednost može odrediti induktivno. Ovaj pristup odozdo prema gore dobro funkcionira kada nova vrijednost ovisi samo o prethodno izračunatim vrijednostima.

Primjer

Minimalni koraci za postizanje broja 1

Za bilo koji pozitivni cijeli broj "e" može se provesti bilo koji od sljedeća tri koraka.

- oduzmi 1 od broja. (e = e-1).

- Ako je djeljivo sa 2, dijeli se s 2 (ako je e% 2 == 0, onda je e = e / 2).

- Ako je djeljiv sa 3, dijeli se s 3 (ako je e% 3 == 0, onda je e = e / 3).

Na temelju gore navedenih koraka, trebalo bi pronaći najmanji broj tih koraka koji e dovode do 1. Na primjer:

- Ako je e = 1, rezultat: 0.

- Ako je e = 4, rezultat: 2 (4/2 = 2/2 = 1).

- Kad je e = 7, rezultat: 3 (7-1 = 6/3 = 2/2 = 1).

Usredotočenost

Moglo bi se razmišljati o tome da se uvijek odabere korak koji čini n što nižim i nastavlja ovako, sve dok ne dosegne 1. No, vidi se da ova strategija ovdje ne funkcionira.

Na primjer, ako je e = 10, koraci bi bili: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 koraka). Međutim, optimalni oblik je: 10-1 = 9/3 = 3/3 = 1 (3 koraka). Stoga se moraju pokušati svi mogući koraci koji se mogu poduzeti za svaku vrijednost od n, odabirom minimalnog broja tih mogućnosti.

Sve započinje rekurzijom: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)} ako je> 1, uzimajući za osnovni slučaj: F (1) = 0. Imajući jednadžbu recidiva, možete početi kodirati rekurziju.

No, može se vidjeti da ima podprobleme koji se preklapaju. Nadalje, optimalno rješenje za određeni ulaz ovisi o optimalnom rješenju njegovih podproblema.

Kao i kod memorizacije, gdje se rješenja subproblema koji su riješeni pohranjuju za kasniju upotrebu. Kao i kod dinamičkog programiranja, započnete pri dnu, radeći svoj put prema zadanom e. Zatim oba koda:

pamćenje

Dinamično programiranje odozdo prema gore

Prednost

Jedna od glavnih prednosti korištenja dinamičkog programiranja je što ubrzava obradu, jer se koriste ranije izračunate reference. Kako se radi o rekurzivnoj tehnici programiranja, ona smanjuje linije koda u programu.

Glasni algoritmi vs dinamično programiranje

Pohlepni algoritmi slični su dinamičkom programiranju po tome što su oba alata za optimizaciju. Međutim, pohlepni algoritam traži optimalno rješenje na svakom lokalnom koraku. Odnosno, traži pohlepni izbor u nadi da će pronaći globalni optimum.

Stoga pohlepni algoritmi mogu napraviti pretpostavku koja u to vrijeme izgleda optimalno, ali u budućnosti postaje skupa i ne jamči globalni optimalni.

S druge strane, dinamičko programiranje pronalazi optimalno rješenje za podprobleme, a zatim donosi informirani izbor kombinirajući rezultate tih podproblema kako bi se zapravo pronašlo najoptimalnije rješenje.

Nedostaci

- Potrebno je puno memorije za pohranjivanje izračunatog rezultata svakog podprograma, bez mogućnosti garancije da će se pohranjena vrijednost koristiti ili ne.

- Mnogo puta se izlazna vrijednost pohranjuje, a da se tijekom izvršavanja nikada ne koristi u sljedećim potprogramima. To dovodi do nepotrebne uporabe memorije.

- U dinamičkom programiranju funkcije se nazivaju rekurzivno. Tako se memorija stalka stalno povećava.

Rekurzija vs dinamično programiranje

Ako imate ograničenu memoriju za pokretanje koda, a brzina obrade nije problem, možete upotrijebiti rekurziju. Na primjer, ako razvijate mobilnu aplikaciju, memorija je veoma ograničena za pokretanje aplikacije.

Ako želite da program radi brže i nema ograničenja memorije, poželjno je koristiti dinamičko programiranje.

Prijave

Dinamičko programiranje učinkovita je metoda rješavanja problema koji se u protivnom mogu činiti izuzetno teškim za razumno vrijeme.

Algoritmi temeljeni na paradigmi dinamičkog programiranja koriste se u mnogim područjima znanosti, uključujući mnoge primjere umjetne inteligencije, od planiranja rješavanja problema do prepoznavanja govora.

Algoritmi temeljeni na dinamičkom programiranju

Dinamičko programiranje prilično je učinkovito i djeluje vrlo dobro za širok raspon problema. Mnogi se algoritmi mogu shvatiti kao pohlepni programi algoritama, kao što su:

- Fibonaccijev niz broja.

- Kule u Hanoju.

- Svi parovi kraćih ruta kroz Floyd-Warshall.

- Problem s ruksakom.

- Planiranje projekata.

- Najkraći put kroz Dijkstra.

- Kontrola leta i kontrola robotike.

- Problemi matematičke optimizacije.

- Vremensko dijeljenje: zakažite posao kako biste maksimalno iskoristili CPU.

Fibonaccijev niz broja

Fibonaccijevi brojevi su brojevi koji se nalaze u sljedećem slijedu: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, itd.

U matematičkoj terminologiji, niz Fn Fibonaccijevih brojeva definiran je formulom ponavljanja: F (n) = F (n -1) + F (n -2), gdje je F (0) = 0 i F (1) = 1.

Pristup odozdo prema gore

U ovom primjeru, niz pretraživanja sa svim početnim vrijednostima inicijalizira se sa -1. Kad god je potrebno rješenje podproblema, prvo će se pretraživati ​​ova matrica pretraživanja.

Ako je izračunata vrijednost tamo, tada će se ta vrijednost vratiti. U suprotnom, izračunat će se rezultat spremiti u polje pretraživanja kako bi se kasnije moglo ponovo upotrijebiti.

Pristup odozdo prema gore

U ovom slučaju, za isti Fibonaccijev niz prvo se izračunava f (0), zatim f (1), f (2), f (3) i tako dalje. Tako se rješenja potproblema grade odozdo prema gore.

Reference

1. Vineet Choudhary (2020). Uvod u dinamičko programiranje. Insajder programera. Preuzeto sa: developerinsider.co.
2. Alex Allain (2020). Dinamičko programiranje u C ++. C Programiranje. Preuzeto sa: cprogramming.com.
3. Nakon Akademije (2020). Ideja dinamičkog programiranja. Preuzeto sa: afteracademy.com.
4. Aniruddha Chaudhari (2019). Dinamičko programiranje i rekurzija - razlika, prednosti s primjerom. CSE stog. Preuzeto sa: csestack.org.
5. Kuhar kodova (2020). Vodič za dinamičko programiranje. Preuzeto sa: codechef.com.
6. Programiz (2020). Dinamičko programiranje. Preuzeto sa: programiz.com.