DC подразумевает, что вы решаете задачу на множествах. DP тоже применяется на множествах, но не ограничивается ими.
В бинарном поиске — это массив/отрезок. Важно то, что есть выбор, как именно поделить его. Можно поделить пополам, а можно на 1/3 и 2/3. Понятно, что худший случай лучше, если делить пополам. Можно вообще делить на несколько отрезков, например так работают B-деревья. Главное, что как бы вы не поделили, задачу можно решить из одного конкретного деления.
Парочка чуть менее тривиальных примеров:
1) Сортировка слиянием: делим массив на две части, сортируем каждую по отдельности и делаем слияние. Ключевой момент — слияние двух отсортированных массивов можно сделать за линейное время. Опять же, достаточно сделать одно разделение
2) Построение выпуклой оболочки: берем какую-то прямую, она как-то разделяет множество точек на два подмножества. Строим выпуклые оболочки на подмножествах и объединяем. Опять же, основная сложность — это сделать объединение. И снова, важно то, что одного разбиения достаточно.
С DP ситуация немного иная: DP обычно фокусируется на добавлении элементов по одному, чтобы уменьшить издержки на «переход» от подзадачи к задаче. Вот пара примеров
1) Задача коммивояжера, точное решение DP за 2^n * n^2. Предлагается считать функцию: f(S, i)=«минимальный путь, проходящий ровно один раз по всем вершинам из S и ни по каким другим, и при этом заканчивающийся на вершине i». Стандартный переход — перебрать предпоследнюю вершину j из S и взять минимум по f(S\{i}, j) + cost(i, j). Так или иначе нужно сделать хоть и минимальный но перебор нескольких разбиений. При этом пересчет f(S, i) по произвольному разбиению S не проще исходной задачи.
2) Задача о рюкзаке: есть набор предметов разного целочисленного объема, нужно набрать ровно V. Можно считать функцию f(W, i)=«можно ли набрать первыми i предметами объем W». Такую функцию относительно легко пересчитать, добавляя предметы по одному, а не разделяя на произвольные подмножества.
По поводу постановки задачи: «максимальный этаж, с которого можно бросить яйцо, не разбив» — это не ваша функция f(n, m). Если яйцо не разбивается с этажа k, но разбивается с этажа k+1, то f(n, m) — это максимальное такое число h, что с запасом n яиц и m попыток мы можем гарантировано найти k, если известно, что k<=h.
В финальном коде есть строчка
h += t
Быть может там имелось в виду
h += bk
?
Особых надежд на что-то более быстрое практически нет.
Вроде бы есть. Вообще задача о назначениях часто в научных статьях называется «задачей о паросочетании минимальной стоимости» (minimum cost bipartite matching problem), обычно рассматривается как подкласс задачи о потоке минимальной стоимости (minimum cost flow problem). По этим названиям можно поискать и найти кучу всего, что напридумывали.
Беглый поиск в goolge scholar выдал вот эту статью, судя по абстракту там лучше, чем n^3, но асимптотика содержит величины стоимостей. Скорее всего это не первый подобный алгоритм. Работают ли они быстрее на практике — другой вопрос. Опять же, кажется, что отдельно с задачей о назначениях особо не заморачиваются, штурмуют как минимум потоки.
Хорошей связи между задачей коммивояжера и задачей о назначениях нет… разве что если P=NP.
Наверно речь идет о Christofides algorithm. Есть два известных алгоритма приближенного решения задачи коммивояжера для графа, в котором веса ребер удовлетворяют неравенству треугольника
Простой: находим минимальное остовное дерево, проходим по нему и строим не очень сложным образом цикл. Если выполняется неравенство треугольника, то полученный цикл не более, чем в 2 раза хуже оптимального.
Сложный:
— Находим минимальное остовное дерево
— Находим на вершинах с нечетной степенью в найденном остовном дереве паросочетание наименьшего веса (здесь как раз решается задача о назначениях)
— Находим Эйлеров цикл и несложным образом превращаем его в гамильтонов.
Вуаля, оказывается, что такой алгоритм дает приближение, которое не более, чем в 1.5 хуже оптимального.
Подробнее можно посмотреть тут и тут.
Я точно не уверен, но у сортировки выбором есть одно важное свойство: она сортирует используя минимальное число свопов. По крайней мере я умею доказывать это свойство при условии, что все элементы различны. Выглядит доказательство как-то так: если все элементы различны, то существует ровно одна перестановка элементов, образующая отсортированный порядок, «минимальное число свопов» = «количество элементов» — «количество циклов в этой перестановке», если сортировка выбором делает своп, то количество циклов увеличивается;
Быть может кто-то умеет доказывать/опровергать это в общем случае?
А почему среднее число вершин, смежных с данной — log(n)? У вас всего ребер ~ 0.1 * n^2, то средняя степень должна быть 2 * 0.1 * n.
Кроме того, Θ(n⋅log(n)⋅log(n)) асимптотически меньше, чем n^2, а у вас количество ненулевых коэффициентов ~0.1 * n^2, получается, что Ваш алгоритм делает меньше операций, чем размер выходных данных.
А у вас задача решить СЛАУ или найти LU факторизацию? Правда ли, что указанные солверы (supeLU, SGESV/SGESVX) делают LU факторизацию.
Вообще разреженные СЛАУ исследуют довольно давно, как минимум нужно иметь в виду упомянутые ранее в комментариях методы Крылова — для них базовая оценки не O(n^3), а O(nm), где m — количество ненулевых элементов (достигается кстати как раз в том числе за счет «списков смежности»). Уверен, Вы смогли бы ускориться за счет использования какой-нибудь разновидности метода Крылова после указанных графовых оптимизаций вместо Гаусса.
Пока что создается ощущение, что вы сравниваете «Гаусса» и «Гаусса + графовые оптимизации», и это ожидаемо, что в таком сравнении незаточенный под разреженность Гаусс будет медленней.
и в среднем и в лучшем случаях демонстрирует асимптотику Θ(n⋅log(n)⋅log(n))
Кстати с покоординатным спуском такая история: вроде как он очень хорош для функций, у которых частные производные считать существенно проще, чем весь градиент (например как раз для квадратичных).
— Если выбирать случайно, то он становится частным случаем SGD, но специфический, для него действуют не только плохие оценки SGD, но и хорошие обычного градиентного спуска. Ключевой момент — для SGD точка минимума может меняться в зависимости от реализации неизвестной случайной величины, а для покоординатного не может. Самый простой пример f(x)=E||x-w||^2, w — с.в. f достигает минимума в Ew, соответственно найти приблизительно минимум — равносильно нахождению приближенного мат. ожидания по наблюдениям, вроде как быстрее, чем C/ sqrt(N) (N — кол-во наблюдений) не получить. В покоординатном спуске такого эффекта не будет.
— Говорят, что довольно эффективно выбирать координату с наибольшей по абсолютной величине производной. Вроде бы это один из немногих методов, которые я видел, где «узкое место» — это RMQ (для выбора координаты).
Метод Нелдера-Мида не использует градиент в принципе, вроде как он хуже градиентных, зато он применим на большем классе задач, например в reinforcement learning.
Спасибо, поизучаю на досуге. Я правильно понимаю, что имелось в виду размерность >= 300000? Мне казалось, что при такой размерности квазиньютоновские методы становятся довольно громоздкими.
Поправил. Норма везде подразумевается операторная т.е. ||A||=sup ||Ax||/||x|| (x!=0), такая норма гарантирует ||Ax||<=||A|| ||x|| для всех х. Для симметричных матриц — это просто спектральный радиус, т.е. наибольшее по абсолютной величине собственное число. Если у матрицы A спектр (множество собственных чисел) на отрезке [m, L] (хотя бы 0, так как в противном случае функция не ограничена снизу, а также у вещественных симметричных матриц собственные числа вещественные), то у матрицы I-aA — на отрезке [1-aL, 1-mL]. Соответственно 1-aL>-1 если a<2/L. Если m>0, то 1-mL < 1, что верно для положительно определенных матриц, но с m=0 градиентный спуск тоже корректно работает, но чуть сложнее это показать. К слову L в этом случае как раз будет константой липшица для градиента f.
Да, для нейронных сетей это может быть не так важно, но все-таки оптимизация не только в них применяется, а проблема локальных минимумов появилась задолго до нейронок.
По нейронным сетям есть замечательная экспериментальная статья здесь же на хабре. Ключевая связь между градиентными методами и обучением нейронных сетей — это так называемый «метод обратного распространения ошибки» (backpropagation). Про него мне кажется можно посмотреть вот здесь и здесь.
Формально нейронные сети — это класс функций, который теоретически умеет приближать все, что угодно (вот тут упомянуты две теоремы на этот счет, страница 4), к сожалению идеально подобрать параметры приближения — довольно сложно. При применении градиентных методов этот как раз выражается в частом застревании в локальных минимумах — это известная проблема, к сожалению какого-то универсального решения нет. Есть генетические методы, метод отжига, метод муравьиных колоний и т.п., которые частично умеют это обходить, но они требуют больше вычислений.
Согласен, тут я немного приврал. Вообще говоря для квадратичных функций поведение BFGS схоже с методом сопряженных градиентов, по крайней мере сходится за конечное число шагов, но не уверен, что умеет использовать разреженность матриц. В нелинейном случае, если не считать вычисление градиента, то метод сопряженных градиентов (а остальные уж тем более) не делают умножений матрица-вектор. Вроде бы понятно, что если размерность пространства больше ~10^4-10^5, то это становится критичным.
В бинарном поиске — это массив/отрезок. Важно то, что есть выбор, как именно поделить его. Можно поделить пополам, а можно на 1/3 и 2/3. Понятно, что худший случай лучше, если делить пополам. Можно вообще делить на несколько отрезков, например так работают B-деревья. Главное, что как бы вы не поделили, задачу можно решить из одного конкретного деления.
Парочка чуть менее тривиальных примеров:
1) Сортировка слиянием: делим массив на две части, сортируем каждую по отдельности и делаем слияние. Ключевой момент — слияние двух отсортированных массивов можно сделать за линейное время. Опять же, достаточно сделать одно разделение
2) Построение выпуклой оболочки: берем какую-то прямую, она как-то разделяет множество точек на два подмножества. Строим выпуклые оболочки на подмножествах и объединяем. Опять же, основная сложность — это сделать объединение. И снова, важно то, что одного разбиения достаточно.
С DP ситуация немного иная: DP обычно фокусируется на добавлении элементов по одному, чтобы уменьшить издержки на «переход» от подзадачи к задаче. Вот пара примеров
1) Задача коммивояжера, точное решение DP за 2^n * n^2. Предлагается считать функцию: f(S, i)=«минимальный путь, проходящий ровно один раз по всем вершинам из S и ни по каким другим, и при этом заканчивающийся на вершине i». Стандартный переход — перебрать предпоследнюю вершину j из S и взять минимум по f(S\{i}, j) + cost(i, j). Так или иначе нужно сделать хоть и минимальный но перебор нескольких разбиений. При этом пересчет f(S, i) по произвольному разбиению S не проще исходной задачи.
2) Задача о рюкзаке: есть набор предметов разного целочисленного объема, нужно набрать ровно V. Можно считать функцию f(W, i)=«можно ли набрать первыми i предметами объем W». Такую функцию относительно легко пересчитать, добавляя предметы по одному, а не разделяя на произвольные подмножества.
В финальном коде есть строчка
h += t
Быть может там имелось в виду
h += bk
?
Вроде бы есть. Вообще задача о назначениях часто в научных статьях называется «задачей о паросочетании минимальной стоимости» (minimum cost bipartite matching problem), обычно рассматривается как подкласс задачи о потоке минимальной стоимости (minimum cost flow problem). По этим названиям можно поискать и найти кучу всего, что напридумывали.
Беглый поиск в goolge scholar выдал вот эту статью, судя по абстракту там лучше, чем n^3, но асимптотика содержит величины стоимостей. Скорее всего это не первый подобный алгоритм. Работают ли они быстрее на практике — другой вопрос. Опять же, кажется, что отдельно с задачей о назначениях особо не заморачиваются, штурмуют как минимум потоки.
Наверно речь идет о Christofides algorithm. Есть два известных алгоритма приближенного решения задачи коммивояжера для графа, в котором веса ребер удовлетворяют неравенству треугольника
Простой: находим минимальное остовное дерево, проходим по нему и строим не очень сложным образом цикл. Если выполняется неравенство треугольника, то полученный цикл не более, чем в 2 раза хуже оптимального.
Сложный:
— Находим минимальное остовное дерево
— Находим на вершинах с нечетной степенью в найденном остовном дереве паросочетание наименьшего веса (здесь как раз решается задача о назначениях)
— Находим Эйлеров цикл и несложным образом превращаем его в гамильтонов.
Вуаля, оказывается, что такой алгоритм дает приближение, которое не более, чем в 1.5 хуже оптимального.
Подробнее можно посмотреть тут и тут.
Быть может кто-то умеет доказывать/опровергать это в общем случае?
Кроме того, Θ(n⋅log(n)⋅log(n)) асимптотически меньше, чем n^2, а у вас количество ненулевых коэффициентов ~0.1 * n^2, получается, что Ваш алгоритм делает меньше операций, чем размер выходных данных.
Вообще разреженные СЛАУ исследуют довольно давно, как минимум нужно иметь в виду упомянутые ранее в комментариях методы Крылова — для них базовая оценки не O(n^3), а O(nm), где m — количество ненулевых элементов (достигается кстати как раз в том числе за счет «списков смежности»). Уверен, Вы смогли бы ускориться за счет использования какой-нибудь разновидности метода Крылова после указанных графовых оптимизаций вместо Гаусса.
Пока что создается ощущение, что вы сравниваете «Гаусса» и «Гаусса + графовые оптимизации», и это ожидаемо, что в таком сравнении незаточенный под разреженность Гаусс будет медленней.
Откуда эта асимптотика была взята?
— Если выбирать случайно, то он становится частным случаем SGD, но специфический, для него действуют не только плохие оценки SGD, но и хорошие обычного градиентного спуска. Ключевой момент — для SGD точка минимума может меняться в зависимости от реализации неизвестной случайной величины, а для покоординатного не может. Самый простой пример f(x)=E||x-w||^2, w — с.в. f достигает минимума в Ew, соответственно найти приблизительно минимум — равносильно нахождению приближенного мат. ожидания по наблюдениям, вроде как быстрее, чем C/ sqrt(N) (N — кол-во наблюдений) не получить. В покоординатном спуске такого эффекта не будет.
— Говорят, что довольно эффективно выбирать координату с наибольшей по абсолютной величине производной. Вроде бы это один из немногих методов, которые я видел, где «узкое место» — это RMQ (для выбора координаты).
Метод Нелдера-Мида не использует градиент в принципе, вроде как он хуже градиентных, зато он применим на большем классе задач, например в reinforcement learning.
Диссертация (к. ф.-м. н.): Рандомизированные алгоритмы распределения ресурсов в адаптивных мультиагентных системах — если в кратце, то я занимался распределенной децентрализованной оптимизацией, то есть такими алгоритмами, которые не требуют какого-то «центрального» вычислительного узла, имеющего информацию о всей сети в целом.
По нейронным сетям есть замечательная экспериментальная статья здесь же на хабре. Ключевая связь между градиентными методами и обучением нейронных сетей — это так называемый «метод обратного распространения ошибки» (backpropagation). Про него мне кажется можно посмотреть вот здесь и здесь.
Формально нейронные сети — это класс функций, который теоретически умеет приближать все, что угодно (вот тут упомянуты две теоремы на этот счет, страница 4), к сожалению идеально подобрать параметры приближения — довольно сложно. При применении градиентных методов этот как раз выражается в частом застревании в локальных минимумах — это известная проблема, к сожалению какого-то универсального решения нет. Есть генетические методы, метод отжига, метод муравьиных колоний и т.п., которые частично умеют это обходить, но они требуют больше вычислений.