Dinamičko programiranje

Sama reč programiranje u terminu dinamičko programiranje se kao i u linearnom programiranju odnosi na popunjavanje tabele pri rešavanju problema, a ne na upotrebu programskoj jezika ili računara. Tehnike optimizacije koje koriste dinamičko programiranje bile su poznate i pre II svetskog rata, ali se tvorcem metode smtra profesor Richard Belman, koji je sredinom pedesetih godinaproučavao problem tako što je proučavao hijerarhiju podproblema sadržanih u glavnom problemu i rešavanje počinjao od najjednostavnijih.

Algoritmi iz prakse koji koriste dinamičko programiranje

• Cocke-Younger-Kasami (CYK) algoritam - determiniše da li i kako zadati string se može generisati iz zadate kontekst-slobodne gramatike

• transpoziciona tabela za igranje šaha na računaru, račinanje pozicija premeštanja i napada

• Viterbi algoritam, nalaženje najverovatnije sekvence za neko skriveno stanje, npr. šema za korekciju grešaka u digitalnim komunikacionim linijama u kojima se pojavljuju i šumovi;

• Floyd algoritam za nalaženje najkraćih puteva u grafu

Operacija editovanja najmanje cene zapravo predstavlja Levenshtein ili edit rastojanje dve niske. Nazvana je po ruskom naučniku (Vladimir Levenshtein) koji se 1965. bavio ovim rastojanjem.

Koristi se u aplikacijama u kojima je potrebno znati koliko su slične dve niske, npr.

1. spell checker-i (provera pravopisa)

   Spell checkeri porede reč sa ulaza sa jedinicom rečnika. Ako reč nije pronađena u rečniku, smatra se da nije korektno uneta i izlistavaju se moguće reči iz rečnika, počev od onih sa najmanjom Levenshtein udaljenosti od ulazne reči.

2. aplikacije molekularne biologije (DNK analiza; što je veći stepen sličnosti dve sekvence, bilo DNK, RNK ili amino-kiselina, to im je sličnija i funkcija ili struktura, npr. kod multiplskleroze koja to bakterijska ili virusna sekvenca iz ranije infekcije je slična sekvenci proteinske mijelinske ovojnice )

3. detekcija plagijata

4. prepoznavanje govora

   Što je Levenštajnovo rastojanje dve niske veće, to se one više razlikuju među sobom.

Procena sličnosti dve niske može se utvrditi na osnovu Levenštajnovog rastojanja ili LCS algoritmom koji pronalazi najduužu zajedničku podsekvencu (podsekvenca se dobija iz niske brisanjem 0 ili više karaktera). Oba algoritma će biti navedena kao ilustracija tehnike dinamičkog programiranja.

Inače, današnje softverske alatke koriste više metrika, a često i njihovu kombinaciju. Neke metrike su pogodnije za oblast molekularne biologije, neke za oblast text mining-a. Više o metrikama nad niskama može se pogledati u lekciji Metrike nad niskama.

Oznake: Neka je A(k) niz koji se sastoji od prvih k elemenata niza A. Neka je B(k) niz koji se sastoji od prvih k elemenata niza B.

Nizovi edit operacija koji transformišu A(i) u B(j) zavisno od poslednje operacije u nizu edit operacija

Postoje tri ključne situacije:
1. ako je A(i-1) transformisan u B(j), onda se obavlja delete znaka a[i]
2. ako je A(i) transformisan u B(j-1), onda se obavlja insert znaka b[j]
3. ako je A(i-1) transformisan u B(j-1), onda se obavlja replace znaka a[i] (istim ili različitim) znakom b[j]

Dakle, najmanja cena transformacije A(i) u B(j), tj. Cena[i,j] jednaka je Cena[i,j]=Min_3_broja (c1, c2, c3), gde

• c1 - slučaj prethodnog delete a[i], c1= Cena[i-1,j]+1
• c2 - slučaj prethodnog insert b[j], c2= Cena[i,j-1]+1
• c3 - slučaj prethodnog replace a[i] sa b[j], c3= Cena[i-1,j-1]+ (a[i]==b[j])
  

pseudo-jezik:
Algoritam NajjeftinijeEditovanje (a, b, n, m)
ulaz: a, n, b, m
izlaz: Cena /* tabela (n+1)*(m+1) */

{

/* i, j su lokalne promenljive i imaju ulogu brojača u petljama
Potez je matrica koju pregledamo unazad (počev od Potez[n,m]), ne bi li dobili konačan niz operacija editovanja.

Potez[i,j]

poslednja operacija (delete ili insert ili replace) editovanja koja se obavlja da bi Cena[i,j] bila minimalna

c1 - slučaj prethodnog delete a[i]
c2 - slučaj prethodnog insert b[j]
c3 - slučaj prethodnog replace a[i] sa b[j]
*/
/* transformacija prefiksa A(i) u praznu nisku B(0) */
for (i=0; i <= n; i++)
{
    Cena[i,0]=i;
    Potez[i,0]= delete;
}

/* transformacija praznog prefiksa A(0) u prefiks B(j) */
for (j=0; j <= m; j++)
{
    Cena[0,j]=j;
    Potez[0,j]= insert;
}

/* i!=0, j!=0 i najjeftinija transformacija A(i) u B(j) */
for (i=1; i <= n; i++)
 for (j=1; j <= m; j++)
  {
    c1= Cena[i-1,j]+1;
    c2= Cena[i,j-1]+1;
   if (a[i]==b[j])
     c3= Cena[i-1,j-1];
    else
      c3= Cena[i-1,j-1]+1;
  Cena[i,j]=Min_3_broja (c1, c2, c3);
   Potez[i,j] = izabrana_operacija_editovanja_u_Min_3_broja;
  } /*for */
} /*KRAJ*/

Procena složenosti

Svaki element matrice Cena se i izračunava za konstantno vreme, pa je vremenska složenost algoritma O(mn), dok je i prostorna složenost O(mn). Može se postići prostorna složenost reda O(m), ali ako se matrica Cena popunjava po vrstama (jer jedna vrsta zavisi samo od prethodne vrste).

Primer

Primer formiranja matrice cena za niske "SAMBA" i "SIMBAD".

Koraci 1, 2

		S	A	M	B	A
	0	1	2	3	4	5
S	1
I	2
M	3
B	4
A	5
D	6

Koraci od 3 do 6 kada i = 1

		S	A	M	B	A
	0	1	2	3	4	5
S	1	0
I	2	1
M	3	2
B	4	3
A	5	4
D	6	5

Koraci od 3 do 6 kada i = 2

		S	A	M	B	A
	0	1	2	3	4	5
S	1	0	1
I	2	1	1
M	3	2	2
B	4	3	3
A	5	4	4
D	6	5	5

Koraci od 3 do 6 kada i = 3

		S	A	M	B	A
	0	1	2	3	4	5
S	1	0	1	2
I	2	1	1	2
M	3	2	2	1
B	4	3	3	2
A	5	4	4	3
D	6	5	5	4

Koraci od 3 do 6 kada i = 4

		S	A	M	B	A
	0	1	2	3	4	5
S	1	0	1	2	3
I	2	1	1	2	3
M	3	2	2	1	2
B	4	3	3	2	1
A	5	4	4	3	2
D	6	5	5	4	3

Koraci od 3 do 6 kada i = 5

		S	A	M	B	A
	0	1	2	3	4	5
S	1	0	1	2	3	4
I	2	1	1	2	3	4
M	3	2	2	1	2	3
B	4	3	3	2	1	2
A	5	4	4	3	2	1
D	6	5	5	4	3	2

Step 7

Rastojanje je u donjoj desnoj ćeliji, tj. 2, što odgovara i inuitivnoj realizaciji da se niska "SAMBA" može transformisati u nisku "SIMBAD" zamenom slova "A" slovom "I" i dodavanjem slova "D" (1 zamena i 1 umetanje = 2 operacije ).

Java implementacija

public class Distance {



  //****************************

  // minimum tri vrednosti a, b, c

  //****************************



  private int Minimum (int a, int b, int c) {

  int mi;



    mi = a;

    if (b < mi) {

      mi = b;

    }

    if (c < mi) {

      mi = c;

    }

    return mi;



  }



  //*****************************

  // Izracunavanje Levenshtein rastojanja

  //*****************************



  public int LD (String s, String t) {

  int d[][]; // matrica

  int n; // duzina za s

  int m; // duzona za  t

  int i; // indeks niza s

  int j; // indeks niza t

  char s_i; // i-ti karakter za s

  char t_j; // j-ti karakter za  t

  int cena; // cena



    // Korak 1



    n = s.length ();

    m = t.length ();

    if (n == 0) {

      return m;

    }

    if (m == 0) {

      return n;

    }

    d = new int[n+1][m+1];



    // Korak 2



    for (i = 0; i <= n; i++) {

      d[i][0] = i;

    }



    for (j = 0; j <= m; j++) {

      d[0][j] = j;

    }



    // Korak 3



    for (i = 1; i <= n; i++) {



      s_i = s.charAt (i - 1);



      // Korak 4



      for (j = 1; j <= m; j++) {



        t_j = t.charAt (j - 1);



        // Korak 5



        if (s_i == t_j) {

          cena = 0;

        }

        else {

          cena = 1;

        }



        // Korak 6



        d[i][j] = Minimum (d[i-1][j]+1, d[i][j-1]+1, d[i-1][j-1] + cena);



      }



    }



    // Korak 7



    return d[n][m];



  }



}

Domaći

A=aabccbba, B=baacbabacc, Cena=?

 

2.     Zajednički podniz

Upotrebu dinamičkog programiranja demonstriraćemo na problemu određivanja najvećeg zajedničkog podniza (u daljem tekstu LCS - od engleskog naziva longest common subsequence) dvaju nizova.

Niz a=(a₁, a₂, ..., a_k) je podniz niza b=(b₁, b₂, ..., b_m), ako i samo ako postoji strogo rastući niz (i₁, i₂, ..., i_k) indeksa, takav da za svako j= 1, 2, ... k važi b_ij=a_j.

Na primer, niz a=(A, N, A) je podniz niza b=(G, L, A, D, N, A) gde je odgovarajući niz indeksa (3, 5, 6).  Ili (2,4,5) ako je indeks prvog elementa niza nula, a ne jedan.

Ako su data dva niza X i Y, kažemo da je niz Z zajednički podniz od X i Y, ako je Z podniz i od X i od Y.

Niz Z=(A, N, A) je zajednički podniz nizova X=(B, A, N, A, N, A) i Y=(B, R, A, N, A) i njegova dužina je 3, ali Z nije najveći zajednički podniz od X i Y, već je to niz (B, A, N, A), čija je dužina 4.

Formulacija problema:

Neka su zadata su dva niza: niz p sa m elemenata i niz q sa n elemenata. Odrediti zajednički podniz najveće moguće dužine za nizove p i q.

Algoritam "grube sile" u ovom slučaju daje slabe rezultate, iz prostog razloga što bi zbog ukupnog broja podnizova niza p takav algoritam bio eksponencijalne složenosti.

Uvedimo prvo neke skraćene oznake.

LCS (c,d)= najduži zajednički podniz za nizove P_c, Q_d
P_c je niz koji se sastoji od prvih c elemenata niza p gde je c <= m

Nizovi LCS operacija koji transformišu Pc u Qd zavisno od poslednje LCS operacije:

LCS(m,n)=?

• Ako element p_m=q_n

  Onda: LCS(m,n)=LCS(m-1,n-1) * {p _m }, gde je * oznaka za operaciju dopisivanja

• ako element p_mnije jednak elementu q_n, onda:                                                           LCS(m,n) = max {LCS(m-1, n),    LCS(m,n-1) }

Dalje, svakako važi :

LCS(c,0) = prazan niz

LCS (0,d) = prazan niz

Neka B je matrica koja čuva dužine za LCS i pozicije indeksa.
Elementi matrice B su:

B(c,0) = B(0,d)=0

B(c,d) =B(c-1, d-1) +1 , ako je p(c)=q(d) /*već je objašnjeno zašto */

B(c,d) = max { B(c, d-1)    ,     B(c-1,d) } ,    ako nije p(c)=q(d)

 

Iz ovog razmatranja je jasan algoritam:

Algoritam LCS (p,m,q,n)

ulaz: p,q, m, n    /*p, q su nizovi duzine redom m, n*/

izlaz: B (matrica duzina za LCS), LCS(m,n)

{

  for (i=0;i < =m; i++)   B[i,0]=0;

  for (j=0;j < =n; j++)   B[0,j]=0;

   for (i=1; i < =m; i++)

          for (j=1;j < =n; j++)

               if (p[i]==q[j])    B[i,j]=B[i-1,j-1]+1;

               else  if ( B[i-1,j]  > B[i, j-1]  )   B[i,j]=B[i-1,j]

                        else B[i,j]=B[i,j -1]

    LCS_print (m, n);

}

procedure LCS_print (i,j)

ulaz: i, j

izlaz: ispis LCS za dva niza

{

    if (i > 0         &&     j > 0)

        if (p[i] == q[j])

           {   LCS_ispis( i-1, j-1);

                ispisati p[i];

            }

          else  if ( B[i-1,j]  > B[i, j-1]  ) LCS_ispis(i-1, j);

                   else LCS_ispis (i, j-1)

}

Rešenje je dobijeno dinamčkim programiranjem, a rekurzija se koristi samo za ispis rešenja. Procedura LCS_print(m,n) ispisuje put do polja (m,n) i poziva se rekurzivno najviše onoliko puta koliko ima polja na putu od polja (1,1) do polja (m,n), tj. ne više od m+n puta (tj. nije dominatna u proceni složenosti).

 

3. Dat je niza celih brojeva a sa n elemenata. Odrediti podniz niza a čija je suma elemenata maksimalna, a u kome nema susednih elemenata niza a. Smatrati da je suma elemenata praznog niza jednaka 0.

REŠENJE:  Neka je a niz od n celih brojeva.
Neka je R=R(A) jedan podniz iz formulacije zadatka koji odgovara nizu a.
Neka je A_k niz koji se sastoji od prvih k elemenata niza a.

Podniz niza A₀ je prazan niz, dok je podniz niza A₁ element a[1] ako je a[1]>0.

1. Ako element a[n] ne pripada podnizu R=R(A), onda je R 
podniz iz formulacije zadatka koji odgovara nizu A_n-1.
2. Ako element a[n] pripada podnizu R=R(A), onda je R \ a[n]
podniz iz formulacije zadatka koji odgovara nizu A_n-2.

Dakle, za i=2..n, važi da R(A_i) je ili R(A_i-1) ili R(A_i-2)* {a[i]}, tj. 
uzima se onaj od podnizova koji ima veci zbir.

Neka je niz s takav da:
s(i) je suma podniza R(A_i).
Iz gore izlozenog, jasno je da:
s(0)=0, 
s(1)=max(0, a[1]), 
s(i)=max{ s(i-1), s(i-2) + a[i] }, i=2..n

Iz niza s će se ispisati rešenje R.

Algoritam MSN (a,n)

ulaz: a, n   /* niz a duzine n, BSO clanovi su a[1]...a[n] */

izlaz: podniz niza a cija suma je maksimalana, 

gde podniz ne sadrzi uzastopne elemente iz a

{

  s[0]=0;        /* s[j] = suma elemenata podniza b koji je resenja zadatka za podniz A(j) */

                    /* s[0]=0, jer suma praznog niza je 0, po dogovoru */

if (a[1] > 0)  s[1]=a[1];

               else s[1]=0;





for (i=2;i <= n; i++)  /*uzimamo da indeks prvog clana niza je 1, drugog je 2,...*/



     if  (s[i-2] + a[i]  > s[i-1])

             s[i]= s[i-2] + a[i];

      else s[i]= s[i-1];



MSN_ispis (n);

}





procedure  MSN_ispis (n)

ulaz: n

izlaz: ispis clanova podniza koji sadrzi nesusedne clanove niza,

         ali tako da je suma podniza maksimalna

{

if (n > 0)

   if (s[n] = = s[n-1)  MSN_ispis(n-1);

   else

      {  MSN_ispis(n-2);

          ispisati  a[n];   /*jer je clan niza b */

      }



}

 

4.   Neka n ljudi čeka u redu da kupi karte za predstavu, pri cemu t_i je vreme koje je i-tom kupcu potrebno da kupi kartu. Ako se po dvoje suseda u redu udruzi da kupi karte - na primer k-ti i k+1-vi kupac-onda vreme potrebno da oni kupe karte je p_k,  k=1..n-1. Udruzivanjem kupaca moze da se ubrza kupovina karata, a i ne mora. Ulazni podaci su broj kupaca n i nizovi t i p. Konstruisati algoritam koji odredjuje takav nacin udruzivanja da ukupno vreme potrebno da svih n kupaca kupi kartu bude minimalno.

Resenje:Neka je niz a takav da a[k] je usteda u vremenu kupovine karata koja nastaje udruzivanjem k-tog i k+1-vog kupca, tj:
a[k]=t[k]+t[k+1]-p[k]
Jasno da clanovi niza a u opstem slucaju su i pozitivni i negativni celi brojevi.
Dalje, k-ti covek se ne moze istovremeno udruziti sa k+1-vim i k-1-vim covekom,
tj. odatle sledi da u nizu ne mogu istovremeno i a[k-1] i a[k] biti ustede,
tj.potrebno je pronaci podniz niza a koji ima najvecu sumu u kojoj ne ucestvuju susedni clanovi, a to je upravo problem koji je tema 3. zadatka.

 

5.   CYK algoritam

Cocke-Younger-Kasami (CYK) algoritam se koristi radi utvrđivanja da li zadata niska može niti generisana zadatom kontekst-slobodnom gramatikom (a ako je odgovor potvrdan, može dati i način generisanja). Algoritam pripada paradigmi dinamičkog programiranja.

CYK zapravo prepoznaje jezik(e) definisane kontekst-slobodnim gramtikama u normalnoj formi Čomskog.

PODSEĆANJE

• Kontekst-slobodne gramatike u hijerarhiji Čomskog pripadaju tipu 2 koji generiše kontekst-slobodne jezike. Oni su definišu pravilima oblika  A → γ gde A je neterminal,  γ je niska sačinjena od  terminala i neterminala. Ovi jezici su tačno svi oni jezici koji se mogu prepoznati  nedeterminističkim potisnim automatom. Kontekst slobodni jezici su teorijska osnova za sintaksu većine programskih jezika.
• Formalna gramtika je u normalnoj formi Čomskog akko sva produkciona pravila su oblika :

  A → BC    ili

  A → α

  gde A, B i C su neterminalni simboli,  α je a terminalni simbol.

Algoritam CYK

ulaz: karakteri a₁ ... a_n  od kojih se sastoji zadata niska, simboli zadate gramatike: r terminala i neterminali R₁ ... R_r, gde R₁ je početni simbol

izlaz: odgovor da li niska pripada jeziku gramatike

{ lokalne varijable:

i, j, k /*brojacke promenljive*/

matrica logickih vrednosti P[n,n,r] (na pocetku svaki element matrice ima vrednost 0)

/*tokom rada algoritma P[i,j,k] ce postati 1 ako podniska ulazne niske od pozicije i na duzini j moze se generisati iz R_k*/

 

for( i = 1; i<= n; i++)  /*BSO uzecemo da 1. element je P[1,1,1], a ne P[0,0,0] */

za svako pravilo gramatike R_j → a_i postaviti  P[i,1,j] = 1 ;

 

for( i = 2; i<= n; i++)  /* skenira se ulazna niska, a za svako a[i] */     
 for(j = 1; j<= n-i+1; j++)  /* pregleda se prefiks niske duzine j */

for( k = 1; k<= i-1;k++) /* izvodjenje iz produkcionih pravila gramatike*/

za svako pravilo R_A -> R_B R_C

if   ((P[j,k,B]==1) && (P[j+k,i-k,C]==1))  P[j,i,A] = 1; /* tj. ako pravilo  R_A -> R_B R_C

             je takvo da iz R_B se moze generisati podniska duzine k pocev od pozicije j, i

             iz R_C  se moze generisati  podniska duzine i-k pocev od pozicije j+k, onda se iz R_A

moze generisati  podniska duzine i pocev od pozicije j, tj. P[j,i,A] = 1*/

 

if  (P[1,n,1]==1) print 'niska je clan jezika'
else  print 'niska nije clan jezika'

}

Složenost

Asimptotska složenost najgoreg slučaja je  Θ(n³), gde n je dužina ulayne niske koja se parsira. (zbog ugnježdena 3 for ciklusa sa do n iteracija). Dakle, ovaj algoritam pripada najjefikasnijim algoritmima (po kubnoj složenosti) za prepoznavanje kontekst-slobodnih jezika.

Modifikacije algoritma i primene

1. Radi konstrukcije drveta parsiranja, CYK algoritam se se može modifikovati tako da elmenti matrice P ne budu 0,1 već čvorovi stabla parsiranja. Kako gramatika može biti višeznačna, neophodno je pamtiti u matrici zapravo listu čvorova i rezultat će biti neşamo jedno parsersko drvo, već šuma mogućih stabla parsiranja.

2. Teoretski značaj CYK algoritma leži u mogučnosti da se koristi kao konstruktivan dokaz da problem pripadnosti kontekst-slobodnim jezicima je odlučiv.

3. Radi parsiranja stohastičkih kontekst slobodnih gramatika (SKSG), CYK algoritam se se može modifikovati tako da elmenti matrice P ne budu 0,1 već verovatnoće.  Naime, SKSG su kontekst slobodne gramatike u kojim se svaka primena produkcije obavlja uz neku verovatnoću. Preciznije, verovatnoća izvođenja je proizvod verovatnoća pravila koji se koriste u tim izvođenjima.

SKSG se koriste u oblasti NLP (obrada prirodnih jezika) i proučavanja RNK molekula u bioinformatici.

Na primer neka a,c,g,u predstavljaju nukleotide i neka jedini neterminal je S koji je i početni simbol:

S --> aSu | cSg | gSc | uSa

Ova kontekst slobodna gramatika predstavlja RNK molekul koji se sastoji samo od dva komplementarana regiona sa kanonskim parovima tipa  A-U i C-G.

Ali,  pridruživanjem verovatnoća, moguće je modelovati osnovu ili osnovne parove koji su konzistetni sa očekivanim RNK molekulskim obrascem. Ovo modelovanje upotrebom SKSG je počelo da se koristi u aplikacijama počev od 1998. SKSG se koriste zbog

1. predstavljanje obrazaca RNK genske familije u bazi
2. pretrage sekvence genoma koji mogu pripadati pomenutoj familiji
3. komparitivnog istraživanja genoma - testiranja da li u dva organizma je sačuvana informacija i o sekundarnoj strukturi ili čak i predikcija sekundarne strukture RNK molekula

 

 

 

 

6.  Neka je dat niz celih brojeva a sa n clanova. Postaviti zagrade u izraz a[1]-a[2]-...-a[n] tako da vrednost izraza bude minimalna.

Rešenje:

Proširićemo ršsavanje ovog problema tako što ćemo rešavati zadatak: pronaći raspored zagrada koji minimizira izraz i raspored zagrada koji maksimira izraz.

Naime, dešava se da se vrši prosirivanjem problema, jer se novi problem jednostavnije rešava.
Na primer: Ako želimo da dokažemo neko tvrđenje P indukcijom po n, potrebno je da pokazemo da
(za svako k < n) P(k) => P(n).
Ali, moguce je da je jednostavnije dokazati tvrdjenje da
(za svako k < n) P(k) & Q(k) => P(n) .
Da bi se moglo koristiti Q u indukcijskoj hipotezi, jednostavnije je prosiriti polazni problem i dokazati jace tvrdjenje
P & Q. Tada u indukcijskom koraku treba dokazati da
(za svako k < n) P(k) & Q(k) => ( P(n) & Q(n) ) , sto, takodje, cesto moze biti jednostavnije u odnosu na polazni problem.

Ako k-to oduzimanje sleva na desno je poslednje oduzimanje koje se izvrsava u resenju (tj. optimalnom zagradjivanju), onda su u izrazu levo od k-tog operatora minus zagrade postavljene tako da on ima mnimalnu vrednost,a u izraz desno tako da ima maksimalnu vrednost.
Neka je l-to oduzimanje sleva ono koje se poslednje izvrsava pri racunanju maksimalne vrednosti izraza. Tada su u prvom delu izraza zagrade postavljene tako da on ima maksimalnu vrednost, a u drugom delu tako da ima minimalnu vrednost.

Stoga formiramo dve matrice Max i Min tako da:

za 1 <=i <=n:	Min[i,i]=Max[i,i]=a[i]
za 1 <=i < j < = n:	Min[i,j] je najmanja vrednost izraza koja pocinje sa a[i] i zavrsava se sa a[j]
za 1 <=i < j <= n:	Min[j,i] je redni broj oduzimanja koje se poslednje izvrsava tako da izraz koji pocinje sa a[i] i zavrsava se sa a[j] ima minimalnu vrednost
za 1 <= i < j <= n:	Max[i,j] je najveca vrednost izraza koja pocinje sa a[i] i zavrsava se sa a[j]
za 1 <= i < j <= n:	Max[j,i] je redni broj oduzimanja koje se poslednje izvrsava tako da izraz koji pocinje sa a[i] i zavrsava se sa a[j] ima maksimalnu vrednost

 

Svaka od matrica Max i Min se koristi za pamcenje dva tipa podataka:

• informacija o ekstremnoj vrednosti izraza

• informacija o rednom broju poslednje izvrsene operacije oduzimanja, potrebne za rekonstrukciju izraza

dakle:

• ako je j-i=1, onda:
  Min[i,j]=Max[i,j]=a[i]-a[j]
  Min[j,i]=Max[j,i]=i (jer se izvrsava samo jedno oduzimanje)

• ako je j-i>1, onda:
  Max[i,j]=max _{i <= k < j} {Max[i,k]-Min[k+1,j]}
  Min[i,j]=min _{i <= k < j} {Min[i,k]-Max[k+1,j]}

Matrice se popunjavaju po dijagonalama, a pocev od glavne i vrsi se popunjavanje elemenata ciji indeksi su [s,t] gde s=i, t=j-i.

 

Algoritam OptIzrazOduzimanja (a,n)
ulaz: a /* niz celih brojeva, clanova izraza a[1]-a[2]-...-a[n] */
       n /* dimenzija niza a */
izlaz: optimalni izraz sa zagradama

for (k=1;k < = n; k++) Max[k,k]=Min[k,k]=a[k];

for (t=1;t < = n-1; t++)
   for(s=1;s < = n-t; s++)
    {
     Max[t+s,s]=s;
     Max[s,t+s]=Max[s,s]-Min[s+1,t+s];
     Min[t+s,s]=s;
     Min[s,t+s]=Min[s,s]-Max[s+1,t+s];
    for(k=s+1;k<=t+s-1;k++)
      {
         if (Max[s,k]-Min[k+1,t+s] > Max[s,t+s])
           {
              Max[s,t+s]=Max[s,k]-Min[k+1, t+s];
              Max[t+s,s]=k;
           }

           if (Min[s,k]-Max[k+1,t+s] < Min[s,t+s])
           {
              Min[s,t+s]=Min[s,k]-Max[k+1, t+s];
              Min[t+s,s]=k;
           }
      }

   }

OPT_ispis(1,n);
    }

Algoritam OPT_ispis (i,j);
if (i==j) print(a[i]);
else
    {
      print( "(" ); OPT_ispis(i, Min[j,i]);
      print( ") - (" ); OPT_ispis(Min[j,i]+1, j); print (" ) " );
    }
  }

 

7.  Nepristrasne igre  i tehnika memoizacije u dinamičkom programiranju

Jedna od primena dinamičkog programiranja su logičke igre: treba pronaći najbolji potez u nekoj poziciji.

U matematičkoj teoriji igara, Nim pripada klasi nepristrasnih igara, tj. klasi igara u kojima su potezi igrača impersonalni, tj.  potezi jednog igrača rasploživi su i drugim igračima. Npr. šah nije nepristrasna igra, jer postoji igrač sa belim i igrač sa crnim figurama.

Teorijsku osnovu Nim igre prvi je prikazao matematičar Charles Bouton na Harvard Universitetu 1901. Zapravo, Bouton, je upotrebio igru da bi prikazao prednosti upotrebe binarnog sistema, ali je demonstrirao i formulu prema kojoj igrači igre mogu da utvrde korektnost sledećog potezai.

Nim igra je drevna igra iz Kine (zvana Tsyanshidzi, tj, "uzmi kamenčić").

Interesantno da u francuskom filmu (nominovan za Oskara za scenario 1962.)  "Poslednja godina u Marienbadu"  likovi upravo učestvuju u Nim igri.

Na početku igre se na gomili nalazi n, (n>=2) šibica. Igrač koji je prvi na potezu, može da uzme sa gomile najmanje jednu, a najviše n-1 šibicu. U svakom sledećem potezu, igrač koji je na potezu može da uzme najmanje jednom a najviše dva puta više šibica, nego što je njegov protivnik uzeo u prethodnom potezu. Igra se završava kada na stolu ne ostane ni jedna šibica, a pobednik je igrač koji je uzeo poslednju šibicu. Nerešen ishod nije moguć.

Razmotrimo poziciju u kojoj je inicijalno bilo sedam šibica. Ako uzmete dve, protivnik može da uzme jednu, dve, tri ili četiri; ako uzme više od jedne, Vi u sledećem potezu možete uzeti sve preostale i tako pobediti; ako uzme jednu šibicu, ostaće ih četiri; potom Vi uzimete jednu (ostaje ih tri), a on može uzeti jednu ili dve; u svakom slučaju, Vi uzimte poslednju i pobeđujete. Iz ove priče sledi da, ako je na stolu inicijalno sedam šibica, igrač koji je prvi na potezu sigurno pobeđuje, naravno ako ne napravi grešku. Sa druge strane, lako je dokazati da na tabli sa osam šibica nema dobre strategije za igrača koji je prvi na potezu, odnosno on može da pobedi samo ako protivnik napravi grešku.

Za predstavljanje neke pozicije mora se znati i koliko najviše šibica može da ukloni igrač koji je na potezu. Sledi da se pozicija može predstaviti uređenim parom (i, j), 0<=j<=i, gde je i broj preostalih šibica, j maksimalan broj šibica koje igrač na potezu sme da ukloni. Početna pozicija sa n šibica se opisuje sa (n, n-1). Iz pozicije (i, j) mogu da nastanu pozicije (i-k, min(i-k, 2k)), 1<=k<=j, a završna pozicija je (0, 0). Dakle, nikakvim sledom regularnih poteza ne može da se dođe do pozicija (i, j) gde je j neparan broj i pri tome je j<i-1.

Zadatak je da za datu poziciju (i, j) kažemo da li je za igrača na potezu pobednička i, ako jeste, koliko šibica treba da uzme da bi pobedio. Ako ne postoje izgledi za pobedu, najpovoljnije je da program uzme samo jednu šibicu - partija će duže trajati pa su i veće šanse da protivnik napravi grešku.

Pođimo redom. Pozicija (0, 0) je gubitnička, a ako su sve pozicije koje mogu nastati iz pozicije (i, j) pobedničke, onda je sama pozicija (i, j) gubitnička (jer, ma šta odigrao onaj koji zatekne poziciju (i, j), njegov protivnik će imati pobednički potez), a ako je bar jedna od njih gubitnička, onda je pozicija (i, j) pobednička. Posledica ovog razmišljanja je sledeća rekurentna formula, koja za poziciju (i, j) govori da li je gubitnička (0) ili pobednička (broj različit od nule):

        0, i=j=0

f(i,j)= 0, za svako k,k=1..j,f(i-k,min(i-k,2k)>0

        k, postoji k, k=1..j, f(i-k, min(i-k, 2k)=0

Jasno je da su sve pozicije oblika (i, i) pobedničke, jer ako uzmemo i šibica dobijamo finalnu poziciju (0,0) (f(i,i)=i), ali izbegavanjem da taj slučaj uključimo u izloženu formulu ne umanjuje se opštost priče.

Gruba sila: Prvo što pada na pamet je da, na osnovu prethodne formule se sastavi rekurzivna funkciju, koja redom proverava moguće vrednosti za 1<=k<=j, i traži takvo k za koje je pozicija (i-k, min(2*k, i-k)) gubitnička (0). Ukoliko nađe takvu poziciju, funkcija vraća baš to k, a ukoliko takvo k ne postoji, funkcija vraća 0. Vrednosti za k ćemo razmatrati redom: od 1 do j. Kod ove igre to je manje-više svejedno, ali u opštem slučaju se pozicije nekako klasifikuju: prvo se ispituju one za koje se veruje da je veća šansa da će biti gubitničke, a to se čini iz vrlo prostog razloga - što pre otkrijemo gubitničku poziciju, pre ćemo znati vrednost tražene pozicije. Ova ideja se primenjuje kod šaha, iks-oksa i donosi velika ubrzanja u odnosu na ispitivanje pozicija redom. Implementacija:

int nim1(i,j)

int i,j;

{

  int k;

  for(k=1;k=j;k++)

    if (nim1(i-k,min(2*k,i-k))==0) return(k);

  return(0);

}

Nedostatak ovog algoritma je  preklapanje potproblema. Ako funkciju pozovete sa nim1 (1000,999) radiće dosta dugo, iako se uočava jda maksimalan teorijski broj potproblema (u ovom slučaju potproblemi su pozicije) je svega O(n*n). Dakle, ima smisla primeniti dinamičko programiranje!

Prikažimo dva pristupa: kod prvog, koristeći dinamičko programiranje, obrazovaćemo matricu pos[maxn][maxn], gde je maxn maksimalan broj šibica, takvu da je pos[i][j]=0 ako je (i, j) gubitnička pozicija, dok je u suprotnom, kada je pozicija (i, j) pobednička, pos[i][j] jednako broju šibica koje treba ukloniti, da bi novodobijena pozicija bila gubitnička. Matricu ćemo popunjavati redom: odozgo nadole i sleva udesno, tako da kada razmatramo poziciju (i, j) znamo vrednosti svih pozicija koje iz nje mogu nastati. Dobijamo klasičan bottom-up algoritam: kreće se od rešavanja najjednostavnijih problema ka sve složenijim, koji se posle "oslanjaju" na rešenja onih jednostavnijih.

   Na kraju, traženu vrednost čuva član pos[n][n-1], tj. implementacija gore navedenog pristupa glasi:

int nim_igra(int n)

{

  int i,j,k;

  pos[0][0]=0;

  for (i=1; i=n; i++)

   for (j=1; j=i; j++)

     {

         k=1;

         while ((k<j) && (pos(i-k][min(2*k,i-k)]))   k++;

    

    

         if (k<j) pos[i][j] =k; 

         else  if (pos[i-j][min(2*j,i-j)]==0) pos[i][j]=j;

         else pos[i][j]=0;

     }

  return (pos[n][n-1]);

}

Očigledno je da je ovaj algoritam iterativan i polinomijalne složenosti, u najgorem slučaju O(n³) (ali mnogo bliže O(n²)), što je veliki napredak u odnosu na prvi algoritam, koji je bio eksponencijalne složenosti. On, ipak, računa i neke nepotrebne vrednosti: već je napomenuto da se do pozicija  (i, j), gde je j neparan broj i važi j<i-1, ne može regularno doći, ali ih ovaj algoritam uzima u razmatranje. Ovo se može lako popraviti jednom if selekcijom, ali ima i težih problema.

Rekurzivan algoritam, dat na početku teksta, je neefikasan, jer ne vodi računa o preklapanju potproblema, te iste vrednosti računa više puta. Ipak, taj algoritam je top-down, te nikada ne računa nepotrebne vrednosti kao opisani bottom-up algoritam. Na primer, za poziciju (15, 14), rekurzivni algoritam će saznati da je pobednička, čim otkrije da je njen drugi sledbenik, pozicija (13,4) gubitnička, pa neće razmatrati (12,6), (11,8)..., kojima će s druge strane bottom-up algoritam razmatrati. Kod pozicije (15, 14), treba razmotriti svega 27 podpozicija, dok iterativni algoritam to čini sa njih 121. Ovo se ne može popraviti, jer bottom-up algoritam ne može unapred znati da nije potrebno razmatrati poziciju (12, 6). Kombinovanjem prvog i drugog rešenja stižemo do onoga što se zove "rekurzija sa pamćenjem" (memoization). U tu svrhu uvešćemo pomoćnu globalnu logičku matricu prosao [maxn][maxn], inicijalizovanu na FALSE (0), koja nam govori koje smo pozicije već razmotrili (prosao [i][j] je 1 ako je pos[i][j] već izračunato i tada je pos[i][j] tražena vrednost).

int NimIgra3 (int i,int j)

{ int k;

  if (prosao[i][j]==TRUE) return(pos[i][j]);

  else {

     for (k=1; k=j; k++)

        if (NimIgra3(i-k, min(2*k,i-k))==0) {

           pos[i][j]=k;prosao[i][j]=TRUE;

           return(k);

        }

        return(0);

  }

}

Ovaj algoritam je primetno brži od svog polinomijalnog prethodnika - što je više šibica, razlike u vremenu izvršavanja postaju sve drastičnije. Upotreba matrice prosao uvodena je samo zbog veće čitljivosti, jer, na primer, bilo je dovoljno matricu pos popuniti negativnim vrednostima, koje bi "glumile" FALSE u nizu prosao, ali ovako je lakše za praćenje.

Memoization je veoma moćna tehnika, ali njeno korišćenje nije uvek opravdano. Ako je zadatak takav da ćemo na sve (ili veliku većinu) potprobleme naići tokom izračunavanja tražene vrednosti, može se desiti da memoization radi čak i sporije od iterativnog bottom-up algoritma, jer je tehnika rekurzivna, pa se vreme troši na kopiranje parametara i lokalnih promenljivih na stek. Ipak, usporenje koje ova tehnika može da donese kod nekog problema mnogo je manje od ubrzanja koje donosi kod mnogih drugih tako da nećete mnogo pogrešiti ako je često primenjujete. U svakom slučaju, korisno je proceniti da li postoje potproblemi koji se neće razmatrati, i ako postoje koliko ih ima.

No, dinamičko programiranje nije savršena tehnika, primenljiva kod svih logičkih igara. Posmatranjem neke kompleksnije igre, na primer, šaha,  može se zaključiti da broj načina na koji se mogu rasporediti figure na šahovskoj tabli, ne vodeći računa o nemogućim pozicijama (pozicije bez kraljeva, sa nepravilno postavljenim lovcima i slične) je velik i da je nemoguće pretražiti kompletno stablo, a kamoli "popamtiti" vrednosti svih pozicija, te je ovde dinamičko programiranje neupotrebljivo. Zato, postoje neke heuristike (minimax princip i alfa-beta skraćivanje), koje sa prilično velikom tačnošću govore o najboljem potezu, iako ne obrazuju kompletno stablo poteza i ne ispituju sve moguće nastavke date pozicije.

Algoritam Nim (int pos[100][100])

/* Matrice pos i prosao sastavljene tako da je

pos[x][y]=0  akko  prosao[x][y]=FALSE */

void init(int n) /* inicijalizacija matrice pos*/

{  int i,j;

  for(i=0;i=n;i++)

    for(j=0;j=n;j++)     pos[i][j]=-1;

  pos[0][0]=0;

}

int min(int x, int y)

{

  return(x<y?x:y);

}

int nim(int i, int j)  /* formiranje matrice pos prema pravilima nim igre */

{

int k;

  if (pos[i][j]>=0) return(pos[i][j]);

  else

  {

    for(k=1;k=j;k++)

      if (nim(i-k,min(2*k,i-k))==0)

      {

        pos[i][j]=k;

        return(k);

      }

    return(0);

  }

}

void main(void)

{

  int i,j,k;

  printf("\n Unesite broj sibica (100): ");

  scanf("%d",&i);

  init(i);

  

   for(j=i-1;;)

  {

    do{

       printf("\nSTANJE:\n Ima jos %d sibica.\nMozete uzeti maksimalno %d sibica\n Koliko uzimate: ",i,j);

       scanf("%d",&k); }

    while ((k>j)||(k<1));

    j=min(2*k,i-k);

    i=i-k;

    if (i==0)

    {

      printf("\nVI STE POBEDILI!!!\n");

      break;

    }

    k=nim(i,j);

    if (k==0) k=1;

    printf("STANJE:\n Ima jos %d sibica.\n  Moguce je uzeti maksimalno %d sibica.",i,j);

    printf("\n Uzimam %d sibica.",k);

    j=min(2*k,i-k);

    i=i-k;

    if (i==0)

    {

      printf("\nPOBEDIO SAM!.\n");

      break;

    }

  }

}

 

---

Jelena Grmuša

Primene računara

---