Programazio dinamiko

Informatikan, programazio dinamikoa algoritmo baten exekuzio denbora murrizteko metodoa da. Horretarako azpi-problema gainjarriak eta azpi-egitura optimoak erabiltzen ditu.

Richard Bellman matematikariak programazio dinamikoa asmatu zuen 1953. urtean, problema konplexuak optimizatzeko, hauek sekuentzializatuz eta diskretatuz.

 Sarrera 
Azpi-egitura optimo bat, azpi-problemen konponbide optimoak erabili daitezkela esan nahi du, problemaren soluzio optimoa bere osotasunean topatzeko.

Adibidez, grafo baten bi erpinen arteko biderik laburrena kalkulatu daiteke, hasierakoaren aldameneko erpin guztietatik amaiera arte bide laburrena kalkulatuz eta ondoren, emaitza hauek baliatu biderik hoberena aukeratzeko. Oro har, azpi-egitura optimoak erabiliz, problema guztiak ebatzi daitezke hiru pausu hauek jarraituz:
 Problema azpi-problema txikiagotan zatitu.
 Problema hauek era optimoan ebatzi, hiru pausuetako prozesu hau jarraituz.
 Emaitza optimo hauek erabili, problema nagusiaren soluzio optimoa eraikitzeko.
Azpi-problemak azpi-problemetan zatituz ebazten dira kasu errazera ailegatu arte, non emaitza tribiala den.

Problema batek azpi-problema gainjarriak dituela esatea, problema nagusiak ebazteko azpi-problema bera erabiltzen dela esatea da. Adibidez, Fibonacciren zenbakien segidan (F3 = F1 + F2 y F4 = F2 + F3) , F3 eta F4 kalkulatzeko, F2 erabili behar da. F5 kalkulatu nahi badugu, erabili F3 eta F4 beharko ditugu. F5en inplementazio txar batek, F2 bi aldiz edo gehiago kalkulatuko du. Hau beti gertatuko da azpi-problema gainjarriak ditugunean, non algoritmoaren exekuzio denbora igoko den.

Hau ekiditeko kalkulatu ditugun soluzioak zerrenda batean gorde daitezke. Beraz, problema bera berriz ebatzi nahi bada, lehen kalkulatu dugun soluzioa zerrendan bilatu dezakegu, hau berrerabiltzeko (memorizazioa).

Laburbilduz, programazio dinamikoak hauek erabiltzen ditu:
 Azpi-problema gainjarriak
 Azpi-egitura optimoak
 Memorizazioa
Gainera, bi planteamendu ezberdin azpimarra ditzakegu:
 Top-down: Problema azpi-problemetan zatitzen da, eta hauek soluzioak gogoratuz ebazten dira.
 Bottom-up: Ahal diren problema guztian aldez aurretik ebazten dira, eta ondoren, problema nagusiak ebazteko erabiltzen dira.
Programazio funtzional lengoaia batzuk, Haskell batez ere, memorizazioa erabil dezake automatikoki, prozesuak azkartzeko.

 Adibidea 

 Fibonacciren zenbakiak: 
Segida matematiko hau errekurtsio honekin adierazi daiteke:

Fibonacciren segidan n posizioan dagoen zenbakia topatzeko, honako programa errekurtsiboa sor dezakegu, kostu exponentziala eukiko duena:
 FUNC fib(↓n: ARRUNTA): ARRUNTA
 HASIERA
    BALDIN n = 0 ORDUAN
        ITZULI 0
    BESTELA, BALDIN n = 1 ORDUAN
        ITZULI 1
    BESTELA
        ITZULI fib(n-1) + fib(n-2)
    BALDIN AMAITU
 AMAITU

Demagun fib(5) deitzen dugula, orduan zuhaitz dei bat eratuko genuke non parametro berdinak hainbat alditan errepikatuko diren:
 fib(5)
 fib(4) + fib(3)
 (fib(3) + fib(2)) + (fib(2) + fib(1))
 ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
 (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

Ikus daitekenez, hainbat alditan deitu dugu fib programa, parametro berdinekin. Parametro handiagoekin, fib balio berdin gehiago birkalkulatuko lirateke.

Arazo hau konpontzeko, problema programazio dinamikoaren bidez burutu dezakegu, memorizazioa erabiliz (kalkulatuak izan diren balioak gorde, ondoren berriz erabiltzeko). Era honetan, taula batean gordeko ditugu ateratzen joan ditugun balioak, ondoren hauek behar direnean erabiltzeko. Eratutako taula dimentsio bakarrekoa izango litzateke, 0tik n-ra.

Hau kalkulatuko luken programa, Bottom-up erabiliz:

 FUNC Fibonacci (↓n: ARRUNTA): ARRUNTA
 ALDAGAIAK
    taula: ARRAY [0..n] ARRUNTAZKOA
    i: ARRUNTA
 HASIERA
    BALDIN n = 0 ORDUAN
        ITZULI 0
    BESTELA, BALDIN n = 1 ORDUAN
        ITZULI 1
    BESTELA
        taula[0] := 0
        taula[1] := 1
        FOR i = 2TIK nRA EGIN
            taula[i] := taula[i-1] + taula[i-2]
        FOR AMAITU
        ITZULI taula[n]
    BALDIN AMAITU
 AMAITU

Fibonacci funtzioak O(n)ko kostua izango du, 2^n ordez (zuhaitz bitar bat eratzen duelako memorian).  Beste adibide bat, Top-Down erabilita, kalkulatutako azken bi balioekin geratzea izango litzateke, erabilgarriak direnak hurrengo zenbakiak kalkulatzeko.

Honako egitura izango luke:
 FUNC Fibonacci (↓n: ARRUNTA, ↨taula: ARRAY [0..n] ARRUNTAZKOA): ARRUNTA
     ALDAGAIAK
        i: ARRUNTA
     HASIERA
         BALDIN n <= 1 ORDUAN
             ITZULI n
        AMAITU BALDIN
         BALDIN taula[n-1] = -1 ORDUAN
            taula[n-1] := Fibonacci(n-1, taula)
         BALDIN AMAITU
         BALDIN taula[n-2] = -1 ORDUAN
            taula[n-2] := Fibonacci(n-2, taula)
         BALDIN AMAITU
            taula[n] := taula[n-1] + taula[n-2] 
        ITZULI taula[n]
 AMAITU

 Kanpo estekak 

Kategoria:Algoritmoak
Kategoria:Ikerketa operatiboa
Kategoria:Grafo teoria
Kategoria:Sistemen ingeniaritza