Троичный поиск — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
(Псевдокод)
Строка 28: Строка 28:
  
 
  ternarySearchMin(f, left, right, eps)  
 
  ternarySearchMin(f, left, right, eps)  
     if (right - left < eps)
+
     '''if''' (right - left < eps)
 
         return (left + right) / 2
 
         return (left + right) / 2
 
     a = (left * 2 + right) / 3
 
     a = (left * 2 + right) / 3
 
     b = (left + right * 2) / 3
 
     b = (left + right * 2) / 3
     if (f(a) < f(b))
+
     '''if''' (f(a) < f(b))
         return ternarySearchMin(f, left, b, eps)
+
         '''return''' ternarySearchMin(f, left, b, eps)
     else
+
     '''else'''
         return ternarySearchMin(f, a, right, eps)
+
         '''return''' ternarySearchMin(f, a, right, eps)
  
 
Итеративный вариант:
 
Итеративный вариант:
  
 
  ternarySearchMin(f, left, right, eps)  
 
  ternarySearchMin(f, left, right, eps)  
     while (right - left > eps)  
+
     '''while''' (right - left > eps)  
 
         a = (left * 2 + right) / 3
 
         a = (left * 2 + right) / 3
 
         b = (left + right * 2) / 3
 
         b = (left + right * 2) / 3
         if (f(a) < f(b))
+
         '''if''' (f(a) < f(b))
 
             right = b
 
             right = b
         else
+
         '''else'''
 
             left = a
 
             left = a
     return (left + right) / 2
+
     '''return''' (left + right) / 2
  
 
=== Время работы ===
 
=== Время работы ===

Версия 19:20, 22 мая 2014

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

Алгоритм

Пример. [math]f(a) \lt f(b) \Rightarrow x_{min} \in [l, b][/math]

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

Пусть функция [math]f(x)[/math] на отрезке [math][l, r][/math] имеет минимум, и мы хотим найти точку [math]x_{min}[/math], в которой он достигается.

Посчитаем значения функции в точках [math] a = l + \dfrac{(r-l)}{3} [/math] и [math] b = l + \dfrac{2(r-l)}{3} [/math].

Так как в точке [math]x_{min}[/math] минимум, то на отрезке [math][l, x_{min}][/math] функция убывает, а на [math][x_{min}, r][/math] — возрастает, то есть

[math] \forall x', x'' \in [l, r]: \\ l \lt x' \lt x'' \lt x_{min} \Rightarrow f(l) \gt f(x') \gt f(x'') \gt f(x_{min}) \\ x_{min} \lt x' \lt x'' \lt r \Rightarrow f(x_{min}) \lt f(x') \lt f(x'') \lt f(r) [/math].

Значит если [math]f(a) \lt f(b)[/math], то [math]x_{min} \in [l, b][/math], аналогично из [math]f(a) \gt f(b)[/math] следует [math] x_{min} \in [a, r][/math].

Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть [math] r-l \lt \varepsilon [/math].

Псевдокод

Рекурсивный вариант:

ternarySearchMin(f, left, right, eps) 
    if (right - left < eps)
        return (left + right) / 2
    a = (left * 2 + right) / 3
    b = (left + right * 2) / 3
    if (f(a) < f(b))
        return ternarySearchMin(f, left, b, eps)
    else
        return ternarySearchMin(f, a, right, eps)

Итеративный вариант:

ternarySearchMin(f, left, right, eps) 
    while (right - left > eps) 
        a = (left * 2 + right) / 3
        b = (left + right * 2) / 3
        if (f(a) < f(b))
            right = b
        else
            left = a
    return (left + right) / 2

Время работы

Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока [math] r - l \gt \varepsilon[/math], то время работы алгоритма составит [math]2 \log_{\frac32} \left(\dfrac{r - l}{\varepsilon}\right)[/math]

См. также

Литература

  • Дональд Кнут — Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. — The Art of Computer Programming. Vol. 3. Sorting and Searching.