Перейти к содержимому

Для чего нужна декомпозиция в динамическом программировании

  • автор:

Задачи на умножение матриц

Когда мы говорили о линейных функциях и матрицах, все примеры были про геометрию. Так просто проще думать: представлять в уме повороты и растяжения векторов на плоскости легче, чем рассуждать о свойствах абстрактных n-мерных пространств. Однако мы программисты, и нас в основном интересуют задачи вне геометрии.

Большинство применений в контексте олимпиад опираются на ассоциативность матричного умножения:

$$ ABC = (AB)C = A(BC) $$ Если задачу можно свести к возведению матрицы $A$ в какую-то большую степень $n$ — то есть к домножению единичной матрицы $n$ раз на матрицу $A$ — то можно просто воспользоваться свойством ассоциативности и посчитать результат бинарным возведением в степень: $$ A^8 = A^>> = ((AA)(AA))((AA)(AA)) $$

Такой подход имеет множество применений в динамическом программировании, комбинаторике, теории вероятностей и математике в целом.

#Линейные рекурренты

Задача. Дано число $n < 10^$. Требуется вычислить $n$-ное число Фибоначчи:

Заметим, что вычисление очередного числа Фибоначчи выражается как линейная функция от двух предыдущих чисел Фибоначчи — а именно, как их сумма.

Это означает, что мы можем построить матрицу $2 \times 2$, которая будет соответствовать этому преобразованию: как по двум соседним числам Фибоначчи $(f_n, f_)$ вычислить следующее число, то есть перейти к паре $(f_, f_)$.

Обозначим за $A$ эту матрицу перехода. Чтобы посчитать $n$-ное число Фибоначчи, нужно применить $n$ раз эту матрицу к вектору $(f_0, f_1) = (0, 1)$.

Так как размер матрицы $A$ константный, её умножение саму на себя будет работать за $O(1)$. Значит, можно посчитать $A^n$ бинарным возведением в степень за $O(\log n)$ операций, домножить на вектор $(0, 1)$ и взять первый элемент результата — он будет равен в точности $f_n$, что мы и искали.

Примечание. Домножать на вектор явно даже не обязательно — если нам нужен только первый элемент, можно посмотреть на выражение для итогового результата и понять, что достаточно просто взять верхний правый элемент итоговой матрицы.

#Общий случай

В общем случае, когда мы учитываем не $2$, а $k$ последних элементов, причём с разными весами, линейная рекуррента $f_n = a_1 f_ + a_2 f_ + \ldots + a_k f_$ имеет такую матрицу перехода:

$$ \begin 0 & 1 & 0 & \ldots & 0 \\ 0 & 0 & 1 & \ldots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \ldots & 1 \\ a_k & a_ & a_ & \ldots & a_1 \\ \end $$

При домножении на вектор $(f_n, f_, \ldots, f_)$ для последнего элемента получается в точности формула из определения, а все $(k-1)$ предыдущих просто перекопируются.

Отметим, что рекуррентные последовательности задаются не только коэффициентами $a_i$, но и начальными значениями $(f_1, f_2, \ldots, f_k)$.

Упражнение. Для линейной рекурренты порядка $k$ известны её коэффициенты $a_i$ и $k$ пар вида $(i, f_i)$. Восстановите первые $k$ элементов последовательности.

#Геометрическая прогрессия

В статье про бинарное возведение в степень мы обсуждали модификацию алгоритма для нахождения суммы геометрической прогрессии:

$$ f(n) = 1 + a + a^2 + \ldots + a^ $$ Можно подойти к этой задаче с другой стороны. Заметим, что сумма первых $n$ степеней следующим образом выражается через сумму первых $(n-1)$ степеней: $$ f(n) = f(n-1) \cdot a + 1 $$ Это почти линейная зависимость от предыдущего — только ещё добавляется неудобная константа. Можно применить следующий трюк: представить, что мы также зависим ещё и от $(n-2)$-го элемента, но положить его постоянно равным единице: $$ \begin f_ \\ 1 \\ \end = \begin f_n \cdot a + 1 \\ 0 + 1 \\ \end = \begin a & 1 \\ 0 & 1 \\ \end \begin f_ \\ 1 \\ \end $$

Тогда эту матрицу можно аналогично возвести в степень $n$ и вернуть её правое верхнее поле.

#Динамическое программирование

Переходы в некоторых динамиках иногда тоже можно выразить в терминах матричного умножения.

Если бы ограничение на $k$ было сильно меньше, мы бы ввели динамику $f_$, равную количеству способов дойти до $v$-той вершины через ровно $i$ переходов. Пересчёт — перебор предпоследней вершины в пути:

$$ f_ = \sum_ f_ $$ Перепишем эту динамику в терминах матрицы смежности, в ячейке $G_$ которой содержится число ребер между $u$ и $v$ (ровно поэтому она называется матрицей). $$ f_ = \sum_u f_ \cdot G_ $$ Выясняется, что вектор $f_$ зависит от $f_$ линейно: его $v$-тый элемент получается скалярным умножением вектора $f_$ и $v$-того столбца матрицы смежности $G$. Значит, имеет место следующее равенство: $$ f_i = G \cdot f_ $$

Получается, $f_k$ можно раскрыть как $f_k = f_0 \cdot G \cdot G \cdot \ldots \cdot G$ и применить бинарное возведение в степень.

По этой формуле нам потребуется $O(\log k)$ раз перемножить две матрицы размера $n \times n$, что суммарно будет работать за $O(n^3 \log k)$.

 В получившейся матрице в ячейке $G_$ будет находиться количество способов дойти из $i$-той вершины в $j$-тую, используя ровно $k$ переходов. Ответом нужно просто вывести $G_$.

#Модификации задачи

С небольшими изменениями этим методом можно решать много похожих задач:

  • Практически не меняя сам алгоритм, можно решить задачу «с какой вероятностью мы попадём из вершины $s$ в вершину $t$», если вместо матрицы смежности даны вероятности, с которыми мы переходим из вершины в вершину в марковской цепи.
  • Если нам не нужно количество способов, а только сам факт, можно ли дойти за ровно $k$ переходов, то можно обернуть матрицу в битсеты и сильно ускорить решение.
  • Если нас спрашивают «за не более, чем $k$ переходов», то вместо $k$-той степени матрицы мы можем вышеописанным методом посчитать сумму геометрической прогрессии. Альтернативно, можно для каждой вершины добавить вторую, в которую будет вести ребро из изначальной, а единственное исходящее ребро — это петля в саму себя.

Эту технику можно применить и к другим динамикам, где нужно посчитать количество способов что-то сделать — иногда очень неочевидными способами.

Например, можно решить такую задачу: найти количество строк длины $k \approx 10^$, не содержащих данные маленькие запрещённые подстроки. Для этого нужно построить граф «легальных» переходов в Ахо-Корасике, возвести его матрицу смежности в $k$-тую степень и просуммировать в нём первую строчку.

В некоторых изощрённых случаях в матричном умножении вместо умножения и сложения нужно использовать другие операции, которые ведут себя как умножение и сложение. Пример задачи: «найти путь от $s$ до $t$ с минимальным весом ребра, использующий ровно $k$ переходов»; здесь нужно возводить в $(k-1)$-ую степень матрицу весов графа, и вместо и сложения, и умножения использовать минимум из двух весов.

Также в контексте нахождения кратчайших путей известен «distance product»:

$$ C_ = \min_k \ < a_+ b_ \> $$ Возводя матрицу весов в $k$-тую степень мы получаем, соответственно, минимальное расстояние от $a$ до $b$, используя не более $k$ переходов. В частности, при $k=n$ мы за $O(n^3 \log n)$ операций получим матрицу кратчайших расстояний между всеми парами вершины, хотя для этого есть и более прямые методы.

О динамическом программировании на пальцах

Привет, хабр! Сегодня мы поговорим о динамическом программировании.

Я часто решаю задачи на CodeWars, самостоятельно ищу логические задачи в интернете, а также, когда проводятся олимпиады в моей школе по информатике, я записываюсь на них, дабы держать свой ум в порядке и развиваться.

И часто в заданиях, олимпиадах, или даже просто в жизни, попадаются задания на динамическое программирование.

Динамическое программирование — это когда мы разбиваем большую проблему, которая мешает нам, на множество маленьких задач, которые уже можно игнорировать!

(С) Доктор Аргентум, 2022 год нашей эры

Ну а если серьёзно, то динамическое программирование — это система решения заданий, которая предполагает, что большая проблема будет разбита на более мелкие задачи, которые более понятные в решении (способ решения сложных задач путём разбиения их на более простые подзадачи).

Динамическое программирование — это особый подход к решению задач. Не существует какого-то единого определения динамическому программированию, но все-таки попробуем её сформировать. Идея заключается в том, что оптимальное решение зачастую можно найти, рассмотрев все возможные пути решения задачи, и выбрать среди них лучшее.

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

recursion_vs_dynamic_prog

Магия динамического программирования заключается в умном обращении с решениями подзадач. «Умный» в этом контексте значит «не решающий одну и ту же подзадачу дважды». Для этого решения мелких подзадач должны где-то сохраняться. Для многих реальных алгоритмов динамического программирования этой структурой данных является таблица.

В самых простых случаях эта таблица будет состоять только из одной строки — аналогично обычному массиву. Эти случаи будут называться одномерным динамическим программированием, и потреблять O(n) памяти. Например, алгоритм эффективного вычисления чисел Фибоначчи использует обычный массив для запоминания вычисленных промежуточных результатов. Классический рекурсивный алгоритм делает очень много бессмысленный работы — он по миллионному разу рассчитывает то, что уже было рассчитано в соседних ветках рекурсии.

В самых распространённых случаях эта таблица будет выглядеть привычно и состоять из строчек и столбиков. Обычная таблица, похожая на таблицы из Excel. Это называется двумерным динамическим программированием, которое при n строках и n столбцах таблицы потребляет O(n*n) = O(n^2) памяти. Например, квадратная таблица из 10 строк и 10 столбцов будет содержать 100 ячеек. Чуть ниже будет подробно разобрана именно такая задача.

Бывают и более запутанные задачи, использующие для решения трехмерные таблицы, но это редкость — решение задачи с использованием трехмерной таблицы зачастую просто нельзя себе позволить. Небольшая двухмерная таблица на 1024 строки и 1024 столбца может потребовать несколько мегабайт памяти. Трехмерная таблица с такими же параметрами будет занимать уже несколько гигабайт.

1d_vs_2d_vs_3d

Что нужно, чтобы решить задачу динамически, помимо ее исходных данных? Всего три вещи:

  • Таблица, в которую будут вноситься промежуточные результаты. Один из них будет выбран в конце работы алгоритма в качестве ответа
  • Несколько простых правил по заполнению пустых ячеек таблицы, основанных на значениях в уже заполненных ячейках. Универсального рецепта тут нет и к каждой задаче требуется свой подход
  • Правило выбора финального решения после заполнения таблицы

Он применим к задачам с оптимальной подструктурой, которые выглядят как набор перекрывающихся подзадач, сложность которых чуть меньше исходной. В этом случае время вычислений по сравнению с «наивными» методами можно значительно сократить.

Чтобы решить поставленную задачу, требуется решить отдельные части задачи (подзадачи), после чего объединить решения подзадач в одно общее решение. Часто многие из этих подзадач одинаковы.

Представим хакера, который пытается взломать какой-то пароль перебором всех комбинаций символов. Если пароль допускает 10 цифр, 26 маленьких букв, 26 больших букв и 32 специальных символа (например, значок доллара), то для каждого символа в пароле есть 94 кандидата. Значит, чтобы взломать перебором пароль, состоящий из одного символа, потребуется 94 проверки. Если в пароле два символа — 94 кандидата на первую позицию, 94 кандидата на вторую позицию — то придется перебрать аж 94*94 = 8836 возможных пар. Для пароля из десяти символов потребуется уже перебор 94^10 комбинаций.

Если обобщить, то для взлома пароля с произвольной длиной N требуется O(94^N) операций. Такие затраты часто называют «экспоненциальными»: появление каждой новой позиции влечёт за собой увеличение количества операций в 94 раза. Взлом пароля может показаться чем-то экзотическим, но задачи, требующие полного перебора всех вариантов — совсем не экзотика, скорее угрюмая реальность.

Экспоненциальное время — это долго. Даже O(2^N) — это просто непозволительно долго. Настолько долго, что никому и в голову не придет запустить подобный алгоритм даже на простых данных — ведь на решение такой задачи с сотней элементов потребуются тысячи, миллионы или миллиарды лет вычислений. А в реальной жизни нужно решать задачи с намного большим количеством элементов. Как же быть?

Дело в том, что многие задачи без эффективного алгоритма решения можно решить за привлекательное время с помощью одной хитрости — динамического программирования.

Подход динамического программирования состоит в том, чтобы решить каждую подзадачу только один раз, сократив тем самым количество вычислений. Это особенно полезно в случаях, когда число повторяющихся подзадач экспоненциально велико.

Процесс разработки алгоритмов динамического программирования

В процессе составления алгоритмов динамического программирования, требуется следовать последовательности из четырёх действий:

  1. Описать структуру оптимального решения.
  2. Рекурсивно определить значение оптимального решения.
  3. Вычислить значение оптимального решения с помощью метода восходящего анализа.
  4. Составить оптимальное решение на основе полученной информации.

Динамика на примере чисел Фибоначчи

Один из легких примеров для демонстрации силы динамического программирования — известные числа Фибоначчи.

Последовательность Фибоначчи — это список чисел, который начинается с двух единиц, а каждый следующий элемент, то есть число, равно сумме двух предыдущих. Например:

Формула для вычисления числа Фибоначчи представлена ниже:

Давайте создадим простейший алгоритм построения последовательности Фибоначчи на Python:

import timeit # замер времени def fib(n): return 1 if n == 0 or n == 1 else fib(n - 1) + fib(n - 2) # вывод времени работы print(timeit.timeit('fib(20)', number=100, globals=globals())) >>> 2.2218473450011516

Отвратительно получилось. Алгоритм очень медленный. Так давайте улучшим его!

Фундаментальная проблема заключается в многократном выполнении одинаковых вычислений. Например, F3 рассчитывается дважды, а F2 – трижды, хотя результат каждый раз получается одинаковый. Даже если не углубляться в анализ времени выполнения, очевидно, что для этого алгоритма оно будет расти по экспоненте.

На решении подобных проблем и специализируется динамическое программирование. Оно помогает решать рекурсивные задачи с сильно перекрывающейся структурой подзадач. Это означает, что некоторые действия повторяются снова и снова, с одинаковыми входными данными и результатом.

Не каждая задача пригодна для DP. Если подпроблемы не перекрываются, следует использовать алгоритм «разделяй и властвуй», как при сортировке массива слиянием.

Но как же улучшить наш алгоритм?

Ответ простой — мемоизация , запоминание, или же кеширование.

Один из способов избежать постоянного пересчитывания одних и тех же данных – кешировать результаты вычислений. Технически это реализуется так:

  • Если кеш содержит результат для полученных входных данных, использовать значение из кеша.
  • В противном случае, вычислить результат и сохранить его в кеше, поставив в соответствие с входными данными.
import timeit def fib(n, cache=None): if n == 0 or n == 1: return 1 if cache is None: cache = <> if n in cache: return cache[n] result = fib(n - 1, cache) + fib(n - 2, cache) cache[n] = result return result print(timeit.timeit('fib(20)', number=100, globals=globals())) >>> 0.00414187600108562

Невероятно! Скорость выполнения повысилась в 2 раза!

Давайте улучшим и сделаем полный ее рефакторинг, но сам смысл оставим тот же — мемоизация, но применим также декораторы Python:

import timeit from inspect import signature class memoize(dict): def __init__(self, func): self.func = func self.signature = signature(func) def __missing__(self, key): (arg, kwarg) = key self[key] = val = self.func(*arg, **dict(kwarg)) return val def __call__(self, *arg, **kwarg): key = self.signature.bind(*arg, **kwarg) return self[key.args, frozenset(key.kwargs.items())] @memoize def Fibonacci(n): if n

Зависимость от n практически линейна!

Но что насчет пространственной сложности? Для вычисления Fn нужно вычислить Fn-1 и Fn-2, и так далее до F0. Следовательно, придется кэшировать O(n) результатов. Значит, потребуется O(n) памяти.

Можно ли сделать лучше? В этом случае можно!

Динамическое программирование снизу вверх

Простая мемоизация результатов, с которой мы только что имели дело – это классический подход сверху вниз. Но можно коварно зайти и с другой стороны.

Взгляните на эту диаграмму, где каждая подзадача показана только один раз. Это цепочка зависимостей задач. Если две разные проблемы зависят (базируются) от одной и той же подпроблемы, то на нее будут указывать две стрелки.

Такая точка зрения позволяет сделать сразу несколько важных заключений. Прежде всего, у нас есть O(n) подпроблем. Кроме того, эта диаграмма является направленным ациклическим графом (DAG), что означает:

  • есть узлы (задачи) и ребра (зависимости между ними);
  • ребра имеют направление, одна подзадача зависит от другой;
  • нет циклов, значит нельзя начать с одной подзадачи и, следуя по стрелкам, вернуться к ней же.

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

Для ряда Фибоначчи этот порядок соответствует увеличению входных данных. То есть сначала мы должны вычислить F0, затем F1, F2 и так далее до Fn.

Есть еще одна важная вещь, которую мы можем вывести из DAG. Каждая подзадача зависит только от двух других. Если вы вычисляете Fm, то вам нужны только результаты Fm-1 и Fm-2, и совершенно не нужно Fm-10. То есть вы можете спокойно выбрасывать значения, которые не участвуют в текущем вычислении.

Формализация алгоритма
  1. Заведем две локальные переменные, которые будут представлять последние два числа Фибоначчи, с которыми мы работаем.
  2. Поместим в них F0(=1) и F1(=1)
  3. Изменяя i от 2 до n вычислим Fi. Каждая операция зависит только от Fi-1 и Fi-2, которые хранятся в локальных переменных. Получая результат, мы выбрасываем Fi-2, заменяем его на Fi-1, а в оставшуюся переменную записываем Fi.

В Python это выглядит так:

import timeit def fib(n): a = 1 # f(i - 2) b = 1 # f(i - 1) for i in range(2, n + 1): a, b = b, a + b return b print(timeit.timeit('fib(20)', number=100, globals=globals())) >>> 0.0005998830019962043

Зависимость времени выполнения этого алгоритма от входных данных тоже линейная (вы можете запустить его и проверить). Кроме того мы здорово сократили пространственную сложность до константного значения, храня всего лишь два предыдущих результата. Это очень круто!

Этот подход называется "снизу-вверх" (bottom-up approach), так как основывается на решении небольших подзадач с целью построения более крупных.

Задача о рюкзаке

Другой популярный пример применения динамического программирования - задача о рюкзаке (knapsack problem). В этой задаче у нас есть набор предметов с определенной стоимостью и весом, а также рюкзак с ограниченной вместимостью. Нужно выбрать такой набор предметов, чтобы их суммарная стоимость была максимальной, а их суммарный вес не превышал вместимость рюкзака.

Для решения задачи о рюкзаке можно использовать следующий алгоритм:

  1. Создаем матрицу dp размером (n + 1) x (W + 1), где n - количество предметов, W - вместимость рюкзака.
  2. Инициализируем первую строку и первый столбец матрицы dp нулями.
  3. Проходимся по каждому предмету i от 1 до n.
  4. Проходимся по каждой вместимости w от 1 до W.
  5. Если вес предмета i меньше или равен w, то dp[i][w] равно максимуму из значения dp[i-1][w] и стоимости предмета i плюс значения dp[i-1][w-вес предмета i].
  6. Иначе, dp[i][w] равно значению dp[i-1][w].
  7. Возвращаем значение в правом нижнем углу матрицы dp как результат.
import timeit def knapsack(weights, values, capacity): n = len(weights) dp = [[0] * (capacity + 1) for _ in range(n + 1)] for i in range(1, n + 1): for w in range(1, capacity + 1): if weights[i - 1] >> 0.007788784998410847 
weights = [1, 3, 4, 5] values = [1, 4, 5, 7] capacity = 7 result = knapsack(weights, values, capacity) print(result) # Вывод: 9

В данном примере мы выбираем предметы с весами 3, 4 и 5 и получаем максимальную суммарную стоимость равную 9.

Интересные примеры задач

Внешние ссылки на примеры задач, которые могут заинтересовать вас

  • Задача о расстановке знаков в выражении
  • Задача о порядке перемножения матриц
  • Задача о выводе в контекстно-свободной грамматике, алгоритм Кока-Янгера-Касами
  • Задача об оптимальном префиксном коде с сохранением порядка. Монотонность точки разреза
  • Задача о наибольшей общей подпоследовательности
  • Задача о редакционном расстоянии, алгоритм Вагнера-Фишера
  • Задача о расстоянии Дамерау-Левенштейна

Вот такая небольшая статья у нас получилось. Надеюсь вам понравилось, ставьте плюсы, и комментируйте! С вами был доктор Аргентум!

  • программирование
  • фибоначчи
  • динамическое программирование
  • олимпиадное программирование
  • олимпиада
  • динамика
  • код
  • задачи

Декомпозиция задач: что это и зачем нужно

Приходит маркетолог интернет-магазина к разработчику с задачей:

  • добавить на страницу товара счётчик, сколько раз его купили.

Для маркетолога это одна строчка текста. Он думает, что такую простую задачку можно сделать за 15 минут. А разработчик пожимает плечами: «Подумаю, потом назову срок». Что за дичь? А вот так.

Прежде чем эту задачу делать, её было бы неплохо декомпозировать — то есть понять, из чего она состоит, на что влияет и в каком порядке её стоит делать. В случае со счётчиком покупок это получится такой набор подзадач:

  • Добавить в базу товаров столбец с количеством покупок.
  • Написать новый или доработать старый метод для АПИ, чтобы сайт получал значение из этого столбца.
  • Добавить строку текста на страницу товара.
  • Протестировать метод и вёрстку.
  • Подумать, что делать с редкими случаями, например, товар купили, а потом вернули; или если товар суперпопулярный и его купили 9999999999999999 раз.

В зависимости от архитектуры системы могут быть и другие действия. Поэтому назвать срок сразу разработчик не может: сначала надо понять, что вообще нужно делать и сколько времени займёт каждый пункт.

Чем крупнее задача, тем сложнее обойтись без декомпозиции. «Покрасить кнопку в красный» можно не раскладывать. А «Добавить новый раздел в админку» точно стоит сначала разобрать по частям: тут работа и для фронтенда, и для бэкенда. Декомпозиция нужна не всегда, но очень часто.

Зачем декомпозировать

Понять, что и в каком порядке делать. «Добавить счётчик на страницу» кажется задачей для фронтенд-разработчика. Но на самом деле он сможет сделать свою часть, только когда будет готова база данных и АПИ — механизм, по которому эти данные подтягиваются на сайт.

Если фронтенд попробует сам предположить, как будет выглядеть запрос, то после интеграции могут всплыть непредвиденные баги: бэкенд мог реализовать АПИ не так, как думал фронтенд-разработчик. Декомпозиция поможет понять, с какой стороны подступиться и в какой последовательности двигаться.

Оценить сроки. Когда задача разложена на части, можно оценить по времени каждую и понять, сколько потребуется на всё вместе. Понятно, что не получится запустить счётчик за день, если только на базу данных и АПИ нужно два.

Упростить тестирование. Тестировать проще, когда понятно, что нужно проверить. В случае со счётчиком: базу данных, метод и вёрстку.

Расставить приоритеты. Декомпозиция может показать, что задача большая и требует времени. Например, если маркетолог хочет указать не только количество покупок, но и количество городов, в которые товар доставляли. Разработчик может показать, что делать всё вместе — две недели, но счётчик покупок можно выкатить быстрее. А маркетолог уже решит, как лучше поступить.

Как декомпозировать

Декомпозировать можно по-разному, это зависит от масштаба и сути задачи.

Например, запуск мобильного приложения можно декомпозировать сначала на уровне платформ: iOS и Android. Потом — на уровне пользовательских сценариев: регистрация, просмотр контента, покупка, переписка с контактами. Сценарии можно разложить на интерфейс и серверную часть. А их — на отдельные конкретные задачи.

Чаще всего задачи раскладывают вертикально и горизонтально. Вертикально — значит по типам работ. Горизонтально — значит вглубь одного типа работы. Вот как это работает со счётчиком покупок в интернет-магазине:

Вертикальная декомпозиция:

Бэкенд: считать количество покупок и отдавать данные на фронт.

Фронтенд: запрашивать данные при загрузке страницы и выводить.

Горизонтальная декомпозиция:

  • добавить столбец с количеством покупок в БД;
  • считать в этом столбце, сколько раз товар купили;
  • добавить метод, который будет возвращать количество покупок по id товара.
  • добавить на страницу товара строку с количеством покупок;
  • обращаться с помощью метода к БД во время загрузки страницы;
  • настроить отображение счётчика на экранах разных размеров.

Кто должен декомпозировать

Декомпозировать задачу может сам разработчик, тимлид, менеджер проекта или другой компетентный сотрудник: универсальных правил здесь нет. Руководитель службы разработки Яндекс.Практикума Александр Трегер рассказывает, как это работает у них:

Когда появляется новая большая задача, один из опытных разработчиков берёт её на себя. С этого момента он за неё отвечает: собирает встречи, даёт заказчикам обратную связь, определяет, как решить задачу, декомпозирует её. Для разработчиков это возможность расширить свою зону ответственности, попробовать себя в роли архитектора и менеджера проекта.

Иногда нужно выделить время и разобраться в задаче, подумать про пограничные случаи, изучить технологию, придумать решение. Бывает, что на этом этапе задача может разделиться на несколько этапов: что делаем сейчас, а что потом. Так было, например, с проверкой домашних работ от студентов: сначала они приходили в виде архива на проверку, потом появился полноценный интерфейс для ревью кода. Система будет развиваться и дальше, но декомпозиция помогает понять, что и в какой последовательности можно сделать, чтобы быстрее получить результат.

�� Почитайте полное интервью с Александром Трегером. Там больше подробностей о разработке Практикума.

Получите ИТ-профессию

В «Яндекс Практикуме» можно стать разработчиком, тестировщиком, аналитиком и менеджером цифровых продуктов. Первая часть обучения всегда бесплатная, чтобы попробовать и найти то, что вам по душе. Дальше — программы трудоустройства.

Динамическое программирование

ЛЕКЦИЯ 7 ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ Постановка задачи динамического программирования. Принцип оптимальности. Рекуррентные вычисления в динамическом программировании. Задача о кратчайшем пути. Задача распределения ограниченных ресурсов. Динамическое программирование – метод оптимизации, используемый для решения задач, в которых процесс принятия решений может быть разбит на отдельные этапы (шаги). В названии динамического программирования под программированием понимают принятие решения, а слово динамическое указывает на существенную роль времени и порядка выполнения операций в рассматриваемых процессах и методах. В основу метода динамического программирования положен принцип оптимальности, сформулированный в начале 50 годов XX столетия американским математиком Р.Беллманом. Принцип оптимальности. Каково бы ни было начальное состояние на любом шаге и решение, выбранное на этом шаге, последующие решения должны выбираться оптимальными относительно состояния, к которому придет система в конце данного шага. Использование этого принципа гарантирует, что решение, выбранное на любом шаге, является не локально лучшим, а лучшим с точки зрения задачи в целом. Оптимальное решение в динамическом программировании строится постепенно, шаг за шагом. На каждом шаге оптимизируется решение только этого шага, но решение выбирается с учетом последствий, так как решение, оптимальное для этого шага, может привести к неоптимальному решению всей задачи, т.е. оптимальное решение задачи содержит оптимальные решения ее подзадач.

Рекомендуемые материалы

[ПОЛНОСТЬЮ ВЕРНО by БЕЛОУСОВ] Д/З 9 ВАРИАНТ [ВСЯ КОМБИНАТОРИКА] [for IU7]
Дискретная математика
Вариант 7 - Домашняя работа №2
Дискретная математика
Вариант 17 - ДЗ №1 - ТФКП
Математический анализ
599 290 руб.
ДЗ-2 Графы, конечные автоматы СМ5,7,11 Шишкина
Дискретная математика
Билеты к 3-ему РК (СМ 2017)
Математический анализ
7 вариант ДЗ №1 - ТФКП
Математический анализ
599 290 руб.

Вычисления в динамическом программировании выполняются рекуррентно в том смысле, что оптимальное решение одной подзадачи используется в качестве исходных данных для следующей. Решив последнюю подзадачу, мы получим оптимальное решение исходной задачи. Способ выполнения рекуррентных вычислений зависит от того, как выполняется декомпозиция исходной задачи. В частности, подзадачи обычно связаны между собой некоторыми общими ограничениями. Если осуществляется переход от одной подзадачи к другой, то должны учитываться эти ограничения. Динамическое программирование позволяет резко сократить объем переборов вариантов и объем вычислений. Методику решения задач методом динамического программирования рассмотрим на примерах. При рассмотрении каждого примера особое внимание необходимо обратить на три основных элемента моделей динамического программирования. 1. Определение этапов. 2. Определение на каждом этапе вариантов решения. 3. Определение состояний на каждом этапе. Из перечисленных выше элементов понятие состояния, как правило, представляется весьма Самым сложным для восприятия является понятие состояния. Рассмотренные в этом разделе приложения последовательно показывают, что определение состояния меняется в зависимости от моделируемой ситуации. При рассмотрении каждого приложения полезно ответить на следующие вопросы. 1. Какие соотношения связывают этапы вместе? 2. Какая информация необходима для того, чтобы получить допустимые решения на текущем этапе без повторной проверки решений, принятых на предыдущих этапах? Пример 6.1. Пусть требуется найти путь минимальной стоимости неориентированной ациклической сети, показанной на рис. 6.1. Обозначим через cij стоимость проезда из пункта i в пункт j. Численные значения величин cij приведены непосредственно на рисунке. Цель – найти путь из п. 1 в п. 10, для которого общая стоимость проезда является минимальной. Сложность решения подобных задач сострит в том, что они по своей природе являются комбинаторными: необходимо перебрать все возможные маршруты и подсчитать общую стоимость проезда по каждому из них. Для того, чтобы решить эту комбинаторную задачу, используем метод динамического программирования, позволяющий получить искомое решение, не прибегая к полному перебору вариантов. При решении задачи будем рассматривать такие процессы принятия решений, которые позволяют ограничиться рассмотрением стратегий, зависящих только от наилучшего состояния. Для сетевой модели (см. рис. 6.1) узлы являются «состоянием». Дуги, выходящие из какого-либо узла, указывают направления возможных переходов, определяющих соответствующие решения, которые можно принимать в данном узле (состоянии). Такое толкование соответствует тому, что переход происходит из состояния в состояние, а состояния представляют собой узлы, в которых принимаются решения. Процедуру принятия решения будем называть стратегией. Оптимальная стратегия – стратегия оптимальная одновременно для каждого состояния. Теперь можно формулировать лежащий в основе динамического программирования принцип оптимальности. Принцип оптимальности. Оптимальная стратегия обладает тем свойством, что, каков бы ни был путь достижения некоторого состояния (пункта), последующие решения должны принадлежать оптимальной стратегии для части пути, начинающегося из этого состояния. Это означает, что оптимальный путь в примере 6.1 из п. 7 не зависит от того, каким маршрутом мы пришли в этот пункт. Следуя этой идее, можно сделать вывод, что если известны оптимальные пути из пп. 5–7, то достаточно легко определить и оптимальный путь из п. 2. Для этого достаточно суммировать стоимость переезда из п. 2 (будь то c2,5 или c2,6 ) с ранее вычисленной стоимостью оптимального пути из п. 5 или п. 6 соответственно, а затем сравнить полученные суммы и выбрать тот пункт, для которого эта сумма минимальная. Для того, чтобы практически использовать принцип оптимальности и его вычислительный смысл, введем следующие обозначения: fn(s) – стоимость, отвечающая стратегии минимальных затрат для пути от пункта s, если до конечного пункта остается n этапов: in(s) – решение, позволяющее достичь fn(s). Для успешного усвоения последующего материала этой главы очень важно понять систему обозначений, используемую в моделях динамического программирования. В принятых обозначениях все буквы и индексы несут важную смысловую нагрузку: f означает, что данное число есть значение целевой функции; s – что это значение зависит от состояния системы; для условий нашего примера это номер пункта сети. И, наконец, индекс n показывает, сколько этапов остается до конца пути. Конкретная запись, такая, например, как f2(5) будет обозначать стоимость минимальных затрат, необходимых на перемещение из пункта 5 до конечного пункта (пункт 10), когда для достижения поставленной цели остается 2 этапа. В примере 6.1 конечная цель, стоящая перед нами: достижение п. 10. Используя принятые обозначения, можно записать для что соответствует ситуации, когда поставленная цель достигнута (мы находимся в конечном пункте 10) и, следовательно, дальнейшие затраты равны нулю. В соответствии с изложенными выше рассуждениями легко определить f1(8) и f1(9): к f0(10) достаточно прибавить или . Выполнив эти действия, мы определим стоимость стратегии минимальных затрат для всех случаев, когда до конечного пункта остается один шаг (рис 2)

n = 1 csj + f0(j) n = 2 csj + f1(j)
10 i1(s) f1(s) 8 9 i2(s) f2(s)
8 1+0 10 1 5 7+1 5+4 8 8
9 4+0 10 4 6 3+1 4+4 8 4
7 7+1 1+4 9 5
Рис. 2. Рис. 3.

На следующем этапе, когда до конечного пункта остается два шага, мы можем находиться в пунктах 5, 6 или 7. Нашей задачей на этом этапе является определение f2(5), f2(6), f2(7). Эти величины можно определить исходя из следующих соображений Если, например, мы находимся в пункте 5, то из него можно попасть либо р пункт 8, либо в пункт 9. Величины c5,8 и c5,9 известны из условия задачи, функции f1(8) и f1(9) определены на предыдущем этапе. Следовательно, искомая функция f2(5) может быть определена как меньшая из сумм c5,8 + f1(8) или c5,9 +f1(9) (рис. 3). Как видим, начинает просматриваться определенная закономерность, которая может быть представлена в виде так называемого рекуррентного соотношения: (1) Выражение (1) означает, что необходимо вычислить все возможные значения стоимости, отвечающие различным стратегиям, суммируя соответствующую стоимость для очередного шага пути (перемещение из пункта s в пункт j) и стоимость, отвечающую оптимальной стратегии выбора пути из пункта j до конечного пункта. Характерной особенностью вычислительного процесса с использованием (1) является использованием результатов полученных на предыдущем этапе.

n = 3 csj + f2(j) n = 4 csj + f3(j)
5 6 7 i1(s) f1(s) 2 3 4 i2(s) f2(s)
2 10+8 12+4 6 16 1 2+16 5+12 1+18 3 7
3 5+8 10+4 7+5 7 12
4 15+4 13+5 7 18
Рис. 4. Рис. 5.

На рис. 2, 3, 4 и 5 приводятся результаты поэтапных расчетов на основе рекуррентного соотношения (1) для рассматриваемого примера Они представлены в виде таблиц, так как это наиболее распространенная форма записи числовых результатов в динамическом программировании. Нетрудно заметить, что изложенная процедура расчетов является итеративной и состоит в выполнении одних и тех же операций на каждом шаге, чтобы по известному fn-1(s) вычислить .fn(s) Несмотря на возможные большие объемы вычислений алгоритм расчетов, как правило, несложен и легко программируется нa ЭВМ. Проблема заключается в том, что рекуррентные соотношения имеют различный вид для разных задач Вид этих соотношений определяется структурой решаемой задачи. Это обстоятельство не дает возможности создать общую программу дли решения на ЭВМ всех задач динамического программирования, как это делается, например, в линейном программировании. Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом (обычно даже одной) переменных в каждой. Это значительно сокращает объем вычислений. Однако такое преимущество достигается лишь при двух условиях: когда критерий оптимальности аддитивен, т.е. общее оптимальное решение является суммой оптимальных решений каждого шага, и когда будущие результаты не зависят от предыстории того состояния системы, при котором принимается решение. Все это вытекает из принципа оптимальности Беллмана, лежащего в основе теории динамического программирования. Из него же вытекает основной прием — нахождение правил доминирования, на основе которого на каждом шаге производится сравнение вариантов будущего развития и заблаговременное отсеивание заведомо бесперспективных вариантов. Когда эти правила обращаются в формулы, однозначно определяющие элементы последовательности один из других, их называют разрешающими правилами. Несмотря на выигрыш в сокращении вычислений, их объем остается очень большим. Поэтому размерность практических задач динамического программирования всегда незначительна, что ограничивает его применение. Можно выделить два наиболее общих класса задач, к которым в принципе мог бы быть применим этот метод, если бы не «проклятие размерности» (на самом деле на таких задачах, взятых в крайне упрощенном виде, пока удается лишь демонстрировать общие основы метода и анализировать экономико-математические модели). Первый — задача планирования деятельности экономического объекта (предприятия, отрасли и т.п.) с учетом изменения потребности в производимой продукции во времени. Второй класс задач — оптимальное распределение ресурсов между различными направлениями во времени. Сюда можно отнести, в частности, такую интересную задачу: как распределить урожай зерна каждого года на питание и на семена, чтобы за ряд лет получить наибольшее количество хлеба? Задача распределения ограниченных ресурсов Постановка задачи. Для развития отрасли на плановый период выделены капитальные вложения в размере X. Имеется n объектов вложений, по каждому из которых известна ожидаемая прибыль, получаемая от вложения определенной суммы средств. Необходимо распределить капитальные вложения между n объектами таким образом, что бы получить максимально возможную суммарную прибыль Задача управления запасами предприятия Постановка задачи. Предприятие должно разработать календарную программу выпуска некоторого вида изделия на плановый период, состоящий из N отрезков. Предполагается, что для каждого из этих отрезков имеется точный прогноз спроса на выпускаемую продукцию Время изготовления партии изделия настолько мало, что им можно пренебречь. Соответственно продукция, изготавливаемая в течение отрезка t может быть использована для полного и частичного покрытия спроса в течение этого отрезка времени. Для разных отрезков спрос не одинаков. Кроме того, ни экономические показатели производства влияют размеры изготавливаемых партий, поэтому предприятию нередко бывает выгодно изготовлять в течении некоторого месяца продукцию в объеме, превышающем спрос в пределах этого отрезка, и хранить излишки, используя их для удовлетворения последующего спроса. Вместе с тем хранение возникающих при этом запасов связано с определенными затратами. В зависимости oт обстоятельств затраты обусловлены такими факторами, как проценты на капитал, взятый взаймы для создания запасов; арендная плата за складские помещения; страховые взносы и расходы по содержанию запасов. Эти затраты необходимо учитывать и при установлении программы выпуска. Задача о рюкзаке Постановка задачи. Имеется рюкзак заданной грузоподъемности; также имеется некоторое множество предметов различного веса и различной стоимости (ценности); требуется упаковать рюкзак так, чтобы он закрывался и сумма стоимостей упакованных предметов была бы максимальной. Люди также интересуются этой лекцией: Дескриптивные исследования, опрос и наблюдение. Задача планирования рабочей силы Постановка задачи. Число рабочих, необходимых для выполнения проекта регулируется путем найма и увольнения. Как наем так и увольнение рабочих связано с дополнительными затратами. Требуется определить, каким образом должна регулироваться численность рабочих в период выполнения проекта, чтобы дополнительные затраты, связанные с наймом и увольнением рабочих были минимальными. Задача замены оборудования Постановка задачи. Необходимо определить оптимальную стратегию использования оборудования в период времени длительностью n лет, если для оборудования возраста t лет известны прибыль от использования оборудования, годовые затраты на обслуживание, остаточная стоимость оборудования и стоимость нового оборудования. Суть оптимальной стратегии использования оборудования заключается в том, чтобы в начале каждого года принять решение либо об эксплуатации оборудования еще один год, либо о замене его новым. Задача инвестирования Постановка задачи. В начале каждого из следующих n лет необходимо сделать инвестиции P1, P2,…, Pn соответственно. Есть возможность вложить капитал в два банка: первый банк выплачивает годовой сложный процент r1, а второй - r2. Для поощрения депозитов оба банка выплачивают новым инвесторам премии в виде процента от вложенной суммы. Премиальные меняются от года к году, и для і-ого года равны qi1 и qi2 в первом и втором банках соответственно. Они выплачиваются к концу года, на протяжении которого сделан вклад, и могут быть инвестированы в один из двух банков на следующий год. Это значит, что лишь указанные проценты и новые деньги могут быть инвестированы в один из двух банков. Размещенный в банке вклад должен находится там до конца рассматриваемого периода. Необходимо разработать стратегию инвестиции на следующие n лет.

Похожие публикации:
  1. Body css что это
  2. Usb beep message в биосе что это
  3. Как называть блоки в html
  4. Что такое легенда в информатике

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *