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 aldatu

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 (F₃ = F₁ + F₂ y F₄ = F₂ + F₃) , F₃ eta F₄ kalkulatzeko, F₂ erabili behar da. F₅ kalkulatu nahi badugu, erabili F₃ eta F₄ beharko ditugu. F₅en inplementazio txar batek, F₂ 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 aldatu

Fibonacciren zenbakiak: aldatu

Segida matematiko hau errekurtsio honekin adierazi daiteke:

F(n):={\begin{cases}0&{\mbox{baldin eta }}n=0;\\1&{\mbox{baldin eta }}n=1;\\F(n-1)+F(n-2)&{\mbox{baldin eta }}n>1.\\\end{cases}}

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 aldatu

Datuak: Q380679