Quad search
The ternary (or ternary) search is an algorithm for finding the minimum (or maximum) of a convex function on a segment. You can search for the minimum (maximum) of the function of the real argument, you can at least (the maximum) on the array. For definiteness, we will look for the minimum of the function f (x).
He is familiar to many, but for those who do not know, I will tell in brief.
Ternary search is as follows. Let there be a recursive function search (L, R), which by the two ends of the segment L, R determines the minimum on the cut [L, R]. If R - L <eps, then we have already calculated the point where the minimum is reached, with an accuracy of eps. Otherwise, divide the segment [L, R] into three equal lengths of the segment [L, A], [A, B] and [B, R]. Compare the value at points A and B. Recalling that the function f is convex, we can conclude that if f (A)> f (B), then the minimum lies on the segment [A, R]. Otherwise, on the segment [L, B]. In accordance with this, one can start recursively from one of the segments [L, B] or [A, R]. Each time, the length of the search area is reduced by one and a half, which means that the minimum on the segment of length X with an accuracy of eps will be found during O (log (X / eps)).
')
And here I want to talk about quadratic (or fourfold) search .
In fact, this is some optimization of ternary search. As in it, we will recursively calculate the minimum of the function on the interval L, R. Only now we will calculate the value of the function not at two, but at three points: at A = (3L + R) / 4, B = (L + R ) / 2 and C = (L + 3R) / 4. Let's see which of these values in these three points is the smallest. If the left - then we run recursively on the segment [L, B], if the right - on the segment [B, R], and if the average - then on the segment [A, C]. The length of the segment is always reduced by half. In this case, it should be noted that if f (A) <= f (B), then this already means that the left value is the smallest, if f (C) <= f (B) then the right one; in other cases, the average. Therefore, it is not necessary to do a lot of checks: we do one, and if it did not work, then another.
Now notice one thing. When we start from one of the three segments, we will need to know three values on this segment. But one of them is the average - we already calculated at the previous step: if we started from the left segment, then it is f (A), if from the right segment, then f (C), and if from the middle one - f (B). Therefore, it is not necessary to calculate it again: you can simply transfer it. It means that at each step we calculate not 3, but 2 values.
Now notice one more thing. After all, in order to know that we need to go to the left segment, we need to find out only the values at points A and B. Therefore, the value at point C can not be calculated yet: it may not be useful.
Thus, the number of required iterations in log 1.5 is 2 times less, and the number of calculated values per iteration is on average less (it is difficult to estimate how many times, perhaps approximately one and a half), but certainly not more than in the ternary search. What looks tempting, especially when calculating the value takes a long time.
And for completeness, the code, a total of ten lines:
PS Transferred to the "Algorithms" from a personal blog.
He is familiar to many, but for those who do not know, I will tell in brief.
Ternary search is as follows. Let there be a recursive function search (L, R), which by the two ends of the segment L, R determines the minimum on the cut [L, R]. If R - L <eps, then we have already calculated the point where the minimum is reached, with an accuracy of eps. Otherwise, divide the segment [L, R] into three equal lengths of the segment [L, A], [A, B] and [B, R]. Compare the value at points A and B. Recalling that the function f is convex, we can conclude that if f (A)> f (B), then the minimum lies on the segment [A, R]. Otherwise, on the segment [L, B]. In accordance with this, one can start recursively from one of the segments [L, B] or [A, R]. Each time, the length of the search area is reduced by one and a half, which means that the minimum on the segment of length X with an accuracy of eps will be found during O (log (X / eps)).
')
And here I want to talk about quadratic (or fourfold) search .
In fact, this is some optimization of ternary search. As in it, we will recursively calculate the minimum of the function on the interval L, R. Only now we will calculate the value of the function not at two, but at three points: at A = (3L + R) / 4, B = (L + R ) / 2 and C = (L + 3R) / 4. Let's see which of these values in these three points is the smallest. If the left - then we run recursively on the segment [L, B], if the right - on the segment [B, R], and if the average - then on the segment [A, C]. The length of the segment is always reduced by half. In this case, it should be noted that if f (A) <= f (B), then this already means that the left value is the smallest, if f (C) <= f (B) then the right one; in other cases, the average. Therefore, it is not necessary to do a lot of checks: we do one, and if it did not work, then another.
Now notice one thing. When we start from one of the three segments, we will need to know three values on this segment. But one of them is the average - we already calculated at the previous step: if we started from the left segment, then it is f (A), if from the right segment, then f (C), and if from the middle one - f (B). Therefore, it is not necessary to calculate it again: you can simply transfer it. It means that at each step we calculate not 3, but 2 values.
Now notice one more thing. After all, in order to know that we need to go to the left segment, we need to find out only the values at points A and B. Therefore, the value at point C can not be calculated yet: it may not be useful.
Thus, the number of required iterations in log 1.5 is 2 times less, and the number of calculated values per iteration is on average less (it is difficult to estimate how many times, perhaps approximately one and a half), but certainly not more than in the ternary search. What looks tempting, especially when calculating the value takes a long time.
And for completeness, the code, a total of ten lines:
double quadSearch(double L, double R, double midVal) { if (R - L < eps) return (R + L)/2; double leftVal = f((3*L + R)/4); if (leftVal < midVal) return quadSearch(L, (L + R)/2, leftVal); else { double rightVal = f((L + 3*R)/4); if (rightVal < midVal) return quadSearch((L + R)/2, R, rightVal); else return quadSearch((3*L + R)/4, (L + 3*R)/4, midVal); } }
double quadSearch(double L, double R, double midVal) { if (R - L < eps) return (R + L)/2; double leftVal = f((3*L + R)/4); if (leftVal < midVal) return quadSearch(L, (L + R)/2, leftVal); else { double rightVal = f((L + 3*R)/4); if (rightVal < midVal) return quadSearch((L + R)/2, R, rightVal); else return quadSearch((3*L + R)/4, (L + 3*R)/4, midVal); } }
PS Transferred to the "Algorithms" from a personal blog.
Source: https://habr.com/ru/post/92591/
All Articles