Викиконспекты - Вклад участника [ru]

Вещественный двоичный поиск

2014-05-23T19:55:37Z

178.66.186.45: /* Способы закончить поиск */

'''Вещественный двоичный поиск''' {{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
{| class="wikitable"
! Способы || Плюсы || Минусы
|-
| 1) Окончание, когда рассматриваемый отрезок станет меньше заданного эпсилон. || Заданная точность найденного значения. || Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно, при больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения.
|-
| 2) Окончание, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. б) Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно, при быстром возрастании значений функции мы можем не найти такие границы, что значение на них различается менее, чем на заданное эпсилон.
|-
| 3) «Абсолютно точный поиск» Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен 0.
|-
| 4) «Итеративный способ» Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
|}

== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) == c //**
return mid; //**
else if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Примеры использования ==
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
* Если функция нестрого монотонна, то, убрав из приведенного выше алгоритма строки, отмеченные <tex>(**)</tex>, мы получим алгоритм, который будет находить <tex>x</tex> такой, что <tex>f(x) = c</tex> и <tex>f(x - \epsilon) < c</tex>.
== Замечания ==
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
* Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]

Вещественный двоичный поиск

2014-05-23T19:54:56Z

178.66.186.45: /* Способы закончить поиск */

'''Вещественный двоичный поиск''' {{---}} алгоритм поиска аргумента для заданного значения монотонной вещественной функции.

== Формулировка задачи ==
Пусть нам задана монотонная функция. Необходимо найти значение аргумента <tex>x</tex> этой функции, в которой она принимает определенное значение <tex>C</tex>.

[[Файл:Function.png]]

== Решение задачи ==
Применим идею двоичного поиска. Выберем такие границы, где значение функции точно больше и точно меньше заданного значения. Выберем значение в середине этого отрезка. Если оно меньше, чем заданное, то сместим левую границу в середину отрезка. В противном случае сместим правую границу. Далее повторим процесс сужения границ. Встает вопрос, когда остановиться. Есть несколько способов сделать это.

== Способы закончить поиск ==
{| class="wikitable"
! Способы || Плюсы || Минусы
|-
| 1) Окончание, когда рассматриваемый отрезок станет меньше заданного эпсилон. || Заданная точность найденного значения. || Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно, при больших значениях функции длина отрезка может никогда не уменьшиться до заданного значения.
|-
| 2) Окончание, когда значение функции на концах отрезках различается менее, чем на заданное эпсилон. || Значение функции от найденного значения имеет заданную точность. || а) Возможна большая погрешность, если функция будет очень медленно возрастать. б) Алгоритм может зациклиться. В компьютере мы работаем с конечным числом вещественных чисел. У чисел есть точность. Соответственно, при быстром возрастании значений функции мы можем не найти такие границы, что значение на них различается менее, чем на заданное эпсилон
|-
| 3) «Абсолютно точный поиск» Окончание, когда границы отрезка — два соседних по представлению значения в типе данных. Утверждается, что два числа — соседние, если середина их отрезка совпадает или с левой, или с правой границей. || Максимально возможная точность найденного значения. || Возможно плохое поведение, если искомый аргумент равен 0.
|-
| 4) «Итеративный способ» Выполнение конечного числа итераций. || У способа фиксированная погрешность. || Довольно плохая точность, если границы отрезка находятся на большом расстоянии.
|}

== Выбор границы отрезка для поиска==
Для начала найдем правую границу. Выберем произвольную положительную точку (например <tex>1</tex>). Будем удваивать ее до тех пор, пока значение функции в этой точке меньше заданного. Для того, чтобы найти левую границу выберем произвольную отрицательную точку (например <tex>-1</tex>). Будем удваивать ее до тех пор, пока значение в ней будет больше заданного значения.

== Псевдокод ==
<pre>
findLeft(c)
x = -1;
while f(x) > c
x = x * 2;
return x;
</pre>
<pre>
findRight(c)
x = 1;
while f(x) < c
x = x * 2;
return x;
</pre>
<pre>
binSearch(c)
left = findLeft(с);
right = findRight(с);
while left < right - eps //Здесь можно использовать другое условие выхода
mid = (left + right) / 2;
if f(mid) == c //**
return mid; //**
else if f(mid) < c
left = mid;
else
right = mid;
return l;
</pre>
== Примеры использования ==
* Классической задачей на вещественный двоичный поиск является задача поиска корня <tex>n</tex>-ой степени из числа <tex>x</tex>: <tex>\sqrt[n]{x}</tex>. При <tex>x \ge 1</tex> нижней границей для поиска будет <tex>1</tex>, а верхней {{---}} <tex>x</tex>.
* Если функция нестрого монотонна, то, убрав из приведенного выше алгоритма строки, отмеченные <tex>(**)</tex>, мы получим алгоритм, который будет находить <tex>x</tex> такой, что <tex>f(x) = c</tex> и <tex>f(x - \epsilon) < c</tex>.
== Замечания ==
* Необходимо отметить, то функция должна быть строго монотонна, если мы ищем конкретный корень и он единственный. Нестрого монотонна, если нам необходимо найти самый левый (правый) аргумент. Если же функция не монотонна, то данный алгоритм не найдет искомый аргумент, либо найдет аргумент, но он не будет единственным.
* Важным отличием от целочисленного поиска является то, что мы передвигаем границу ровно в середину отрезка (<tex>left = mid</tex>), а не со смещением внутрь отрезка (<tex>left = mid + 1</tex>).
== Источники ==
* [http://www.intuit.ru/department/algorithms/basicalgos/2/ Интернет университет, лекция сортировка и поиск]