Virtual Laboratory Wiki
Advertisement

Трои́чный по́иск (Тернарный поиск) — это метод в информатике для поиска максимумов и минимумов функции, которая либо сначала строго возрастает, затем строго убывает, либо наоборот. Троичный поиск определяет, что минимум или максимум не может лежать либо в первой, либо в последней трети области, и затем повторяет поиск на оставшихся двух третях. Троичный поиск демонстрирует парадигму программирования «разделяй и властвуй».

Функция

Предположим, что мы ищем максимум функции f(x), и что нам известно, что максимум лежит между A и B. Чтобы алгоритм был применим, должно существовать некоторое значение x, такое что

  • для всех a,b, для которых A ≤ a < b ≤ x, выполняется f(a) < f(b), и
  • для всех a,b, для которых x ≤ a < b ≤ B, выполняется f(a) > f(b).

Алгоритм

function ternarySearch(f, left, right, absolutePrecision) 
//left and right are the current bounds; the maximum is between them
    if (right-left < absolutePrecision) return (left+right)/2
    leftThird := (left*2+right)/3
    rightThird := (left+right*2)/3
    if (f(leftThird) < f(rightThird))
        return ternarySearch(f, leftThird, right, absolutePrecision)
    else
        return ternarySearch(f, left, rightThird, absolutePrecision)
end

См. также

  • Алгоритмы поиска
  • Двоичный поиск (используется для поиска точки, где производная меняет знак)
  • Метод Ньютона (используется для поиска точки, где производная обращается в ноль)
  • Метод золотого сечения (схож с троичным поиском, полезен, если за одну итерацию вычисление f занимает больше всего времени)
  • Интерполирующий поиск
  • Линейный поиск
  • Троичные алгоритмы

Эта страница использует содержимое раздела Википедии на русском языке. Оригинальная статья находится по адресу: Троичный поиск. Список первоначальных авторов статьи можно посмотреть в истории правок. Эта статья так же, как и статья, размещённая в Википедии, доступна на условиях CC-BY-SA .


Advertisement