Вещественный двоичный поиск — различия между версиями
(→Формулировка задачи) |
|||
| Строка 27: | Строка 27: | ||
== Псевдокод == | == Псевдокод == | ||
<code> | <code> | ||
| − | '''double''' findLeftBoard( | + | '''double''' findLeftBoard(C : '''double'''): |
x = -1 | x = -1 | ||
| − | '''while''' f(x) > | + | '''while''' f(x) > C |
x = x * 2 | x = x * 2 | ||
'''return''' x | '''return''' x | ||
</code> | </code> | ||
<code> | <code> | ||
| − | '''double''' findRightBoard( | + | '''double''' findRightBoard(C : '''double'''): |
x = 1 | x = 1 | ||
| − | '''while''' f(x) < | + | '''while''' f(x) < C |
x = x * 2 | x = x * 2 | ||
'''return''' x | '''return''' x | ||
</code> | </code> | ||
<code> | <code> | ||
| − | '''double''' binSearch( | + | '''double''' binSearch(C : '''double'''): |
| − | left = findLeftBoard( | + | left = findLeftBoard(C) |
| − | right = findRightBoard( | + | right = findRightBoard(C) |
'''while''' right - left < eps <font color=green> // Здесь можно использовать другое условие выхода </font> | '''while''' right - left < eps <font color=green> // Здесь можно использовать другое условие выхода </font> | ||
mid = (left + right) / 2 | mid = (left + right) / 2 | ||
| − | '''if''' f(mid) < | + | '''if''' f(mid) < C |
left = mid | left = mid | ||
'''else''' | '''else''' | ||
Версия 01:10, 11 июня 2014
Вещественный двоичный поиск (англ. Bisection method)— алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
Содержание
Формулировка задачи
Пусть нам задана монотонная функция и какое-то значение этой функции. Необходимо найти значение аргумента этой функции, такое, что .
Решение задачи
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
Способы закончить поиск
| Способы | Плюсы | Минусы | Оценка на число итераций |
|---|---|---|---|
| Окончание, когда рассматриваемый отрезок станет меньше заданной погрешности . | Заданная точность найденного значения. | Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел, у которых есть точность. При больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения. | В данном случае нам нужно рассмотреть чисел примерное число итераций . |
| Окончание, когда значение функции на концах отрезках различается менее, чем на заданную погрешность . | Значение функции от найденного значения имеет заданную точность. | а) Возможна большая погрешность, если функция будет очень медленно возрастать. б) Может зациклиться по той же причине, что и в первом способе. |
Аналогичная с первым случаем логика, примерное число итераций . |
| «Абсолютно точный поиск» Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. |
Максимально возможная точность найденного значения. | Возможно плохое поведение, если искомый аргумент равен нулю. | При работе с числами с плавающей точкой количество итераций зависит от плотности чисел на данном отрезке. При работе с числами фиксированной точности количество итераций аналогично первому и второму случаю равно . |
| «Итеративный способ» Выполнение конечного числа итераций. |
У способа фиксированная погрешность. | Довольно плохая точность, если границы отрезка находятся на большом расстоянии. | Выполняется заданное количество итераций. |
Выбор границы отрезка для поиска
Для начала найдем левую границу, выберем произвольную отрицательную точку (например ). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения. Для того, чтобы найти правую границу, выберем произвольную положительную точку (например ). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного.
Псевдокод
double findLeftBoard(C : double):
x = -1
while f(x) > C
x = x * 2
return x
double findRightBoard(C : double):
x = 1
while f(x) < C
x = x * 2
return x
double binSearch(C : double):
left = findLeftBoard(C)
right = findRightBoard(C)
while right - left < eps // Здесь можно использовать другое условие выхода
mid = (left + right) / 2
if f(mid) < C
left = mid
else
right = mid
return (left + right) / 2
Замечания
- Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
- Классической задачей на вещественный двоичный поиск является задача поиска корня -ой степени из числа : . При нижней границей для поиска будет , а верхней — .
