\documentclass{article}

\usepackage{amsthm}
\newtheorem{thm}{Teorema}

\title{Nedelja 4 - Uvodni primer za dinami\v{c}ko programiranje}

\begin{document}
\maketitle

\begin{enumerate}

\item Problem najjeftnijieg puta kroz matricu. Neka je data matrica A dimenzija m x n (ne mora 
se unositi sa ulaza, mo\v{z}e biti fiksirana u kodu). Potrebno je prona\'{c}i put kroz polja 
matrice (od gornjeg levog ugla - pozicije (0,0) do donjeg desnog - pozicije (m-1,n-1) takav da 
je zbir tro\v{s}kova prelazaka preko polja najmanji mogu\'c. Primetiti da ima 
smisla i\'ci samo dole ili desno. Ovo je primer jedne matrice tro\v{s}kova:

\begin{verbatim}
 3  5 19  1 11
 4 15  6 14 17
13 13  6  1  9
 5  4  4 17 17
\end{verbatim}

ZA DOMA\'CI URADITI pod (a) i (b).

\begin{enumerate}

\item Dati rekurzivno re\v{s}enje problema.

\item Dati re\v{s}enje zasnovano na dinami\v{c}kom programiranju. Logika u slu\v{c}aju 
dinami\v{c}kog programiranja je slede\'ca. Najpre pokazujemo da sme da se primeni dinami\v{c}ko 
programiranje. Da bi moglo da se primeni, mora da va\v{z}i da je optimalno re\v{s}enje 
sa\v{c}injeno iz optimalnih re\v{s}enja manjih problema (potproblema).
\begin{thm}
Neka je P optimalni put izmedju pozicija (0,0) i (m-1,n-1). Posmatrajmo neku poziciju (i,j) koja 
se nalazi na optimalnom putu. Neka je P1 put od (0,0) do (i,j), a P2 put od (i,j) do (m-1,n-1). 
Tvrdimo da su i putevi P1 i P2 optimalni putevi.
\end{thm}
\begin{proof}[Dokaz]
Pretpostavimo suprotno tvrdjenju, naime, pretpostavimo da postoji neki put Q koji je kra\'{c}i 
od P1. Onda bi va\v{z}ilo da je Q+P2 put od (0,0) do (m-1,n-1) koji je kra\'{c}i od P, \v{s}to 
je nemogu\'ce jer je P najkra\'ci (optimalni) put. Kontradikcija.
\end{proof}
Sada se mo\v{z}e primeniti gradjenje re\v{s}enja ododzdo navi\v{s}e, \v{s}to je osnovna ideja 
kod dinami\v{c}kog programiranja. Krenemo da re\v{s}avamo probleme redom od manjih ka ve\'cim 
dimenzijama. Ovde je veza izmedju re\v{s}enja manjeg i ve\'{c}eg problema data na 
slede\'ci 
na\v{c}in (d(i,j) je optimalni tro\v{s}ak dolaska do pozicije (i,j)) :

\begin{equation}
\nonumber
d(i,j)=\left\{
\begin{array}{ll}
  c(0,0) &  i=0, j=0\\
  d(i-1,0)+c(i,0) & i>0, j=0\\
  d(0,j-1)+c(0,j) & i=0, j>0\\
  min\{d(i-1,j),d(i,j-1)+c(i,j)\} & i>0, j>0
\end{array}\right.
\end{equation}

Kada se primeni na prethodno datu matricu, dobija se slede\'ca matrica ukupnih tro\v{s}kova:

\begin{verbatim}
 3  8 27 28 39
 7 22 28 42 56
20 33 34 35 44
25 29 33 50 61 
\end{verbatim}

Najjeftiniji put se rekonstrui\v{s}e prolazom unazad (od pozicije (m-1,n-1)) pra\'cenjem linije 
najmanjih tro\v{s}kova. Najjeftiniji put:

\begin{verbatim}
 3   
 7 22 28
      34 35
            61
\end{verbatim}

\end{enumerate}

\end{enumerate}

\end{document} 
