Эта статья возникла из личного публичного аккаунта:TechFlow
В предыдущей статье мы подробно остановились на дихотомии, особенно обсудив проблемы с границами при написании кода. Портал:
Краткий разговор об алгоритмах — дихотомия, которую знают все, но многие пишут неправильно
В сегодняшней статье мы продолжим разговор об алгоритмах и не будем говорить о дихотомии. Давайте поговорим о расширенной версии дихотомии -Правило третей.
Да, вы правильно прочитали, это не мое волевое имя, но есть реальный алгоритм. Однако, если поискать в поисковике, скорее всего, вы найдете трехточечный композиционный метод фотосъемки, но алгоритм трехточечного поиска сложно найти.
Основная причина в том, что это гораздо более нишевое понятие, чем дихотомия, и почти во всех книгах по алгоритмам нет введения в трихотомию. Он существует больше в соревнованиях по алгоритмам, таких как ACM-ICPC, но не имеет значения, является ли он нишевым, главное, чтобы он был полезен. Принцип правила третей тоже очень прост, и он почти такой же, как метод дихотомии, за исключением того, что, когда мы делим интервал, мы делим интервал не на два, а на три. После этого также используем метод сужения интервала, чтобы определить, где находится искомое значение.
Увидев это, я считаю, что вы все должны понимать принцип алгоритма, но должен быть задан вопрос:Зачем нам нужно делить на три части, если деление на две части может решить проблему?
Прежде чем ответить на этот вопрос, давайте рассмотрим другой вопрос. Какую задачу в математике решает дихотомия?
Помните предпосылку используемой дихотомии? Массив должен быть упорядочен, поэтому метод деления пополам фактически решает проблему решения монотонной функции. Пока массив упорядочен, согласно определению функции, его можно рассматривать как функцию, которая отображает индекс массива в значение массива. Очевидно, что это монотонная функция. Один из элементов v находим бинарным методом, суть собственно в том, чтобы найтиf(x) = vрешение этой функции.
Следовательно, сценарий, используемый дихотомией, является монотонной функцией, то есть линейной функцией. Итак, если я хочу найти минимальное значение квадратичной функции, возможно ли использовать метод деления пополам?
Очевидно, что это невозможно, потому что после взятия середины мы не знаем, в каком интервале может появиться ответ. Здесь требуется правило третей.
Как известно, правило третей делит интервал на трети. Разделенный на три части, естественно нужны две конечные точки. Каждая из этих двух конечных точек имеет значение, которое мы называем m1 и m2 соответственно. Мы запрашиваем минимальное значение функции, поэтому нам нужна экстремальная аппроксимация.
Но у нас есть две промежуточные точки, как их аппроксимировать?
Мы непосредственно анализируем его в соответствии с изображением функции, Согласно приведенному выше рисунку, мы видим, что значения функции m1 и m2 связаны с их расстоянием от крайней точки. Чем ближе к крайней точке, тем меньше значение функции (а возможно и больше, в зависимости от функции). На картинке выше
, поэтому m2 ближе к крайней точке. Мы хотим сузить диапазон и приблизиться к крайней точке, поэтому мы должны положить l=m1
Здесь есть небольшая проблема, как определить, что крайняя точка находится между m2 и m1? Что, если он находится на правой стороне m2?
Когда мы рисуем изображение, в этой ситуации нет никакой разницы, мы просто отбрасываем интервал [l, m1] , не влияет на крайнюю точку.
Будет ли крайняя точка находиться на левой стороне m1? Это невозможно, так как если крайняя точка находится слева от m1, то m2 должно быть дальше от экстремума, чем m1, при этом значение функции в точке m2 не может быть меньше m1.
Другими словами, суть правила третей заключается в сужении интервала на одну треть путем сравнения величины двух значений за раз. Пока диапазон последнего интервала не станет меньше установленного нами порога. Алгоритм нетруден для понимания, но когда мы действительно сталкиваемся с проблемой экстремального значения квадратичной функции, трудно думать об алгоритме, если мы заранее не столкнулись с правилом третей.
Само по себе правило третей не сложно, как только мы понимаем алгоритм, легко написать псевдокод:
def trichotomy():
l, r = start, end
epsilon = 1e-6
# 我们自定义的终止条件是区间长度小于1d-6
while l + epsilon < r:
margin = (r - l) / 3.0
m1 = l + margin
m2 = m1 + margin
if f(m1) <= f(m2):
r = m2
else:
l = m1
return l
Наконец, давайте рассмотрим задачу алгоритма, связанную с правилом третей, и применим правило третей на практике.
Это POJ3737, ссылка следующая:Crack.org/проблема?ID=…
Позвольте мне кратко представить смысл темы. Смысл вопроса очень прост: теперь у нас есть кусок ткани, мы знаем размер ткани, и нам нужно сделать из ткани конус. Чтобы максимизировать объем конуса, предполагая, что ткань не теряется во время обработки, каковы объем, радиус основания и высота конуса?
Я не буду помещать ответ здесь, вы можете подумать об этом сами, если вы действительно не можете этого сделать, ответьте на ответ правила третей в официальном аккаунте, чтобы получить решение.
Если вы считаете статью полезной, отсканируйте код, чтобы получить следующее: