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
Pomoću algoritama dinamičkog programiranja, potproblemi jednog problema postaju međusobno zavisni, pa je dovoljno da ih samo jednom rešite, da bi Vaš rad bio lakši i brži.
Postoji velika klasa problema koje je moguće rešiti tako što se polazni problem podeli na potprobleme, a oni dalje na pot-pot-probleme i sve tako dok se ne stigne do najjednostavnijih problema, koje se ne moraju dalje deliti i koji se odmah rešavaju. Divide-and-conquer je jedan od metoda koji "radi" na ovom principu (Quick sort).
Realno je očekivati da postoje problemi kod kojih se dešava da prilikom deobe na potprobleme se neke pojave više puta. Ukoliko bi svaki bi rešavan onog trenutka kada se na njega naiđe, ne vodeći računa o tome da li je već jednom rešen, moglo bi se desiti da isti posao rađen više puta, što može rezultirati katastrofalno sporim algoritmom.
Osnovna ideja na koju se oslanjaju algoritmi dinamičkog programiranja je da se svaki dobijeni međurezultat (rešenje nekog potproblema) sačuva i potom, kada se sledeći put naiđe na taj isti potproblem, izbegne njegovo ponovno rešavanje. Već sada se uočava bitna razlika između dinamičkog programiranja i divide-and-conquer metoda: kod ovog drugog potproblemi su međusobno nezavisni, dok kod dinamičkog programiranja nisu.
1. Formirati algoritam koji za dve reči dužine n (prva reč), m (druga reč) nad azbukom slova i cifara pronalazi niz operacija editovanja najmanje cene kojim se prva reč transformiše u drugu reč. Dozvoljene su tri vrste operacija editovanja i svaka ima cenu jedan:
insert = umetanje jednog karaktera
delete = brisanje 1 karaktera
replace = zamena jednog karaktera drugim karakterom
A(1)=amaak
/*insert a*/
A(2)=amaa /*delete k */
CENA: 1+1=2
A(1)=aak /*delete m*/
A(2)=amak /*insert m */
A(3)=amaa /*replace k slovom a */
CENA: 1+1+1=3
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.
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.
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 )
detekcija plagijata
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.
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. pseudo-jezik:
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 formiranja matrice cena za niske "SAMBA" i "SIMBAD".
S A M B A 0 1 2 3 4 5 S 1 I 2 M 3 B 4 A 5 D 6 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 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 3 D 6 5 4 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 3 3 D 6 5 4 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 3 3 2 D 6 5 4 4 3 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 3 3 2 1 D 6 5 4 4 3 2 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 A=aabccbba,
B=baacbabacc, Cena=?
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=(a1, a2,
..., ak) je podniz niza b=(b1, b2,
..., bm), ako i samo ako postoji strogo rastući niz
(i1, i2, ..., ik) indeksa, takav
da za svako j= 1, 2, ... k važi bij=aj.
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.
Bez smanjenja opstosti, smatrajmo da elementi nizova su p=(p1, p2,
..., pm) i q=(q1, q2,
..., qn) 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 Pc, Qd Nizovi LCS operacija koji transformišu Pc u Qd zavisno od poslednje
LCS operacije:
LCS(m,n)=?
Ako element pm=qn
Onda:
LCS(m,n)=LCS(m-1,n-1) * {p m }, gde je * oznaka za
operaciju dopisivanja
ako
element pmnije jednak elementu qn, 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. 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:
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
niz 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.
TEST PRIMERI
REŠENJE: Neka je a niz od n celih brojeva.
Podniz niza A0 je prazan
niz, dok je podniz niza A1 element a[1] ako
je a[1]>0.
1. Ako element a[n] ne pripada podnizu R=R(A), onda je
R
Dakle, za i=2..n, važi da R(Ai) je ili R(Ai-1) ili R(Ai-2)* {a[i]},
tj.
Neka je niz s takav da:
Iz niza s će se ispisati rešenje R.
4.
Neka n ljudi čeka u redu da kupi karte za
predstavu, pri cemu ti 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 pk, 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: 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 gde A, B i C
su neterminalni
simboli, α
je a terminalni simbol. Algoritam CYK ulaz: karakteri a1 ... an
od kojih se sastoji zadata niska, simboli zadate gramatike: r
terminala i neterminali R1
... Rr, gde R1
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) } Složenost Asimptotska složenost najgoreg slučaja je Θ(n3),
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. 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: 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 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.
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. 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: ako
je j-i>1, onda: 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.
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. 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ć. 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:
Nizovi edit operacija koji transformišu A(i) u B(j) zavisno od poslednje operacije u nizu edit operacija
Postoje tri ključne situacije:
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
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
Primer
Koraci 1, 2
Koraci od 3 do 6 kada i = 1
Koraci od 3 do 6 kada i = 2
Koraci od 3 do 6 kada i = 3
Koraci od 3 do 6 kada i = 4
Koraci od 3 do 6 kada i = 5
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
2. Zajednički
podniz
Pc je
niz koji se sastoji od prvih c elemenata niza p
gde je c <= m
Elementi
matrice B su:
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)
}
Zadaci za samostalni rad
ULAZ(a) IZLAZ(podniz) 5 2 -1 8 10 -2 -5 5 10 -1 -2 -4 3 1 -2 1 3 1 -3 4 -5 -4 1 18 12 4 18
Neka je R=R(A) jedan podniz iz formulacije zadatka koji odgovara nizu
a.
Neka je Ak niz koji se sastoji od prvih
k elemenata niza a.
podniz iz formulacije zadatka koji odgovara nizu An-1.
2. Ako element a[n] pripada podnizu R=R(A), onda je
R \ a[n]
podniz iz formulacije zadatka koji odgovara nizu An-2.
uzima se onaj od podnizova koji ima veci zbir.
s(i) je suma podniza R(Ai).
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
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 */
}
}
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
for(j = 1; j<= n-i+1; j++) /* pregleda se prefiks niske duzine j
*/
else print 'niska
nije clan jezika'Modifikacije algoritma i primene
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.
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.
Min[i,j]=Max[i,j]=a[i]-a[j]
Min[j,i]=Max[j,i]=i
(jer se izvrsava samo jedno oduzimanje)
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]}
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 (" ) " );
}
}
Napredne tehnike
7. Nepristrasne igre i tehnika memoizacije u
dinamičkom programiranju
Nim igra je drevna igra iz Kine (zvana
Tsyanshidzi, tj, "uzmi kamenčić").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!
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(n3) (ali mnogo bliže O(n2)),
š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;
}
}
}