Алгоритам тражења врха
Врх је елемент низа који задовољава својство да је већи или једнак од своја два суседна елемента. Ако имамо низ бројева, који су смештени у једнодимензионални низ (1Д) и желимо да нађемо један од елемената који је врх, а који не мора да буде највећи врх, онда ћемо користити алгоритме тражења (проналажења) врха.[1]
Постоји неколико различитих начина, а неки од њих су: проналажење врха у 1Д низу "Brute-Force" претрагом, и методом "Divide and Conquer".
Такође можемо пронаћи врх у 2Д низу (матрици) користећи се неким техникама које примењујемо и за 1Д низ.
Налажење врха у 1Д низу "Brute-Force" претрагом
уредиКренућемо од почетка низа и проверавати да ли тренутни елемент испуњава услов врха тј. да ли су оба његова суседа мања или једнака њему.
У најгорем случају мораћемо да прођемо кроз цео низ, тако да би сложеност алгоритма била линеарна О(n).
for i in range(n)
if(A[i-1] <= A[i] >= A[i+1])
return i;
Проналажење врха у 1Д низу методом "Divide and Conquer"
уредиРешење у логаритамском времену О(logn), са базом 2, је доста брже и боље. Користимо методу "подели па владај" ("Divide and conquer"), као што се користи у бинарном стаблу претраге. Бинарно стабло претраге дели низ на половине све док не пронађе тражени елемент низа. Сличан приступ се примењује у проналажењу врха. Ако узмемо низ {1, 3, 4, 3, 5, 1, 3} знамо да ако почнемо у средини то ће бити елемент 3, који је мањи од 4 и 5. Можемо ићи на леву страну и поделити низ на пола, па добијамо низ {1, 3, 4} и поново бирамо средњи елемент 3, али 3 је само већи од 1 а мањи од 4, па зато идемо на десну страну, овог пута имамо само {4} који је остао, па је он наш базни случај.
Дакле, имамо само један елемент тако да је он врх.
Ово је дати алгоритам где А представља низ, 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);
Анализа сложености алгоритма
уредиПриликом рекурзије смањујемо низ дужине n на n/2 у О(1) времену (тј. поређење средњег елеммента са суседима).
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)
Претрага врха у 2Д низу "похлепним" алгоритмом
уредиПохлепни алгоритам тражења 2Д врха ("Gready Ascent algorithm") бира правац и покушава да га прати како би нашао врх.
Треба само да се направи модел кретања за овај алгоритам.
Алгоритам гласи:
- Одабере се одакле почиње (од ког елемента) - if одабрани леви (или десни) сусед већи од елемента, идемо у том правцу (већег суседа) - else идемо у супротном правцу - if стигнемо до границе идемо доле - if тренутни елемент већи од својих суседа, врх је нађен
За било коју смишљену стратегију (тј. модел кретања), најгори случај сложености ће бити да се прође кроз све елементе матрице.
Дакле, сложеност би била О(mn) или ако је квадратна матрица m = n онда O(n²).
Проналажење врха у 2Д низу (матрица)
уредиАко нам је дата матрица М[ ][ ] димензија mxn, треба пронаћи елемент матрице М[i][j] који је већи или једнак (>=) од својих суседа тј. M[i+1][j], M[i−1][j], M[i][j+1], i M[i][j−1].
Постоје наравно бржи и спорији алгоритми налажења врха у 2Д низу.
Ако је m број колона, а n број редова онда алгоритам гласи:
- изабери средњу колону ј = 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)
Следи пар случајева које треба обрадити, као нпр. кад је низ празан.
if (problem.Length <= 0)
return 0;
if (right == -1)
right = problem[0].Length;
int j = (left + right) / 2;
int globalMax = FindGlobalMax(problem, j);
Овако решавамо случај када позовемо нашу методу за вредност right = -1. Иницијализујемо right са дужином низа, затим израчунамо тренутну колону тј. средину и на крају гледамо глобални максимум. Правимо помоћну методу која ради ово.
Све што она ради је да иде преко истог индекса колоне за сваки ред у низу. На овај начин можемо наћи индекс са највећим елементом у колони.
Овај метод изгледа:
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;
}
Користимо горње редове колона ако не можемо да нађемо вредност која је већа од тренутне. Ако можемо онда само повећамо индекс све док не пронађемо највећи. Следи метода која проверава суседа тренутног елемента:
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];
}
У овом случају проверавамо четири ствари, у свари проверићемо само 3 ствари, јер бирањем средње колоне која има само 0, нема глобалне максимуме и користиће горње приликом провере суседа. Зато и проверавамо границе, да не бисмо ништа радили изван њих. Након провере суседа, знамо да морамо да идемо лево или десно ако је могуће, а ако није ми смо на тренутном глобалном максимуму. Ако одемо лево, поставићемо десну границу на тренутну средину, а ако одемо десно поставићемо леву границу на тренутну средину. Затим ћемо радити рекурзију овако:
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];
Ево целог кода за проналажење 2Д врха:
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;
}
}
Види још
уредиРеференце
уреди- ^ Thomas H. Cormen; Charles E. Leiserson; Ronald L. Rivest; Stein, Clifford. Introduction to Algorithms (3rd изд.). MIT Press. ISBN 9780262033848.