Dinaminis programavimas

Dinaminis programavimas (angl. dynamic programming) yra gudrus triukas, panašus į „skaldyk ir valdyk“. Priminsiu, kas yra „skaldyk ir valdyk“: problema skaidoma į mažesnes dalis, tos dalys sprendžiamos rekursyviai, mažesniųjų problemų sprendimai apjungiami ir gaunamas pirmosios problemos sprendimas. Tačiau kartais „skaldyk ir valdyk“ algoritmai būna labai neefektyvūs.

Pavyzdys: Fibonačio skaičiai. Jei tiesiog užrašysime rekursinę funkciją

function Fib(n: Integer): Integer;
begin
  Fib := Fib(n - 1) + Fib(n - 2);
end;

tai mūsų sprendimas bus labai neefektyvus, nes skaičiuos tas pačias Fib(n) reikšmes po daugybę kartų.

Dinaminį programavimą reikia taikyti, jei tos mažesnės problemos dalys nėra nepriklausomos, o kertasi tarpusavyje. Šio metodo esmė yra ta, kad visos mažesnės problemos yra sprendžiamos ne daugiau nei vieną kartą, jų sprendimai surašomi į lentelę ir vėliau naudojami didesnių subproblemų sprendimams suskaičiuoti.

Pavyzdys: Fibonačio skaičiai -- rekursija su įsiminimu (angl. memoization).

var
  FibTable: array[1..MaxN] of Integer;

function Fib(n: Integer): Integer;
begin
  if FibTable[n] = -1 then
    FibTable[n] := Fib(n - 1) + Fib(n - 2);
  Fib := FibTable[n];
end;

...

begin
  for n := 1 to MaxN do
    FibTable[n] := -1;
  FibTable[1] := 1;
  FibTable[2] := 1;
  ...

Jau geriau, bet šiek tiek griozdiška.

Pavyzdys: Fibonačio skaičiai -- lentelės užpildymas „iš apačios į viršų“

var
  FibTable: array[1..MaxN] of Integer;

function Fib(n: Integer): Integer;
begin
  Fib := FibTable[n];
end;

...

begin
  FibTable[1] := 1;
  FibTable[2] := 1;
  for n := 3 to MaxN do
    FibTable[n] := FibTable[n - 1] + FibTable[n - 2];
  ...

Dinaminis programavimas dažnai taikomas optimizavimo uždaviniams spręsti. Tokiuose uždaviniuose sprendimų gali būti daug, su kiekvienu sprendimu yra susieta jo vertė, ir mes norime rasti sprendimą su optimalia (didžiausia ar mažiausia) verte. Beje, optimalių sprendimų gali būti daug; mums tinka bet kuris iš jų.

Dinaminio programavimo taikymas:

Nustatome optimalaus sprendimo struktūrą.
Išreiškiame optimalaus sprendimo vertę rekursyvia formule.
Suskaičiuojame optimalaus sprendimo vertę „iš apačios į viršų“.
Sukonstruojame patį optimalų sprendimą.

Kartais mus domina tik optimalaus sprendimo vertė, bet ne jo struktūra. Tuomet ketvirtą žingsnį galime praleisti.

Pavyzdys: 0-1-knapsack problem.

Vagis įsigauna naktį į parduotuvę ir randa ten n daiktų. Kiekvienas daiktas vertas kažkiek litų ir sveria kažkiek kilogramų. Vagis nori pasiimti kiek galima vertingesnį krovinį, bet jis gali panešti tik W kilogramų. Ką jis turėtų pasiimti?

Nesunku pamatyti, kad sprendimai yra visi aibės {1, ..., n} poaibiai, tad jei perrinkinėsime visus įmanomus poaibius ir skaičiuosime jų vertę, mūsų algoritmas bus neefektyvus -- O(2ⁿ).

Galime bandyti pirma imti vertingiausius dalykus (žiūrėdami į jų vertę arba vertės ir svorio santykį), bet nesunku sugalvoti pavyzdžių, rodančių, jog ši „godi“ strategija ne visada duoda teisingą atsakymą.

Apibrėžkime optimalaus sprendimo vertę. Pažymėkime daiktų vertes v_i, jų svorius w_i, optimalaus sprendimo vertę, jei nagrinėjame daiktus 1..j ir galime panešti k kilogramų V(j, k). Skaičiuodami V(j, k) turime du pasirinkimus:

j-tąjį daiktą palikti: tuomet iš j-1 daikto galime susirinkti krovinį, sveriantį k kilogramų -- t.y. V(j, k) = V(j-1, k).
j-tąjį daiktą pasiimti: tuomet iš j-1 daiko galime susirinkti krovinį, sverianti k-w_j kilogramų, ir prie jo vertės pridėti j-tojo daikto vertę v_j -- t.y. V(j, k) = V(j-1, k-w_j) + v_j.

Kadangi mes norime maksimizuoti V(j, k), turime paprastą rekursyvią formulę

V(j, k) = max(V(j-1, k), V(j-1, k-w_j) + v_j)
V(0, k) = 0

Mums tereikia suskaičiuoti V(n, W) pasinaudojant įsiminimu arba užpildant lentelę iš apačios į viršų. Algoritmo efektyvumas -- O(nW).

var
  V: array[0..MaxN, 0..MaxW] of Integer;
  Value, Weight: array[1..MaxN] of Integer;
  N, W, J, K: Integer;
begin
  ... perskaitom pradinius duomenis ...
  for K := 0 to W do
    V[0, K] := 0;
  for J := 1 to N do
    begin
      V[J, K] := V[J-1, K];
      if Weight[J] <= K then
        V[J, K] := Max(V[J, K], V[J-1, K-Weight[J]] + Value[J]);
    end;
...

Dabar turime optimalaus sprendimo vertę, bet kaip gauti patį sprendimą -- kuriuos būtent daiktus turime pasiimti?

Vienas būdas yra toks: pasiimame papildomą lentelę B[J, K] ir joje įrašome, ar skaičiuodami V[J, K] reikšmę mes ėmėme j-tąjį daiktą, ar neėmėme:

var
  B: array[0..MaxN, 0..MaxW] of Boolean;

...

  for J := 1 to N do
    begin
      V[J, K] := V[J-1, K];
      B[J, K] := False;
      if (Weight[J] <= K) and
         (V[J-1, K-Weight[J]] + Value[J] > V[J, K]) then
        begin
          V[J, K] := V[J-1, K-Weight[J]] + Value[J] > V[J, K];
          B[J, K] := True;
        end;
    end;

...

Turėdami šią lentelę galime lengvai sukonstruoti atsakymą pasinaudoję rekursyvia funkcija

procedure PrintAnswer(J, K: Integer);
begin
  if J > 0 then
    begin
      if B[J, K] then
        begin
          PrintAnswer(J-1, K-Weight[J]);
          WriteLn('Imame daiktą ', J);
        end
      else
        PrintAnswer(J-1, K);
    end;
end;

Taip pat galime sutaupyti vietos ir apsieiti be lentelės B.

procedure PrintAnswer(J, K: Integer);
begin
  if J > 0 then
    begin
      if V[J, K] <> V[J-1, K] then
        begin
          PrintAnswer(J-1, K-Weight[J]);
          WriteLn('Imame daiktą ', J);
        end
      else
        PrintAnswer(J-1, K);
    end;
end;