Алгоритми/Динамичко програмирање

Динамичко програмирање се може посматрати као оптимизациона техниказа одређене класе бектрекинг алгоритама где се под проблеми у више наврата решавају. Приметите да се израз динамичко у динамичком програмирању не сме мешати динамичким језицима за програмиање, као што су Scheme или Lisp. Нити би термин програмирање смео да се меша са чином писања кумпјутерских програма. У контексту алгоритама, динамичко програмирање се увек односи на технику попуњавања табеле вредностима које су израчунате од вредности других табела. (ово је динамичко јер се вредности у табели попуњавају од стране алгоритма базираног на осталим вредностима табеле, а програмирање је јер у смислу смештања ствари у табелу, као на пример, како се програмирање телевизија брине о томе кад ће се емитовати која емисија.)

Фибоначијеви бројеви

Пре него што ћемо представити технику динамичког програмирања, корисно је да најпре прикажемо сродну технику, која се зове меморизација, на примеру Фибоначијевих бројева. Оно што желимо да направимо је рутина која израчунава n-ти Фибоначијев број:

// fib -- рачуна Fibonacci(n)
function fib(integer n): integer

По дефиницији, nти Фибоначијев број, у ознаци ${\textrm {F}}_{n}$ је:

${\textrm {F}}_{0}=0$

${\textrm {F}}_{1}=1$

${\textrm {F}}_{n}={\textrm {F}}_{n-1}+{\textrm {F}}_{n-2}$

Како бисмо направили добар алгоритам за налажење n-тог Фибоначијевог броја? Почнимо са наивним алгоритмом, који кодира математичку дефиницију:

// fib -- рачуна Fibonacci(n)
function fib(integer n): integer
  assert (n >= 0)
  if n == 0: return 0 fi
  if n == 1: return 1 fi
  
  return fib(n - 1) + fib(n - 2)
end

Приметите да је ово врло једноставан пример јер постоји математички израз за израчунавање ${\textrm {F}}_{n}$:

$F(n)={\phi ^{n}-(1-\phi )^{n} \over {\sqrt {5}}}$

Где је:

$\phi ={1+{\sqrt {5}} \over 2}$

Ова друга једначина је позната као златна размера Golden Ratio. Наиме, програм би могао ефикасно да рачуна ${\textrm {F}}_{n}$ чак и за веома велико n. Међутим, битно је да се разуме због чека је овај алгоритам толико неефикасан. Како бисмо анализирали време потребно за извршавање кода fib , погледаћемо стабло позива за нешто тако мало као што је шести Фибоначијев број:

Сваки лист из стабла позива има ведност 0 или 1, и сума ових вредности је коначни резултат. Тако, за било које n, број листова у стаблу позива је уствари ${\textrm {F}}_{n}$. Затворена форма на говори да је број листова у fib(n) приближно једнак:

$\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}\approx 1.618^{n}=2^{\lg(1.618^{n})}=2^{n\lg(1.618)}\approx 2^{0.69n}.$

( Уочите алгебарску манипулацију коришћену у изразу изнад како би база експонента била једнака броју 2.) Ово значи да има превише листова, посебно ако се узму у обзир понављани шаблони који се налазе у стаблу позива на слици изнад. Једна оптимизација коју можемо да направимо је да сачувамо резултат у табелу кад се израчуна, тако да се један исти резултат рачуна само једном. Оптимизациони процес се зове меморизација и прилагођен је следећој методологији:

Методологија меморизације Почети са бектрекинг алгоритмом Потражити проблем у табели; Ако постоји валидан улаз у табелу за тај проблем, вратити ту вредност У супротном, прорачунати проблем рекурзивно, и затим ставити резултат у табелу пре враћања вредности returning the value

Узети у обзир решење презентовано у поглављу бектрекинг, за проблем најдуже заједничке под секвенце. Током извршавања тог алгоритма, многи заједнички под проблеми су израчунавани више пута. Као оптимизацију, можемо израчунати ове под проблеме једном, а затим запамтити резултате да би се касније прочитали. Рекурзивни алгоритам са меморизацијом се може изврнути у итеративни алгоритам који попуњава табелу решења под проблема. Неки од решених под проблема можда неће бити потребни за коначно решење (овде се динамичко програмирање разликује од меморизације), али динамичко програмирање може бити веома ефикасно јер његова итеративна верзија боље користи кеш меморију и има мањи вишак позива. Асимптотски, динамичко програмирање и меморизација имају исто комплкесност. Дакле, како би програм бројева радио користећи меморизацију? Посматрајмо следећи програм (f[n] садржи n-ти Фибоначијев број ако је он израчунат, у супротном, садржи вредност -1):

function fib(integer n): integer
  if n == 0 or n == 1:
    return n
  else-if f[n] != -1:
    return f[n]
  else
    f[n] = fib(n - 1) + fib(n - 2)
    return f[n]
  fi
end

Код би требало да буде поприлично очигледан. Ако је вредност fib(n) већ израчуната, онда је она запамћена у f[n] и затим враћена уместо да се поново рачуна. Ово значи да се све копије из стабала под позива уклањају из калкулације.

Вредности у плавим правоугаоницима су вредности које су већ израчунате и позиви би онда могли да се прескоче. Овај алгоритам је много бржи од обичног рекурзивног алгоритма. Како се свака вредност мања од n рачуна само једном, први пута када с епокрене програм, асимптотско време извршавање кода је $O(n)$. Сваки други позив ће имати $O(1)$ време извшавања, јер су вредности већ израчунате ( под претпоставком да је аргумент сваког позива суб секвенце мањи од n). Овај алгоритам користи много меморије. Када рачунамо fib(n), вредности fib(0) до fib(n) се складиште у главну меморију. Да ли ово може да се унапреди? Да, може, мада ће време извршавања суб секвенцијалних позива да се изгуби јер вредности нису меморисане. Како вредност fib(n) зависи само од вредности fib(n-1) и fib(n-2), остале вредности можемо одбацити тако што идемо од дна ка врху. Ако желимо да израчунамо fib(n), прво израчунамо fib(2)=fib(0) + fib(1). Затим рачунамо fib(3) тако што саберемо fib(1) и fib(2). После тога fib(0) и fib(1) могу да се одбац, јер нам нису потребни за рачунање нових вредности. Од fib(2) и fib(3) рачунамо fib(4) и одбацујемо fib(2), затим рачунамо fib(5) и одбацујемо fib(3), итд. Код за ово изгледа овако:

function fib(integer n): integer
  if n == 0 or n == 1:
    return n
  fi

  let u := 0
  let v := 1

  for i := 2 to n:
    let t := u + v
    u := v
    v := t
  repeat
  
  return v
end

Можемо да модификујемо код да складишти вредности у низ за под секвенцијалне позиве, али поента је у томе да не морамо. Овај метод је типичан за динамичко програмирање. Прво идентификујемо који под проблеми треба да се реше како би се решио целокупан проблем, а затим рачунамо вредности од дна ка почетку користећи итеративни процес.

Најдужа заједничка под секвенца (верзија са динамичким програмирањем)

Ово ће нас подсетити на бектрекинг верзију, а затим ћемо је унапредити уз помоћ меморизације. Коначно, рекурзивни алгоритам ће постати итеративан и биће право решење коришћењем динамичког програмирања.

Ланчано множење матрица

Замислимо да треба да помножимо серију од $n$ матрица $M_{1},\ldots ,M_{n}$ како бисмо формирали матрицу производа $P$:

$P=M_{1}\cdot M_{2}\cdots M_{n-1}\cdot M_{n}$

Ово ће захтевати $n-1$ множење, али који је најбржи начин за добијање овог производа? Множење матрица је асоцијативно, тј.:

$(A\cdot B)\cdot C=A\cdot (B\cdot C)$

За свако $A,B,C$, тако да можемо да бирамо које множење ћемо прво да обавимо. ( Приметите да множење матрица није комутативно, тј. не важи $A\cdot B=B\cdot A$.) Како можемо множити само две матрице у тренутку, производ $M_{1}\cdot M_{2}\cdot M_{3}\cdot M_{4}$ може бити подељен на следеће начине:

$((M_{1}M_{2})M_{3})M_{4}$

$(M_{1}(M_{2}M_{3}))M_{4}$

$M_{1}((M_{2}M_{3})M_{4})$

$(M_{1}M_{2})(M_{3}M_{4})$

$M_{1}(M_{2}(M_{3}M_{4}))$

Две матрице $M_{1}$ и $M_{2}$ могу да се множе само ако је број колона једне матрице једнак броју редова друге. Број редова $M_{1}$ њиховог производа биће једнак броју редова прве матрице, а број колона ће бити једнак броју колона друге матрице. Дакле, ако су димензије $M_{1}$ $a\times b$ и $M_{2}$ има димензије $b\times c$ њихов производ ће имати димензије $a\times c$.

За множење две матрице, користимо функцију која се зове множење матрица, која узима две матрице и враћа њихов производ. За сад нећемо причати о имплементацији ове функције јер то није циљ овог поглавља (како најбрже помножити две матрице је проблем који се интензивно изучава већ неколико година). Време које је овој функцији потребно да помножи две матрице димензија $a\times b$ и $b\times c$ је пропорционално броју скаларних множења, који је пропорционалан $abc$. Тако да је подела производа већег броја матрица битна: рецимо да имамо, на пример три матрице $M_{1}$, $M_{2}$ и $M_{3}$. $M_{1}$ има димензије $5\times 100$, $M_{2}$, има димензије $100\times 100$ и $M_{3}$ има димензије $100\times 50$. Хајде да поделимо овај производа на два могућа начина и да видимо који начин захтева најмању количину множења. Та два начина су следећи:

$((M_{1}M_{2})M_{3})$, и

$(M_{1}(M_{2}M_{3}))$.

Формирање производа на први начин захтева 75000 скаларних множења (5*100*100=50000 за формирање производа $(M_{1}M_{2})$ и још 5*100*50=25000 за последња множења.) Ово може да делује као велики број, али у поређењу са 525000 скаларних множења која су потребна за рачунање проивода на други начин (50*100*100=500000 плус 5*50*100=25000) је занемарљиво! Одавде можете видети како је избор начина поделе производа матрица веома важан: замислите шта би се десило кад би требало да се израчуна производ 50 матрица!

Формирање рекурзивног решења

Уочите да се бавимо налажењем броја потребних скаларних множења, уместо поретка. Ово је због тога што, кад нађемо добар алгоритам за налажење количине множења, креирање алгоритма за поделу производа постаје тривијално. Ово ће бити поменуто на крају поглавља. Дакле, како би алгоритам за оптималнии поделу производа изгледао? По наслову поглавља, да је у питању метод динамичког програмирања. Дакле како би метод динамичког програмирања радио? Како су алгоритми динамичког програмирања базирани на оптималној под структури, шта би била оптимална под структура за овај проблем? Замислимо да оптимална подела производа

$M_{1}M_{2}\dots M_{n}$

Дели производ код k-те матрице:

$(M_{1}M_{2}\dots M_{k})(M_{k+1}M_{k+2}\dots M_{n})$.

Онда оптимално решење садржи оптимална решења за два под проблема

$(M_{1}\dots M_{k})$

$(M_{k+1}\dots M_{n})$

Ово је у сагласности са фундаменталним принципом динамичког програмирања, решење проблема зависи од решења проблема мањих под проблема. Рецимо да је потребно $c(n)$ скаларних множења како би се помножиле матрице $M_{n}$ и $M_{n+1}$, и $f(m,n)$ је број скаларних множења када се користи оптимална подела производа матрица $M_{m}\dots M_{n}$. Дефинисање $f(m,n)$ је први корак ка решењу. Када је $n-m=1$, формулација је тривијална; то је само $c(m)$. Али шта је када је дистанца већа? Користећи обсервацију одозго, можемо да дођемо до формулације. Претпоставимо да оптимално решење проблема дели производ код матрица k и k+1 (на пример, $(M_{m}\dots M_{k})(M_{k+1}\dots M_{n})$) онда је број скаларних множења једнак:

$f(m,k)+f(k+1,n)+c(k)$

То је време потребно за формирање првог производа, другог производа и време потребно за формирање коначног производа. Али која је ова оптимална вредност k? Одговор је, наравно, вредност за коју формула одозго има минималну вредност. На тај начин можемо формирати комплетну дефиницију функције:

$f(m,n)={\begin{cases}\min _{m\leq k<n}f(m,k)+f(k+1,n)+c(k)&{\mbox{if }}n-m>1\\0&{\mbox{if }}n=m\end{cases}}$

Рекурзивно решење би изгледало овако:

function f(m, n) {

    if m == n
        return 0

    let minCost := $\infty$

    for k := m to n - 1 {
        v := f(m, k) + f(k + 1, n) + c(k)
        if v < minCost
            minCost := v
    }
    return minCost
}

Ово једноставно решење, на жалост, није добро. Користи много времена да изнова врши прорачуне и његово време извршавања је експоненцијално.

Користећи исту адаптацију као горе, добијамо:

function f(m, n) {

    if m == n
        return 0

    else-if f[m,n] != -1:
      return f[m,n]
    fi

    let minCost := $\infty$

    for k := m to n - 1 {
        v := f(m, k) + f(k + 1, n) + c(k)
        if v < minCost
            minCost := v
    }
    f[m,n]=minCost
    return minCost
}

Парсирање било које граматике без контекста

Специјални случајеви граматика без контекста се могу парсирати много ефикасније него овом техником, али уопштено, динамичко програмирање је једини начин.