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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показано 37 промежуточных версий 5 участников)
Строка 1: Строка 1:
'''Троичный поиск''' (или ''тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке.
+
'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.
 
 
 
== Алгоритм ==
 
== Алгоритм ==
  
 +
[[File:Ternar2.png|thumb|280px|Пример. <tex>f(a) < f(b) \implies x_{min} \in [l, b]</tex>]]
  
 
+
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).  
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен). [[File:Ternar2.png|thumb|300px|Пример]]
 
  
 
Пусть функция <tex>f(x)</tex> на отрезке <tex>[l, r]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, в которой он достигается.
 
Пусть функция <tex>f(x)</tex> на отрезке <tex>[l, r]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, в которой он достигается.
  
Посчитаем значения функции в точках <tex> a = l + \frac{(r-l)}{3} </tex> и <tex> b = l + \frac{2(r-l)}{3} </tex>.
+
Посчитаем значения функции в точках <tex> a = l + \dfrac{(r-l)}{3} </tex> и <tex> b = l + \dfrac{2(r-l)}{3} </tex>.
  
Так как в точке <tex>x_{min}</tex> минимум, то на отрезке <tex>[l, r]</tex> функция {{---}} выпуклая вниз.
+
Так как в точке <tex>x_{min}</tex> минимум, то на отрезке <tex>[l, x_{min}]</tex> функция убывает, а на <tex>[x_{min}, r]</tex> {{---}} возрастает, то есть
  
 
<tex> \forall x', x'' \in [l, r]: \\
 
<tex> \forall x', x'' \in [l, r]: \\
l      < x' < x'' < x_{min} \Rightarrow f(l)      > f(x') > f(x'') > f(x_{min}) \\
+
l      < x' < x'' < x_{min} \implies f(l)      > f(x') > f(x'') > f(x_{min}) \\
x_{min} < x' < x'' < r      \Rightarrow f(x_{min}) < f(x') < f(x'') < f(r)      </tex>.
+
x_{min} < x' < x'' < r      \implies f(x_{min}) < f(x') < f(x'') < f(r)      </tex>.
  
 
Значит если <tex>f(a) < f(b)</tex>, то <tex>x_{min} \in [l, b]</tex>,
 
Значит если <tex>f(a) < f(b)</tex>, то <tex>x_{min} \in [l, b]</tex>,
 
аналогично из <tex>f(a) > f(b)</tex> следует <tex> x_{min} \in [a, r]</tex>.
 
аналогично из <tex>f(a) > f(b)</tex> следует <tex> x_{min} \in [a, r]</tex>.
 +
 
Тогда нам нужно изменить границы поиска и искать дальше,
 
Тогда нам нужно изменить границы поиска и искать дальше,
 
пока не будет достигнута необходимая точность, то есть <tex> r-l < \varepsilon </tex>.
 
пока не будет достигнута необходимая точность, то есть <tex> r-l < \varepsilon </tex>.
 +
 +
Из рассуждений и рисунка может возникнуть идея взять, например, отрезок <tex>[l, a]</tex> вместо отрезка <tex>[l, b]</tex>. Но этого делать нельзя, потому что мы не умеем различать случаи, когда <tex>f(a) < f(b)</tex> и <tex>a</tex> слева или справа от минимума.
 +
 +
Можно заметить, что если мы всегда будем брать отрезок <tex>[l, b]</tex> при <tex>f(a) < f(b)</tex> или <tex>[a, r]</tex> при <tex>f(a) > f(b)</tex> , то минимум функции всегда будет в нашем отрезке. Если <tex>f(a) = f(b)</tex>, то можно взять любой отрезок.
  
 
=== Псевдокод ===
 
=== Псевдокод ===
  
ternarySearchMin(f, l, r, eps)
+
Рекурсивный вариант:
  if (r - l < eps)
 
    return (left + right) / 2
 
  a = (left * 2 + right) / 3
 
  b = (left + right * 2) / 3
 
  if (f(a) < f(b))
 
    return ternarySearch(f, l, b, eps)
 
  else
 
    return ternarySearch(f, a, r, eps)
 
end
 
  
Возможен и нерекурсивный вариант:
+
  '''double''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' eps):
 
+
    '''if''' right - left < eps
  ternarySearchMin(f, l, r, eps)  
+
        '''return''' (left + right) / 2
  while (r - l < 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)
      r = b
+
        '''return''' ternarySearchMin(f, left, b, eps)
     else
+
     '''else'''
      l = a
+
        '''return''' ternarySearchMin(f, a, right, eps)
  }
+
 
  return (left + right) / 2
+
Итеративный вариант:
end
 
  
 +
'''double''' ternarySearchMin('''double''' f(), '''double''' left, '''double''' right, '''double''' 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
  
 
=== Время работы ===
 
=== Время работы ===
Строка 55: Строка 56:
 
Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока <tex> r - l > \varepsilon</tex>,
 
Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока <tex> r - l > \varepsilon</tex>,
 
то время работы алгоритма составит  
 
то время работы алгоритма составит  
<tex>2 \log_{\frac32} \left(\frac{r - l}{\varepsilon}\right)</tex>
+
<tex dpi = "135">2 \log_{\frac32} \left(\dfrac{r - l}{\varepsilon}\right)</tex>
  
== Смотрите также ==
+
== См. также ==
  
Есть оптимизация этого алгоритма, если делить отрезок не на равные части, а в отношении золотого сечения, {{---}} [[Поиск с помощью золотого сечения]]
+
* [[Поиск с помощью золотого сечения]]
  
[http://ru.wikipedia.org/wiki/%D0%A2%D1%80%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA Троичный поиск на Википедии]
+
== Источники информации ==
  
== Литература ==
+
* Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.
 +
* [[wikipedia:ru:Троичный поиск|Троичный поиск — Википедия]]
 +
* [[wikipedia:Ternary search|Ternary search {{---}} Wikipedia]]
  
Дональд Кнут Искусство программирования, том 3. Сортировка и поиск = The Art of Computer Programming, vol.3. Sorting and Searching.
+
[[Категория: Дискретная математика и алгоритмы]]
 +
[[Категория: Алгоритмы поиска]]

Текущая версия на 19:05, 4 сентября 2022

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

Алгоритм

Пример. [math]f(a) \lt f(b) \implies 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} \implies f(l) \gt f(x') \gt f(x'') \gt f(x_{min}) \\ x_{min} \lt x' \lt x'' \lt r \implies 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].

Из рассуждений и рисунка может возникнуть идея взять, например, отрезок [math][l, a][/math] вместо отрезка [math][l, b][/math]. Но этого делать нельзя, потому что мы не умеем различать случаи, когда [math]f(a) \lt f(b)[/math] и [math]a[/math] слева или справа от минимума.

Можно заметить, что если мы всегда будем брать отрезок [math][l, b][/math] при [math]f(a) \lt f(b)[/math] или [math][a, r][/math] при [math]f(a) \gt f(b)[/math] , то минимум функции всегда будет в нашем отрезке. Если [math]f(a) = f(b)[/math], то можно взять любой отрезок.

Псевдокод

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

double ternarySearchMin(double f(), double left, double right, double 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)

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

double ternarySearchMin(double f(), double left, double right, double 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]

См. также

Источники информации