Эта статья посвящена двум алгоритмам поиска — дихотомии и градиентному спуску (как ни странно, на хабре не писали ни про один из них).
Дихотомия — поиск делением пополам.
Допустим есть отсортированный массив чисел:
a[10] = {0,15,23,37,42,51,69,74,81,99}
Нам надо узнать, каким по счёту в этом массиве находится число 74. Можно, конечно, пройтись по всем элементам массива по порядку и найти нужное число, но тогда, в худшем случае, это займёт O(n) операций. Для небольших значений n это не критично, но при больших значениях n или при большом количестве запросов поиска, это может сильно уменьшить время работы программы. В таком случае можно воспользоваться дихотомией: будем разбивать наш массив на две части и смотреть, в какой из них находится искомое число, далее делаем ту же операцию с найденной частью, и так до тех пор, пока найденная часть не будет состоять из одного элемента.
На примере с нашим массивом:
Разобьём его на две части:
{0,15,23,37,42} и {51,69,74,81,99}. Искомое число 74 находится во второй части. Разобьём её ещё на две:
{51,69,74} и {81,99}. Искомое число находится в первой части. Разобьём её:
{51,69} и {74}. Искомое число находится во второй части. Вторая часть состоит из одного элемента, значит это и есть искомое число.
Теперь реализация этого примера на C++:
Алгоритм предназначен для нахождения минимума/макчимума функции на заданном отрезке.
К примеру, нужно найти минимум функции y=x*x на интервале [-4,+4]:
В данном случае минимум функции y=0 при x=0.
Гардиентный спуск работает следующим образом:
1) Берётся какое-либо значение для шага, не привышающее размер интервала, на котором ищем.
2) Берётся любое значение x, такое, что x+шаг и x-шаг не выходили за пределы интервала.
3) Ищем значение функции для x.
4) Ищем значение функции для x+шаг. Если значении функции f(x+шаг) уменьшилось, по сравнению со значением f(x), то x=x+шаг.
5) Ищем значение функции для x-шаг. Если значении функции f(x-шаг) уменьшилось, по сравнению со значением f(x), то x=x-шаг.
6) Если и f(x+шаг), и f(x-шаг) больше f(x), то уменьшаем шаг в два раза.
Повторяем пункты 3-6 до тех пор, пока шаг>eps, где eps — точность поиска.
Вот как работает алгоритм:
Нашли х и шаг. f(х+шаг) оказалось меньше, чем f(x) и f(x-шаг). Теперь х=х+шаг.
Дальше опять повторяется предыдущая ситуация:
На следующем шаге и f(x+шаг) и f(x-шаг) больше f(x), значит уменьшаем шаг в два раза:
В конце-концов, мы находим ответ.
Вот реализация алгоритма на C++:
Оба алгоритма часто приходится использовать в спортивном программировании, в разных типах задач: поиск максимума/минимума функции(дихотомия и градиентный спуск), поиск в массиве(дихотомия), приближённое решение уравнений(дихотомия и градиентный спуск), часто используются в геометрических задачах(например для поиска точек пересечения отрезка и окружности).
Дихотомия
Дихотомия — поиск делением пополам.
Допустим есть отсортированный массив чисел:
a[10] = {0,15,23,37,42,51,69,74,81,99}
Нам надо узнать, каким по счёту в этом массиве находится число 74. Можно, конечно, пройтись по всем элементам массива по порядку и найти нужное число, но тогда, в худшем случае, это займёт O(n) операций. Для небольших значений n это не критично, но при больших значениях n или при большом количестве запросов поиска, это может сильно уменьшить время работы программы. В таком случае можно воспользоваться дихотомией: будем разбивать наш массив на две части и смотреть, в какой из них находится искомое число, далее делаем ту же операцию с найденной частью, и так до тех пор, пока найденная часть не будет состоять из одного элемента.
На примере с нашим массивом:
Разобьём его на две части:
{0,15,23,37,42} и {51,69,74,81,99}. Искомое число 74 находится во второй части. Разобьём её ещё на две:
{51,69,74} и {81,99}. Искомое число находится в первой части. Разобьём её:
{51,69} и {74}. Искомое число находится во второй части. Вторая часть состоит из одного элемента, значит это и есть искомое число.
Теперь реализация этого примера на C++:
int a[10] = {0,15,23,37,42,51,69,74,81,99};
int l = 0;
int r = 9;
while(l<r)
{
int m = (l+r)/2;
if(a[m]>=74)
r = m;
else
l = m+1;
}
cout<<l;
Гардиентный спуск
Алгоритм предназначен для нахождения минимума/макчимума функции на заданном отрезке.
К примеру, нужно найти минимум функции y=x*x на интервале [-4,+4]:
В данном случае минимум функции y=0 при x=0.
Гардиентный спуск работает следующим образом:
1) Берётся какое-либо значение для шага, не привышающее размер интервала, на котором ищем.
2) Берётся любое значение x, такое, что x+шаг и x-шаг не выходили за пределы интервала.
3) Ищем значение функции для x.
4) Ищем значение функции для x+шаг. Если значении функции f(x+шаг) уменьшилось, по сравнению со значением f(x), то x=x+шаг.
5) Ищем значение функции для x-шаг. Если значении функции f(x-шаг) уменьшилось, по сравнению со значением f(x), то x=x-шаг.
6) Если и f(x+шаг), и f(x-шаг) больше f(x), то уменьшаем шаг в два раза.
Повторяем пункты 3-6 до тех пор, пока шаг>eps, где eps — точность поиска.
Вот как работает алгоритм:
Нашли х и шаг. f(х+шаг) оказалось меньше, чем f(x) и f(x-шаг). Теперь х=х+шаг.
Дальше опять повторяется предыдущая ситуация:
На следующем шаге и f(x+шаг) и f(x-шаг) больше f(x), значит уменьшаем шаг в два раза:
В конце-концов, мы находим ответ.
Вот реализация алгоритма на C++:
const double eps = 0.001;
double x,step;
x = -3;
step = 1;
while(step>eps)
{
if(x*x>(x-step)*(x-step))
x-=step;
else
if(x*x>(x+step)*(x+step))
x+=step;
else
step/=2;
}
cout<<x;
Оба алгоритма часто приходится использовать в спортивном программировании, в разных типах задач: поиск максимума/минимума функции(дихотомия и градиентный спуск), поиск в массиве(дихотомия), приближённое решение уравнений(дихотомия и градиентный спуск), часто используются в геометрических задачах(например для поиска точек пересечения отрезка и окружности).