May 2, 2010 at 01:55Quad search
Ternary (or ternary) search is an algorithm for finding the minimum (or maximum) of a convex function in a segment. You can search for a minimum (maximum) of a function of a real argument, you can search for a minimum (maximum) on an array. For definiteness, we seek the minimum of the function f (x).
He is familiar to many, but for those who do not know, I will tell you briefly.
Ternary search is as follows. Let there be a recursive function search (L, R), which at the two ends of the segment L, R determines the minimum on the segment [L, R]. If R - L <eps, then we have already calculated the point where the minimum is reached, with accuracy eps. Otherwise, we 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]. Accordingly, it is possible to start recursively from one of the segments [L, B] or [A, R]. Each time, the length of the search area decreases by one and a half times, which means that a minimum on a segment of length X will be found with accuracy eps in time O (log (X / eps)).
And here I want to talk about quadrature (or quadruple) search.
In fact, this is some optimization of ternary search. Like 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 at these three points is the smallest. If the left - then we start recursively on the segment [L, B], if the right - on the segment [B, R], and if the middle - then on the segment [A, C]. The length of the segment is always reduced by half. At the same time, 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; in other cases - average. Therefore, it is not necessary to do a bunch of checks: we do one, and if it does not work, then another.
Now note one thing. When we start from one of the three segments, we need to know the three values on this segment. But one of them - the average - we already calculated at the previous step: if we started from the left segment, then it is f (A), if it is from the right, then f (C), and if from the middle - f (B). Therefore, it does not need to be calculated again: it can simply be transferred. So, at each step, we calculate not 3, but 2 values.
Now let's notice one more thing. Indeed, 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.
So the number of iterations required in log 1.52 times less, and the number of calculated values per iteration is on average less (it is difficult to estimate how many times, perhaps about one and a half), but certainly not more than in ternary search. Which looks tempting, especially when calculating the value takes a long time.
And to complete the picture, the code consists of only 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 you briefly.
Ternary search is as follows. Let there be a recursive function search (L, R), which at the two ends of the segment L, R determines the minimum on the segment [L, R]. If R - L <eps, then we have already calculated the point where the minimum is reached, with accuracy eps. Otherwise, we 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]. Accordingly, it is possible to start recursively from one of the segments [L, B] or [A, R]. Each time, the length of the search area decreases by one and a half times, which means that a minimum on a segment of length X will be found with accuracy eps in time O (log (X / eps)).
And here I want to talk about quadrature (or quadruple) search.
In fact, this is some optimization of ternary search. Like 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 at these three points is the smallest. If the left - then we start recursively on the segment [L, B], if the right - on the segment [B, R], and if the middle - then on the segment [A, C]. The length of the segment is always reduced by half. At the same time, 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; in other cases - average. Therefore, it is not necessary to do a bunch of checks: we do one, and if it does not work, then another.
Now note one thing. When we start from one of the three segments, we need to know the three values on this segment. But one of them - the average - we already calculated at the previous step: if we started from the left segment, then it is f (A), if it is from the right, then f (C), and if from the middle - f (B). Therefore, it does not need to be calculated again: it can simply be transferred. So, at each step, we calculate not 3, but 2 values.
Now let's notice one more thing. Indeed, 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.
So the number of iterations required in log 1.52 times less, and the number of calculated values per iteration is on average less (it is difficult to estimate how many times, perhaps about one and a half), but certainly not more than in ternary search. Which looks tempting, especially when calculating the value takes a long time.
And to complete the picture, the code consists of only ten lines: PS Transferred to the "Algorithms" from a personal blog.
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);
}
}