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

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
'''Троичный поиск''' {{---}} метод поиска минимума или максимума функции на отрезке.
+
'''Троичный поиск''' (или ''тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке.
  
 
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
 
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
  
Пусть функция <tex>f(x)</tex> на отрезке <tex>[a, b]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, в которой он достигается.
+
Пусть функция <tex>f(x)</tex> на отрезке <tex>[l, r]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, в которой он достигается.
  
Посчитаем значения функции в точках <tex> x_1 = a + \frac{(b-a)}{3} </tex> и <tex> x_2 = a + \frac{2(b-a)}{3} </tex>. Так как в точке <tex>x_{min}</tex> минимум, то до нее на отрезке <tex>[a, b]</tex> функция убывает, а после нее {{---}} возрастает, то есть
+
Посчитаем значения функции в точках <tex> a = l + \frac{(r-l)}{3} </tex> и <tex> b = l + \frac{2(r-l)}{3} </tex>. Так как в точке <tex>x_{min}</tex> минимум, то на отрезке <tex>[l, x_{min}]</tex> функция убывает, а на <tex>[x_{min}, r]</tex> {{---}} возрастает, то есть
<tex> \forall x', x'' \in [a, b]: \\
+
<tex> \forall x', x'' \in [l, r]: \\
a       < x' < x'' < x_{min} \Rightarrow f(a)      > f(x') > f(x'') > f(x_{min}) \\
+
l       < x' < x'' < x_{min} \Rightarrow f(l)      > f(x') > f(x'') > f(x_{min}) \\
x_{min} < x' < x'' < b       \Rightarrow f(x_{min}) < f(x') < f(x'') < f(b)      </tex>.
+
x_{min} < x' < x'' < r       \Rightarrow f(x_{min}) < f(x') < f(x'') < f(r)      </tex>.
  
Значит если <tex>f(x_1) < f(x_2)</tex>, то <tex>x_{min} \in [a, x_2]</tex>, аналогично из <tex>f(x_1) > f(x_2)</tex> следует <tex> x_{min} \in [x_1, b]</tex>. Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть <tex> b-a < \varepsilon </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, g]</tex>.
 +
Тогда нам нужно изменить границы поиска и искать дальше,
 +
пока не будет достигнута необходимая точность, то есть <tex> r-l < \varepsilon </tex>.
 +
 
 +
Псевдокод:
 +
 
 +
ternarySearch(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, a, r, eps)
 +
  else
 +
    return ternarySearch(f, l, b, eps)
 +
end

Версия 16:40, 15 июня 2011

Эта статья находится в разработке!

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

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

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

Посчитаем значения функции в точках [math] a = l + \frac{(r-l)}{3} [/math] и [math] b = l + \frac{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, g][/math]. Тогда нам нужно изменить границы поиска и искать дальше, пока не будет достигнута необходимая точность, то есть [math] r-l \lt \varepsilon [/math].

Псевдокод:

ternarySearch(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, a, r, eps)
  else
    return ternarySearch(f, l, b, eps)
end