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


Троичный поиск (ternary search, тернарный поиск) — метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.

Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).

Пусть функция f(x)на отрезке [L,R] имеет минимум, и мы хотим найти точку xmin, в которой он достигается.
Так как в точке xmin минимум, то на отрезке [L,xminфункция убывает, а на [xmin,R] — возрастает.
Для любых точек x′, x′′ ∈ [L,R] возможна одна из трех ситуаций:

  • (A )    L < x′ < x′′< xmin  и заничит f(L) > f(x′) > f(x′′) > f(xmin) 
  • (B)     xmin<x′<x′′<r  и значит  f(xmin) < f(x′) < f(x′′) < f(R)
  • (C)     L< x′<= xmin <=x′′< R  и значит f(L) > f(x′) и  f(x′′) < f(R)
Разделим отрезок на три части определив точки L<a<b<R (например: a=L+(R−L)/3 и b=L+2(R−L)/3 ) и
посчитаем значения функции в точках a и b. Будут возможны два случая:
  •  f(a) > f(b)  и тогда для точек a, b, xmin  возможен случай (A) или (C) и => xmin ∈ [a,R];
  •  f(a) <= f(b)  и тогда для точек a, b, xmin  возможен случай (B) или (C) и => xmin ∈ [L,b];

Таким образом на каждом шаге отрезок поиска будет сокращается (на треть) и в итоге можно получить требуемое значение с заданной точностью.
 


Задача: На отрезке АВ найдите точку с минимальным расстоянием то начала координат. 
Рассмотрим решение задачи с помощью стандартного тернарного поиска. 
  • Будем искать точку с минимальным квадратом расстояния. Квадрат расстояния до начала координат для точки
    с координатами ( x, y, z ) равен  x2+y2+z2
  • Пусть вершины отрезка L,R имеют координаты (Lx, Ly, Lz) и (Rx, Ry, Rz). Тогда точки с координатами
    ((2Lx+Rx)/3, (2Ly+Ry)/3, (Lz+Rz)/3) и ((Lx+2Rx)/3, (Ly+2Ry)/3, (Lz+2Rz)/3) будут принадлежать отрезку и делить его на три равные части
  •  Точность вычислений задавать не будем, а зададим количество шагов вычислений 
 


Пусть мы хотим найти максим/минимум функции тернарным поиском. 
Для деления отрезка на три части можно использовать различные подходы:
  • строгое деление на равные части
  • деление методом "золотого сечения"
  • метод "чисел Фибоначчи"
Рассмотрим подробнее метод "числел Фибоначчи".
Задание точности вычисления можно определить с помощью числа выполняемых шагов алгоритма тернарного поиска.
Пусть мы определини, что алгоритм будет выполняться n шагов.  Построим последовательность F0,  F1,..., Fn-1, Fn (1, 1, 2, 3, 5, ...)
Опишем алгоритм поиска минимума:
  • Задаются начальные границы отрезка L,R и число итераций n, рассчитываются начальные точки деления:
                 \(x_1=L+(R-L)\frac{F_{n-2}}{F_n},\ x_2=L+(R-L)\frac{F_{n-1}}{F_n} \) и значения в них целевой функции: \(y_1=f(x_1),\ y_2=f(x_2) \)
  • Пока n>1 :
    • n=n-1
    • Если  \(y_1\ >\ y_2,\ то \)
      • \(L,\ x_1\ =\ x_1,\ x_2\)
      • \(x_2\ = R-(x_1\ -\ L)\)
      • \(y_1,\ y_2\ =\ y_2,\ f(x_2)\)
    • Иначе 
      • \(R,\ x_2\ =\ x_2,\ x_1\)
      • \(x_1\ =\ L+(R\ -\ x_2\ )\)
      • \(y_2,\ y_1\ =\ y_1,\ f(x_1)\)
  • n=1 : \(x \ =\ \frac{x_1\ +\ x_2}{2}\)
Реализуем этот алгоритм на примере задачи 1. 
Заметим, что при реализации, преобразования можно упростить

 


Задача 1: На отрезке АВ с целочисленными координатами вершин найдите точку с минимальным расстоянием то начала координат. 
При решении задачи воспользуемся методом чисел Фибоначчи. Ответ x,y определим по правилу:
Если y1<y2, то: x,y=x1,y1
Иначе: x,y=x2,y2

 


Метод числе Фибоначчи имеет более длинный код, но дает более "интересный" результат.
Вы можете сравнить результата методоы для разных k. 
Оба метода на определенном этапе "стабилизируются" (это связано с точностью вещественного представления)

Для сравнения удобно взять "египетский треугольник".
Введите значения
0 3
4 0
Расстояние должно быть 2,4
Можно увидеть, что лучший результат в методе "чисел Фибоначчи" достигается при k=24 .
При стандартном тернарном поиске лучший результат достигается при k=52-55

Задача 2. Найдите максимальный объем прямоугольного параллелипипеда у которого одна из граней есть квадрат, а сумм трех измерений 1 метр.
В ответе укажите сторону квадрата (в метрах).
Легко заметить, что для решения такой задачи компьютер не нужен, но мы решим задачу с помощью тернарного поиска использую метод чисел Фибоначчи и модуль fractions (работа с рациональным представлением)
Аналитика: если сторона квадрата a,  то строны параллелипипеда a,a,1-2a и объем равен a2-2a3, следовательно максимум будет при a=1/3
При решении с помощью программы будем выводить промежуточные значения величин x1, x2
 


Модифицируем решение задачи 1. Будем использовать модуль fractions и метод чисел Фибоначчи..
Задача 1: На отрезке АВ с целочисленными координатами вершин найдите точку с минимальным расстоянием то начала координат. 
 


Можно убедиться, что достигается абсолютная точность - для египетского треугольника при k>36
Подведем итоги: используйте тернарный поиск с модулем fractions и методом чисел Фибоначчи.

time 1000 ms
memory 256 Mb

Комментарий учителя

Foxford Lectarium.ru