Тернарный поиск нужен нам для поиска максимума или минимума унимодальной функции на отрезке [l,r]. Унимодальной функция является когда у нее на отрезке есть один экстремум.
Поиск максимальных значений функции часто используется для оптимизационных задач, например нам надо найти максимально возможный угол прямоугольного треульника, при котором площадь будет наибольшей. Для этого мы перебирем углы от 0 до 90 и на этом отрезке ищем площадь, которая сначала возрастет , а потом будет уменьшаться, т.е. функция будет унимодальной.
Принцип работы
Принцип работы схож с двоичным поиском, но у нас возможно возникнет случай при делении отрезка пополам, когда у нас серединам отрезка попадет ровно на экстремум, и и внятного результата мы не получим.
Поэтому, чnобы избежать подобного случая надо делить отрезок не на две части, а на три, и ту часть в которой нет экстремума отбрасываем и т.д., до тех пор пока границы не сойдутся на результате.
double f( double hypo, double alpha ) {
alpha = (alpha *M_PI)/180;
return 0.5 * hypo * hypo * cos(alpha) * sin(alpha);
}
int main() {
double l = 0;
double r = 90;
double EPS = 1e-6;
double hypo = 100;
while (r - l >= EPS) {
double m1 = l + (r - l) / 3;
double m2 = r - (r - l) / 3;
if (f(hypo, m1) < f(hypo, m2)) {
l = m1;
}
else {
r = m2;
}
}
cout << ((l + r) / 2);
return 0;
}
Тернарный поиск можно модицифицировать используя
метод золотого сечения, который увеличивает скорость сходимости примерно в 2 раза.
Источники:
1)
тернарный поиск и метод золотого сечения
2)
тернарный поиск