ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ: ХАРАКТЕРИСТИКИ, ПРИМЕР, ДОСТОИНСТВА, НЕДОСТАТКИ - ТЕХНОЛОГИЯ - 2025

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

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

Динамическое программирование. Подзадачи, накладываемые на последовательность Фибоначчи. Источник: Wikimedia commons, en: User: Dcoatzee, отслежено пользователем: Stannered / Public domain

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

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

Это прекрасная идея для исправления памяти, когда использование дополнительного места может сократить время, необходимое для поиска решения.

Особенности динамического программирования

Следующие важные характеристики - это то, с чем у вас должна быть проблема, прежде чем можно будет применить динамическое программирование:

Оптимальная подконструкция

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

Например, в графе оптимальная подструктура будет представлена ​​на кратчайшем пути r, который идет от вершины s к вершине t:

То есть в этом кратчайшем r можно взять любую промежуточную вершину i. Если r действительно является кратчайшим маршрутом, то его можно разделить на подмаршруты r1 (от s до i) и r2 (от i до t) таким образом, чтобы они, в свою очередь, были кратчайшими маршрутами между соответствующими вершинами.

Следовательно, чтобы найти кратчайшие пути, решение может быть легко сформулировано рекурсивно, что и делает алгоритм Флойда-Уоршалла.

Перекрывающиеся подзадачи

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

Например, чтобы создать ряд Фибоначчи, мы можем рассмотреть эту рекурсивную формулировку: Fn = F (n - 1) + F (n - 2), взяв в качестве базового случая F1 = F2 = 1. Тогда мы будем иметь: F33 = F32 + F31 и F32 = F31 + F30.

Как видите, F31 разбивается на рекурсивные поддеревья как F33, так и F32. Хотя общее количество подзадач действительно невелико, если вы примете такое рекурсивное решение, вы в конечном итоге будете решать одни и те же проблемы снова и снова.

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

Нисходящий подход

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

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

Подход «снизу вверх

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

Это также обычно делается в табличной форме, итеративно генерируя решения для больших и больших подзадач, используя решения меньших подзадач. Например, если значения F31 и F30 уже известны, значение F32 можно рассчитать напрямую.

Сравнение с другими техниками

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

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

пример

Минимальные шаги для достижения 1

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

- Вычтите 1 из числа. (е = е-1).

- Если он делится на 2, он делится на 2 (если e% 2 == 0, то e = e / 2).

- Если он делится на 3, он делится на 3 (если e% 3 == 0, то e = e / 3).

Основываясь на шагах, описанных выше, необходимо найти минимальное количество этих шагов, чтобы довести e до 1. Например:

- Если e = 1, результат: 0.

- Если e = 4, результат: 2 (4/2 = 2/2 = 1).

- Когда e = 7, результат: 3 (7-1 = 6/3 = 2/2 = 1).

фокус

Можно подумать о том, чтобы всегда выбирать шаг, который делает n настолько низким, насколько это возможно, и продолжать так, пока он не достигнет 1. Однако можно видеть, что эта стратегия здесь не работает.

Например, если e = 10, шаги будут: 10/2 = 5-1 = 4/2 = 2/2 = 1 (4 шага). Однако оптимальная форма: 10-1 = 9/3 = 3/3 = 1 (3 шага). Следовательно, необходимо попробовать все возможные шаги, которые можно выполнить для каждого найденного значения n, выбрав минимальное количество этих возможностей.

Все начинается с рекурсии: F (e) = 1 + min {F (e-1), F (e / 2), F (e / 3)}, если e> 1, принимая в качестве базового случая: F (1) = 0. Имея рекуррентное уравнение, вы можете начать кодировать рекурсию.

Однако можно увидеть, что у него есть частично совпадающие подзадачи. Кроме того, оптимальное решение для данного входа зависит от оптимального решения его подзадач.

Как в запоминании, где решения подзадач, которые были решены, сохраняются для дальнейшего использования. Или, как в динамическом программировании, вы начинаете снизу, продвигаясь к заданному e. Тогда оба кода:

запоминание

Динамическое восходящее программирование

преимущество

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

Прожорливые алгоритмы против динамического программирования

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

Следовательно, жадные алгоритмы могут делать предположения, которые выглядят оптимальными в то время, но становятся дорогостоящими в будущем и не гарантируют глобального оптимума.

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

Недостатки

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

- Часто выходное значение сохраняется без использования в следующих подзадачах во время выполнения. Это приводит к ненужному использованию памяти.

- В динамическом программировании функции вызываются рекурсивно. Благодаря этому объем памяти стека постоянно увеличивается.

Рекурсия против динамического программирования

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

Если вы хотите, чтобы программа работала быстрее и не имела ограничений памяти, предпочтительнее использовать динамическое программирование.

Приложения

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

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

Алгоритмы на основе динамического программирования

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

- Числовой ряд Фибоначчи.

- Башни Ханоя.

- Все пары более коротких маршрутов через Флойд-Уоршалл.

- Проблема с рюкзаком.

- Планирование проекта.

- Кратчайший путь через Дейкстру.

- Управление полетом и управление робототехникой.

- Математические задачи оптимизации.

- Таймшер: запланируйте задание для максимального использования ЦП.

Числовой ряд Фибоначчи

Числа Фибоначчи - это числа, расположенные в следующей последовательности: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144 и т. Д.

В математической терминологии последовательность чисел Фибоначчи Fn определяется рекуррентной формулой: F (n) = F (n -1) + F (n -2), где F (0) = 0 и F ( 1) = 1.

Нисходящий подход

В этом примере массив поиска со всеми начальными значениями инициализируется значением -1. Когда требуется решение подзадачи, сначала выполняется поиск в этой матрице поиска.

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

Подход «снизу вверх

В этом случае для того же ряда Фибоначчи сначала вычисляется f (0), затем f (1), f (2), f (3) и т. Д. Таким образом, решения подзадач строятся снизу вверх.

Ссылки

1. Винит Чоудхари (2020). Введение в динамическое программирование. Developer Insider. Взято с сайта developerinsider.co.
2. Алекс Аллен (2020). Динамическое программирование на C ++. C Программирование. Взято с сайта cprogramming.com.
3. После Академии (2020). Идея динамического программирования. Взято с: afteracademy.com.
4. Анируддха Чаудхари (2019). Динамическое программирование и рекурсия - разница, преимущества с примером. Стек CSE. Взято с: csestack.org.
5. Code Chef (2020). Учебник по динамическому программированию. Взято с: codechef.com.
6. Programiz (2020). Динамическое программирование. Взято с: programiz.com.