Представьте себе массив чисел, в котором существует только одна вершина, как найти такое число и его индекс? Последовательный поиск, вероятно, первое решение, которое приходит нам в голову. Можем ли мы сделать лучше? Да, вероятно, используя двоичный поиск, чтобы уменьшить временную сложность с O(N)
до log(N)
. Это единственное решение, которое у нас есть? НЕТ… мы могли бы использовать более продвинутый и утонченный подход под названием Поиск золотого сечения.
Вопросы:
Назовем массив A
горой, если выполняются следующие свойства:
A.length >= 3
- Есть такие
0 < i < A.length - 1
, чтоA[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Для массива, который определенно является горой, верните любое i
такое, что A[0] < A[1] < ... A[i-1] < A[i] > A[i+1] > ... > A[A.length - 1]
Решения:
Давайте сначала рассмотрим закуски, прежде чем переходить к главному блюду.
- # 1) Стандартный метод линейного / последовательного поиска, найдите индекс пика
i
, гдеA[i]>A[i+1]
.O(N)
временная сложность, очень прямолинейно.
- # 2) Двоичный поиск, определение указателей
left
иright
и вычислениеmid
для каждой итерации. КогдаA[mid]<A[mid+1]
, это означает, что числа все еще увеличиваются, поэтому пик должен находиться справа отmid
, поэтому мы обновляем указательleft
; В противном случае это означает, что пик должен быть слева отmid
, мы обновляем указательright
. В конце концов, встречаются два указателя и определяется пиковый индекс.Olog(N)
временная сложность, намного быстрее, если у нас большой ввод.
- №3) Поиск по золотому сечению - это метод нахождения минимума / максимума строго унимодальной функции (идеально соответствует нашему определению проблемы горы с единственной вершиной). Чтобы понять алгоритм, нам нужно вспомнить золотое сечение ϕ (phi) и вывести некоторые из его свойств, которые будут использоваться позже.
(a+b)/a = a/b = ϕ 1 + 1/ϕ = ϕ ϕ^2 - ϕ - 1 = 0 Solve for ϕ and given ϕ > 0: ϕ = (1+sqrt(5))/2 = 1.61803... From 1 + 1/ϕ = ϕ, we get 1/ϕ = ϕ - 1, divided both sides by ϕ: 1/(ϕ^2) = 1 - 1/ϕ
Теперь давайте разберемся, как работает поиск по золотому сечению, с помощью приведенного ниже графика. Задача - найти максимальное значение (пик). Учитывая left
и right
границы исходного пространства поиска, мы хотели бы сначала найти две золотые точки x1
и x2
, где (x2-left)=(right-x1)
и (right-left)/(x2-left) = (x2-left)/(x1-left)
. Это именно тот вывод, который мы сделали ранее. Следовательно, мы формулируем x1
и x2
как:
x1 = right - (right-left)/ϕ x2 = left + (right-left)/ϕ
Далее мы собираемся сравнить значения f(x1)
и f(x2)
. Подобно двоичному поиску, пространство поиска уменьшается после каждой итерации. Если f(x1)>f(x2)
, мы понимаем, что пик не может находиться между x2
и right
, поэтому мы сокращаем диапазон поиска и обновляем right
до значения x2
.
после определения нового right
нам нужно пересчитать x1
и x2
. Есть уловка для сохранения вычислений относительно newx2
(как x2'
ниже).
x2' = left + (right'-left)/ϕ, where right' = x2 = left + (right-left)/ϕ substitute right' and with some algebra, we get: x2' = left + (right-left)/(ϕ^2), Recall earlier we proved 1/(ϕ^2) = 1 - 1/ϕ, again with some algebra: x2' = right - (right-left)/ϕ = x1 Amazing! x2' = x1
Здесь мы показали, что новое значение x2
будет просто значением x1
в предыдущей итерации. Это одно из удивительных свойств золотого сечения ϕ (фи). Точно так же, если f(x1) < f(x2)
, мы понимаем, что пик не может находиться между left
и x1
, поэтому мы обновляем left
до значения x1
(left=x1)
и нового x1
, чтобы он был значением x2
в предыдущей итерации.
Собрав все части вместе, у нас есть код ниже. Применено несколько методов оптимизации кода: 1) Умножение работает лучше, чем деление, поэтому вместо применения деления на phi
мы умножаем его обратное phi_inv
. 2) Вернемся к исходной проблеме Mountain Array, функция f
на самом деле является дискретной унимодальной функцией, которая преобразует целочисленные индексы в целые значения. Следовательно, в служебных функциях cal_x1
и cal_x2
должно применяться целочисленное округление. После того, как поиск сходится, требуется некоторая пост-проверка и корректировка, чтобы убедиться, что введен правильный индекс.
Алгоритм можно дополнительно усовершенствовать с помощью интересного математического вывода, касающегося вычисления нового x1
после оператора x2=x1
. Здесь я докажу x1' = cal_x1(left,right') = cal_x2(left, x2')
. Обратите внимание, здесь x2'
уже был обновлен до значения x1
в предыдущей итерации.
Apply formula for calcualting x1:
x1' = cal_x1(left,right') =
right' - (right'-left)/ϕ = x2 - (x2-left)/ϕ
Recall x2 = left + (right-left)/ϕ, substitute x2 in the above equation & with some algebra
x1' = left + (ϕ-1)(right-left)/(ϕ^2)
What about cal_x2(left,x2')?
cal_x2(left,x2') = cal_x2(left,x1) = left + (x1-left)/ϕ
Recall x1 = right - (right-left)/ϕ, substitute x1 in the above equation & with some algebra
cal_x2(left,x2') = left + (ϕ-1)(right-left)/(ϕ^2)
Amazing! x1' = cal_x1(left,right') = cal_x2(left,x1)
Разве не в этом прелесть симметрии в математике? Точно так же мы могли бы показать это x2' = cal_x2(left',right) = cal_x1(x1',right)
. Таким образом, он дает нам код ниже.
Я считаю, что эта картина лучше всего резюмирует мои предыдущие выводы. Помните, что проблема, которую мы решили, является частным случаем, когда и ввод, и вывод являются дискретными целыми значениями. Сам алгоритм также может применяться для поиска min / max для непрерывных унимодальных функций. Если обратить внимание на уменьшение пространства поиска после каждой итерации: скорость сходимости постоянна 1 / ϕ = 0,61803 (пространство поиска уменьшается на 38,196% на каждой итерации). В то время как бинарный поиск (поиск пополам) сходится линейно со скоростью 1/2.
Поиск по золотому сечению и бинарный поиск обычно имеют разные варианты использования:
1) бинарный поиск отсортированного массива; 2) поиск по золотому сечению унимодальной функции в заданном диапазоне. Замечательно работать над примером, в котором можно применить два алгоритма поиска.
В заключение я поделюсь менее актуальным, но очень кратким решением, чтобы показать красоту Python как языка программирования:
Ссылка
- Https://en.wikipedia.org/wiki/Golden-section_search
- Https://chemicalstatistician.wordpress.com/2013/04/22/using-the-bisection-method-with-the-golden-ratio-for-numerical-optimization/
- Https://ece.uwaterloo.ca/~dwharder/NumericalAnalysis/11Optimization/golden/
- Http://www.math.ucla.edu/~wotaoyin/math273a/slides/Lec3a_1d_search_273a_2015_f.pdf
- Http://www.ing.unitn.it/~bertolaz/2-teaching/2011-2012/AA-2011-2012-OPTIM/lezioni/slides-m1D.pdf
- Http://heath.cs.illinois.edu/scicomp/notes/chap06_8up.pdf
- Https://www.youtube.com/watch?v=hLm8xfwWYPw
- Https://www.youtube.com/watch?v=VBFuqglVW3c
- Https://wall.alphacoders.com/big.php?i=270595