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
aldatuAzpi-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
aldatuFibonacciren zenbakiak:
aldatuSegida 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