Тернарный (или троичный) поиск — это алгоритм поиска минимума (или максимума) выпуклой функции на отрезке. Можно искать минимум (максимум) функции от вещественного аргумента, можно минимум (максимум) на массиве. Будем, для определённости, искать минимум функции f(x).
Он многим знаком, а для тех, кто не знает, расскажу вкратце.
Тернарный поиск заключается в следующем. Пусть есть рекурсивная функция search(L, R), которая по двум концам отрезка L, R определяет минимум на орезке [L, R]. Если R — L < eps, то мы уже вычислили точку, где достигается минимум, с точностью eps. Иначе, разделим отрезок [L,R] на три равных по длине отрезка [L, A], [A, B] и [B, R]. Сравним значение в точках А и В. Вспомнив, что функция f выпуклая, можно сделать вывод, что если f(A) > f(B), то минимум лежит на отрезке [A,R]. Иначе — на отрезке [L, B]. В соответсвии с этим, можно рекурсивно запуститься от одного из отрезков [L, B] или [A, R]. Каждый раз длина области поиска уменьшается в полтора раза, значит, минимум на отрезке длины X с точностью eps будет найден за время O(log(X/eps)).
А здесь я хочу рассказать о квадрарном (или четверичном) поиске.
По сути, это некоторая оптимизация тернарного поиска. Как и в нём, мы будет рекурсивно вычислять минимум функции на промежутке L, R. Только теперь мы будем вычислять значение функции не в двух, а в трёх точках: в A=(3L+R)/4, B=(L+R)/2 и C=(L+3R)/4. Посмотрим, какое из этих значений в этих трёх точках самое маленькое. Если левое — то запускаемся рекурсивно на отрезке [L,B], если правое — на отрезке [B,R], а если среднее — то на отрезке [A,C]. Длина отрезка всегда уменьшается в два раза. При этом, надо заметить, что если f(A) <= f(B), то это уже означает, что левое значение — самое маленькое, если f(С) <= f(B) — то правое; в остальных случаях — среднее. Поэтому не надо делать кучу проверок: делаем одну, а если она не сработала, то ещё одну.
Теперь заметим одну вещь. Когда мы запустимся от одного из трёх отрезков, нам понадобится знать три значения на этом отрезке. Но одно из них — среднее — мы уже вычисляли на предыдущем шаге: если мы запустились от левого отрезка, то это f(A), если от правого то f(С), а если от среднего — f(B). Поэтому его не надо вычислять ещё раз: его можно просто передать. Значит, на каждом шаге мы вычисляем уже не 3, а 2 значения.
А теперь заметим ещё одну вещь. Ведь для того, чтобы знать, что надо перейти в левый отрезок, нам надо узнать только значения в точках A и B. Поэтому значение в точке C можно пока не вычислять: оно может и не пригодится.
Таким образом, количество требуемых итераций в log1.52 раз меньше, а количество вычисляемых значений за итерацию в среднем меньше (сложно оценить, во сколько раз, возможно, примерно в полтора), но уж точно не больше, чем в тернарном поиске. Что выглядит заманчиво, особенно когда вычисление значения происходит долго.
И для полноты картины, код, всего из десяти строк:
P.S. Перенесено в «Алгоритмы» из личного блога.
Он многим знаком, а для тех, кто не знает, расскажу вкратце.
Тернарный поиск заключается в следующем. Пусть есть рекурсивная функция search(L, R), которая по двум концам отрезка L, R определяет минимум на орезке [L, R]. Если R — L < eps, то мы уже вычислили точку, где достигается минимум, с точностью eps. Иначе, разделим отрезок [L,R] на три равных по длине отрезка [L, A], [A, B] и [B, R]. Сравним значение в точках А и В. Вспомнив, что функция f выпуклая, можно сделать вывод, что если f(A) > f(B), то минимум лежит на отрезке [A,R]. Иначе — на отрезке [L, B]. В соответсвии с этим, можно рекурсивно запуститься от одного из отрезков [L, B] или [A, R]. Каждый раз длина области поиска уменьшается в полтора раза, значит, минимум на отрезке длины X с точностью eps будет найден за время O(log(X/eps)).
А здесь я хочу рассказать о квадрарном (или четверичном) поиске.
По сути, это некоторая оптимизация тернарного поиска. Как и в нём, мы будет рекурсивно вычислять минимум функции на промежутке L, R. Только теперь мы будем вычислять значение функции не в двух, а в трёх точках: в A=(3L+R)/4, B=(L+R)/2 и C=(L+3R)/4. Посмотрим, какое из этих значений в этих трёх точках самое маленькое. Если левое — то запускаемся рекурсивно на отрезке [L,B], если правое — на отрезке [B,R], а если среднее — то на отрезке [A,C]. Длина отрезка всегда уменьшается в два раза. При этом, надо заметить, что если f(A) <= f(B), то это уже означает, что левое значение — самое маленькое, если f(С) <= f(B) — то правое; в остальных случаях — среднее. Поэтому не надо делать кучу проверок: делаем одну, а если она не сработала, то ещё одну.
Теперь заметим одну вещь. Когда мы запустимся от одного из трёх отрезков, нам понадобится знать три значения на этом отрезке. Но одно из них — среднее — мы уже вычисляли на предыдущем шаге: если мы запустились от левого отрезка, то это f(A), если от правого то f(С), а если от среднего — f(B). Поэтому его не надо вычислять ещё раз: его можно просто передать. Значит, на каждом шаге мы вычисляем уже не 3, а 2 значения.
А теперь заметим ещё одну вещь. Ведь для того, чтобы знать, что надо перейти в левый отрезок, нам надо узнать только значения в точках A и B. Поэтому значение в точке C можно пока не вычислять: оно может и не пригодится.
Таким образом, количество требуемых итераций в log1.52 раз меньше, а количество вычисляемых значений за итерацию в среднем меньше (сложно оценить, во сколько раз, возможно, примерно в полтора), но уж точно не больше, чем в тернарном поиске. Что выглядит заманчиво, особенно когда вычисление значения происходит долго.
И для полноты картины, код, всего из десяти строк:
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);
}
}
P.S. Перенесено в «Алгоритмы» из личного блога.
