http://neerc.ifmo.ru/wiki/api.php?action=feedcontributions&user=89.110.19.74&feedformat=atomВикиконспекты - Вклад участника [ru]2024-03-28T13:13:02ZВклад участникаMediaWiki 1.30.0http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA&diff=38552Вещественный двоичный поиск2014-06-11T11:18:21Z<p>89.110.19.74: Отмена правки 38551 участника 89.110.19.74 (обсуждение)</p>
<hr />
<div>'''Вещественный двоичный поиск''' (англ. ''Bisection method''){{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.<br />
<br />
== Формулировка задачи == <br />
Пусть нам задана монотонная функция <tex> f </tex> и какое-то значение <tex> C </tex> этой функции. Необходимо найти значение аргумента <tex> x </tex> этой функции, такое, что <tex> f(x) = C </tex>.<br />
<br />
[[Файл:Function.png]]<br />
<br />
== Решение задачи ==<br />
Применим идею [[целочисленный двоичный поиск | двоичного поиска]]. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.<br />
<br />
=== Способы закончить поиск ===<br />
{| class="wikitable"<br />
! Способы || Плюсы || Минусы || Оценка на число итераций<br />
|-<br />
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности <tex> \varepsilon </tex>. || Заданная точность найденного значения. || Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. || В данном случае нам нужно рассмотреть <tex dpi=130> \genfrac{}{}{}{}{R - L}{\varepsilon} </tex> чисел <tex> \Rightarrow </tex> примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.<br />
|-<br />
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность <tex> \varepsilon </tex>. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. <br> б) Может зациклиться по той же причине, что и в первом способе. || Аналогичная с первым случаем логика, примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{f(R) - f(L)}{\varepsilon}) </tex>.<br />
|-<br />
| «Абсолютно точный поиск» <br> Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен нулю. || При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности <tex>\varepsilon</tex> количество итераций аналогично первому и второму случаю равно <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.<br />
|-<br />
| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.<br />
|}<br />
<br />
=== Выбор границы отрезка для поиска ===<br />
Для начала найдем левую границу, выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.<br />
<br />
== Псевдокод ==<br />
<code><br />
'''double''' findLeftBoard(C : '''double'''): <br />
x = -1<br />
'''while''' f(x) > C <br />
x = x * 2<br />
'''return''' x <br />
</code><br />
<code><br />
'''double''' findRightBoard(C : '''double'''):<br />
x = 1<br />
'''while''' f(x) < C<br />
x = x * 2<br />
'''return''' x<br />
</code><br />
<code><br />
'''double''' binSearch(C : '''double'''):<br />
left = findLeftBoard(C)<br />
right = findRightBoard(C)<br />
'''while''' right - left < eps <font color=green> // Здесь можно использовать другое условие выхода </font><br />
mid = (left + right) / 2<br />
'''if''' f(mid) < C<br />
left = mid<br />
'''else'''<br />
right = mid<br />
'''return''' (left + right) / 2<br />
</code><br />
<br />
== Замечания ==<br />
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.<br />
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \geqslant 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.<br />
<br />
== Источники информации == <br />
* [http://en.wikipedia.org/wiki/Bisection_method Bisection method {{---}} Wikipedia]<br />
* [http://www.youtube.com/watch?v=qkLLcdgJj_o Видеолекция "сортировка и поиск"]<br />
* [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch Binary search {{---}} Topcoder]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Двоичный поиск]]</div>89.110.19.74http://neerc.ifmo.ru/wiki/index.php?title=%D0%92%D0%B5%D1%89%D0%B5%D1%81%D1%82%D0%B2%D0%B5%D0%BD%D0%BD%D1%8B%D0%B9_%D0%B4%D0%B2%D0%BE%D0%B8%D1%87%D0%BD%D1%8B%D0%B9_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA&diff=38551Вещественный двоичный поиск2014-06-11T11:17:25Z<p>89.110.19.74: </p>
<hr />
<div>'''Вещественный двоичный поиск''' (англ. ''Bisection method''){{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.<br />
<br />
== Формулировка задачи == <br />
Пусть нам задана монотонная функция <tex> f </tex> и какое-то значение <tex> C </tex> этой функции. Необходимо найти значение аргумента <tex> x </tex> этой функции, такое, что <tex> f(x) = C </tex>.<br />
<br />
[[Файл:Function.png]]<br />
<br />
== Решение задачи ==<br />
Применим идею [[целочисленный двоичный поиск | двоичного поиска]]. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.<br />
<br />
=== Способы закончить поиск ===<br />
{| class="wikitable"<br />
! Способы || Плюсы || Минусы || Оценка на число итераций<br />
|-<br />
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности <tex> \varepsilon </tex>. || Заданная точность найденного значения. || Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. || В данном случае нам нужно рассмотреть <tex dpi=130> \genfrac{}{}{}{}{R - L}{\varepsilon} </tex> чисел <tex> \Rightarrow </tex> примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.<br />
|-<br />
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность <tex> \varepsilon </tex>. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. <br> б) Может зациклиться по той же причине, что и в первом способе. || Аналогичная с первым случаем логика, примерное число итераций <tex dpi=130> \log(\genfrac{}{}{}{}{f(R) - f(L)}{\varepsilon}) </tex>.<br />
|-<br />
| «Абсолютно точный поиск» <br> Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен нулю. || При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности <tex>\varepsilon</tex> количество итераций аналогично первому и второму случаю равно <tex dpi=130> \log(\genfrac{}{}{}{}{R - L}{\varepsilon}) </tex>.<br />
|-<br />
| «Итеративный способ» <br> Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии. || Выполняется заданное количество итераций.<br />
|}<br />
<br />
=== Выбор границы отрезка для поиска ===<br />
Для начала найдем левую границу, выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.<br />
<br />
== Псевдокод ==<br />
<code><br />
'''double''' findLeftBoard(C : '''double'''): <br />
x = -1<br />
'''while''' f(x) > C <br />
x = x * 2<br />
'''return''' x <br />
</code><br />
<code><br />
'''double''' findRightBoard(C : '''double'''):<br />
x = 1<br />
'''while''' f(x) < C<br />
x = x * 2<br />
'''return''' x<br />
</code><br />
<code><br />
'''double''' binSearch(C : '''double'''):<br />
left = findLeftBoard(C)<br />
right = findRightBoard(C)<br />
'''while''' right - left < eps <font color=green> // Здесь можно использовать другое условие выхода </font><br />
mid = (left + right) / 2<br />
'''if''' f(mid) < C<br />
left = mid<br />
'''else'''<br />
right = mid<br />
'''return''' (left + right) / 2<br />
</code><br />
<br />
== Замечания ==<br />
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.<br />
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \geqslant 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.<br />
<br />
== См. также ==<br />
* [[Целочисленный двоичный поиск]]<br />
<br />
== Источники информации == <br />
* [http://en.wikipedia.org/wiki/Bisection_method Bisection method {{---}} Wikipedia]<br />
* [http://www.youtube.com/watch?v=qkLLcdgJj_o Видеолекция "сортировка и поиск"]<br />
* [http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binarySearch Binary search {{---}} Topcoder]<br />
<br />
[[Категория: Дискретная математика и алгоритмы]]<br />
[[Категория: Двоичный поиск]]</div>89.110.19.74