Algoritam traženja vrha
Vrh je element niza koji zadovoljava svojstvo da je veći ili jednak od svoja dva susedna elementa. Ako imamo niz brojeva, koji su smešteni u jednodimenzionalni niz (1D) i želimo da nađemo jedan od elemenata koji je vrh, a koji ne mora da bude najveći vrh, onda ćemo koristiti algoritme traženja (pronalaženja) vrha.[1]
Postoji nekoliko različitih načina, a neki od njih su: pronalaženje vrha u 1D nizu "Brute-Force" pretragom, i metodom "Divide and Conquer".
Takođe možemo pronaći vrh u 2D nizu (matrici) koristeći se nekim tehnikama koje primenjujemo i za 1D niz.
Nalaženje vrha u 1D nizu "Brute-Force" pretragom[uredi | uredi kod]
Krenućemo od početka niza i proveravati da li trenutni element ispunjava uslov vrha tj. da li su oba njegova suseda manja ili jednaka njemu.
U najgorem slučaju moraćemo da prođemo kroz ceo niz, tako da bi složenost algoritma bila linearna O(n).
for i in range(n)
if(A[i-1] <= A[i] >= A[i+1])
return i;
Pronalaženje vrha u 1D nizu metodom "Divide and Conquer"[uredi | uredi kod]
Rešenje u logaritamskom vremenu O(logn), sa bazom 2, je dosta brže i bolje. Koristimo metodu "podeli pa vladaj" ("Divide and conquer"), kao što se koristi u binarnom stablu pretrage. Binarno stablo pretrage deli niz na polovine sve dok ne pronađe traženi element niza. Sličan pristup se primenjuje u pronalaženju vrha. Ako uzmemo niz {1, 3, 4, 3, 5, 1, 3} znamo da ako počnemo u sredini to će biti element 3, koji je manji od 4 i 5. Možemo ići na levu stranu i podeliti niz na pola, pa dobijamo niz {1, 3, 4} i ponovo biramo srednji element 3, ali 3 je samo veći od 1 a manji od 4, pa zato idemo na desnu stranu, ovog puta imamo samo {4} koji je ostao, pa je on naš bazni slučaj.
Dakle, imamo samo jedan element tako da je on vrh.
Ovo je dati algoritam gde A predstavlja niz, i početak niza i j = n-1 :
pronadjiVrh(A, i, j):
m = (i + j) /2;
if A[m-1] <= A[m] >= A[m+1]
return m;
else if A[m-1] > A[m]
return pronadjiVrh(A, i, m-1);
else if A[m+1] > A[m]
return pronadjiVrh(A, m+1, j);
Analiza složenosti algoritma[uredi | uredi kod]
Prilikom rekurzije smanjujemo niz dužine n na n/2 u O(1) vremenu (tj. poređenje srednjeg elemmenta sa susedima).
T(n) = T(n/2) + c (1)
T(n) = T(n/4) + c + c (2)
T(n) = T(n/8) + c + c + c (3)
T(n) = T(n/2k) + ck (4)
smena k = log2n (5)
T(n) = T(n/2log2n) + clog2n (6)
= T(1) + clog2n (7)
= O(logn) (8)
Pretraga vrha u 2D nizu "pohlepnim" algoritmom[uredi | uredi kod]
Pohlepni algoritam traženja 2D vrha ("Gready Ascent algorithm") bira pravac i pokušava da ga prati kako bi našao vrh.
Treba samo da se napravi model kretanja za ovaj algoritam.
Algoritam glasi:
- Odabere se odakle počinje (od kog elementa) - if odabrani levi (ili desni) sused veći od elementa, idemo u tom pravcu (većeg suseda) - else idemo u suprotnom pravcu - if stignemo do granice idemo dole - if trenutni element veći od svojih suseda, vrh je nađen
Za bilo koju smišljenu strategiju (tj. model kretanja), najgori slučaj složenosti će biti da se prođe kroz sve elemente matrice.
Dakle, složenost bi bila O(mn) ili ako je kvadratna matrica m = n onda O(n²).
Pronalaženje vrha u 2D nizu (matrica)[uredi | uredi kod]
Ako nam je data matrica M[ ][ ] dimenzija mxn, treba pronaći element matrice M[i][j] koji je veći ili jednak (>=) od svojih suseda tj. M[i+1][j], M[i−1][j], M[i][j+1], i M[i][j−1].
Postoje naravno brži i sporiji algoritmi nalaženja vrha u 2D nizu.
Ako je m broj kolona, a n broj redova onda algoritam glasi:
- izaberi srednju kolonu j = m/2 - pronađi globalni maksimum (najveću vrednost) u trenutnoj koloni - uporedi (i, j) sa susedima (i, j-1) i (i, j+1) - if (i, j-1) > (i, j) izaberi leve kolone, - if (i, j+1) > (i, j) izaberi desne kolone - if (i, j) >= (i, j-1) i (i, j) >= (i, j+1) , 2D vrh (i, j) je nađen - novi problem ćemo rešiti sa polovinom kolona - kada imamo jednu kolonu, naći globalni maksimum (kraj)
Složenost algoritma T(n, m) = T(n, m/2) + O(n) ... bazni slučaj T(n, 1) = O(n) T(n, m) = O(n) + ... + O(n) ovo će se izvršavati log2m puta konačna složenost je O(nlog2m)
Sledi par slučajeva koje treba obraditi, kao npr. kad je niz prazan.
if (problem.Length <= 0)
return 0;
if (right == -1)
right = problem[0].Length;
int j = (left + right) / 2;
int globalMax = FindGlobalMax(problem, j);
Ovako rešavamo slučaj kada pozovemo našu metodu za vrednost right = -1. Inicijalizujemo right sa dužinom niza, zatim izračunamo trenutnu kolonu tj. sredinu i na kraju gledamo globalni maksimum. Pravimo pomoćnu metodu koja radi ovo.
Sve što ona radi je da ide preko istog indeksa kolone za svaki red u nizu. Na ovaj način možemo naći indeks sa najvećim elementom u koloni.
Ovaj metod izgleda:
int FindGlobalMax(int[][] problem, int column) {
int max = 0;
int index = 0;
for (int i = 0; i < problem.Length; i++) {
if (max < problem[i][column])
max = problem[i][column]; index = i;
}
return index;
}
Koristimo gornje redove kolona ako ne možemo da nađemo vrednost koja je veća od trenutne. Ako možemo onda samo povećamo indeks sve dok ne pronađemo najveći. Sledi metoda koja proverava suseda trenutnog elementa:
if ( (globalMax - 1 > 0 && problem[globalMax][j] >= problem[globalMax - 1][j])
&& (globalMax + 1 < problem.Length && problem[globalMax][j] >= problem[globalMax + 1][j])
&& (j - 1 > 0 && problem[globalMax][j] >= problem[globalMax][j - 1])
&& (j + 1 < problem[globalMax].Length && problem[globalMax][j] >= problem[globalMax][j + 1])
)
{
return problem[globalMax][j];
}
U ovom slučaju proveravamo četiri stvari, u svari proverićemo samo 3 stvari, jer biranjem srednje kolone koja ima samo 0, nema globalne maksimume i koristiće gornje prilikom provere suseda. Zato i proveravamo granice, da ne bismo ništa radili izvan njih. Nakon provere suseda, znamo da moramo da idemo levo ili desno ako je moguće, a ako nije mi smo na trenutnom globalnom maksimumu. Ako odemo levo, postavićemo desnu granicu na trenutnu sredinu, a ako odemo desno postavićemo levu granicu na trenutnu sredinu. Zatim ćemo raditi rekurziju ovako:
else if (j > 0 && problem[globalMax][j - 1] > problem[globalMax][j]) {
right = j;
return FindPeak(problem, left, right);
}
else if (j + 1 < problem[globalMax].Length && problem[globalMax][j + 1] > problem[globalMax][j]) {
left = j;
return FindPeak(problem, left, right);
}
return problem[globalMax][j];
Evo celog koda za pronalaženje 2D vrha:
class Program {
static void Main(string[] args) {
int[][] problem = new[]{
new [] {0, 0, 9, 0, 0, 0, 0},
new [] {0, 0, 0, 0, 0, 0, 0},
new [] {0, 1, 0, 0, 0, 8, 9},
new [] {0, 2, 0, 0, 0, 0, 0},
new [] {0, 3, 0, 0, 0, 0, 0},
new [] {0, 5, 0, 0, 0, 0, 0},
new [] {0, 4, 7, 0, 0, 0, 0},
};
int peak = new Program().FindPeak(problem);
Console.WriteLine("Found a peak with value : {0}", peak);
}
int FindPeak(int[][] problem, int left = 0, int right = -1) {
if (problem.Length <= 0) return 0;
if (right == -1) right = problem[0].Length;
int j = (left + right) / 2;
int globalMax = FindGlobalMax(problem, j);
if ( (globalMax - 1 > 0 && problem[globalMax][j] >= problem[globalMax - 1][j])
&& (globalMax + 1 < problem.Length && problem[globalMax][j] >= problem[globalMax + 1][j])
&& (j - 1 > 0 && problem[globalMax][j] >= problem[globalMax][j - 1])
&& (j + 1 < problem[globalMax].Length && problem[globalMax][j] >= problem[globalMax][j + 1]) ) {
return problem[globalMax][j];
}
else if (j > 0 && problem[globalMax][j - 1] > problem[globalMax][j]) {
right = j;
return FindPeak(problem, left, right);
}
else if (j + 1 < problem[globalMax].Length && problem[globalMax][j + 1] > problem[globalMax][j]) {
left = j;
return FindPeak(problem, left, right);
}
return problem[globalMax][j];
}
int FindGlobalMax(int[][] problem, int column) {
int max = 0;
int index = 0;
for (int i = 0; i < problem.Length; i++) {
if (max < problem[i][column]) {
max = problem[i][column]; index = i;
}
}
return index;
}
}
Vidi još[uredi | uredi kod]
Reference[uredi | uredi kod]
- ↑ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Stein, Clifford. Introduction to Algorithms (3rd izd.). MIT Press. ISBN 9780262033848.