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

Материал из Викиконспекты
Перейти к: навигация, поиск
м (rollbackEdits.php mass rollback)
 
(не показано 49 промежуточных версий 10 участников)
Строка 1: Строка 1:
'''Поиск с помощью золотого сечения''' (''Golden section search'') - это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащий для поиска минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации). За счет этого достигается выйгрыш в производительности.
+
'''Поиск с помощью золотого сечения''' (англ. ''Golden section search'') {{---}} это улучшение наивной реализации [[Троичный поиск|троичного поиска]], служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации).  
  
 
==Алгоритм==
 
==Алгоритм==
Рассмотрим одну итерацию алгоритма троичного поиска. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.  
+
===Обоснование===
 +
Рассмотрим одну итерацию алгоритма [[Троичный поиск|троичного поиска]]. Попробуем подобрать такое разбиение отрезка на три части, чтобы на следующей итерации одна из точек нового разбиения совпала с одной из точек текущего разбиения. Тогда в следующий раз не придется считать функцию в двух точках, так как в одной она уже была посчитана.  
  
[[Файл:Goldensection.gif|220px]]
+
[[Файл:new_seg.gif|right|450px|Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).]]
  
Точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок на три части. Потребуем, чтобы одновременно выполнялось:  
+
Для этого нам потребуется, чтобы одновременно выполнялись равенства:
  
<tex> \frac{a + b}{c} = \frac{b + c}{a} = \phi </tex>
+
<tex> \dfrac{a + b}{c} = \dfrac{b + c}{a} = \varphi </tex>
  
<tex> \frac{a}{b} = \phi </tex>
+
Расстояние от <tex>l</tex> до <tex>x1 = a + b - c = a' </tex>, от <tex>x2 </tex> до <tex> r = b = c'</tex>, от <tex>х1 </tex> до <tex> х2 = c - b = b'</tex>. Т.е. если мы подставим <tex>a', b', c'</tex> в старое соотношение <tex> \dfrac{a + b}{c} </tex>, то получится <tex> \dfrac {a + b - c + c - b}{b} = \dfrac{a}{b}</tex>.
  
<tex> \frac{c}{b} = \phi </tex>
+
<tex> \dfrac{a}{b} = \varphi </tex>
  
Где <tex> \phi </tex> - это некоторое отношение, в котором мы делим отрезок (точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок симметрично).
+
<tex> \dfrac{c}{b} = \varphi </tex>
 +
 
 +
Где <tex> \varphi </tex> {{---}} это некоторое отношение, в котором мы делим отрезок (точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок симметрично).
  
 
Тогда:
 
Тогда:
  
<tex> a + b = \phi c, a = \phi b, c = \phi b</tex>, откуда получаем <tex> \phi + 1 = \phi^2 \Rightarrow \phi = \frac{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; (тот корень уравнения, который меньше нуля, по понятным причинам отбросили).
  
Это число совпадает с золотым сечением. Отсюда название метода.  
+
Это число совпадает с золотым сечением. Отсюда название метода.
  
Для реализации алгоритма нам потребуется найти <tex> a </tex> и <tex> a + b </tex>. Если <tex> L </tex> - длина исследуемого отрезка, тогда:  
+
===Свойства золотого сечения===
 +
Для реализации алгоритма нам потребуется найти <tex> a </tex> и <tex> a + b </tex>. Если <tex> L </tex> {{---}} длина исследуемого отрезка, тогда:  
  
<tex> (\frac{b + c}{a} = \phi;\; b + c = L - a) \Rightarrow</tex>
+
<tex> \left(\dfrac{b + c}{a} = \varphi;\; b + c = L - a \right) \Rightarrow</tex>
  
<tex> a = \frac{L}{\phi + 1} </tex>
+
<tex> a = \dfrac{L}{\varphi + 1} </tex>
  
<tex> a + b = L - c = L - a = L - \frac{L}{\phi + 1}</tex>
+
<tex> a + b = L - c = L - a = L - \dfrac{L}{\varphi + 1}</tex>
  
Причем, заметим что в силу того что <tex>\phi</tex> - золотое сечение, то <tex>\frac{1}{\phi + 1} = 2 - \phi</tex>.
+
Заметим, что в силу того, что <tex>\varphi</tex> {{---}} золотое сечение, то <tex>\dfrac{1}{\varphi + 1} = 2 - \varphi</tex>.
  
Формально для поиска минимума (для максимума - делается аналогично) функции <tex> f </tex> делаем следующее:
+
===Итоговый алгоритм выбора границ===
 +
Формально для поиска минимума (для максимума {{---}} делается аналогично) функции <tex> f </tex> делаем следующее:
  
 
:'''Шаг 1''':
 
:'''Шаг 1''':
::Определяем границы поиска <tex>lbound</tex> и <tex>rbound</tex>, затем устанавливаем текущее разбиение:
+
::Определяем границы поиска <tex>l</tex> и <tex>r</tex>, затем устанавливаем текущее разбиение:
::<tex>x_1 = lbound + \frac{rbound - lbound}{\phi + 1}</tex>  
+
::<tex>x_1 = l + \dfrac{r - l}{\varphi + 1}</tex>  
::<tex>x_2 = rbound - \frac{rbound - lbound}{\phi + 1}</tex>
+
::<tex>x_2 = r - \dfrac{r - l}{\varphi + 1}</tex>
::и вычислем функцию на них: <tex>f_1 = f(x_1), f_2 = f(x_2)</tex>
+
::и вычислим функцию на них: <tex>f_1 = f(x_1), f_2 = f(x_2)</tex>
[[Файл:Nextsection.gif|thumb|380px|Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).]]
+
 
 
:'''Шаг 2''':  
 
:'''Шаг 2''':  
 
:: если <tex>f_1 < f_2</tex>, тогда
 
:: если <tex>f_1 < f_2</tex>, тогда
::: <tex>rbound = x_2</tex>
+
::: <tex>r = x_2</tex>
 
::: <tex>x_2 = x_1, f_2 = f_1</tex>
 
::: <tex>x_2 = x_1, f_2 = f_1</tex>
::: <tex>x_1 = lbound + \frac{rbound - lbound}{\phi + 1},\; f_1 = f(x_1)</tex>  
+
::: <tex>x_1 = l + \dfrac{r - l}{\varphi + 1},\; f_1 = f(x_1)</tex>  
 
:: иначе:
 
:: иначе:
::: <tex>lbound = x_1</tex>
+
::: <tex>l = x_1</tex>
 
::: <tex>x_1 = x_2, f_1 = f_2</tex>
 
::: <tex>x_1 = x_2, f_1 = f_2</tex>
::: <tex>x_2 = rbound - \frac{rbound - lbound}{\phi + 1},\; f_2 = f(x_2)</tex>
+
::: <tex>x_2 = r - \dfrac{r - l}{\varphi + 1},\; f_2 = f(x_2)</tex>
 
:'''Шаг 3''':
 
:'''Шаг 3''':
:: если точность <tex>|rbound - lbound| < \varepsilon</tex> нас устраивает, тогда останавливаемся, и искомая точка <tex>x = \frac{lbound + rbound}{2}</tex>, иначе назад к шагу 2
+
:: если точность <tex>|r - l| < \varepsilon</tex> нас устраивает, тогда останавливаемся, и искомая точка <tex>x = \dfrac{l + r}{2}</tex>, иначе назад к шагу 2
  
 
===Псевдокод===
 
===Псевдокод===
  phi = (1 + sqrt(5)) / 2
+
 
resphi = 2 - phi
+
  '''double''' goldenSectionSearch(f: '''double -> double''', l: '''double''', r: '''double''', eps: '''double'''):
+
    phi = (1 + sqrt(5)) / 2
goldenSectionSearch(f, lbound, rbound, eps)
+
    resphi = 2 - phi
    x1 = lbound + resphi * (rbound - lbound)
+
    x1 = l + resphi * (r - l)
    x2 = rbound - resphi * (rbound - lbound)
+
    x2 = r - resphi * (r - l)
    f1 = f(x1)
+
    f1 = f(x1)
    f2 = f(x2)
+
    f2 = f(x2)
   
+
    '''do'''
    do
+
      '''if''' f1 < f2
        if f1 < f2:
+
        r = x2
            rbound = x2
+
        x2 = x1
            x2 = x1
+
        f2 = f1
            f2 = f1
+
        x1 = l + resphi * (r - l)
            x1 = lbound + resphi * (rbound - lbound)
+
        f1 = f(x1)
            f1 = f(x1)
+
      '''else'''
        else:
+
        l = x1
            lbound = x1
+
        x1 = x2
            x1 = x2
+
        f1 = f2
            f1 = f2
+
        x2 = r - resphi * (r - l)
            x2 = rbound - resphi * (rbound - lbound)
+
        f2 = f(x2)
            f2 = f(x2)
+
    '''while''' abs(r - l) < eps
    while (abs(rbound - lbound) < eps)
+
    '''return''' (x1 + x2) / 2
   
+
 
    return (x1 + x2) / 2
+
===Ошибки псевдокода===
 +
1. Используются вычислительно-неустойчивые формулы.
 +
2. Учитывается только абсолютная длина отрезка.
 +
Подробнее:
 +
http://mech.math.msu.su/~iliagri/zip/sem2book.pdf
 +
 
 
==Время работы==
 
==Время работы==
На каждой итерации исследуемый отрезок сокращается в <tex>\phi</tex> раз и делается один расчет функции, до тех пор, пока не станет <tex>|L| < \varepsilon</tex>. Если считать, что одна итерация выполняется за 1 времени, то потребуется <tex> n </tex> операций, чтобы: <tex>L \cdot (\frac{1}{\phi})^n < \varepsilon \Rightarrow n = [log_{\phi}(\frac{L}{\varepsilon})]</tex>.
+
Так как на каждой итерации мы считаем одно значение функции и уменьшаем область поиска в <tex> \varphi </tex> раз, пока <tex> r - l > \varepsilon</tex>,
 +
то время работы алгоритма составит
 +
<tex> \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)</tex>.
  
Значит время работы можно оценивать как <tex> log_{\phi}(\frac{L}{\varepsilon})</tex>.
+
Если удельный вес вычисления функции <tex> f </tex> достаточно большой, тогда получим ускорение работы по сравнению с неулучшенным [[Троичный поиск|троичным поиском]] (<tex> \log_{\varphi}\left(\dfrac{r - l}{\varepsilon}\right)</tex> против <tex>2 \log_{\frac32} \left(\dfrac{r - l}{\varepsilon}\right)</tex>.
Если удельный вес вычисления функции <tex> f </tex> достаточно большой, тогда получим ускорение работы примерно в 2,3 раз по сравнению с неулучшенным троичным поиском.
+
 
 +
За счет этого достигается выигрыш в производительности, т.к. каждый новый отрезок в <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> раза меньше вычислений. 
  
 
==См также==
 
==См также==
 
*[[Троичный поиск]]
 
*[[Троичный поиск]]
 +
*[[Целочисленный двоичный поиск]]
  
==Ссылки==
+
==Источники информации==
*[http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F Википедия - Метод золотого сечения]
+
*[http://ru.wikipedia.org/wiki/%D0%9C%D0%B5%D1%82%D0%BE%D0%B4_%D0%B7%D0%BE%D0%BB%D0%BE%D1%82%D0%BE%D0%B3%D0%BE_%D1%81%D0%B5%D1%87%D0%B5%D0%BD%D0%B8%D1%8F Википедия {{---}} Метод золотого сечения]
 
+
*[http://en.wikipedia.org/wiki/Golden_section_search Wikipedia {{---}} Golden section search]  
*[http://en.wikipedia.org/wiki/Golden_section_search Wikipedia - Golden section search] (english)
 
  
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 +
[[Категория:Алгоритмы поиска]]

Текущая версия на 19:05, 4 сентября 2022

Поиск с помощью золотого сечения (англ. Golden section search) — это улучшение наивной реализации троичного поиска, служащего для нахождения минимума/максимума функции. При простом троичном поиске на каждой итерации функция вычисляется в двух точках. Метод же золотого сечения требует вычисления лишь в одной точке (за исключением первой итерации).

Алгоритм

Обоснование

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

Старая точка x1 уже делит отрезок в нужном отношении, поэтому нет необходимости вычислять ее заново (красным отмечены новые значения точек).

Для этого нам потребуется, чтобы одновременно выполнялись равенства:

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

Расстояние от [math]l[/math] до [math]x1 = a + b - c = a' [/math], от [math]x2 [/math] до [math] r = b = c'[/math], от [math]х1 [/math] до [math] х2 = c - b = b'[/math]. Т.е. если мы подставим [math]a', b', c'[/math] в старое соотношение [math] \dfrac{a + b}{c} [/math], то получится [math] \dfrac {a + b - c + c - b}{b} = \dfrac{a}{b}[/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]
Шаг 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

Псевдокод

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

Ошибки псевдокода

1. Используются вычислительно-неустойчивые формулы. 2. Учитывается только абсолютная длина отрезка. Подробнее: http://mech.math.msu.su/~iliagri/zip/sem2book.pdf

Время работы

Так как на каждой итерации мы считаем одно значение функции и уменьшаем область поиска в [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].

За счет этого достигается выигрыш в производительности, т.к. каждый новый отрезок в [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] раза меньше вычислений.

См также

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