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
urediKrenuć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"
urediReš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
urediPrilikom 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)
смена к = log2n (5)
T(n) = T(n/2log2n) + clog2n (6)
= T(1) + clog2n (7)
= O(logn) (8)
Pretraga vrha u 2D nizu "pohlepnim" algoritmom
urediPohlepni 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:
- Одабере се одакле почиње (од ког елемента) - if одабрани леви (или десни) сусед већи од елемента, идемо у том правцу (већег суседа) - else идемо у супротном правцу - if стигнемо до границе идемо доле - if тренутни елемент већи од својих суседа, врх је нађен
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)
urediAko 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:
- изабери средњу колону ј = m/2 - пронађи глобални максимум (највећу вредност) у тренутној колони - упореди (i, j) са суседима (i, j-1) i (i, j+1) - if (i, j-1) > (i, j) изабери леве колоне, - if (i, j+1) > (i, j) изабери десне колоне - if (i, j) >= (i, j-1) i (i, j) >= (i, j+1) , 2Д врх (i, j) је нађен - нови проблем ћемо решити са половином колона - када имамо једну колону, наћи глобални максимум (крај)
Сложеност алгоритма T(n, m) = T(n, m/2) + O(n) ... базни случај T(n, 1) = O(n) T(n, m) = O(n) + ... + O(n) ово ће се извршавати log2m пута коначна сложеност је 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š
urediReference
uredi- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Stein, Clifford. Introduction to Algorithms (3rd izd.). MIT Press. ISBN 9780262033848.