Dinamično programiranje: Razlika med redakcijama

Izbrisana vsebina Dodana vsebina

Znotrajvrstično

Redakcija: 10:35, 5. januar 2006

Iskanje najkraše poti. Odebeljena črta predstavlja najkrajšo pot med dvema vozliščema

Dinamično programiranje je prva metoda, ki sistematično pregleduje vse možne poti v reševanju problema in zato tudi pride do optimalne rešitve.

V splošnih primerih ne moremo dobiti na tekočem koraku delčke rešitve, vidimo le množico potencionalnih rešitev do konca in potem jih rekonstruiramo. Končna rešitev je sestavljena iz komponent rešitve oziroma iz delnih rešitev. Ko na tekočem koraku ugotovimo, da delna rešitev oziroma komponenta neke rešitve ne vodi h cilju, to delno delno rešitev zavržemo.

Dinamično programiranje temelji na pravilu optimalnosti, saj vsako podzaporedje optimalnega zaporedja je tudi optimalno.

Osnova za dinamično programiranje je rekurzivna enačba, ki se imenuje Bellmanova enačba. Vsak problem rešen s pomočjo metode dinamičnega programiranja ima svojo Bellmanovo enačbo.

Ker potencialne rešitve na tekočem koraku določamo na osnovi potencialnih rešitev iz prejšnjega koraka, je pri dinamičnem programiranju prisotna rekurzivna relacija. Poznamo dva pristopa za reševanje:

pristop naprej
pristop nazaj

Prednost dinamičnega programiranja je predvsem ta, da kadar želimo delati z več objekti, ne rabimo zanje rezervirati fiksnih količin spomina (glej tabela) ampak ga lahko dodeljujemo dinamično po potrebi. Podatke lahko s kazalci uredimo na primer v vrsto (podatkovni tip) oseb, ki stojijo pred blagajno. Vsak objekt (Oseba) v tej vrsti bo vseboval atribute o sebi ter kazalec na naslednjo osebo. Zadnji objekt bo vseboval kazalec na prazen prostor (null). Kadar dodamo novo osebo v vrsto, dinamično rezerviramo v pomnilniku prostor za novo osebo (ustvarimo nov objekt), ter zadnji osebi spremenimo prazen kazalec na novoustvarjeno osebo. (glej tudi podatkovne strukture seznam, sklad)

Tak način dodeljevanja pomnilnika je zelo pomemben pri algoritmih, ki zahtevajo veliko število operacij nad veliko količino podatkov. Prav tako lahko pri zahtevnejših podatkovnih strukturah kazalci kažejo na več sosednjih objektov in s tem tvorijo drevo (glej binarna odločitvena drevesa (ang. Binary Decision Tree, BDT)). Za optimizacijo iskalnega časa je potrebno podatke že ob vstavljanju umestiti na ustrezno mesto ter včasih tudi spremeniti strukturo drevesa (Bayerjevo drevo, rdeče-črna drevesa, rotacije). Pri tem dinamićno spreminjamo kazalce med objekti.

Algoritmi

@@ Vrstica 12: / Vrstica 12: @@
 * pristop nazaj
+Prednost dinamičnega programiranja je predvsem ta, da kadar želimo delati z več objekti, ne rabimo zanje rezervirati fiksnih količin spomina (glej [[tabela (računalništvo)|tabela]]) ampak ga lahko dodeljujemo dinamično po potrebi. Podatke lahko s kazalci uredimo na primer v vrsto (podatkovni tip) oseb, ki stojijo pred blagajno. Vsak objekt (Oseba) v tej vrsti bo vseboval atribute o sebi ter kazalec na naslednjo osebo. Zadnji objekt bo vseboval kazalec na prazen prostor (null). Kadar dodamo novo osebo v vrsto, dinamično rezerviramo v pomnilniku prostor za novo osebo (ustvarimo nov objekt), ter zadnji osebi spremenimo prazen kazalec na novoustvarjeno osebo. (glej tudi podatkovne strukture seznam, sklad)
-Pri [[programiranje|programiranju]] uporabljamo različne [[podatkovni tip|podatkovne tipe]] (odvisno od [[programski jezik|programskega jezika]]. Osnovni so običajno int (integer, celo število), bool (da ali ne), char (znaki, tudi črke). Vsak izmed njih v pomnilniku (strojno) zaseda neko število ničel in enic (bitov). Iz teh lahko gradimo zahtevnejše podatkovne tipe, znane pod imenom [[razred|razredi]] (ang. Class). Gre za podatkovne tipe, kjer enemu [[objekt|objektu]] dodelimo več [[atribut|atributov]]. V primeru razreda 'Oseba' bi bili atributi 'int leto_rojstva', polje znakov 'char[] ime', 'int visina', 'int teza', ... Tako lahko uporabimo kar spremenljivko tipa 'Oseba' in na enem primeru osebe (tukaj že govorimo o objektu) razpolagamo z vsebovanimi atributi. Kadar ustvarimo polje oseb, se v spominu rezervira prostor za vse vsebovane objekte (dimenzija polja). Eden izmed atributov objekta je lahko tudi objekt istega razreda, ali v primeru dinamičnega programiranja pogosteje [[kazalec|kazalec]] (ang. pointer) na objekt istega razreda. S pomočjo kazalcev lahko tako med seboj povezujemo objekte, kar v veliki meri izkoriščajo iskalni algoritmi.
-Prednost dinamičnega programiranja je predvsem ta, da kadar želimo delati z več objekti, ne rabimo zanje rezervirati fiksnih količin spomina (glej [[polje|polja]] (ang. array) ampak ga lahko dodeljujemo dinamično po potrebi. Podatke lahko s kazalci uredimo na primer v vrsto (podatkovni tip) oseb, ki stojijo pred blagajno. Vsak objekt (Oseba) v tej vrsti bo vseboval atribute o sebi ter kazalec na naslednjo osebo. Zadnji objekt bo vseboval kazalec na prazen prostor (null). Kadar dodamo novo osebo v vrsto, dinamično rezerviramo v pomnilniku prostor za novo osebo (ustvarimo nov objekt), ter zadnji osebi spremenimo prazen kazalec na novoustvarjeno osebo. (glej tudi podatkovne strukture seznam, sklad)
 Tak način dodeljevanja pomnilnika je zelo pomemben pri algoritmih, ki zahtevajo veliko število operacij nad veliko količino podatkov. Prav tako lahko pri zahtevnejših podatkovnih strukturah kazalci kažejo na več sosednjih objektov in s tem tvorijo drevo (glej binarna odločitvena drevesa (ang. Binary Decision Tree, BDT)). Za optimizacijo iskalnega časa je potrebno podatke že ob vstavljanju umestiti na ustrezno mesto ter včasih tudi spremeniti strukturo drevesa (Bayerjevo drevo, rdeče-črna drevesa, rotacije). Pri tem dinamićno spreminjamo kazalce med objekti.