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

Материал из Викиконспекты
Перейти к: навигация, поиск
м
Строка 15: Строка 15:
 
<tex> \frac{c}{b} = \phi </tex>
 
<tex> \frac{c}{b} = \phi </tex>
  
Где <tex> \phi </tex> - это некоторое отношение, в котором делим отрезок (точки <tex>x_1</tex> и <tex>x_2</tex> разбивают отрезок симметрично).
+
Где <tex> \phi </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 = \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 </tex> и <tex> a + b </tex>. Если <tex> L </tex> - длина исследуемого отрезка, тогда:
  
Формально для поиска минимума (для максимума - делается аналогично) функции <tex> f </tex>:
+
<tex> (\frac{b + c}{a} = \phi;\; b + c = L - a) \Rightarrow</tex>
 +
 
 +
<tex> a = \frac{L}{\phi + 1} </tex>
 +
 
 +
<tex> a + b = L - c = L - a = L - \frac{L}{\phi + 1}</tex>
 +
 
 +
Причем, заметим что в силу того что <tex>\phi</tex> - золотое сечение, то <tex>\frac{1}{\phi + 1} = 2 - \phi</tex>.
 +
 
 +
Формально для поиска минимума (для максимума - делается аналогично) функции <tex> f </tex> делаем следующее:
  
 
:'''Шаг 1''':
 
:'''Шаг 1''':
Строка 31: Строка 40:
 
::<tex>x_2 = rbound - \frac{rbound - lbound}{\phi + 1}</tex>
 
::<tex>x_2 = rbound - \frac{rbound - lbound}{\phi + 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(x_1) < f(x_2)</tex>
+
:: если <tex>f_1 < f_2</tex>, тогда
::
+
::: <tex>rbound = x_2</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>lbound = x_1</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>
 +
:'''Шаг 3''':
 +
:: если точность <tex>|rbound - lbound| < \varepsilon</tex> нас устраивает, тогда останавливаемся, и искомая точка <tex>x = \frac{lbound + rbound}{2}</tex>, иначе назад к шагу 2
  
:'''Шаг 3''':
 
 
===Псевдокод===
 
===Псевдокод===
 +
phi = (1 + sqrt(5)) / 2
 +
resphi = 2 - phi
 +
 +
goldenSectionSearch(f, lbound, rbound, eps)
 +
    x1 = lbound + resphi * (rbound - lbound)
 +
    x2 = rbound - resphi * (rbound - lbound)
 +
    f1 = f(x1)
 +
    f2 = f(x2)
 +
   
 +
    do
 +
        if f1 < f2:
 +
            rbound = x2
 +
            x2 = x1
 +
            f2 = f1
 +
            x1 = lbound + resphi * (rbound - lbound)
 +
            f1 = f(x1)
 +
        else:
 +
            lbound = x1
 +
            x1 = x2
 +
            f1 = f2
 +
            x2 = rbound - resphi * (rbound - lbound)
 +
            f2 = f(x2)
 +
    while (abs(rbound - lbound) < eps)
 +
   
 +
    return (x1 + x2) / 2
 +
==Время работы==
 +
На каждой итерации исследуемый отрезок сокращается в <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> log_{\phi}(\frac{L}{\varepsilon})</tex>.
 +
Если удельный вес вычисления функции <tex> f </tex> достаточно большой, тогда получим ускорение работы примерно в 2,3 раз по сравнению с неулучшенным троичным поиском.
  
 
+
==См также==
==Асимптотика==
+
*[[Троичный поиск]]
 
 
  
 
==Ссылки==
 
==Ссылки==
[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] (english)
+
*[http://en.wikipedia.org/wiki/Golden_section_search Wikipedia - Golden section search] (english)

Версия 20:19, 15 июня 2011

Эта статья находится в разработке!

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

Алгоритм

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

Goldensection.gif

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

[math] \frac{a + b}{c} = \frac{b + c}{a} = \phi [/math]

[math] \frac{a}{b} = \phi [/math]

[math] \frac{c}{b} = \phi [/math]

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

Тогда:

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

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

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

[math] (\frac{b + c}{a} = \phi;\; b + c = L - a) \Rightarrow[/math]

[math] a = \frac{L}{\phi + 1} [/math]

[math] a + b = L - c = L - a = L - \frac{L}{\phi + 1}[/math]

Причем, заметим что в силу того что [math]\phi[/math] - золотое сечение, то [math]\frac{1}{\phi + 1} = 2 - \phi[/math].

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

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

Псевдокод

phi = (1 + sqrt(5)) / 2
resphi = 2 - phi

goldenSectionSearch(f, lbound, rbound, eps)
   x1 = lbound + resphi * (rbound - lbound)
   x2 = rbound - resphi * (rbound - lbound)
   f1 = f(x1)
   f2 = f(x2)
   
   do
       if f1 < f2:
           rbound = x2
           x2 = x1
           f2 = f1
           x1 = lbound + resphi * (rbound - lbound)
           f1 = f(x1)
       else:
           lbound = x1
           x1 = x2
           f1 = f2
           x2 = rbound - resphi * (rbound - lbound)
           f2 = f(x2)
   while (abs(rbound - lbound) < eps)
   
   return (x1 + x2) / 2

Время работы

На каждой итерации исследуемый отрезок сокращается в [math]\phi[/math] раз и делается один расчет функции, до тех пор, пока не станет [math]|L| \lt \varepsilon[/math]. Если считать, что одна итерация выполняется за 1 времени, то потребуется [math] n [/math] операций, чтобы: [math]L \cdot (\frac{1}{\phi})^n \lt \varepsilon \Rightarrow n = [log_{\phi}(\frac{L}{\varepsilon})][/math].

Значит время работы можно оценивать как [math] log_{\phi}(\frac{L}{\varepsilon})[/math]. Если удельный вес вычисления функции [math] f [/math] достаточно большой, тогда получим ускорение работы примерно в 2,3 раз по сравнению с неулучшенным троичным поиском.

См также

Ссылки