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

Постановка задачи

Пусть дана функция $f(x)$ , унимодальная на некотором отрезке $[l;r]$ . Под унимодальностью понимается один из двух вариантов. Первый: функция сначала строго возрастает, потом достигает максимума (в одной точке или целом отрезке), потом строго убывает. Второй вариант, симметричный: функция сначала убывает убывает, достигает минимума, возрастает. В дальнейшем мы будем рассматривать первый вариант, второй будет абсолютно симметричен ему.

Требуется найти максимум функции $f(x)$ на отрезке $[l;r]$ .

Алгоритм

Возьмём любые две точки $m_1$ и $m_2$ в этом отрезке: $l < m_1 < m_2 < r$ . Посчитаем значения функции $f(m_1)$ и $f(m_2)$ . Дальше у нас получается три варианта:

Если окажется, что $f(m_1) < f(m_2)$ , то искомый максимум не может находиться в левой части, т.е. в части $[l;m_1]$ . В этом легко убедиться: если в левой точке функция меньше, чем в правой, то либо эти две точки находятся в области "подъёма" функции, либо только левая точка находится там. В любом случае, это означает, что максимум дальше имеет смысл искать только в отрезке $[m_1;r]$ .
Если, наоборот, $f(m_1) > f(m_2)$ , то ситуация аналогична предыдущей с точностью до симметрии. Теперь искомый максимум не может находиться в правой части, т.е. в части $[m_2;r]$ , поэтому переходим к отрезку $[l;m_2]$ .
Если $f(m_1) = f(m_2)$ , то либо обе эти точки находятся в области максимума, либо левая точка находится в области возрастания, а правая — в области убывания (здесь существенно используется то, что возрастание/убывание строгие). Таким образом, в дальнейшем поиск имеет смысл производить в отрезке $[m_1;m_2]$ , но (в целях упрощения кода) этот случай можно отнести к любому из двух предыдущих.

Таким образом, по результату сравнения значений функции в двух внутренних точках мы вместо текущего отрезка поиска $[l;r]$ находим новый отрезок $[l^\prime;r^\prime]$ . Повторим теперь все действия для этого нового отрезка, снова получим новый, строго меньший, отрезок, и т.д.

Рано или поздно длина отрезка станет маленькой, меньшей заранее определённой константы-точности, и процесс можно останавливать. Этот метод численный, поэтому после остановки алгоритма можно приближённо считать, что во всех точках отрезка $[l;r]$ достигается максимум; в качестве ответа можно взять, например, точку $l$ .

Осталось заметить, что мы не накладывали никаких ограничений на выбор точек $m_1$ и $m_2$ . От этого способа, понятно, будет зависеть скорость сходимости (но и возникающая погрешность). Наиболее распространённый способ — выбирать точки так, чтобы отрезок $[l;r]$ делился ими на 3 равные части:

$m_1 = l + \frac{r-l}{3}$
$m_2 = r - \frac{r-l}{3}$

Впрочем, при другом выборе, когда $m_1$ и $m_2$ ближе друг к другу, скорость сходимости несколько увеличится.

Случай целочисленного аргумента

Если аргумент функции $f$ целочисленный, то отрезок $[l;r]$ тоже становится дискретным, однако, поскольку мы не накладывали никаких ограничений на выбор точек $m_1$ и $m_2$ , то на корректность алгоритма это никак не влияет. Можно по-прежнему выбирать $m_1$ и $m_2$ так, чтобы они делили отрезок $[l;r]$ на 3 части, но уже равные только приблизительно.

Второй отличающийся момент — критерий остановки алгоритма. В данном случае тернарный поиск надо будет останавливать, когда станет $r-l<3$ , ведь в таком случае уже невозможно будет выбрать точки $m_1$ и $m_2$ так, чтобы были различными и отличались от $l$ и $r$ , и это может привести к зацикливанию. После того, как алгоритм тернарного поиска остановится и станет $r-l<3$ , из оставшихся нескольких точек-кандидатов $(l,l+1,\ldots,r)$ надо выбрать точку с максимальным значением функции.

Реализация

Реализация для непрерывного случая (т.е. функция $f$ имеет вид: $\rm double\ f\ (double\ x)$ ):

double l = ..., r = ..., EPS = ...; // входные данные
while (r - l > EPS) {
   double m1 = l + (r - l) / 3,
      m2 = r - (r - l) / 3;
   if (f (m1) < f (m2))
      l = m1;
   else
      r = m2;
}

Здесь $\rm EPS$ — фактически, абсолютная погрешность ответа (не считая погрешностей, связанных с неточным вычислением функции).

Вместо критерия "while (r - l > EPS)" можно выбрать и такой критерий останова:

for (int it=0; it<iterations; ++it)

С одной стороны, придётся подобрать константу $\rm iterations$ , чтобы обеспечить требуемую точность (обычно достаточно нескольких сотен, чтобы достичь максимальной точности). Но зато, с другой стороны, число итераций перестаёт зависеть от абсолютных величин $l$ и $r$ , т.е. мы фактически с помощью $\rm iterations$ задаём требуемую относительную погрешность.