Napisati program koji određuje broj kombinacija bez ponavljanja dužine \(k\) iz skupa od \(k\) elemenata (tj. broj različitih kombinacija u igri loto ako se iz bubnja koji sadrži \(n\) loptica izvlači njih \(k\)).
Sa standardnog ulaza se zadaje broj \(k\) (\(1 \leq k \leq n\)) i broj \(n\) (\(1 \leq n \leq 40\)).
Na standardni izlaz ispisati traženi broj kombinacija.
3 5
10
To su kombinacije \((1, 2, 3)\), \((1, 2, 4)\), \((1, 2, 5)\) \((1, 3, 4)\), \((1, 3, 5)\), \((1, 4, 5)\), \((2, 3, 4)\), \((2, 3, 5)\), \((2, 4, 5)\) i \((3, 4, 5)\).
7 39
15380937
Iako postoje razni načini da se do rešenja ovog zadatka dođe, prikazaćemo tehniku zasnovanu na tome da program koji nabraja sve kombinatorne objekte malo po malo transformišemo do efikasnog programa koji ih broji. Ova tehnika nije specifična za kombinacije bez ponavljanja i može se primeniti na brojanje bilo koje vrste kombinatornih objekata koje nabrajamo rekurzivnom funkcijom.
Broj kombinacija jednak je binomnom koeficijentu
\[\binom{n}{k} = \frac{n!}{(n-k)!k!}.\]
Međutim, izračunavanje na osnovu direktne primene ove formule bi veoma brzo dovelo do prekoračenja (usled veoma brzog rasta faktorijelske funkcije). Malo bolja situacija je da se izračuna
\[\binom{n}{k} = \frac{n(n-1)\ldots(n-k+1)}{k!},\]
no ni to u potpunosti ne uklanja problem prekoračenja, jer imenilac može biti preveliki.
Možemo krenuti od ranije opisane procedure za generisanje svih kombinacija u kojoj se održava interval \([n_{min}, n_{max}]\) iz kojeg se mogu uzeti vrednosti kojima se proširuje započeta kombinacija i u kojoj se kroz dva rekurzivna poziva razmatra mogućnost da se vrednost \(n_{min}\) uvrsti u kombinaciju i mogućnost da se ona ne uvrsti u kombinaciju.
Umesto procedure koja ispisuje kombinacije, definišemo fukciju koja vraća broj kombinacija. Pošto nam je bitan samo broj kombinacija, a ne i same kombinacije, možemo u potpunosti izbaciti niz koji se popunjava i umesto njega prosleđivati samo njegovu dužinu \(k\).
long long brojKombinacija(int i, int k,
int n_min, int n_max) {
// ako je popunjen ceo niz postoji jedna kombinacija
if (i == k) return 1;
// ako niz nije moguće popuniti do kraja,
// tada nema kombinacija
if (k - i > n_max - n_min + 1)
return 0;
// broj kombinacija je jednak zbiru
// broja kombinacija koje sadrže vrednost n_min i
// broja kombinacija koje ne sadrže vrednost n_min
return brojKombinacija(i+1, k, n_min+1, n_max) +
brojKombinacija(i, k, n_min+1, n_max);
}
long long brojKombinacija(int K, int N) {
return brojKombinacija(0, K, 1, N);
}#include <iostream>
#include <vector>
using namespace std;
long long brojKombinacija(int i, int k,
int n_min, int n_max) {
// ako je popunjen ceo niz postoji jedna kombinacija
if (i == k) return 1;
// ako niz nije moguće popuniti do kraja,
// tada nema kombinacija
if (k - i > n_max - n_min + 1)
return 0;
// broj kombinacija je jednak zbiru
// broja kombinacija koje sadrže vrednost n_min i
// broja kombinacija koje ne sadrže vrednost n_min
return brojKombinacija(i+1, k, n_min+1, n_max) +
brojKombinacija(i, k, n_min+1, n_max);
}
long long brojKombinacija(int K, int N) {
return brojKombinacija(0, K, 1, N);
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}Možemo primetiti da nam konkretne vrednosti \(k\) i \(i\) nisu bitne, već je bitan samo broj elemenata u intervalu \([i, k)\) tj. razlika \(k-i\). Slično, nisu nam bitne ni konkretne vrednosti \(n_{max}\) i \(n_{min}\) već samo broj elemenata u segmentu \([n_{min}, n_{max}]\) tj. vrednost \(n_{max} - n_{max} + 1\). Ako te dve veličine zamenimo sa \(k\) tj. \(n\) dobijamo narednu definiciju.
long long brojKombinacija(int k, int n) {
// niz je uspešno popunjen
if (k == 0) return 1;
// niz nije moguće popuniti do kraja
if (k > n) return 0;
// broj kombinacija je jednak zbiru kombinacija u dva slučaja
return brojKombinacija(k-1, n-1) + brojKombinacija(k, n-1);
}#include <iostream>
#include <vector>
using namespace std;
long long brojKombinacija(int k, int n) {
// niz je uspešno popunjen
if (k == 0) return 1;
// niz nije moguće popuniti do kraja
if (k > n) return 0;
// broj kombinacija je jednak zbiru kombinacija u dva slučaja
return brojKombinacija(k-1, n-1) + brojKombinacija(k, n-1);
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}Ako funkciju pozovemo za vrednosti \(k \leq n\), slučaj \(k > n\) može nastupiti jedino iz drugog rekurzivnog poziva za \(k=n\) (jer odnos između \(k\) i \(n\) u prvom rekurzivnom pozivu ostaje nepromenjen, a u drugom se menja samo za \(1\)). Međutim, kako je ilustrovano na narednoj slici, u slučaju poziva funkcije za \(k=n\) dobiće se uvek povratna vrednost \(1\) (jedan rekurzivni poziv će uvek vraćati nulu, a drugi će prouzrokovati smanjivanje oba argumenta sve dok se ne dođe do \(k=n=0\), kada će se \(1\) vratiti na osnovu prvog izlaza iz rekurzije), što je sasvim u skladu sa tim da tada postoji samo jedna kombinacija.
Na osnovu ovoga iz rekurzije možemo izaći za \(k=n\) vrativši vrednost \(1\), čime onda eliminišemo potrebu za proverom da li je \(k > n\) (naravno, pod pretpostavkom da ćemo funkciju pozivati samo za \(k \leq n\)).
Primećujemo da smo ovom transformacijom dobili dobro poznate osobine binomnih koeficijenata.
\[\binom{n}{0} = 1, \qquad \binom{n}{n} = 1, \qquad \binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}.\]
One čine osnovu Paskalovog trougla u kom se nalaze binomni koeficijenti (u narednoj tabeli koeficijent \(\binom{n}{k}\) je napisan u vrsti \(n\) i koloni \(k\), da bi se prikazao uobičajeni oblik Paskalovog trougla, koji se popunjava vrstu po vrstu).
1 (0,0) 1 1 (1,0) (1,1) 1 2 1 (2,0) (2,1) (2,2) 1 3 3 1 (3,0) (3,1) (3,2) (3,3) 1 4 6 4 1 (4,0) (4,1) (4,2) (4,3) (4,4) 1 5 10 10 5 1 (5,0) (5,1) (5,2) (5,3) (5,4) (5,5) 1 6 15 20 15 6 1 (6,0) (6,1) (6,2) (6,3) (6,4) (6,5) (6,6)
Prva veza govori da su elementi prve kolone uvek jednaki 1, druga da su na kraju svake vrste elementi takođe jednaki 1, a treća da je svaki element u trouglu jednak zbiru elementa neposredno iznad njega i elementa neposredno ispred tog.
Naravno, do ovih formula i do rekurzivne definicije smo mogli doći i direktno, razmatranjem definicija kombinacija, na primer, u modelu gde se \(k\) kuglica bez vraćanja izvlače iz bubnja u kom se nalazi \(n\) različitih kuglica. Postoji jedinstven način da se iz bubnja ne izvuče ni jedna kuglica. Takođe, postoji jedinstven način da se iz bubnja izvuče svih \(n\) kuglica. U suprotnom (ako je \(0 < k < n\)), tada sve načine razdvajamo na one u kojima jeste i na one u kojima nije izvučena prva kuglica (kuglica sa najmanjim brojem). Ako ona jeste izvučena, preostalo je da se izvuče još \(k-1\) kuglica iz bubnja u kom se nalazi \(n-1\) kuglica, a ako nije, tada je preostalo da se izvuče još \(k\) kuglica iz bubnja u kom se nalazi još \(n-1\) kuglica (pošto smo pretpostavili da u drugoj grupi načina kuglica sa najmanjim brojem neće biti među izvučenim kuglicama, možemo je odmah izbaciti iz bubnja i skloniti negde sa strane).
long long brojKombinacija(int k, int n) {
// ako je popunjen ceo niz postoji jedna kombinacija
if (k == 0) return 1;
// ako treba popuniti još tačno n elemenata, tada postoji
// tačno jedna kombinacija
if (k == n) return 1;
// broj kombinacija je jednak zbiru kombinacija u dva slučaja
return brojKombinacija(k-1, n-1) + brojKombinacija(k, n-1);
}#include <iostream>
#include <vector>
using namespace std;
long long brojKombinacija(int k, int n) {
// ako je popunjen ceo niz postoji jedna kombinacija
if (k == 0) return 1;
// ako treba popuniti još tačno n elemenata, tada postoji
// tačno jedna kombinacija
if (k == n) return 1;
// broj kombinacija je jednak zbiru kombinacija u dva slučaja
return brojKombinacija(k-1, n-1) + brojKombinacija(k, n-1);
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}Vreme koje se utroši u svakom rekurzivnom pozivu (ne računajući rekurzivne pozive koji se iz njega iz pozivaju) je očigledno \(O(1)\). Jednačina kojom se opisuje vreme rada funkcije je \(T(k, n) = T(k-1, n-1) + T(k, n-1) + O(1)\), \(T(0, n) = T(n, n) = O(1)\), i vreme izvršavanja je \(T(k, n) = O(\binom{n}{k})\). Za fiksirano \(k\), ovo je složenost opisana polinomom promenljive \(n\), koji može biti veoma visokog stepena (\(k\)), dok za fiksirano \(n\) ovaj broj raste eksponencijalno sa porastom \(k\). U svakom slučaju, jasno je da je složenost izuzetno visoka i da je ovaj program praktično neupotrebljiv za veće vrednosti \(n\) i \(k\).
Razlog ovoj neefikasnosti su ponovljeni rekurzivni pozivi, što se može videti na slici. Svakom listu drveta odgovara tačno jedna kombinacija, pa pošto ukupno kombinacija ima \(\binom{n}{k}\), ukupan broj rekurzivnih poziva je ograničen sa \(2\binom{n}{k}\) (jer u binarnom drvetu ne može biti više nego duplo više čvorova nego listova). U svakom pozivu se vrši \(O(1)\) operacija, pa je složenost \(O(\binom{n}{k})\).
Iako korektna, gornja funkcija je neefikasna i može se popraviti tehnikom dinamičkog programiranja. Najjednostavnije prilagođavanje je da se upotrebi memoizacija. Pošto funkcija ima dva parametra, za memoizaciju ćemo upotrebiti matricu. Ako se \(\binom{n}{k}\) pamti u matrici na poziciji \((n, k)\), matricu možemo alocirati na \(n+1\) vrsta, gde poslednja vrsta ima \(n+1\) elemenata, a svaka prethodna jedan element manje (u matricu će se popunjavati elementi Paskalovog trougla).
Pošto nas neće zanimati vrednosti veće od polaznog \(k\) i pošto se i \(k\) i \(n\) smanjuju tokom rekurzije, pri čemu je \(k \leq n\), možemo i odseći deo trougla desno od pozicije \(k\).
Pošto su brojevi kombinacija uvek veći od nule, vrednosti \(0\) u matrici će nam označavati da poziv za te parametre još nije izvršen.
I memorijska i vremenska složenost memoizovane verzije je \(O(nk)\). Naime, u drvetu rekurzivnih poziva se svaki čvor može javiti najviše dva puta. Pošto svaki čvor sadrži par brojeva takvih da je prvi od \(0\) do \(k\), a drugi od \(0\) do \(n\), ukupan broj čvorova je odozgo ograničen sa \(2nk\) (a može biti i manji, jer se neki parovi ne mogu javiti).
Ako je poznato gornje ograničenje na vrednosti \(n\) i \(k\) tada umesto matrice koja se dinamički alocira možemo upotrebiti statički alociranu matricu, čime se izbegava nepotrebno trošenje vremena na dinamičku alokaciju, po cenu da program i za manje vrednosti \(n\) i \(k\) zauzima veliku količinu memorije. U tom slučaju nije moguće alocirati samo trougaoni deo matrice, već ceo, pravougaoni blok memorije.
long long brojKombinacija(int k, int n,
vector<vector<long long>>& memo) {
// ako smo već računali broj kombinacija, ne računamo ga
// ponovo
if (memo[n][k] != 0) return memo[n][k];
// broj kombinacija na početku i na kraju svake vrste jednak
// je 1
if (k == 0 || k == n) return memo[n][k] = 1;
// broj kombinacija u sredini jednak je zbiru broja
// kombinacija iznad i iznad levo od tekućeg elementa
return memo[n][k] = brojKombinacija(k-1, n-1, memo) +
brojKombinacija(k, n-1, memo);
}
long long brojKombinacija(int K, int N) {
// alociramo prostor za rezultate rekurzivnih poziva koji se
// mogu desiti i popunjavamo matricu nulama
vector<vector<long long>> memo(N+1);
for (int n = 0; n <= N; n++)
memo[n].resize(min(K+1, n+1), 0);
// pozivamo funkciju koja će izračunati traženi broj
return brojKombinacija(K, N, memo);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long brojKombinacija(int k, int n,
vector<vector<long long>>& memo) {
// ako smo već računali broj kombinacija, ne računamo ga
// ponovo
if (memo[n][k] != 0) return memo[n][k];
// broj kombinacija na početku i na kraju svake vrste jednak
// je 1
if (k == 0 || k == n) return memo[n][k] = 1;
// broj kombinacija u sredini jednak je zbiru broja
// kombinacija iznad i iznad levo od tekućeg elementa
return memo[n][k] = brojKombinacija(k-1, n-1, memo) +
brojKombinacija(k, n-1, memo);
}
long long brojKombinacija(int K, int N) {
// alociramo prostor za rezultate rekurzivnih poziva koji se
// mogu desiti i popunjavamo matricu nulama
vector<vector<long long>> memo(N+1);
for (int n = 0; n <= N; n++)
memo[n].resize(min(K+1, n+1), 0);
// pozivamo funkciju koja će izračunati traženi broj
return brojKombinacija(K, N, memo);
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}Umesto memoizacije možemo upotrebiti i dinamičko programiranje naviše, osloboditi se rekurzije i popuniti trougao vrstu po vrstu naniže. Popunjavanje celog trougla je prilično jednostavno.
long long brojKombinacija(int K, int N) {
// alociramo prostor za smeštanje celog trougla
vector<vector<long long>> dp(N+1);
for (int n = 0; n <= N; n++)
dp[n].resize(n+1);
// obrađujemo vrstu po vrstu
for (int n = 0; n <= N; n++) {
// na početku svake vrste nalazi se 1
dp[n][0] = 1;
// unutrašnje elemente izračunavamo kao zbir elemenata
// iznad njih
for (int k = 1; k < n; k++)
dp[n][k] = dp[n-1][k-1] + dp[n-1][k];
// na kraju svake vrste nalazi se 1
dp[n][n] = 1;
}
// vraćamo traženi rezultat
return dp[N][K];
}#include <iostream>
#include <vector>
using namespace std;
long long brojKombinacija(int K, int N) {
// alociramo prostor za smeštanje celog trougla
vector<vector<long long>> dp(N+1);
for (int n = 0; n <= N; n++)
dp[n].resize(n+1);
// obrađujemo vrstu po vrstu
for (int n = 0; n <= N; n++) {
// na početku svake vrste nalazi se 1
dp[n][0] = 1;
// unutrašnje elemente izračunavamo kao zbir elemenata
// iznad njih
for (int k = 1; k < n; k++)
dp[n][k] = dp[n-1][k-1] + dp[n-1][k];
// na kraju svake vrste nalazi se 1
dp[n][n] = 1;
}
// vraćamo traženi rezultat
return dp[N][K];
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}I u ovom slučaju možemo odseći nepotrebne desne kolone u trouglu. Moguće je odseći i deo ispod odgovarajuće dijagonale – takva odsecanja se obično ne radi u dinamičkom programiranju naviše jer ne menjaju asimptotsku složenost, dok ih rekurzivna implementacija zasnovana na memoizaciji prirodno izbegava. Na narednoj slici su obeleženi elementi Paskalovog trougla koji su potrebni za izračunavanje broja \(\binom{6}{3} = 20\).
long long brojKombinacija(int K, int N) {
// alociramo prostor za smeštanje relevantnog dela trougla
vector<vector<long long>> dp(N+1);
for (int n = 0; n <= N; n++)
dp[n].resize(min(K+1, n+1));
// trougao popunjavamo kolonu po kolonu
for (int n = 0; n <= N; n++) {
// na početku svake vrste nalazi se 1
dp[n][0] = 1;
// unutrašnje elemente izračunavamo kao zbir elemenata
// iznad njih
for (int k = 1; k <= min(n-1, K); k++)
dp[n][k] = dp[n-1][k-1] + dp[n-1][k];
// ako je potrebno da znamo krajnji element kolone,
// postavljamo ga na vrednost 1
if (n <= K)
dp[n][n] = 1;
}
// vraćamo traženi rezultat
return dp[N][K];
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long brojKombinacija(int K, int N) {
// alociramo prostor za smeštanje relevantnog dela trougla
vector<vector<long long>> dp(N+1);
for (int n = 0; n <= N; n++)
dp[n].resize(min(K+1, n+1));
// trougao popunjavamo kolonu po kolonu
for (int n = 0; n <= N; n++) {
// na početku svake vrste nalazi se 1
dp[n][0] = 1;
// unutrašnje elemente izračunavamo kao zbir elemenata
// iznad njih
for (int k = 1; k <= min(n-1, K); k++)
dp[n][k] = dp[n-1][k-1] + dp[n-1][k];
// ako je potrebno da znamo krajnji element kolone,
// postavljamo ga na vrednost 1
if (n <= K)
dp[n][n] = 1;
}
// vraćamo traženi rezultat
return dp[N][K];
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}Pažljivijom analizom prethodnog koda vidimo da, kako je to obično slučaj u dinamičkom programiranju, ne moramo istovremeno čuvati sve elemente matrice, jer svaka vrsta zavisi samo od prethodne i dovoljno je umesto matrice čuvati samo njene dve vrste (prethodnu i tekuću). Zapravo, dovoljno je čuvati samo jedan vektor vrstu ako je pažljivo popunjavamo i ako tokom njenog ažuriranja u jednom njenom delu čuvamo tekuću, a u drugom narednu vrstu. Pošto element \((n, k)\) zavisi od elementa \((n-1, k-1)\) i od elementa \((n-1, k)\) znači da svaki element zavisi od elemenata koji su levo od njega, ali ne od elemenata koji su desno od njega. Zato ćemo vektor popunjavati zdesna nalevo. Pretpostavićemo da tokom ažuriranja važi invarijanta da se na pozicijama strogo većim od \(k\) nalaze elementi vrste \(n\), a da se na pozicijama manjim ili jednakim od \(k\) nalaze elementi vrste \(n-1\). Ažuriranje započinje time što na kraj vrste dopišemo vrednost 1 (osim u slučaju kada vršimo sasecanje desnog dela trougla) i nastavlja se tako što se element na poziciji \(k\) uveća za vrednost na poziciji \(k-1\). Zaista, pre ažuriranja se na poziciji \(k\) nalazi vredost trougla sa pozicije \((n-1, k)\), dok se na poziciji \(k-1\) nalazi vrednost trougla sa pozicije \((n-1, k-1)\). Njihov zbir je vrednost trougla na poziciji \((n, k)\), pa se on upisuje na poziciju \(k\) i nakon toga se \(k\) smanjuje za \(1\), čime se invarijanta održava. Ažuriranje se vrši do pozicije \(k=1\), jer se na poziciji \(k=0\) u svim vrstama nalazi vrednost \(1\).
Memorijska složenost ovog rešenja je \(O(k)\), dok je vremenska \(O(n\cdot k)\). Primetimo kako smo od veoma neefikasnog rešenja eksponencijalne složenosti tehnikom dinamičkog programiranja dobili veoma efikasno i uz to prilično jednostavno rešenje.
long long brojKombinacija(int K, int N) {
// tekuća vrsta
vector<long long> dp(K+1);
// na početku svake vrste nalazi se 1
dp[0] = 1;
// trougao popunjavamo vrstu po vrstu
for (int n = 1; n <= N; n++) {
// vrstu ažruriramo zdesna nalevo
// na kraju svake vrste nalazi se 1
if (n <= K) dp[n] = 1;
// ažuriramo unutrašnje elemente
for (int k = min(n-1, K); k > 0; k--)
dp[k] += dp[k-1];
}
// vraćamo traženi rezultat
return dp[K];
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
long long brojKombinacija(int K, int N) {
// tekuća vrsta
vector<long long> dp(K+1);
// na početku svake vrste nalazi se 1
dp[0] = 1;
// trougao popunjavamo vrstu po vrstu
for (int n = 1; n <= N; n++) {
// vrstu ažruriramo zdesna nalevo
// na kraju svake vrste nalazi se 1
if (n <= K) dp[n] = 1;
// ažuriramo unutrašnje elemente
for (int k = min(n-1, K); k > 0; k--)
dp[k] += dp[k-1];
}
// vraćamo traženi rezultat
return dp[K];
}
int main() {
int K, N;
cin >> K >> N;
cout << brojKombinacija(K, N) << endl;
return 0;
}Napomenimo i da smo mogli krenuti od algoritma nabrajanja svih kombinacija u kom se u petlji razmatraju svi kandidati za element na tekućoj poziciji. Time bi se dobio algoritam koji bi element \(\binom{n}{k}\) računao po sledećoj formuli:
\[\binom{n}{k} = \sum_{n'=k}^{n} \binom{n'}{k-1}.\]
Napiši program koji izračunava dužinu najvećeg zajedničkog podniza dve niske. Podniz čine karakteri niske koji ne moraju biti uzastopni, ali se javljaju u istom redosledu kao u originalnoj niski. Na primer za niske abacbc i babbca najduža zajednička podniska je babc.
Dve linije standardnog ulaza sadrže dve niske koje se sastoje od malih slova engleske azbuke i dugačke su najviše 1000 karaktera.
Na standardni izlaz ispisati samo traženu dužinu.
xmjyauz mzjawxu
4
Podniz obe niske dužine 4 je mjau
Ako je bilo koja od dve niske prazna, tada je jedini njen podniz prazan, pa je dužina najdužeg zajedničkog podniza jednaka nuli.
Ako su obe niske neprazne, tada možemo uporediti njihova poslednja slova.
Ako su ona jednaka, ona mogu biti uključena u najduži zajednički podniz dve niske i problem se rekurzivno svodi na pronalaženje najdužeg zajedničkog podniza prefiksa tih niski dobijenih isključivanjem poslednjih slova. Naglasimo da nije greška eksplicitno analizirati i slučajeve kada neko od ta dva poslednja slova nije uključeno u najduži zajednički podniz (time smo sigurniji da ćemo dobiti korektan algoritam), ali se može dokazati da za tim nema potrebe.
U suprotnom, nije moguće da oba poslednja slova budu uključena u zajednički podniz. Zato razmatramo najduži zajednički podniz prve niske i prefiksa druge niske bez njenog poslednjeg slova i zajednički podniz druge niske i prefiksa prve niske bez njenog poslednjeg slova. Duži od dva podniza biće najduži zajednički podniz te dve niske. Naglasimo i da u ovom slučaju nije neophodno eksplicitno analizirati najduži zajednički podniz ta dva prefiksa (jer on ne može biti duži od najdužih zajedničkih podnizova dobijenih kada se neki od tih prefiksa proširi dodatnim slovom).
Pošto rekurzija teče po prefiksima niski, jedini promenljivi parametri tokom rekurzije mogu biti dužine tih prefiksa. Ako sa \(f(n_1, n_2)\) označimo dužinu najdužeg zajedničkog podniza prefiksa niske \(s\) dužine \(n_1\) i prefiksa niske \(t\) dužine \(n_2\), tada važi sledeća rekurentna veza:
\[\begin{align*} f(0, n_2) &= 0\\ f(n_1, 0) &= 0\\ f(n_1, n_2) &= f(n_1-1, n_2-1) + 1, \quad \textrm{za}\ s_{n_1-1} = t_{n_2-1}\\ f(n_1, n_2) &= \max{(f(n_1, n_2-1), f(n_1-1, n_2))}, \quad \textrm{za}\ s_{n_1-1} \neq t_{n_2-1} \end{align*}\]
// najduzi zajednici podniz (longest common substring, LCS)
// prefiksa duzine n1 niske s1 i
// prefiksa duzine n2 niske s2
int LCS(const string& s1, int n1,
const string& s2, int n2) {
if (n1 == 0 || n2 == 0)
return 0;
int rez = max(LCS(s1, n1, s2, n2-1),
LCS(s1, n1-1, s2, n2));
if (s1[n1-1] == s2[n2-1])
rez = max(rez, LCS(s1, n1-1, s2, n2-1) + 1);
return rez;
}
int LCS(const string& s1, const string& s2) {
return LCS(s1, s1.size(), s2, s2.size());
}#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
// najduzi zajednici podniz (longest common substring, LCS)
// prefiksa duzine n1 niske s1 i
// prefiksa duzine n2 niske s2
int LCS(const string& s1, int n1,
const string& s2, int n2) {
if (n1 == 0 || n2 == 0)
return 0;
int rez = max(LCS(s1, n1, s2, n2-1),
LCS(s1, n1-1, s2, n2));
if (s1[n1-1] == s2[n2-1])
rez = max(rez, LCS(s1, n1-1, s2, n2-1) + 1);
return rez;
}
int LCS(const string& s1, const string& s2) {
return LCS(s1, s1.size(), s2, s2.size());
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cout << LCS(s1, s2) << endl;
return 0;
}U direktnom rekurzivnom rešenju ima mnogo preklapajućih rekurzivnih poziva. Stoga je efikasnost moguće popraviti tehnikom dinamičkog programiranja. Jedan mogući pristup je da upotrebimo memoizaciju. Vrednost dužine najdužeg podniza za svaki par dužina prefiksa možemo pamtiti u matrici.
// najduzi zajednici podniz (longest common substring, LCS)
// prefiksa duzine n1 niske s1 i
// prefiksa duzine n2 niske s2
int LCS(const string& s1, int n1,
const string& s2, int n2,
vector<vector<int>>& memo) {
if (memo[n1][n2] != -1)
return memo[n1][n2];
if (n1 == 0 || n2 == 0)
return memo[n1][n2] = 0;
int rez = max(LCS(s1, n1, s2, n2-1, memo),
LCS(s1, n1-1, s2, n2, memo));
if (s1[n1-1] == s2[n2-1])
rez = max(rez, LCS(s1, n1-1, s2, n2-1, memo) + 1);
return memo[n1][n2] = rez;
}
int LCS(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> memo(n1+1);
for (int i = 0; i <= n1; i++)
memo[i].resize(n2 + 1, -1);
return LCS(s1, n1, s2, n2, memo);
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// najduzi zajednici podniz (longest common substring, LCS)
// prefiksa duzine n1 niske s1 i
// prefiksa duzine n2 niske s2
int LCS(const string& s1, int n1,
const string& s2, int n2,
vector<vector<int>>& memo) {
if (memo[n1][n2] != -1)
return memo[n1][n2];
if (n1 == 0 || n2 == 0)
return memo[n1][n2] = 0;
int rez = max(LCS(s1, n1, s2, n2-1, memo),
LCS(s1, n1-1, s2, n2, memo));
if (s1[n1-1] == s2[n2-1])
rez = max(rez, LCS(s1, n1-1, s2, n2-1, memo) + 1);
return memo[n1][n2] = rez;
}
int LCS(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> memo(n1+1);
for (int i = 0; i <= n1; i++)
memo[i].resize(n2 + 1, -1);
return LCS(s1, n1, s2, n2, memo);
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cout << LCS(s1, s2) << endl;
return 0;
}Problem prekalpajućih rekurzivnih poziva se može rešiti ako se upotrebi dinamičko programiranje naviše. Dužine najdužih podnizova prefiksa možemo čuvati u matrici. Element matrice na poziciji \((n_1, n_2)\) zavisi samo od elemenata na pozicijama \((n_1-1, n_2)\), \((n_1, n_2-1)\) i \((n_1-1, n_2-1)\), tako da matricu požemo da popunjavamo bilo vrstu po vrstu, bilo kolonu po kolonu.
Primer 8.A.1. Prikažimo matricu za primer dve niske xmjyauz i mzjawxu.
mzjawxu 01234567 --------- 0|00000000 x 1|00000011 m 2|01111111 j 3|01122222 y 4|01122222 a 5|01123333 u 6|01123334 z 7|01223334
// najduzi zajednici podniz (longest common substring, LCS)
int LCS(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> dp(n1+1);
for (int i = 0; i <= n1; i++)
dp[i].resize(n2 + 1);
for (int i = 0; i <= n1; i++)
dp[i][0] = 0;
for (int j = 0; j <= n2; j++)
dp[0][j] = 0;
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; j++) {
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
if (s1[i-1] == s2[j-1])
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
}
return dp[n1][n2];
}#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
// najduzi zajednici podniz (longest common substring, LCS)
int LCS(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<vector<int>> dp(n1+1);
for (int i = 0; i <= n1; i++)
dp[i].resize(n2 + 1);
for (int i = 0; i <= n1; i++)
dp[i][0] = 0;
for (int j = 0; j <= n2; j++)
dp[0][j] = 0;
for (int i = 1; i <= n1; i++)
for (int j = 1; j <= n2; j++) {
dp[i][j] = max(dp[i][j-1], dp[i-1][j]);
if (s1[i-1] == s2[j-1])
dp[i][j] = max(dp[i][j], dp[i-1][j-1] + 1);
}
return dp[n1][n2];
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cout << najduziZajednickiPodniz(s1, s2) << endl;
return 0;
}Možemo primetiti da se prilikom popunjavanja matrice vrstu po vrstu sadržaj svake naredne vrste popunjava samo na osnovu prethodne vrste. Stoga nije potrebno istovremeno pamtiti celu matricu, već je dovoljno pamtiti samo jednu, tekuću vrstu. Ažuriranje vrste moramo vršiti s leva nadesno, jer svaki element u tekućoj vrsti zavisi od elementa koji mu prethodi u toj vrsti. Primetimo da nam je u nekom trenutku potrebno da znamo prethodni element tekuće vrste, a ponekad prethodni element prethodne vrste, tako da prilikom ažuriranja vrste moramo da u pomoćnoj promenljivoj pamtimo staru vrednost prethodnog elementa vrsta (jer se ažuriranjem prethodnog elementa njegova stara vrednost gubi, a ona nam može zatrebati u slučaju da su odgovarajući karakteri u niskama jednaki).
// najduzi zajednici podniz (longest common substring, LCS)
int LCS(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> dp(n2 + 1, 0);
for (int i = 1; i <= n1; i++) {
int prethodni = dp[0];
for (int j = 1; j <= n2; j++) {
int tekuci = dp[j];
if (s1[i-1] == s2[j-1])
dp[j] = prethodni + 1;
else
dp[j] = max(dp[j-1], dp[j]);
prethodni = tekuci;
}
}
return dp[n2];
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// najduzi zajednici podniz (longest common substring, LCS)
int LCS(const string& s1, const string& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> dp(n2 + 1, 0);
for (int i = 1; i <= n1; i++) {
int prethodni = dp[0];
for (int j = 1; j <= n2; j++) {
int tekuci = dp[j];
if (s1[i-1] == s2[j-1])
dp[j] = prethodni + 1;
else
dp[j] = max(dp[j-1], dp[j]);
prethodni = tekuci;
}
}
return dp[n2];
}
int main() {
string s1, s2;
cin >> s1 >> s2;
cout << najduziZajednickiPodniz(s1, s2) << endl;
return 0;
}Ovaj zadatak je ponovljen u cilju ilustrovanja različitih tehnika rešavanja.
Prikazaćemo dva rešenja zasnovana na dinamičkom programiranju, koja su različite efikasnosti.
Postoji veoma jednostavno svođenje ovog problema na problem pronalaženja najdužeg zajedničkog podniza dva niza. Naime, dužina najdužeg rastućeg podniza datog niza jednaka je dužini najdužeg zajedničkog podniza tog niza i niza koji se dobija neopadajućim sortiranjem i uklanjanjem duplikata tog niza.
int najduziRastuciPodniz(const vector<int>& a) {
// sortirana kopija niza a
vector<int> b = a;
sort(begin(b), end(b));
// uklanjamo duplikate iz vektora b
b.erase(unique(begin(b), end(b)), end(b));
return najduziZajednickiPodniz(a, b);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int najduziZajednickiPodniz(const vector<int>& s1, const vector<int>& s2) {
int n1 = s1.size(), n2 = s2.size();
vector<int> dp(n2 + 1, 0);
for (int i = 1; i <= n1; i++) {
int prethodni = dp[0];
for (int j = 1; j <= n2; j++) {
int tekuci = dp[j];
if (s1[i-1] == s2[j-1]) {
dp[j] = prethodni + 1;
} else {
dp[j] = max(dp[j-1], dp[j]);
}
prethodni = tekuci;
}
}
return dp[n2];
}
int najduziRastuciPodniz(const vector<int>& a) {
// sortirana kopija niza a
vector<int> b = a;
sort(begin(b), end(b));
// uklanjamo duplikate iz vektora b
b.erase(unique(begin(b), end(b)), end(b));
return najduziZajednickiPodniz(a, b);
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << najduziRastuciPodniz(a) << endl;
return 0;
}Izmenom induktivno-rekurzivne konstrukcije možemo dobiti i mnogo efikasnije rešenje. Ključna ideja je da pretpostavimo da uz dužinu \(d_{max}\) najdužeg rastućeg podniza do sada obrađenog dela niza možemo za svaku dužinu podniza \(1 \leq d \leq d_{max}\) da odredimo najmanji element kojim se završava neki rastući podniz dužine \(d\).
Primer 8.A.2. Neka je, na primer, dat niz \(a = [3, 2, 6, 9, 5, 4, 3, 7, 2, 8]\). Tokom prolaska kroz elemente niza \(a\) održavaćemo niz \(DP\), u kome je na svakoj poziciji \(d-1\) \((d \geq 1)\) najmanji element niza \(a\), kojim se završava neki rastući podniz od \(a\), dužine \(d\).
Niz \(DP\) menja se na sledeći način:
1 2 3 4 5 6 7 8 9 10 - - - - - - - - - - 3 - - - - - - - - - 3 2 - - - - - - - - - 2 2 6 - - - - - - - - 6 2 6 9 - - - - - - - 9 2 5 9 - - - - - - - 5 2 4 9 - - - - - - - 4 2 3 9 - - - - - - - 3 2 3 7 - - - - - - - 7 2 3 7 - - - - - - - 2 2 3 7 8 - - - - - - 8
Razmislimo sada o postupku transformisanja niza \(DP\).
Ako se dosadašnji ukupno najduži podniz završavao elementom koji je manji od tekućeg, na kraj niza \(DP\) dopisujemo tekući element jer smo našli podniz koji je duži za jedan od prethodno najdužeg. Tekući element je jedini, pa time i najmanji kojim se završava rastući podniz nove dužine. To se u primeru dešava prilikom obrade elementa 3, elementa 6, elementa 9 i elementa 8.
Razmotrimo i situaciju u kojoj obrađujemo element 5. Do tada smo videli elemente 3, 2, 6 i 9. Element 2 na prvoj poziciji u tabeli označava da je najmanji element kojim se može završiti jednočlani rastući niz jednak 2. Element 6 na drugoj poziciji u tabeli označava da je najmanji element kojim se može završiti dvočlani rastući niz jednak 6 (u pitanju je niz 2 6 ili niz 3 6). Element 9 na trećoj poziciji u tabeli označava da je najmanji element kojim se može završiti tročlani rastući niz jednak 9 (u pitanju je niz 2 6 9 ili 3 6 9). Pošto je 5 manji od 9 nijedan od ovih tročlanih nizova nije moguće proširiti elementom 5, pa četvoročlanih rastućih nizova nema. Postavlja se pitanje da li se možda tročlani nizovi mogu završiti elementom 5, no ni to nije moguće. Naime, pošto je u tabeli dvočlanim nizovima pridružena vrednost 6, to znači da se svi dvočlani rastući nizovi završavaju bar sa 6, pa nije moguće 9 zameniti sa 5. Sa druge strane, pošto je 5 veće od 2, završni element dvočlanih nizova 6 je moguće zameniti sa 5 i time dobiti manju završnu vrednost dvočlanih nizova (to su u ovom slučaju nizovi 3 5 i 2 5). Dakle, u tabeli vrednost 6 treba zameniti vrednošću 5. Vrednost 2 levo od 6 nema smisla zameniti sa 5, jer bi se time završna vrednost jednočlanih nizova uvećala, a mi u tabeli pamtimo najmanje završne vrednosti.
Primetimo da niz \(DP\) u svakom trenutku mora da bude strogo rastući. Zaista, ako je \(a_i\) najmanji završetak strogo rastućeg niza dužine \(d\), onda se pretposlednjim elementom \(a_j\) tog rastućeg niza (koji je manji od \(a_i\)) završava jedan rastući niz dužine \(d-1\), a \(DP_{d-2} \leq a_j < a_i = DP_{d-1}\).
Na osnovu analize ovog primera možemo da zaključimo da je prilikom analize svakog tekućeg elementa potrebno pronaći prvu poziciju \(d\) u tabeli na kojoj se nalazi element koji je veći ili jednak od tekućeg i poziciju \(d\) umesto toga upisati tekući element. Ako su svi elementi manji od tekućeg (ako je \(d = d_{max}\)), onda se tekući element dodaje na kraj niza (i u tom slučaju zapravo radimo isto - upisujemo element na poziciju \(d\)). Ostali elementi u tabeli ostaju nepromenjeni. Zaista na svim pozicijama u tabeli levo od pozicije \(d\) upisani su elementi strogo manji od tekućeg i njihovom zamenom sa tekućim se ne bi smanjila vrednost završnog elemenata tih nizova. Za elemente desno od pozicije \(d\), iako su veći od tekućeg, ažuriranje nije moguće. U svim nizovima dužine \(d' > d\) neki prefiks se morao završavati elementom na poziciji \(d\) ili elementom većim od njega, a pošto je on bio veći ili jednak od tekućeg, zamenog poslednjeg elementa tekućim ne bismo dobili više rastući niz.
Ključni dobitak nastaje kada se primeti da, pošto su elementi u tabeli sortirani, poziciju prvog elementa koji je veći ili jednak od tekućeg možemo ostvariti binarnom pretragom. Otuda sledi efikasna implementacija (u nizu dp vrednost najmanjeg završnog elementa za nizove dužine \(d\) pamtimo na poziciji \(d-1\)).
Vremenska složenost takve implementacije je \(O(n \log{(n)})\), dok je memorijska složenost \(O(n)\).
Binarna pretraga može biti izvršena bibliotečkom funkcijom.
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduziRastuciPodniz(const vector<int>& a) {
int n = a.size();
vector<int> dp(n);
int max = 0;
for (int i = 0; i < n; i++) {
auto it = lower_bound(dp.begin(), next(dp.begin(), max),
a[i]);
*it = a[i];
int d = distance(dp.begin(), it);
if (d + 1 > max)
max = d + 1;
}
return max;
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// pronalazi duzinu najduzeg strogo rastuceg podniza niza a
int najduziRastuciPodniz(const vector<int>& a) {
int n = a.size();
vector<int> dp(n);
int max = 0;
for (int i = 0; i < n; i++) {
auto it = lower_bound(dp.begin(), next(dp.begin(), max),
a[i]);
*it = a[i];
int d = distance(dp.begin(), it);
if (d + 1 > max)
max = d + 1;
}
return max;
}
int main() {
ios_base::sync_with_stdio(false);
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++)
cin >> a[i];
cout << najduziRastuciPodniz(a) << endl;
return 0;
}Data je matrica koja sadrži pozitivne cele brojeve. Put može da krene sa bilo kog polja u prvoj vrsti matrice i da se završi na bilo kom polju u poslednjoj vrsti matrice, pri čemu u svakom koraku prelazi sa polja tekuće vrste na jedno od njemu tri susedna polja naredne vrste (naravno, polja na levoj i i desnoj ivici imaju dva, a ne tri susedna polja). Zbir puta je zbir vrednosti na svim poljima koja se nalaze na tom putu. Odrediti najmanji zbir puta u datoj matrici i bar jedan put koji ima taj zbir.
U narednoj matrici su istaknuta polja koja pripadaju putu najmanjeg zbira u toj matrici (najmanji zbir puta je 5).
3 8 2 .1 9 2 .1 7 2 3 4 .2 1 9 2 .1
Osnovna ideja optimalnog rešenja je da se za svako polje matrice odredi najmanji zbir puta koji polazi od tog polja. U narednoj tabeli su prikazane te vrednosti za svako polje matrice iz prethodnog primera. Primetimo da je najmanji zbir puta koji kreće iz gornjeg levog ugla 5 (to je ujedno i najmanji zbir nekog puta koji počinje na nekom od polja prve vrste).
8 12 6 5 12 5 4 10 3 4 6 3 1 9 2 1
Pretpostavimo da matrica \(A_{i,j}\) ima \(m\) vrsta i \(n\) kolona. Neka je \(f(i,j)\) funkcija koja određuje najmanji zbir puta koji počinje na polju \((i,j)\), za \(0 \leq i < m\), \(0 \leq j < n\). Sa polja u poslednjoj vrsti se put ne može dalje nastavljati, pa je:
\[f(m − 1,j) = A_{m-1,j}, \mathrm{za\ svako\ } 0 \leq j < n.\]
Razmotrimo sada polja u ostalim vrstama matrice. Za početak razmotrimo polja koja nisu u prvoj niti u poslednjoj koloni tj. polja sa koordinatama \((i,j)\) za \(0 \leq i < m - 1\), \(0 < j < n - 1\). Sa svakog takvog polja može da se pređe ili na polje dole-levo, ili dole ili dole-desno, tj. na polje sa koordinatama \((i + 1,j - 1)\), \((i + 1,j)\) ili \((i + 1,j + 1)\). Minimalni zbir puta se dobija kada se pređe na ono od ta tri polja sa kog se može postići minimalni zbir. Dakle, za svako \(0 \leq i < m - 1\), \(0 < j < n - 1\) je
\[f(i,j) = A_{i,j} + \min\{f(i + 1,j - 1), f(i + 1,j), f(i + 1,j + 1)\}.\]
Slično važi i za polja na levoj tj. desnoj ivici, jedino što se za njih umesto tri gledaju dva susedna polja.
\(f(i, 0) = A_{i,j} + \min\{f(i + 1,j), f(i + 1,j + 1)\}, \mathrm{za\ svako\ } 0 \leq i < m - 1.\) \(f(i, n − 1) = A_{i,j} + \min\{f(i + 1,j − 1), f(i + 1,j)\}, \mathrm{za\ svako\ } 0 \leq i < m - 1\).
Ovim je kompletirana rekurzivna definicija funkcije \(f\) koja omogućava njeno izračunavanje. Najjednostavniji način je da se funkcija u programskom jeziku implementira rekurzivno, direktno na osnovu prethodne definicije. U narednoj implementaciji u jeziku C++, matrica je implementirana korišćenjem kolekcije vector, koja je deo standardne biblioteke jezika C++.
int najmanjiZbirPuta(const vector<vector<int>>& A,
int i, int j) {
int m = A.size(), n = A[0].size();
if (i == m-1) return A[m-1][j];
int M = najmanjiZbirPuta(A, i+1, j);
if (j > 0)
M = min(M, najmanjiZbirPuta(A, i+1, j-1);
if (j < n-1)
M = min(M, najmanjiZbirPuta(A, i+1, j+1);
return A[i][j] + M;
}Prethodna implementacija je veoma neefikasna, usled ponovljenih identičnih rekurzivnih poziva (razmislite koliko puta se ponavljaju rekurzivni pozivi za iste vrednosti parametara \(i\) i \(j\)). Stoga je potrebno upotrebiti tehniku dinamičkog programiranja. Rezultate poziva funkcije, tj. vrednosti \(f(i,j)\) pamtimo u novoj matrici \(\mathit{DP}_{i,j}\) koju popunjavamo odozdo naviše. Pošto svaka vrsta zavisi samo od elemenata vrste ispod nje, mogli bismo da uštedimo memoriju i da umesto cele matrice \(\mathit{DP}\) pamtimo samo njenu tekuću vrstu. Međutim, videćemo da nam pamćenje cele matrice omogućava da pored najmanjeg zbira puta odredimo i polja na tom putu (reprezentovana vektorom koji sadrži samo indekse kolona). Na taj način se dobija naredna implementacija.
vector<int> najboljiPut(const vector<vector<int>>& A) {
int m = A.size(), n = A[0].size();
// za svako polje (i, j) određujemo zbir
// najmanjeg puta koji kreće sa tog polja
vector<vector<int>> dp(m, vector<int>(n));
// polja u poslednjoj vrsti
for (int j = 0; j < n; j++)
dp[m-1][j] = A[m-1][j];
// polja u ostalim vrstama
for (int i = m-2; i >= 0; i--) {
// prva kolona
dp[i][0] = A[i][0] + min(dp[i+1][0], dp[i+1][1]);
// unutrašnje kolone
for (int j = 1; j < n-1; j++)
dp[i][j] = A[i][j] +
min({dp[i+1][j-1], dp[i+1][j], dp[i+1][j+1]});
// poslednja kolona
dp[i][n-1] = A[i][n-1] + min(dp[i+1][n-2], dp[i+1][n-1]);
}
// rekonstruišemo put (za svaku vrstu se pamti indeks kolone)
vector<int> put(m);
// određujemo kolonu u kojoj se nalazi
// najmanja vrednost u prvoj vrsti
int pmin = 0;
for (int j = 0; j < n; j++)
if (dp[0][j] < dp[0][pmin])
pmin = j;
// put kreće od te kolone
put[0] = pmin;
// obrađujemo jednu po jednu vrstu, od druge do poslednje
for (int i = 1; i < m; i++) {
// određujemo kolonu u kojoj se nalazi
// naredno polje na putu
// pmin je pozicija minimuma (indeks kolone)
// za vrednosti dp[i][j-1], dp[i][j], dp[j+1]
int j = pmin;
pmin = j;
if (j > 0 && dp[i][j-1] < dp[i][pmin])
pmin = j-1;
if (j < n - 1 && dp[i][j+1] < dp[i][pmin])
pmin = j+1;
put[i] = pmin;
}
return put;
}Iako je ovo veoma tipičan problem za tehniku dinamičkog programiranja, studentima ponekad može delovati da su problemi ovog tipa veštački smišljeni samo za potrebe ispita i da nemaju neku realnu primenu. U nastavku ćemo pokazati da to nije slučaj, odnosno da se baš ovaj zadatak u neizmenjenom obliku direktno primenjuje u jednom naizgled veoma naprednom algoritmu veštačke inteligencije.
Na slici 22 levo je prikazana slika Salvadora Dalija “Upornost sećanja”, dok je na desnoj slici ta slika sužena primenom algoritma koji ćemo sada razmotriti. Primetimo da su sa slike uklonjene površine koje su na neki način najmanje važne (na primer, pod sa desne strane stola), dok su važni delovi slike (na primer, satovi) ostali nepromenjeni. Iako na prvi pogled deluje da je to postignuto nekim naprednim algoritmom prepoznavanja oblika, algoritam je prilično jednostavan i zasnovan je na algoritmu dinamičkog programiranja koji smo razmotrili u uvodu. Algoritam je poznat pod imenom “Rezbarenje šavova” (engl. seam carving).
Prvi korak algoritma podrazumeva da se izvrši detekcija ivica originalne slike. Na primeru Dalijeve slike, rezultat prepoznavanja ivica je prikazan na slici 23.
Algoritmi detekcije slike su dobro opisani u literaturi i lako se implementiraju. Pre detekcija ivica poželjno je da se slika prevede u crno-belo i da se malo zamuti. Jedan od najpoznatijih algoritama detekcije ivica je Soboljev detektor ivica (engl. Sobel edge detector). Horizontalne ivice se prepoznaju tako što se računa razlika između vrednosti susednih piksela (piksela koji su jedni pored drugih) – tamo gde je ta razlika velika, tu se nalazi ivica horizontalna ivica objekta (svakom pikselu se pridružuje broj između 0 i 1 koji opisuje “jačinu” horizontalne ivice). Slično se nalaze i vertikalne ivice, jedino što se razmatra razlika vrednosti piksela koji su jedni iznad drugih. Na kraju se horizontalne i vertikalne ivice objedinjavaju i jačina ivice za taj piksel se dobija izračunavanjem neke središnje vrednosti jačine vertikalne i jačine horizontalne ivice za taj piksel (to je najčešće koren iz zbira kvadrata). Kada se jačina ivice svakog piksela normalizuje na interval 0 i 255 (tako da se svakom pikselu dodeli tačno jedan bajt), dobija se crno-bela slika koja prikazuje ivice i koja je iznad prikazana.
U nastavku ćemo prikazati C++ kod koji koristi biblioteku OpenCV koji implementira pronalaženje ivica date slike. Biblioteka OpenCV je jedna od najpoznatijih biblioteka za obradu slika, otvorenog je koda, besplatna je i lako se preuzima i instalira. Slika se predstavlja tipom Mat. Prevođenje slike u drugi format (ovde u crno-belo) vrši se funkcijom cvtColor, zamućenje se postiže funkcijom blur, Soboljev detktor ivica je dostupan pomoću funkcije Sobel, funkcija magnitude objedinjuje dve matrice u jednu nalaženjem korena iz zbira kvadrata vrednosti polaznih matrica, dok se funkcijom normalize vrednosti piksela preslikavaju na dati raspon. Pokušajte da na internetu pronađete detaljne opise ovih funkcija.
Mat detect_edges(const Mat& img) {
// gradimo zamućenu crno-belu verziju originalne slike
Mat img_gray;
cvtColor(img, img_gray, COLOR_BGR2GRAY);
Mat img_blur;
blur(img_gray, img_blur, Size(5, 5));
// Soboljevim detektorom određujemo
// horizontalne i vertikalne ivice
Mat dx, dy;
Sobel(img_blur, dx, CV_64F, 1, 0, 3);
Sobel(img_blur, dy, CV_64F, 0, 1, 3);
// objedinjavamo horizontalne i vertikalne ivice i dobijamo
// matricu koja sadrži jačinu ivica originalne slike
Mat magn;
magnitude(dx, dy, magn);
// normalizujemo vrednosti ivica na vrednosti [0, 255]
Mat normalized_magn;
normalize(magn, normalized_magn, 0, 255,
NORM_MINMAX, CV_8UC1);
return normalized_magn;
}Nakon detekcije ivica treba da izvršimo sužavanje slike. To radimo iterativno, tako što u svakom koraku sliku sužavamo za jedan piksel, sve dok se ne dobije slika željene širine. Iz svake vrste, dakle, treba odabrati po jedan piksel koji će se izbaciti. Najjednostavnija varijanta je da se u svakom koraku izbacuje po jedna
kolona. Međutim, može se dobiti i kvalitetniji rezultat od toga. Dakle, pikseli koji se izbacuju ne moraju pripadati istoj koloni, ali ipak želimo da pikseli koji se izbacuju u susednim vrstama budu susedni tj. da čine neki put (kaže se šav) koji spaja gornju i donju ivicu slike. U suprotnom bi se dobile slike veoma neprirodnog izgleda i nezadovoljavajućeg kvaliteta. Od svih mogućih šavova treba izbaciti onaj koji što manje seče ivice. Naime, delovi slike koji imaju puno ivica su važni objekti na slici, dok su delovi slike bez ivica manje značajni i pikseli iz tih zona se mogu uklanjati sa manjim uticajem na izgled slike. Dakle, na slici (matrici) koja sadrži ivice originalne slike tražimo šav (put od prve do poslednje vrste) takav da je zbir vrednosti (jačine ivica) na tom putu minimalan. Međutim, to je upravo problem koji smo u uvodu ovog članka rešili dinamičkim programiranjem. Na slici 24 prikazan je jedan šav koji je detektovan pomoću tog algoritma i koji se uklanja sa slike.
Izbacivanjem jednog po jednog šava, dobija se sužena slika. Nakon detekcije ivica i šava koji se uklanja implementacija njegovog uklanjanja je veoma jednostavna (i prepuštamo je čitaocu za vežbu).
Algoritam je moguće dodatno prilagođavati. Umesto vertikalnog možemo napraviti i horizontalno sužavanje, a i kombinaciju horizontalnog i vertikalnog sužavanja. Dalje, na primer, korisnik može mišem da obeleži objekte koje je poželjno ukloniti sa slike i objekte koje ne bi trebalo uklanjati. Na osnovu te informacije modifikuje se matrica koja sadrži jačine ivica i algoritam se primenjuje na tako modifikovanu matricu. Iako se na ispitima iz programiranja često daju zadaci koji su specifični za ispite ili takmičarsko programiranje, tehnike koje se kroz te zadatke uvežbavaju primenjive su u rešavanju realnih programerskih zadataka. Prikazani algoritam rezbarenja šavova daje veoma kvalitetne rezultate, a u svojoj osnovi je direktno zasnovan na algoritmu pronalaženja puta u matrici čiji je zbir minimalan, koji je jedan od tipičnih zadataka koji se zadaju na takmičenjima iz programiranja i na ispitima iz programiranja na fakultetima. Ako se u programiranju koriste i gotove biblioteke (poput biblioteke OpenCV), sa malo relativno jednostavnog programskog koda moguće je dobiti veoma lepe rezultate.