Изменения

{{В разработке}}'''Троичный поиск''' (''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.== Алгоритм ==

Рассмотрим этот алгоритм на примере поиска минимума [[File:Ternar2.png|thumb|280px|Пример. <tex>f(поиск максимума аналогиченa).< f(b) \implies x_{min} \in [l, b]</tex>]]

Пусть функция <tex>fРассмотрим этот алгоритм на примере поиска минимума (xпоиск максимума аналогичен)</tex> на отрезке <tex>[a, b]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, в которой он достигается.

Посчитаем значения функции в точках Пусть функция <tex> x_1 = a + \frac{f(b-ax)}{3} </tex> и <tex> x_2 = a + \frac{2(b-a)}{3} </tex>. Так как в точке <tex>x_{min}</tex> минимум, то до нее на отрезке <tex>[al, br]</tex> функция убываетимеет минимум, а после нее {{---}} возрастает, то естьи мы хотим найти точку <tex> \forall x', x'' \in [a, b]: \\a < x' < x'' < x_{min} \Rightarrow f(a) > f(x') > f(x'') > f(x_{min}) \\x_{min} < x' < x'' < b \Rightarrow f(x_{min}) < f(x') < f(x'') < f(b) </tex>, в которой он достигается.

Посчитаем значения функции в точках <tex> a = l + \dfrac{(r-l)}{3} </tex> и <tex> b = l + \dfrac{2(r-l)}{3} </tex>. Так как в точке <tex>x_{min}</tex> минимум, то на отрезке <tex>[l, x_{min}]</tex> функция убывает, а на <tex>[x_{min}, r]</tex> {{---}} возрастает, то есть <tex> \forall x', x'' \in [l, r]: \\l < x' < x'' < x_{min} \implies f(l) > f(x') > f(x'') > f(x_{min}) \\x_{min} < x' < x'' < r \implies f(x_{min}) < f(x') < f(x'') < f(r) </tex>. Значит если <tex>f(x_1a) < f(x_2b)</tex>, то <tex>x_{min} \in [al, x_2b]</tex>, аналогично из <tex>f(x_1a) > f(x_2b)</tex> следует <tex> x_{min} \in [x_1a, br]</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>, то можно взять любой отрезок. === Псевдокод === Рекурсивный вариант:  '''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 === Время работы === Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока <tex> r - l > \varepsilon </tex>,то время работы алгоритма составит <tex dpi = "135">2 \log_{\frac32} \left(\dfrac{r - l}{\varepsilon}\right)</tex> == См. также == * [[Поиск с помощью золотого сечения]] == Источники информации == * Дональд Кнут {{---}} Искусство программирования. Том 3. Сортировка и поиск. / Knuth D.E. {{---}} The Art of Computer Programming. Vol. 3. Sorting and Searching.* [[wikipedia:ru:Троичный поиск|Троичный поиск — Википедия]]* [[wikipedia:Ternary search|Ternary search {{---}} Wikipedia]] [[Категория: Дискретная математика и алгоритмы]][[Категория: Алгоритмы поиска]]