Поиск с помощью золотого сечения — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Псевдокод)
Строка 1: Строка 1:
'''Поиск с помощью золотого сечения''' (англ. ''Golden section search'') {{---}} это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выигрыш в производительности.
+
'''Поиск с помощью золотого сечения''' (англ. ''Golden section search'') {{---}} это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выигрыш в производительности, т.к. каждый новый отрезок в <tex>\approx 1.618 </tex> раз короче предыдущего (против <tex>1.5</tex> у троичного поиска) и сходится он в <tex>\log_{\frac32} \left(\dfrac{1 + \sqrt{5}}{2}\right) \approx 1.1868 </tex> быстрее, чем в троичном поиске, соответственно, в <tex> \approx 2.3736 </tex> раза меньше вычислений. 
  
 
==Алгоритм==
 
==Алгоритм==
Строка 20: Строка 20:
 
Тогда:
 
Тогда:
  
<tex> a + b = \varphi c, a = \varphi b, c = \varphi b</tex>, откуда получаем <tex> \varphi + 1 = \varphi^2 \Rightarrow \varphi = \dfrac{1 + \sqrt{5}}{2}</tex>  &nbsp; (тот корень уравнения, который меньше нуля, по понятным причинам отбросили).
+
<tex> a + b = \varphi c, a = \varphi b, c = \varphi b</tex>, откуда получаем <tex> \varphi + 1 = \varphi^2 \Rightarrow \varphi = \dfrac{1 + sqrt{5}}{2}</tex>  &nbsp; (тот корень уравнения, который меньше нуля, по понятным причинам отбросили).
  
 
Это число совпадает с золотым сечением. Отсюда название метода.  
 
Это число совпадает с золотым сечением. Отсюда название метода.  

Версия 20:44, 7 июня 2015

Поиск с помощью золотого сечения (англ. Golden section search) — это улучшение наивной реализации троичного поиска, служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выигрыш в производительности, т.к. каждый новый отрезок в [math]\approx 1.618 [/math] раз короче предыдущего (против [math]1.5[/math] у троичного поиска) и сходится он в [math]\log_{\frac32} \left(\dfrac{1 + \sqrt{5}}{2}\right) \approx 1.1868 [/math] быстрее, чем в троичном поиске, соответственно, в [math] \approx 2.3736 [/math] раза меньше вычислений.

Алгоритм

Мотивация

Рассмотрим одну итерацию алгоритма троичного поиска. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.

Пусть [math]l[/math] и [math]r[/math] левая и правая граница исследуемого отрезка. Точки [math]x_1[/math] и [math]x_2[/math] разбивают отрезок на три части длины [math]a, b, c[/math] соответственно.

Потребуем, чтобы одновременно выполнялось:

[math] \dfrac{a + b}{c} = \dfrac{b + c}{a} = \varphi [/math]

[math] \dfrac{a}{b} = \varphi [/math]

[math] \dfrac{c}{b} = \varphi [/math]

Где [math] \varphi [/math] — это некоторое отношение, в котором мы делим отрезок (точки [math]x_1[/math] и [math]x_2[/math] разбивают отрезок симметрично).

Тогда:

[math] a + b = \varphi c, a = \varphi b, c = \varphi b[/math], откуда получаем [math] \varphi + 1 = \varphi^2 \Rightarrow \varphi = \dfrac{1 + sqrt{5}}{2}[/math]   (тот корень уравнения, который меньше нуля, по понятным причинам отбросили).

Это число совпадает с золотым сечением. Отсюда название метода.

Свойства золотого сечения

Для реализации алгоритма нам потребуется найти [math] a [/math] и [math] a + b [/math]. Если [math] L [/math] — длина исследуемого отрезка, тогда:

[math] \left(\dfrac{b + c}{a} = \varphi;\; b + c = L - a \right) \Rightarrow[/math]

[math] a = \dfrac{L}{\varphi + 1} [/math]

[math] a + b = L - c = L - a = L - \dfrac{L}{\varphi + 1}[/math]

Заметим, что в силу того, что [math]\varphi[/math] — золотое сечение, то [math]\dfrac{1}{\varphi + 1} = 2 - \varphi[/math].

Итоговый алгоритм выбора границ

Формально для поиска минимума (для максимума — делается аналогично) функции [math] f [/math] делаем следующее:

Шаг 1:
Определяем границы поиска [math]l[/math] и [math]r[/math], затем устанавливаем текущее разбиение:
[math]x_1 = l + \dfrac{r - l}{\varphi + 1}[/math]
[math]x_2 = r - \dfrac{r - l}{\varphi + 1}[/math]
и вычислим функцию на них: [math]f_1 = f(x_1), f_2 = f(x_2)[/math]
Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).
Шаг 2:
если [math]f_1 \lt f_2[/math], тогда
[math]r = x_2[/math]
[math]x_2 = x_1, f_2 = f_1[/math]
[math]x_1 = l + \dfrac{r - l}{\varphi + 1},\; f_1 = f(x_1)[/math]
иначе:
[math]l = x_1[/math]
[math]x_1 = x_2, f_1 = f_2[/math]
[math]x_2 = r - \dfrac{r - l}{\varphi + 1},\; f_2 = f(x_2)[/math]
Шаг 3:
если точность [math]|r - l| \lt \varepsilon[/math] нас устраивает, тогда останавливаемся, и искомая точка [math]x = \dfrac{l + r}{2}[/math], иначе назад к шагу 2

Псевдокод

int goldenSectionSearch(f, l, r, eps):
    double phi = (1 + sqrt(5)) / 2
    double resphi = 2 - phi
    int x1 = l + resphi * (r - l)
    int x2 = r - resphi * (r - l)
    int f1 = f(x1)
    int f2 = f(x2)
     do
       if f1 < f2
             int r = x2
             x2 = x1
             f2 = f1
             x1 = l + resphi * (r - l)
             f1 = f(x1)
       else
             int l = x1
             x1 = x2
             f1 = f2
             x2 = r - resphi * (r - l)
             f2 = f(x2)
     while abs(r - l) > eps
     return (x1 + x2) / 2

Время работы

Так как на каждой итерации мы считаем одно значение функции и уменьшаем область поиска в [math] \varphi [/math] раз, пока [math] r - l \gt \varepsilon[/math], то время работы алгоритма составит [math] \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)[/math].

Если удельный вес вычисления функции [math] f [/math] достаточно большой, тогда получим ускорение работы по сравнению с неулучшенным троичным поиском ([math] \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)[/math] против [math]2 \log_{\frac32} \left(\dfrac{r - l}{\varepsilon}\right)[/math].

См также

Источники информации