Вещественный двоичный поиск — различия между версиями
(→Способы закончить поиск) |
(→Способы закончить поиск) |
||
| Строка 9: | Строка 9: | ||
== Способы закончить поиск == | == Способы закончить поиск == | ||
# Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы: | # Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы: | ||
| − | + | * Алгоритм с большой точностью найдет найдет значение аргумента | |
| − | + | * Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения | |
# Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное малое значение. | # Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное малое значение. | ||
| − | + | * В отличии от предыдущего, не зацикливается при больших значениях функции. | |
| − | + | * Возможна большая погрешность, если функция будет очень медленно возрастать | |
# Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних значения в типе данных. | # Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних значения в типе данных. | ||
Версия 19:24, 15 июня 2011
Вещественный двоичный поиск - алгоритм поиска аргумента для заданного значения монотонной вещественной функции.
Формулировка задачи
Пусть нам задана монотонная функция. Необходимо найти место, где значение функции становится меньше, чем какое-то заданное значение.
Решение задачи
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.
Способы закончить поиск
- Первый способ заключается в том, чтобы остановиться, когда рассматриваемый отрезок станет меньше заданного эпсилон. Но у этого подхода есть свои плюсы и минусы:
* Алгоритм с большой точностью найдет найдет значение аргумента * Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно при больших значениях функции, длина отрезка может никогда не уменьшиться до заданного значения
- Второй способ менее точен. Предлагается заканчивать алгоритм, когда значение функции на концах отрезках различается менее, чем на заданное малое значение.
* В отличии от предыдущего, не зацикливается при больших значениях функции. * Возможна большая погрешность, если функция будет очень медленно возрастать
- Абсолютно точный поиск. Вспомним о том, что вещественный числа в компьютере дискретным. Будем завершать поиск, когда границы отрезка - два соседних значения в типе данных.
