Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 5
kitten → sitten (замена «s» на «k»)
sitten → sittin (замена «i» на «e»)
Наоборот наверное?
sitten → sittin (замена «i» на «e»)
Наоборот наверное?
Итак, почему же тогда мы все еще имеем два разных подхода (DP и DC) и почему я назвал динамическое программирование расширением. Это потому, что динамическое программирование может быть применено к задачами, которые обладают определенными характеристиками и ограничениями.
вероятно, правильнее было бы назвать DP частным случаем DC, т.к. DP — это оптимизированный с помощью мемоизации и табуляции DC, который работает только если выполняются определенные дополнительные условия (пересекающиеся подзадачи и оптимальные подструктуры)
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». Такую функцию относительно легко пересчитать, добавляя предметы по одному, а не разделяя на произвольные подмножества.
В бинарном поиске — это массив/отрезок. Важно то, что есть выбор, как именно поделить его. Можно поделить пополам, а можно на 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». Такую функцию относительно легко пересчитать, добавляя предметы по одному, а не разделяя на произвольные подмножества.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Динамическое программирование или «Разделяй и Властвуй»