1632
правки
Изменения
м
{{В разработке}}'''Троичный поиск''' (или ''ternary search, тернарный поиск'') {{---}} метод поиска минимума или максимума функции на отрезке, которая либо сначала строго возрастает, затем строго убывает, либо наоборот.== Алгоритм ==
== Алгоритм ==[[File:Ternar2.png|thumb|280px|Пример. <tex>f(a) < f(b) \implies x_{min} \in [l, 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(), l'''double''' left, r'''double''' right, '''double''' eps) : while (r '''if''' right - l left < eps '''return''' (left + right) {/ 2
Есть оптимизация этого алгоритма, если делить отрезок не на равные части, а в отношении золотого сечения, {{---}} * [[Поиск с помощью золотого сечения]]
[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.алгоритмы]][[Категория: Алгоритмы поиска]]
rollbackEdits.php mass rollback
Рассмотрим этот алгоритм на примере поиска минимума (поиск максимума аналогичен).
Пусть функция <tex>f(x)</tex> на отрезке <tex>[l, r]</tex> имеет минимум, и мы хотим найти точку <tex>x_{min}</tex>, в которой он достигается.
Посчитаем значения функции в точках <tex> a = l + \fracdfrac{(r-l)}{3} </tex> и <tex> b = l + \fracdfrac{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} \Rightarrow implies f(l) > f(x') > f(x'') > f(x_{min}) \\x_{min} < x' < x'' < r \Rightarrow 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 [a, r]</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>, то можно взять любой отрезок.
=== Псевдокод ===
a = (left * 2 + right) / 3
b = (left + right * 2) / 3
'''if (''' f(a) < f(b)) r = '''return''' ternarySearchMin(f, left, b, eps) '''else''' l = a } '''return ''' ternarySearchMin(left + f, a, right, eps) / 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
=== Время работы ===
Так как на каждой итерации мы считаем два значения функции и уменьшаем область поиска в полтора раза, пока <tex> r - l > \varepsilon</tex>,
то время работы алгоритма составит
<texdpi = "135">2 \log_{\frac32} \left(\fracdfrac{r - l}{\varepsilon}\right)</tex>
== Смотрите См. также ==
