Тернарный поиск

Тернарный поиск

Тернарный поиск нужен нам для поиска максимума или минимума унимодальной функции на отрезке [l, r]. Унимодальной функция является тогда, когда у нее на отрезке есть один экстремум.
Поиск максимальных значений функции часто используется для оптимизационных задач. Например, нам надо найти максимально возможный угол прямоугольного треугольника, при котором площадь будет наибольшей.  Для этого мы переберём углы от 0 до 90, и на этом отрезке ищем площадь, которая сначала возрастет, а потом будет уменьшаться, т.е. функция будет унимодальной.
 

Принцип работы

Принцип работы схож с двоичным поиском, но у нас, возможно, возникнет случай при делении отрезка пополам, когда у нас середина отрезка попадет ровно на экстремум, и  внятного результата мы не получим.
Поэтому, чтобы избежать подобного случая, надо делить отрезок не на две части, а на три, и ту часть в которой нет экстремума, отбрасываем и т.д., до тех пор пока границы не сойдутся на результате.

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)  тернарный поиск


 

Тернарный поиск

Тернарный поиск нужен нам для поиска максимума или минимума унимодальной функции на отрезке [l, r]. Унимодальной функция является тогда, когда у нее на отрезке есть один экстремум.
Поиск максимальных значений функции часто используется для оптимизационных задач. Например, нам надо найти максимально возможный угол прямоугольного треугольника, при котором площадь будет наибольшей.  Для этого мы переберём углы от 0 до 90, и на этом отрезке ищем площадь, которая сначала возрастет, а потом будет уменьшаться, т.е. функция будет унимодальной.
 

Принцип работы

Принцип работы схож с двоичным поиском, но у нас, возможно, возникнет случай при делении отрезка пополам, когда у нас середина отрезка попадет ровно на экстремум, и  внятного результата мы не получим.
Поэтому, чтобы избежать подобного случая, надо делить отрезок не на две части, а на три, и ту часть в которой нет экстремума, отбрасываем и т.д., до тех пор пока границы не сойдутся на результате.
 

import math


def f(hypo, alpha):
    alpha = (alpha * math.pi)/180
    return 0.5 * hypo * hypo * math.cos(alpha) * math.sin(alpha)


l = 0.
r = 90.
EPS = 1e-6;
hypo = 100
while r - l >= EPS:
    m1 = l + (r - l) / 3
    m2 = r - (r - l) / 3
    if f(hypo, m1) < f(hypo, m2):
        l = m1
    else:
        r = m2

print((l + r) / 2)

Тернарный поиск можно модифицировать, используя метод золотого сечения, который увеличивает скорость сходимости примерно в 2 раза.
 

Источники

1)  тернарный поиск и метод золотого сечения
2)  тернарный поиск