Троичный поиск | это... Что такое Троичный поиск? (original) (raw)
Трои́чный по́иск (Тернарный поиск) — это метод в информатике для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях. Троичный поиск демонстрирует парадигму программирования «разделяй и властвуй».
Возьмём любые две точки и в этом отрезке: . Посчитаем значения функции и . Дальше у нас получается три варианта:
Если окажется, что , то искомый максимум не может находиться в левой части, т.е. в части . В этом легко убедиться: если в левой точке функция меньше, чем в правой, то либо эти две точки находятся в области "подъёма" функции, либо только левая точка находится там. В любом случае, это означает, что максимум дальше имеет смысл искать только в отрезке . Если, наоборот, , то ситуация аналогична предыдущей с точностью до симметрии. Теперь искомый максимум не может находиться в правой части, т.е. в части , поэтому переходим к отрезку . Если , то либо обе эти точки находятся в области максимума, либо левая точка находится в области возрастания, а правая — в области убывания (здесь существенно используется то, что возрастание/убывание строгие). Таким образом, в дальнейшем поиск имеет смысл производить в отрезке , но (в целях упрощения кода) этот случай можно отнести к любому из двух предыдущих. Таким образом, по результату сравнения значений функции в двух внутренних точках мы вместо текущего отрезка поиска находим новый отрезок . Повторим теперь все действия для этого нового отрезка, снова получим новый, строго меньший, отрезок, и т.д.
Рано или поздно длина отрезка станет маленькой, меньшей заранее определённой константы-точности, и процесс можно останавливать. Этот метод численный, поэтому после остановки алгоритма можно приближённо считать, что во всех точках отрезка достигается максимум; в качестве ответа можно взять, например, точку .
Осталось заметить, что мы не накладывали никаких ограничений на выбор точек и . От этого способа, понятно, будет зависеть скорость сходимости (но и возникающая погрешность). Наиболее распространённый способ — выбирать точки так, чтобы отрезок делился ими на 3 равные части:
Впрочем, при другом выборе, когда и ближе друг к другу, скорость сходимости несколько увеличится.
Алгоритм
double l = ..., r = ..., EPS = ...; // входные данные while (r - l > EPS) {
double m1 = l + (r - l) / 3, m2 = r - (r - l) / 3; if (f (m1) < f (m2)) l = m1; else r = m2;
}
См. также
- Алгоритмы поиска
- Двоичный поиск (используется для поиска точки, где производная меняет знак)
- Метод Ньютона (используется для поиска точки, где производная обращается в ноль)
- Метод золотого сечения (схож с троичным поиском, полезен, если за одну итерацию вычисление f занимает больше всего времени)
- Интерполирующий поиск
- Линейный поиск
- Троичные алгоритмы
Методы оптимизации | |
---|---|
Одномерные | Метод золотого сечения • Дихотомия • Метод парабол • Перебор по сетке • Метод Фибоначчи • Троичный поиск |
Прямые методы | Метод Гаусса • Метод Нелдера — Мида • Метод Хука — Дживса • Метод конфигураций • Метод Розенброка |
Первого порядка | Градиентный спуск • Метод Зойтендейка • Покоординатный спуск • Метод сопряжённых градиентов • Квазиньютоновские методы • Алгоритм Левенберга — Марквардта |
Второго порядка | Метод Ньютона • Метод Ньютона — Рафсона |
Стохастические | Метод Монте-Карло • Имитация отжига • Эволюционные алгоритмы • Дифференциальная эволюция • Муравьиный алгоритм • Метод роя частиц |
Методы линейного программирования | Симплекс-метод • Алгоритм Гомори • Метод эллипсоидов • Метод потенциалов |
Методы нелинейногопрограммирования | Последовательное квадратичное программирование |