U nastavku ćemo razmatrati probleme sledećeg tipa:
Ispitati da li postoji neki kombinatorni objekat (često predstavljen torkom brojeva) koji zadovoljava neke date uslove ili, alternativno, prebrojati ili nabrojati sve takve objekte. Ovakvi problemi se nazivaju problemi zadovoljavanja ograničenja (engl. constraint satisfaction problems, CSP). Na primer, potrebno je proveriti da li postoji neki podskup datog skupa brojeva čiji je zbir jednak datoj vrednosti.
Među svim kombinatornim objektima koji zadovoljavaju neke date uslove naći najbolji tj. naći onaj objekat na kome je vrednost neke date funkcije minimalna ili maksimalna. Ovakvi problemi se nazivaju problemi optimizacije uz ograničenja (engl. constraint optimization problems, COP). Ovi problemi se nazivaju i problemi kombinatorne optimizacije.
Ovakvi problemi se često rešavaju raznim varijantama algoritama pretrage u kojima se nabrajaju i proveravaju neki kandidati za rešenja.
Algoritmi grube sile podrazumevaju da se u pretrazi iscrpno nabroje svi kandidati za rešenje i da se za svakog od njih proveri da li zadovoljava uslov (ako je potrebno pronaći bilo koji element koji zadovoljava dati uslov) ili da li je optimalan (ako je potrebno pronaći element koji minimalizuje ili maksimalizuje datu ciljnu funkciju). Svi kandidati se ponekada mogu nabrojati jednostavno, ugnežđenim petljama, dok je nekada potrebno koristiti neki složeniji postupak za nabrajanje određene familije kombinatornih objekata (kombinacija, permutacija, varijacija, podskupova, particija itd. ali i drugih, specifičnih familija kombinatornih objekata).
Algoritmi pretrage sa povratkom tj. bektreking (engl. backtracking) poboljšavaju tehniku grube sile tako što vrše provere i tokom generisanja kandidata za rešenja i tako što se odbacuju parcijalno popunjeni kandidati, za koje se može unapred utvrditi da se ne mogu proširiti do ispravnog tj. optimalnog rešenja. Dakle, bektreking podrazumeva da se tokom obilaska u dubinu drveta kojim se predstavlja prostor potencijalnih rešenja odsecaju oni delovi drveta za koje se unapred može utvrditi da ne sadrže ni jedno rešenje problema tj. da ne sadrže optimalno rešenje, pri čemu se odsecanje vrši i u čvorovima bliskim korenu koji mogu da sadrže i samo parcijalno popunjene kandidate za rešenja. Dakle, umesto da se čeka da se tokom pretrage stigne do lista (ili eventualno unutrašnjeg čvora koji predstavlja nekog kandidata za rešenje) i da se provera zadovoljenosti uslova ili optimalnosti vrši tek tada, prilikom pretrage sa povratkom provera se vrši u svakom koraku i vrši se provera parcijalno popunjenih rešenja (obično su to neke parcijalno popunjene torke brojeva).
Na primer, ako se proverava da li postoji podskup nekog skupa pozitivnih brojeva, čiji je zbir elemenata jednak datom broju i ako se ustanovi da nekoliko odabranih elementa polaznog skupa imaju zbir veći od tog broja, taj deo prostora pretrage se odmah može odseći i nema potrebe generisati sve podskupove u kojima su ti elementi uključeni (jer unapred znamo da nijedan od njih neće predstavljati zadovoljavajuće rešenje).
Efikasnost algoritama zasnovanog na ovom obliku pretrage uveliko zavisi od kvaliteta kriterijuma na osnovu kojih se vrši odsecanje. Iako obično složenost najgoreg slučaja ostaje eksponencijalna (kakva je po pravilu kod algoritama grube sile tj. iscrpne pretrage), pažljivo odabrani kriterijumi odsecanja mogu odseći jako velike delove pretrage (koji su često takođe eksponencijalne veličine u odnosu na dimenzije ulaznog problema) i time značajno ubrzati proces pretrage.
Naglasimo i da neki autori ne prave eksplicitnu razliku između algoritama grube sile (iscrpne pretrage) i algoritama pretrage sa povratkom i da u algoritme tipa pretrage sa povratkom ubrajaju sve algoritme u kojima se drvo koje sadrži sva potencijalna rešenja obilazi u dubinu.
Formulišimo opštu shemu rekurzivne implentacije pretrage sa povratkom. Pretpostavljamo, jednostavnosti radi, da su parametri procedure pretrage trenutni niz v (u kome se smeštaju torke brojeva koji predstavljaju kandidate za rešenja) i dužina trenutno popunjenog dela niza k, pri čemu je niz alociran tako da se u njega može smestiti i najduže rešenje. Takođe, pretpostavljamo da na raspolaganju imamo funkciju odsecanje koja proverava da li je trenutna torka smeštena u niz (na prvih k pozicija) kandidat da bude rešenje ili deo nekog rešenja. Pretpostavljamo i da znamo da li trenutna torka predstavlja rešenje (to utvrđujemo funkcijom jesteResenje — u realnim situacijama se taj uslov često svede ili na to da je uvek tačan, što se dešava kada je svaki čvor drveta potencijalni kandidat za rešenje ili na to da je tačan samo u listovima, što se detektuje tako što se proveri da je k dostiglo dužinu niza v). Na kraju, pretpostavljamo i da za svaku torku dužine k možemo eksplicitno odrediti sve kandidate za vrednost na poziciji k (pozivom funkcije kandidati(v, k)). Rekurzivnu pretragu tada možemo realizovati narednim (pseudo)kodom.
void pretraga(const vector<int>& v, int k) {
if (odsecanje(v, k))
return;
if (jesteResenje(v, k))
ispisi(v, k);
for (int x : kandidati(v, k)) {
v[k] = x;
pretraga(v, k+1);
}
}Alternativno, provere umesto na ulazu u funkciju možemo vršiti pre rekurzivnih poziva (čime se malo štedi na broju rekurzivnih poziva, ali se ponekad implementacija može malo zakomplikovati).
void pretraga(vector<int>& v, int k) {
if (jesteResenje(v, k))
ispisi(v, k);
for (int x : kandidati(v, k)) {
v[k] = x;
if (!odsecanje(v, k+1)) {
pretraga(v, k+1);
}
}
}Rekurzije je moguće osloboditi se uz korišćenje steka.
U svim čvorovima koji predstavljaju kandidate za rešenje (to su obično potpuno popunjene torki brojeva) potrebno je potpuno precizno ispitati da li je tekući kandidat ispravno tj. optimalno rešenje. To znači da u prethodnom kodu funkcija jesteResenje mora potpuno precizno da detektuje da li trentuna torka jeste ili nije ispravno tj. optimalno rešenje (niti sme ispravno rešenje da proglasi neispravnim, jer će se tada ono propustiti, niti sme neispravno rešenje da proglasi ispravnim, jer će se tada ono greškom pojaviti u spisku rešenja). Sa druge strane, u čvorovima u kojima se proveravaju parcijalno popunjena rešenja, provera kriterijuma odsecanja ne mora biti potpuno precizna — sa jedne strane dopušteno je da se ne odseku delovi drveta u kojima nema rešenja (time algoritam ostaje korektan, ali je neefikasniji), međutim, ako se odsecanje izvrši moramo biti apsolutno sigurni da se u odsečenom delu drveta ne nalazi nijedno ispravno rešenje tj. da se ne nalazi se optimalno rešenje. U prethodnom kodu to znači da kada funkcija odsecanje vrati vrednost tačno, moramo biti apsolutno sigurni da se trenutna torka smeštena na prvih k pozicija u nizu v ne može nikako dopuniti do ispravnog tj. optimalnog rešenja (jer bismo u suprotnom propustili neka rešenja). Sa druge strane, ta funkcija može da vrati vrednost netačno praktično bilo kada i time neće biti narušena korektnost (ali se narušava efikasnost). U praksi se ponekad dešava da je veoma komplikovano napraviti funkciju odsecanje koja potpuno precizno određuje da li se torka može produžiti do traženog rešenja problema tako da se zadovoljavamo kriterijumima odsecanja koji se mogu relativno jednostavno proveriti, a garantuju korektnost.
Dodatno ubrzavanje algoritma može da se napravi ako se na neki način može definisati funkcija koja ponekad može da pogodi vrednost x koju treba upisati na poziciju k, bez isprobavanja različitih kandidata. Na primer, ako se prilikom popunjavanja magičnog kvadrata (kvadrata u kom su brojevi raspoređeni tako da sve vrste, sve kolone i obe dijagonale imaju isti, unapred poznat, zbir) u nekoj vrsti popune svi elementi osim jednog, lako možemo da izračunamo koja vrednost mora da bude upisana na tom preostalom mestu. Takve korake zovemo koraci zaključivanja (engl. inferrence). Ni u ovom slučaju nije potrebna potpuna preciznost. Samo je bitno obezbediti da kada se zaključivanjem predloži neka konkretna vrednost, da je ostale mogućnosti bezbedno odseći, jer se među njima ne krije nijedno ispravno rešenje. Sa druge strane, ako je zaključivanje previše komplikovano ostvariti u nekom koraku pretrage, ono se može preskočiti (algoritam je korektan i bez ikakvog oblika zaključivanja).
Prethodne funkcije ispisuju sva rešenja problema tj. sve torke koje zadovoljavaju date uslove. Pretragu je moguće prekinuti i nakon pronalaska prvog rešenja (tada funkcija obično vraća podatak o tome da li jeste ili nije pronašla rešenje u delu drveta koji pretražuje).
bool pretraga(const vector<int>& v, int k) {
if (odsecanje(v, k))
return false;
if (jesteResenje(v, k)) {
ispisi(v, k);
return true;
}
for (int x : kandidati(v, k)) {
v[k] = x;
if (pretraga(v, k+1))
return true;
}
return false;
}Kod rešavanja optimizacionih problema, odsecanje može da nastupi i kada se proceni da u delu drveta koje se trenutno pretražuje ne postoji rešenje koje je bolje od najboljeg trenutno pronađenog rešenja. Dakle, rešenja pronađena u dosadašnjem delu pretrage se koriste da bi se odredile granice na osnovu kojih se vrši odsecanje u drugim delovima pretrage. Ovakav oblik optimizacije naziva se ponekad grananje sa ograničavanjem (engl. branch and bound).
Ilustrujmo pristup grube sile, a zatim i pretrage sa povratkom na jednom klasičnom problemu, problemu osam dama, u kojem se zahteva da se osam dama (kraljica) rasporedi na šahovskoj tabli tako da nijedna ne napada neku drugu (dame se napadaju horizontalno, vertikalno i dijagonalno, kako je prikazano na slici 20, levo). Na slici 20, desno, prikazano je jedno od 92 rešenja koliko ih problem ima. Problemom se (bez upotrebe računara) bavio još znameniti matematičar Gaus, a uz primenu računara do rešenja se dolazi prilično jednostavno.
Prvo pitanje koje se postavlja je kako reprezentovati problem. Jedna mogućnost je da se položaj dama predstavi matricom dimenzija \(8 \times 8\) koja sadrži istinitosne vrednosti (recimo \(0\) na onim poljima na kojima nije dama i \(1\) na onim poljima na kojima jeste dama). Međutim, može se zaključiti da se u svakoj vrsti table mora naći tačno jedna dama, pa se svako rešenje može jednostavno predstaviti nizom brojeva (od 1 do 8, ili od 0 do 7) koji predstavljaju redne brojeve kolona u kojima se nalaze dame (po jedan broj za svaku vrstu, redom). Na primer, raspored na slici 20 može se predstaviti nizom \(0, 6, 4, 7, 1, 3, 5, 2\). Dakle, svaki potencijani raspored dama predstavlja jednu varijaciju dužine osam niza brojeva od \(0\) do \(7\).
Provera da li se dame na poljima \((k_1, v_1)\) i \((k_2, v_2)\) napadaju može se izvršiti primenom aritmetičkih operacija. Naime, dve dame su u istoj koloni ako i samo ako je \(k_1 = k_2\), a u istoj su vrsti ako i samo ako je \(v_1 = v_2\). Dve dame se napadaju dijagonalno ako i samo ako je jednakokrak trougao čija su temena polja dve dame i polje koje se dobije projektovanjem polja jedne dame na vrstu u kojoj se nalazi druga dama. Dužine kateta tog jednakokrakog trougla određene su apsolutnim vrednostima razlike između rednih brojeva vrsta i između rednih brojeva kolona polja na kojih se dame nalaze. Dakle, provera da li se dve dame napadaju može se izvršiti pozivanjem naredne tri funkcije.
int ista_vrsta(int v1, int k1, int v2, int k2) {
return v1 == v2;
}
int ista_kolona(int v1, int k1, int v2, int k2) {
return k1 == k2;
}
int ista_dijagonala(int v1, int k1, int v2, int k2) {
return abs(v2 - v1) == abs(k2 - k1);
}Provera da li niz kolona u kojima se dame nalaze predstavlja rešenje može se izvršiti na sledeći način (vrednost |8| zamenjena je simboličkim imenom DIM, pa se program može lako modifikovati da radi i za druge dimenzije table):
const int DIM = 8;
// ...
int jeste_resenje(int kolone_dama[]) {
int v1, v2;
for (v1 = 0; v1 < DIM; v1++)
for (v2 = v1+1; v2 < DIM; v2++)
if (ista_vrsta(v1, kolone_dama[v1],
v2, kolone_dama[v2]) ||
ista_kolona(v1, kolone_dama[v1],
v2, kolone_dama[v2]) ||
ista_dijagonala(v1, kolone_dama[v1],
v2, kolone_dama[v2]))
return 0;
return 1;
}Kako je izabranom reprezentacijom osigurano da nema dve dame u istoj vrsti, nema potrebe pozivati funkciju ista_vrsta. Pozivi preostale dve funkcije mogu se zameniti njihovim (kratkim) telima, pa se kôd može malo uprostiti.
int jeste_resenje(int kolone_dama[]) {
for (int v1 = 0; v1 < DIM; v1++)
for (int v2 = v1+1; v2 < DIM; v2++)
if (kolone_dama[v1] == kolone_dama[v2] ||
abs(v1-v2) == abs(kolone_dama[v1]-kolone_dama[v2]))
return 0;
return 1;
}Ostaje pitanje kako nabrojati sve moguće nizove koji reprezentuju položaj dama. Jedno, prilično naivno rešenje je da se za to upotrebi 8 ugnežđenih petlji (za svaku vrstu po jedna). Umesto toga može se upotrebiti sledeće rekurzivno rešenje.
void ispisi(int kolone_dama[]) {
static int rbr; // redni broj resenja
cout << rbr++ << ": ";
for (int j = 0; j < DIM; j++)
cout << kolone_dama[j];
cout << endl;
}
void dame(int kolone_dama[], int broj_postavljenih_dama) {
if (broj_postavljenih_dama == DIM) {
if (jeste_resenje(kolone_dama))
ispisi(kolone_dama);
} else {
for (int j = 0; j < DIM; j++) {
kolone_dama[broj_postavljenih_dama] = j;
dame(kolone_dama, broj_postavljenih_dama + 1);
}
}
}Primetimo da navedena funkcija generiše sve varijacije sa ponavljanjem dužine DIM nad DIM elemenata, slično kao što je opisano u delu 6. Tih varijacija ima \(8^8 = 16777216\). Iako navedeni kôd ispravno radi, može se značajno unaprediti. Pošto se ni u jednoj koloni ne mogu nalaziti dve dame, potrebno je da su svi brojevi različiti. Dakle, svaki potencijani raspored dama predstavlja jednu moguću permutaciju niza brojeva od \(0\) do \(7\) (s druge strane, ne zadovoljava svaka permutacija uslov da se nikoje dve dame ne napadaju). Imajući to u vidu, malko unapređen pristup grubom silom koristio bi generisanje svih permutacija (njih \(8! = 40320\)) i za svaku od njih proveru da li zadovoljaju uslov o nenapadanju dama, tj. da li predstavlja ispravno rešenje.
I generisanje permutacija može se implementirati rekurzivno (kao što je opisano u delu 6).
int jeste_resenje(int kolone_dama[]) {
for (int v1 = 0; v1 < DIM; v1++)
for (int v2 = v1+1; v2 < DIM; v2++)
if (abs(v1-v2) == abs(kolone_dama[v1]-kolone_dama[v2]))
return 0;
return 1;
}
void dame(int kolone_dama[], int popunjena_kolona[],
int broj_postavljenih_dama) {
if (broj_postavljenih_dama == DIM) {
if (jeste_resenje(kolone_dama))
ispisi(kolone_dama);
} else {
for (int j = 0; j < DIM; j++) {
if (!popunjena_kolona[j]) {
kolone_dama[broj_postavljenih_dama] = j;
popunjena_kolona[j] = 1;
dame(kolone_dama, popunjena_kolona,
broj_postavljenih_dama + 1);
popunjena_kolona[j] = 0;
}
}
}
}Uz navedeni kôd, pozivom naredne funkcije :
int main() {
int kolone_dama[DIM], popunjena_kolona[DIM];
for (int j = 0; j < DIM; j++)
popunjena_kolona[j] = 0;
dame(kolone_dama, popunjena_kolona, 0);
}dobija se 92 rešenja problema:
0: 04752613 1: 05726314 2: 06357142 ... 91: 73025164
U unapređivanju navedenog algoritma, može se otići još jedan korak dalje. Naime, često se do efikasnije pretrage dolazi ako se odsecanje vrši što ranije. Primetimo da se u prethodnom rešenju provera dijagonala vrši tek na kraju, kada su sve dame postavljene. Mnogo je, međutim, bolje odsecanje vršiti čim se na tablu postavi nova dama koja se napada sa nekom od postojećih dama. Tako se osigurava da će u svakom koraku pretrage dame na tabli zadovoljavati dati uslov nenapadanja i stoga više nije potrebno vršiti nikakve provere na samom kraju, onda kada su sve dame postavljene.
int dama_se_moze_postaviti(int kolone_dama[],
int broj_postavljenih_dama,
int v, int k) {
for (int v1 = 0; v1 < broj_postavljenih_dama; v1++)
if (ista_dijagonala(v1, kolone_dama[v1], v, k))
return 0;
return 1;
}
void dame(int kolone_dama[], int popunjena_kolona[],
int broj_postavljenih_dama)
{
if (broj_postavljenih_dama == DIM)
ispisi(kolone_dama);
else {
for (int j = 0; j < DIM; j++) {
if (!popunjena_kolona[j] &&
dama_se_moze_postaviti(kolone_dama,
broj_postavljenih_dama,
broj_postavljenih_dama, j)) {
kolone_dama[broj_postavljenih_dama] = j;
popunjena_kolona[j] = 1;
dame(kolone_dama, popunjena_kolona,
broj_postavljenih_dama + 1);
popunjena_kolona[j] = 0;
}
}
}
}Pronalaženje dobrih kriterijuma za odsecanje pretrage u najvećoj meri utiče na ukupnu efikasnost pretrage sa povratkom. Ilustrujmo ovo kroz jedan primer.
Napisati program koji određuje koliko podnizova (ne obavezno uzastopnih elemenata) datog niza pozitivnih brojeva ima zbir jednak datom broju.
Sa standardnog ulaza se učitava broj \(1 \leq n \leq 30\), a zatim u narednom redu \(n\) pozitivnih realnih brojeva (zaokruženih na dve decimale), razdvojenih razmacima.
Na standardni izlaz ispisati traženi broj podnizova (dva realna broja se mogu smatrati jednakima ako se razlikuju za manje od \(10^{-5}\)).
4 3.2 5.7 9.4 6.9 12.6
2
Važi da je \(3,2+9,4 = 5,7+6,9 = 12,6\).
Jedna mogućnost je da se zadatak reši grubom silom, tj. da se nabroje svi podnizovi i da se za svaki od njih proveri da li mu je zbir jednak traženom. Nabrajanje podnizova se može postići bilo pomoću funkcije koja određuje naredni podniz u leksikografskom redosledu, bilo pomoću rekurzivnog najbrajanja svih mogućnosti. Jedna mogućnost rekurzivne implementacije je zasnovana na tome da svaki neprazni niz razložimo na njegov prefiks bez poslednjeg elementa i na poslednji element i da nezavisno razmatramo mogućnosti kada poslednji element jeste i kada nije uključen u podniz. Čuvaćemo trenutno odabrani podniz obrađenog dela niza na pozicijama \([n, n_0)\), gde je \(n_0\) dužina celog niza, a \(n\) parametar koji se smanjuje tokom rekurzije. Zadatak rekurzivne funkcije je da na sve moguće načine dopuni taj podniz elementima sa pozicija \([0, n)\) iz polaznog niza i da vrati broj tako napravljenih podnizova koji imaju dati zbir. U startu je \(n=n_0\), a podniz je prazan (to je zaista jedini mogući podniz dela niza na pozicijama \([n_0, n_0)\)).
Ako je \(n=0\), ceo niz je obrađen i podniz ne može više da se dopunjava (jer je skup elemenata na pozicijama \([0, n) = [0, 0)\) prazan). Izračunava se njegov zbir i ako je on jednak ciljnom zbiru, tada funkcija vraća 1 (pronađen je jedan traženi niz koji proširuje trenutni podniz elementima praznog skupa i ima zbir jednak ciljanom), a u suprotnom vraća 0 (ne postoji ni jedan niz koji proširuje trenutni podniz elementima praznog skupa i ima zbir jednak ciljanom).
Ako je \(n\) pozitivno, razmatramo posebno mogućnosti da poslednji element prefiksa \([0, n)\) tj. da element \(\mathit{niz}_{n-1}\) bude ili da ne bude uključen u podniz. U oba slučaja rekurzivno pozivamo funkciju za skraćeni prefiks (tj. za vrednost \(n-1\)).
Da bismo izbegli realokacije, podniz možemo unapred alocirati na dužinu \(n_0\), ali tada parametar funkcije treba da bude i broj elemenata podniza \(p\).
Drvo rekurzivnih poziva koje nastaje prilikom traženja svih podnizova niza \([4, 3, 2, 1]\), čiji je zbir \(5\) je prikazano na narednoj slici (jednostavnosti ilustracije radi, pretpostavili smo da su brojevi u nizu i ciljni zbir celi).
const double EPS = 0.00001;
// funkcija izracunava broj nacina da se dati podniz duzine p
// prosiri elementima niza sa pozicija [0, n) tako da se
// dobije podniz ciji je zbir jednak datom ciljnom zbiru
int brojPodnizovaDatogZbira(const vector<double>& niz, int n,
double ciljniZbir,
vector<double>& podniz, int p) {
// u nizu nema preostalih elemenata, pa je trenutni podniz
// jedini kandidat
if (n == 0) {
// racunamo zbir elemenata trenutnog podniza
double zbirPodniza = 0.0;
for (int i = 0; i < p; i++)
zbirPodniza += podniz[i];
// proveravamo da li je jednak ciljnom zbiru
if (abs(zbirPodniza - ciljniZbir) < EPS)
return 1;
else
return 0;
} else {
// broj podnizova bez ukljucenog poslednjeg elementa niza
int broj = 0;
broj += brojPodnizovaDatogZbira(niz, n-1, ciljniZbir,
podniz, p);
// broj podnizova sa ukljucenim poslednjim elementom niza
podniz[p] = niz[n-1];
broj += brojPodnizovaDatogZbira(niz, n-1, ciljniZbir,
podniz, p+1);
return broj;
}
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
vector<double> podniz(n);
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, n, ciljniZbir,
podniz, 0);
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
const double EPS = 0.00001;
// funkcija izracunava broj nacina da se dati podniz duzine p
// prosiri elementima niza sa pozicija [0, n) tako da se
// dobije podniz ciji je zbir jednak datom ciljnom zbiru
int brojPodnizovaDatogZbira(const vector<double>& niz, int n,
double ciljniZbir,
vector<double>& podniz, int p) {
// u nizu nema preostalih elemenata, pa je trenutni podniz
// jedini kandidat
if (n == 0) {
// racunamo zbir elemenata trenutnog podniza
double zbirPodniza = 0.0;
for (int i = 0; i < p; i++)
zbirPodniza += podniz[i];
// proveravamo da li je jednak ciljnom zbiru
if (abs(zbirPodniza - ciljniZbir) < EPS)
return 1;
else
return 0;
} else {
// broj podnizova bez ukljucenog poslednjeg elementa niza
int broj = 0;
broj += brojPodnizovaDatogZbira(niz, n-1, ciljniZbir,
podniz, p);
// broj podnizova sa ukljucenim poslednjim elementom niza
podniz[p] = niz[n-1];
broj += brojPodnizovaDatogZbira(niz, n-1, ciljniZbir,
podniz, p+1);
return broj;
}
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
vector<double> podniz(n);
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, n, ciljniZbir,
podniz, 0);
}
int main() {
// ucitavamo niz
int n;
cin >> n;
vector<double> niz(n);
for (int i = 0; i < n; i++)
cin >> niz[i];
// ciljni zbir podniza
double ciljniZbir;
cin >> ciljniZbir;
// izracunavamo i ispisujemo trazeni broj podnizova
cout << brojPodnizovaDatogZbira(niz, ciljniZbir) << endl;
return 0;
}Druga mogućnost implementacije pretrage grubom silom je da kao parametar rekurzivne funkcije prosleđujemo trenutni ciljni zbir tj. razliku između traženog zbira i zbira elemenata trenutno uključenih u podniz obrađenog dela niza. Sam taj podniz nije neophodno održavati. Drugim rečima, zadatak rekurzivne funkcije je da vrati koliko podnizova trenutno neobrađenog dela niza ima zbir jednak datom ciljnom zbiru, pri čemu se taj ciljni zbir sada smanjuje kroz rekurzivne pozive (kada god se uključi neki novi element).
Ilustracije radi, recimo da rekurzivna konstrukcija može biti takva da neprazne nizove razlaže na njihov prvi element i sufiks niza iza tog prvog elementa. To znači da će trenutno obrađeni deo niza biti na pozicijama \([0, k)\), dok će neobrađeni deo niza biti na pozicijama \([k, n)\) gde je \(k\) trenutni parametar rekurzije, a \(n\) dužina celog niza. Rekurzija počinje kada je \(k=0\), a završava se kada je \(k=n\).
Ako je ciljni zbir jednak nuli, to znači da je zbir trenutnog podniza elemenata na pozicijama \([0, k)\) jednak polaznom traženom zbiru i da smo našli jedan zadovoljavajući podniz. Dodatno, pošto su svi elementi niza pozitivni, podniz se ne može nikako proširiti dodatnim elementima tako da zbir i dalje ostane jednak ciljnom, tako da nije potrebno dalje nastavljati pretragu. Drugim rečima, jedino prazan niz elemenata sa pozicija \([k, n)\) može imati zbir \(0\), pa funkcija može da vrati rezultat 1 (ona vraća broj nizova).
Ako je ciljni zbir različit od nule, nastavljamo kao i ranije.
Ako je \(k=n\), tada u polaznom nizu nema neobrađenih elemenata tj. preostali niz čije podskupove razmatramo je prazan i on ne može sadržati podskup čiji će ciljni zbir biti pozitivan.
Ako je \(k < n\), tada razmatramo mogućnost da se element \(\mathit{niz}_k\) uključi i mogućnost da se ne uključi u podniz polaznog niza. U prvom slučaju umanjujemo ciljni zbir za vrednost tog elementa (to znači da tražimo broj podnizova elemenata sa pozicija \([k+1, n)\) koji daju taj umanjeni zbir), a u drugom ciljni zbir ostaje nepromenjen.
Na slici je prikazano drvo rekurzivnih poziva kada se određuje broj podnizova niza \([1, 2, 3, 4]\) čiji je zbir jednak \(5\).
// funkcija odredjuje broj podnizova niza odredjenog
// elementima na pozicijama [k, n) takvih da je zbir elemenata
// podniza jednak ciljnom zbiru
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir, int k) {
// jedino prazan niz ima zbir nula
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// posebno brojimo podnizove koji ukljucuju niz[k] i one
// koji ne ukljucuju niz[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir-niz[k], k+1) +
brojPodnizovaDatogZbira(niz, ciljniZbir, k+1);
}
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir) {
// brojimo podnizove niza odredjenog elementima na
// pozicijama [0, n)
return brojPodnizovaDatogZbira(niz, ciljniZbir, 0);
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 0.00001;
// funkcija odredjuje broj podnizova niza odredjenog
// elementima na pozicijama [k, n) takvih da je zbir elemenata
// podniza jednak ciljnom zbiru
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir, int k) {
// jedino prazan niz ima zbir nula
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// posebno brojimo podnizove koji ukljucuju niz[k] i one
// koji ne ukljucuju niz[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir-niz[k], k+1) +
brojPodnizovaDatogZbira(niz, ciljniZbir, k+1);
}
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir) {
// brojimo podnizove niza odredjenog elementima na
// pozicijama [0, n)
return brojPodnizovaDatogZbira(niz, ciljniZbir, 0);
}
int main() {
// ucitavamo niz
int n;
cin >> n;
vector<double> niz(n);
for (int i = 0; i < n; i++)
cin >> niz[i];
// ucitavamo ciljni zbir
double ciljniZbir;
cin >> ciljniZbir;
// izracunavamo i ispisujemo trazeni broj podnizova
cout << brojPodnizovaDatogZbira(niz, ciljniZbir) << endl;
return 0;
}Efikasnija rešenja od rešenja grubom silom se mogu dobiti primenom različitih odsecanja. Jedno važno odsecanje se može sprovesti na osnovu poznavanja intervala u kome mogu ležati zbirovi svih podnizova preostalih elemenata niza. Pošto su svi elementi pozitivni, najmanja moguća vrednost zbira podniza je nula (u slučaju praznog niza), dok je najveća moguća vrednost zbira podniza jednaka zbiru svih elemenata niza. Dakle, ako je ciljni zbir strogo manji od nule ili strogo veći od zbira svih elemenata preostalog dela niza, tada ne postoji ni jedan podniz čiji je zbir jednak ciljnom i moguće je izvršiti odsecanje pretrage. Umesto da zbir svih elemenata preostalog dela niza (dela niza na pozicijama \([k, n)\)) računamo iznova u svakom rekurzivnom pozivu, možemo primetiti da se u svakom narednom rekurzivnom pozivu niz samo može smanjiti za jedan element, pa se zbir može računati inkrementalno, umanjivanjem tokom rekurzije zbira polaznog niza za elemente uklonjene iz niza.
Na slici je prikazano drvo rekurzivnih poziva sa ovim odsecanjima kada se u nizu \([1, 2, 3, 4]\) traže podnizovi čiji je zbir jednak \(5\). Primetimo da je jedno odsecanje izvršeno kada je ciljni zbir bio jednak \(5\) i kada je u neobrađenom delu niza ostala samo vrednost \(4\), jer je zbir svih preostalih vrednosti bio manji od ciljnog zbira, a da je drugo odsecanje nastalo jer je nakon uključivanja vrednosti \([1, 2, 3]\) zbir već pretekao vrednost \(5\) (dobijen je čvor čija je nova ciljna vrednost \(-1\)).
// racuna se broj podnizova elemenata niza na pozicijama [k,
// n) koji imaju dati zbir, pri cemu se zna da je zbir tih
// elemenata jednak zbirPreostalih
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir,
double zbirPreostalih, int k) {
// ciljni zbir 0 se dobija samo ako se ne uzme ni jedan
// element
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// posto su svi brojevi pozitivni, nije moguce dobiti
// negativan ciljni zbir
if (ciljniZbir + EPS < 0)
return 0;
// cak ni uzimanje svih elemenata ne moze dovesti do ciljnog
// zbira, pa nema podnizova koji bi dali ciljni zbir
if (zbirPreostalih + EPS < ciljniZbir)
return 0;
// broj podnizova u kojima ucestvuje element a[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir - niz[k],
zbirPreostalih - niz[k], k+1) +
// broj podnizova u kojima ne ucestvuje element a[k]
brojPodnizovaDatogZbira(niz, ciljniZbir,
zbirPreostalih - niz[k], k+1);
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
// izracunavamo zbir elemenata niza
double zbirNiza = 0;
for (int i = 0; i < n; i++)
zbirNiza += niz[i];
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, ciljniZbir, zbirNiza, 0);
}#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const double EPS = 0.00001;
// racuna se broj podnizova elemenata niza na pozicijama [k,
// n) koji imaju dati zbir, pri cemu se zna da je zbir tih
// elemenata jednak zbirPreostalih
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir,
double zbirPreostalih, int k) {
// ciljni zbir 0 se dobija samo ako se ne uzme ni jedan
// element
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// posto su svi brojevi pozitivni, nije moguce dobiti
// negativan ciljni zbir
if (ciljniZbir + EPS < 0)
return 0;
// cak ni uzimanje svih elemenata ne moze dovesti do ciljnog
// zbira, pa nema podnizova koji bi dali ciljni zbir
if (zbirPreostalih + EPS < ciljniZbir)
return 0;
// broj podnizova u kojima ucestvuje element a[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir - niz[k],
zbirPreostalih - niz[k], k+1) +
// broj podnizova u kojima ne ucestvuje element a[k]
brojPodnizovaDatogZbira(niz, ciljniZbir,
zbirPreostalih - niz[k], k+1);
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
// izracunavamo zbir elemenata niza
double zbirNiza = 0;
for (int i = 0; i < n; i++)
zbirNiza += niz[i];
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, ciljniZbir, zbirNiza, 0);
}
int main() {
// ucitavamo niz
int n;
cin >> n;
vector<double> niz(n);
for (int i = 0; i < n; i++)
cin >> niz[i];
// ucitavamo ciljni zbir
double ciljniZbir;
cin >> ciljniZbir;
// izracunavamo i ispisujemo trazeni broj podnizova
cout << brojPodnizovaDatogZbira(niz, ciljniZbir) << endl;
return 0;
}Još jedno moguće odsecanje se može izvršiti kada se ustanovi da je najmanji od preostalih brojeva u nizu veći od ciljnog zbira. Ako je taj ciljni zbir pozitivan, tada nije moguće dostići ga (jer prazan podniz ima zbir nula, a bilo koji neprazan podniz ima zbir veći ili jednak od tog minimalnog elementa). Minimalni element preostalog dela niza je jednostavno odrediti ako se niz sortira (što možemo uraditi pre početka pretrage). Naglasimo da je ova odsecanje samo mala optimizacija odsecanja čvorova koji imaju negativan ciljni zbir. Na primer, ako bismo imali ciljni zbir \(2\) i preostale elemente \(3\), \(4\), \(5\) i \(6\), pomoću ove optimizacije bismo odmah mogli prekinuti pretragu, dok bi se bez nje dobilo drvo pretrate prikazano na narednoj slici. Dakle, drveta koja se odsecaju ovom optimizacijom, a ne bi bila odsečena bez nje, su samo linearne (a ne eksponencijalne) veličine u odnosu na broj preostalih elemenata niza.
Na slici je prikazano drvo rekurzivnih poziva sa ovim odsecanjima kada se u nizu \([1, 2, 3, 4]\) traže podnizovi čiji je zbir jednak \(5\). Kada su odabrani elementi \([1, 2]\), tada je ciljni zbir \(2\), pa pošto je najmanji preostali element \(3\), može da se izvrši odsecanje. Slično se događa i kada su odabrani elementi \([3]\) (ciljni zbir je \(2\)), \([2]\) (ciljni zbir je \(3\)) i \([1, 3]\) (ciljni zbir je \(1\)), i kada je najmanji (zapravo jedini) preostali element jednak \(4\). Odsecanje nastupa i kada nije izabran nijedan element (ciljni zbir je \(5\)), a jedini preostali element je \(4\) (tada je ciljni zbir veći od zbira svih preostalih elemenata).
// racuna se broj podnizova elemenata niza na pozicijama [k,
// n) koji imaju dati zbir, pri cemu se zna da je zbir tih
// elemenata jednak zbirPreostalih
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir,
double zbirPreostalih, int k) {
// ciljni zbir 0 se dobija samo ako se ne uzme ni jedan
// element
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// cak ni uzimanje svih elemenata ne moze dovesti do ciljnog
// zbira, pa nema podnizova koji bi dali ciljni zbir
if (zbirPreostalih + EPS < ciljniZbir)
return 0;
// vec uzimanje najmanjeg elementa prevazilazi ciljni zbir,
// pa nema podnizova koji bi dali ciljni zbir
if (niz[k] > ciljniZbir + EPS)
return 0;
// broj podnizova u kojima ucestvuje element a[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir - niz[k],
zbirPreostalih - niz[k], k+1) +
// broj podnizova u kojima ne ucestvuje element a[k]
brojPodnizovaDatogZbira(niz, ciljniZbir,
zbirPreostalih - niz[k], k+1);
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
// sortiramo elemente niza neopadajuce
sort(begin(niz), end(niz));
// izracunavamo zbir elemenata niza
double zbirNiza = 0;
for (int i = 0; i < n; i++)
zbirNiza += niz[i];
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, ciljniZbir, zbirNiza, 0);
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
const double EPS = 0.00001;
// racuna se broj podnizova elemenata niza na pozicijama [k,
// n) koji imaju dati zbir, pri cemu se zna da je zbir tih
// elemenata jednak zbirPreostalih
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir,
double zbirPreostalih, int k) {
// ciljni zbir 0 se dobija samo ako se ne uzme ni jedan
// element
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// cak ni uzimanje svih elemenata ne moze dovesti do ciljnog
// zbira, pa nema podnizova koji bi dali ciljni zbir
if (zbirPreostalih + EPS < ciljniZbir)
return 0;
// vec uzimanje najmanjeg elementa prevazilazi ciljni zbir,
// pa nema podnizova koji bi dali ciljni zbir
if (niz[k] > ciljniZbir + EPS)
return 0;
// broj podnizova u kojima ucestvuje element a[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir - niz[k],
zbirPreostalih - niz[k], k+1) +
// broj podnizova u kojima ne ucestvuje element a[k]
brojPodnizovaDatogZbira(niz, ciljniZbir,
zbirPreostalih - niz[k], k+1);
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
// sortiramo elemente niza neopadajuce
sort(begin(niz), end(niz));
// izracunavamo zbir elemenata niza
double zbirNiza = 0;
for (int i = 0; i < n; i++)
zbirNiza += niz[i];
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, ciljniZbir, zbirNiza, 0);
}
int main() {
// ucitavamo niz
int n;
cin >> n;
vector<double> niz(n);
for (int i = 0; i < n; i++)
cin >> niz[i];
// ciljni zbir podniza
double ciljniZbir;
cin >> ciljniZbir;
// izracunavamo i ispisujemo trazeni broj podnizova
cout << brojPodnizovaDatogZbira(niz, ciljniZbir) << endl;
return 0;
}Kada se vrše odsecanja, redosled obilaska vrednosti u drvetu pretrage može značajno da utiče na veličinu drveta. Na primer, umesto da se prvo razmatra uključivanje najmanjeg elementa niza u podniz, može se prvo razmatrati uključivanje najvećeg elementa uz podniz (uz ista odsecanja koja su ranije opisana). Na početku je niz potrebno sortirati nerastuće (umesto neopadajuće), a najmanji element neobrađenog dela niza se uvek nalazi na kraju samog niza.
Na slici je prikazano drvo rekurzivnih poziva sa ovim odsecanjima kada se u nizu \([1, 2, 3, 4]\) traže podnizovi čiji je zbir jednak \(5\). Primetimo da se u ovom primeru većina odsecanja vrši već na osnovu toga da li preostali ciljni zbir pripada intervalu od \(0\) do zbira svih preostalih elemenata, tako da ova strategija grananja otvara mnogo više mogućnosti za ta osnovna odsecanja (u ovom malom primeru se čak nijednom nije desilo da je nastupilo odsecanje na osnovu vrednosti minimalnog elementa u preostalom delu niza).
// racuna se broj podnizova elemenata niza na pozicijama [k,
// n) koji imaju dati zbir, pri cemu se zna da je zbir tih
// elemenata jednak zbirPreostalih
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir,
double zbirPreostalih, int k) {
// ciljni zbir 0 se dobija samo ako se ne uzme ni jedan
// element
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// cak ni uzimanje svih elemenata ne moze dovesti do ciljnog
// zbira, pa nema podnizova koji bi dali ciljni zbir
if (zbirPreostalih + EPS < ciljniZbir)
return 0;
// vec uzimanje najmanjeg elementa prevazilazi ciljni zbir,
// pa nema podnizova koji bi dali ciljni zbir
if (niz[niz.size()-1] > ciljniZbir + EPS)
return 0;
// broj podnizova u kojima ucestvuje element a[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir - niz[k],
zbirPreostalih - niz[k], k+1) +
// broj podnizova u kojima ne ucestvuje element a[k]
brojPodnizovaDatogZbira(niz, ciljniZbir,
zbirPreostalih - niz[k], k+1);
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
// sortiramo elemente niza nerastuce
sort(begin(niz), end(niz), greater<int>());
// izracunavamo zbir elemenata niza
double zbirNiza = 0;
for (int i = 0; i < n; i++)
zbirNiza += niz[i];
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, ciljniZbir, zbirNiza, 0);
}#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <functional>
using namespace std;
const double EPS = 0.00001;
// racuna se broj podnizova elemenata niza na pozicijama [k,
// n) koji imaju dati zbir, pri cemu se zna da je zbir tih
// elemenata jednak zbirPreostalih
int brojPodnizovaDatogZbira(const vector<double>& niz,
double ciljniZbir,
double zbirPreostalih, int k) {
// ciljni zbir 0 se dobija samo ako se ne uzme ni jedan
// element
if (abs(ciljniZbir) < EPS)
return 1;
// jedini podniz praznog niza je prazan, a ciljni zbir je
// pozitivan
if (k == niz.size())
return 0;
// cak ni uzimanje svih elemenata ne moze dovesti do ciljnog
// zbira, pa nema podnizova koji bi dali ciljni zbir
if (zbirPreostalih + EPS < ciljniZbir)
return 0;
// vec uzimanje najmanjeg elementa prevazilazi ciljni zbir,
// pa nema podnizova koji bi dali ciljni zbir
if (niz[niz.size()-1] > ciljniZbir + EPS)
return 0;
// broj podnizova u kojima ucestvuje element a[k]
return brojPodnizovaDatogZbira(niz, ciljniZbir - niz[k],
zbirPreostalih - niz[k], k+1) +
// broj podnizova u kojima ne ucestvuje element a[k]
brojPodnizovaDatogZbira(niz, ciljniZbir,
zbirPreostalih - niz[k], k+1);
}
// funkcija racuna koliko podnizova datog niza ima zbir jednak
// ciljnom
int brojPodnizovaDatogZbira(vector<double>& niz,
double ciljniZbir) {
// broj elemenata niza
int n = niz.size();
// sortiramo elemente niza nerastuce
sort(begin(niz), end(niz), greater<int>());
// izracunavamo zbir elemenata niza
double zbirNiza = 0;
for (int i = 0; i < n; i++)
zbirNiza += niz[i];
// rekurzivnom funkcijom racunamo trazeni broj podnizova
return brojPodnizovaDatogZbira(niz, ciljniZbir, zbirNiza, 0);
}
int main() {
// ucitavamo niz
int n;
cin >> n;
vector<double> niz(n);
for (int i = 0; i < n; i++)
cin >> niz[i];
// ciljni zbir podniza
double ciljniZbir;
cin >> ciljniZbir;
// izracunavamo i ispisujemo trazeni broj podnizova
cout << brojPodnizovaDatogZbira(niz, ciljniZbir) << endl;
return 0;
}