Динамическое программирование — это термин, который, вероятно, уже использовался, если вы работали в этой области какое-то время. Эта тема часто поднимается на совещаниях по анализу проекта и в повседневных разговорах инженеров, а также является центральной темой технических собеседований. Стратегия «разделяй и властвуй» — надежный метод достижения любой цели. В компьютерном программировании та же самая идея верна. Многочисленные трудности имеют подтипы, которые можно выделить и рассматривать отдельно, что позволяет окончательно решить основную проблему. В этой статье мы обсудим алгоритм динамического программирования и Python.
Что такое динамическое программирование?
Динамическое программирование — это метод решения сложных проблем, сначала сводящий их к более простым, а затем использующий решения этих более простых проблем в качестве строительных блоков для решения исходной проблемы.
Мы разделяем проблему под рукой на управляемые куски. В большинстве случаев единственное реальное различие между проблемой родителя и проблемой его ребенка заключается в их относительных размерах. Таким образом, эти мини-проблемы можно разбить на еще большее количество мини-проблем и так далее до бесконечности. Представьте, что проблема и ее различные подзадачи образуют дерево. Первыми решаются «листовые» проблемы, затем их «родительские» проблемы и так далее по дереву проблем. По мере того, как мы справляемся с более мелкими трудностями, мы записываем свой прогресс для дальнейшего использования. Это позволяет нам пропустить эту часть проблемы в будущем.
Этот метод похож на метод «разделяй и властвуй» тем, что он разбивает проблему на более мелкие проблемы, которые можно решать независимо друг от друга, а затем объединять для получения окончательного решения.
Как работает динамическое программирование?
Динамическое программирование эффективно, потому что оно упрощает решение сложных задач, разбивая их на составные части. Следующим шагом является определение наилучших ответов на эти последующие вызовы. Результаты этих процедур можно запомнить, чтобы соответствующие решения можно было извлечь из памяти и использовать без дальнейших вычислений. Также решение можно сохранить, чтобы не пересчитывать ранее решенные подзадачи.
Существует два метода динамического программирования:
№1. Нисходящий подход
В компьютерных науках проблемы обычно решаются путем рекурсивного построения решений или путем использования результатов предыдущих шагов для решения поставленной задачи. Можно запомнить или вести таблицу решений подзадач, если они похожи. Метод «сверху вниз» основан на заучивании наизусть. Мемоизация аналогична повторному выполнению рекурсии и кэширования. Рекурсия предполагает косвенный вызов функции, а кэширование — отслеживание промежуточных результатов.
Среди многих преимуществ подхода «сверху вниз» можно выделить:
- Метод «сверху вниз» прост для понимания и применения. Чтобы лучше понять, что нужно сделать, этот метод разбивает проблемы на составные элементы. Каждое новое развитие приносит с собой облегчение ранее непреодолимого препятствия. Некоторые части могут даже быть применимы к другим задачам.
- Это позволяет решать подзадачи по требованию. Метод «сверху вниз» позволит разбить проблемы на управляемые фрагменты, а решения для этих фрагментов будут сохранены для последующего использования. Затем клиенты могут обратиться за помощью в исправлении каждого компонента.
- Отладка также упрощается. Разделение проблемы на более мелкие части облегчает поиск ответа и выявление потенциальных ошибок.
Ниже приведены некоторые недостатки использования нисходящего подхода:
- Стратегия «сверху вниз» использует метод рекурсии, который занимает больше памяти в стеке вызовов, чем другие подходы. В конечном итоге это приводит к снижению производительности. Кроме того, может произойти переполнение стека, если рекурсия уходит слишком далеко в прошлое.
№ 2. Подход «снизу вверх
После того как решение проблемы было выражено в терминах ее подзадач способом, который зацикливается сам на себе, пользователи могут переписать проблему, используя восходящий подход, при котором они сначала решают меньшие подзадачи, а затем применяют свои решения к более крупным. .
В отличие от метода «сверху вниз» при использовании метода «снизу вверх» исключается рекурсия. Таким образом, рекурсивные функции не добавляют ненужных издержек и не вызывают переполнения стека. Кроме того, он позволяет сжимать данные. Временная сложность рекурсии снижается за счет устранения необходимости повторного вычисления одних и тех же значений.
Некоторые преимущества работы с нуля заключаются в следующем:
- Сначала он определяет, как большая проблема будет построена из более мелких, многократно используемых подзадач.
- Отказ от рекурсии помогает лучше использовать доступную память. Сложность синхронизации снижается как побочный эффект.
Характеристики динамического программирования
Есть две отличительные особенности динамического программирования:
№1. Подзадачи перекрываются
Модификации основной проблемы, которые легче поддаются управлению, называются «подзадачами». Последовательность Фибоначчи, в которой каждое число равно сумме двух предыдущих (0, 1, 1, 2, 3, 5, 8,…). Вы можете разделить задачу поиска n-го значения в последовательности Фибоначчи на более управляемые части. По мере того как вы находите решения, решая одну и ту же подзадачу снова и снова, эти перекрывающиеся наборы трудностей становятся все труднее решить.
Динамическое программирование можно использовать для разделения больших программных заданий на управляемые фрагменты из-за повсеместного возникновения перекрывающихся подзадач.
№ 2. Подструктура имеет оптимальные свойства
Свойство оптимальной подструктуры проявляется, когда из решений всех подзадач можно создать оптимальное решение. Чтобы рекурсия работала, вы должны применить ответ, полученный из каждого перекрытия, ко всей проблеме. Свойство оптимальной подструктуры проявляется у всей задачи, когда, как и в случае последовательности Фибоначчи, каждая подзадача имеет решение, которое можно применить к следующей подзадаче в последовательности для определения ее значения.
Использование динамического программирования в реальном мире
Вот использование динамического программирования.
№1. Проблема с рюкзаком
Динамическое программирование широко использовалось для решения задачи о рюкзаке. Вот проблемы, с которыми мы сталкиваемся:
Идеальное значение для каждой подпроблемы, определяемое количеством рассматриваемых предметов и объемом свободного места в рюкзаке, может храниться в двумерном массиве, что позволяет быстро решить эту проблему. Мы можем максимизировать ценность, включая или исключая текущий элемент на каждом этапе. Ответ можно найти в правом нижнем углу массива.
Задача о рюкзаке может использоваться в самых разных контекстах, от упаковки багажа до принятия инвестиционных решений и распределения ресурсов.
№ 2. Кратчайший путь для всех пар
Проблема кратчайшего пути во взвешенном графе — еще одно типичное применение динамического программирования. Используя такие методы, как Флойд-Уоршалл или Беллман-Форд, мы можем найти кратчайший путь между любыми двумя заданными парами узлов.
Чтобы отслеживать кратчайший путь между любыми двумя заданными узлами, эти алгоритмы используют трехмерный массив. Также, чтобы отслеживать, насколько далеко они находятся от начальной точки, они сравнивают результат с расстоянием между начальной точкой и промежуточным узлом на каждом этапе. После завершения итераций окончательным решением будет матрица расстояний.
Существует несколько применений для решения проблемы кратчайшего пути для всех пар, например, в сетевом анализе, маршрутизации, навигации, анализе социальных сетей и т. Д.
№3. Резьба по шву
В области обработки изображений вырезание швов представляет собой интригующее применение динамического программирования. Задача состоит в том, чтобы уменьшить размер изображения, не изменяя ни одной из его основных характеристик. Маршруты с низким энергопотреблением в изображении, известные как швы, могут использоваться для вычитания или добавления пикселей для достижения этого эффекта.
Используя динамическое программирование, мы можем рассчитать совокупную энергию каждого пикселя изображения на основе его градиента и соседей, а затем использовать эту информацию, чтобы определить, какие швы следует удалить или добавить. Затем, продвигаясь вверх от нижней части изображения, мы можем найти шов с наименьшим количеством потенциальной энергии. Этот метод можно использовать снова, пока не будет достигнут необходимый размер.
Кроме того, изображения можно изменять, обрезать, перенацеливать и т. д. с помощью вырезания швов.
№ 4. Машинное обучение и геномика
Проблемы машинного обучения и геномики, такие как выравнивание последовательностей, скрытые марковские модели и филогенетические деревья, — все они поддаются решению задач динамического программирования.
Выравнивание нескольких последовательностей символов (часто ДНК или белков) для выявления общих черт называется выравниванием последовательностей. Это может пролить свет на их эволюционные связи, функции в обществе или структурные характеристики. Оптимальное выравнивание можно найти с помощью динамического программирования, присваивая баллы совпадениям и несоответствиям между последовательностями.
Вероятностные модели, известные как скрытые марковские модели, используются для описания данных временных рядов, зависящих от неизвестных состояний. Они полезны для моделирования сложных явлений, таких как распознавание речи, НЛП, биоинформатика и т. д. При наличии набора наблюдений методы динамического программирования, такие как Витерби и вперед-назад, могут определить наиболее вероятную последовательность скрытых состояний.
Филогенетические деревья показывают связи между видами или генами во времени. Из этих общих черт можно сделать вывод об общих предках, датах расхождения и эволюционных событиях. Кроме того, алгоритм динамического программирования, такой как Fitch и Sankoff, можно использовать для создания оптимальных филогенетических деревьев с использованием данных секвенирования.
№ 5. Криптография
Криптография, наука о секретных коммуникациях, также выигрывает от способности динамического программирования решать проблемы. Шифрование, дешифрование, цифровые подписи, аутентификация и другие подобные процессы являются частью криптографии.
Шифрование преобразует информацию из удобочитаемой для человека в удобочитаемую для секретного ключа. Расшифровка — это процесс преобразования зашифрованных данных обратно в открытый текст с использованием исходного или нового ключа. Цифровые подписи позволяют проверить подлинность и целостность сообщения или документа. Проверка учетных данных отправителя или получателя может подтвердить личность отправителя или получателя.
Различные типы криптографии, включая криптографию с динамическим ключом, криптографию на основе кода и криптографию на основе динамического программирования, можно реализовать с помощью динамического программирования.
Криптография с динамическим ключом — это механизм шифрования и дешифрования сообщений с постоянно меняющимися ключами. Ключи, которые являются «динамическими», — это те, которые развиваются с течением времени или в ответ на другие факторы. Это делает их более безопасными, чем статические ключи, которые уязвимы для атак. Можно использовать динамическое программирование для генерации и поддержания ключей в актуальном состоянии при реализации криптографии с динамическим ключом.
Используя технику, известную как криптография на основе кода, можно шифровать и расшифровывать сообщения, применяя в процессе коды с исправлением ошибок. Ошибки передачи можно исправить с помощью кодов исправления ошибок. Использование криптографии на основе кода считается квантово-устойчивым, поскольку оно защищено от атак со стороны квантовых компьютеров. Динамическое программирование можно использовать для шифрования и расшифровки сообщений с использованием криптосистемы на основе кода.
В качестве метода шифрования и дешифрования данных криптография на основе динамического программирования опирается на алгоритм динамического программирования. Для решения задач оптимизации методы динамического программирования обычно разбивают задачу на набор более простых подзадач. Криптография динамического программирования использует рюкзак, кратчайший путь и вырезание швов.
Что такое реальный пример динамического программирования?
Многочисленные экземпляры реальных программных приложений используют динамическое программирование для обеспечения гибкости и эффективности при одновременном снижении нагрузки на ресурсы хост-системы. Некоторые примеры следующие:
- Карты Гугл. Карты Google используют динамическое программирование для поиска кратчайшего маршрута из заданного источника в несколько различных пунктов назначения.
- Нетворкинг. Последовательная передача данных от одного отправителя нескольким получателям.
- Проверка орфографии. Алгоритм расстояния редактирования определяет количество шагов, необходимых для преобразования одного слова в другое, и обеспечивает количественную меру степени несходства между двумя словами.
- Программное обеспечение для плагиата. Методы расстояния до документа помогают определить сходство текстового документа.
- Поисковые системы. Чтобы определить, насколько на самом деле похожи две части интернет-контента.
Как решать задачи динамического программирования?
Изучение формулы решения задач динамического программирования — следующий шаг после понимания концепции динамического программирования. Вот несколько советов о том, как применить динамическое программирование к рассматриваемой проблеме и найти работоспособное решение:
№1. Признайте проблему динамического программирования
Наиболее важной частью является осознание того, что алгоритм динамического программирования может решить указанную постановку задачи. Решение этой проблемы требует сначала определить, можно ли каждое из условий задачи разделить на более мелкие части в виде функции.
№ 2. Определите причины проблемы
Если вы уже пришли к выводу, что динамическое программирование является подходящим инструментом для работы, следующим шагом будет выявление рекурсивной структуры проблемы среди составляющих ее подзадач. В этом случае вы должны учитывать изменчивый характер условий проблемы. Эта переменная может быть позицией массива или скоростью решения проблемы.
Кроме того, решающее значение имеет подсчет составных частей задачи.
№3. Выберите между итеративным и рекурсивным методом
Чтобы решить проблемы динамического программирования, вы можете использовать итеративный или рекурсивный подход. Из того, что было сказано до сих пор, можно с уверенностью сказать, что рекурсивный метод предпочтительнее. Однако все вышеупомянутые соображения остаются в силе сами по себе, независимо от выбранного метода решения проблемы.
Как для рекурсивного, так и для итеративного подходов необходимо указать рекуррентное отношение и базовый случай проблемы.
№ 4. Включите систему запоминания
При решении задачи с похожей структурой может быть полезно вспомнить прошлый опыт решения сопоставимых подзадач. В результате этого уменьшится временная сложность задачи. Временная сложность задачи может расти экспоненциально, если мы будем решать одни и те же подзадачи снова и снова, не используя запоминание.
№ 5. Поместите рекуррентное отношение в слова
При решении проблемы многие программисты пропускают определение рекуррентного отношения и сразу переходят к написанию кода. Вы лучше поймете проблему и сможете писать код быстрее, если сможете явно выразить рекуррентное отношение перед тем, как начнете.
Алгоритм динамического программирования
Большинство приложений динамического программирования включают рекурсивный алгоритм. Использование динамического программирования для оптимизации подразумевает, что рекурсия является неотъемлемой частью большинства задач оптимизации.
Однако решить полностью рекурсивные задачи с помощью динамического программирования невозможно. Рекурсия может найти решение только с помощью стратегии «разделяй и властвуй», если нет перекрывающихся подзадач, как в задаче последовательности Фибоначчи.
Это связано с тем, что основные подзадачи в рекурсивном алгоритме, таком как сортировка слиянием, не перекрываются, что исключает использование динамического программирования.
Различные типы алгоритмов динамического программирования
Вот различные типы алгоритмов динамического программирования.
№1. Самая длинная общая подпоследовательность
Элементы самой длинной общей подпоследовательности (LCS) могут появляться в любом порядке в исходных последовательностях; LCS определяется как самая длинная подпоследовательность, общая для всех указанных последовательностей.
Если предоставлены две последовательности S1 и S2, то последовательность Z, являющаяся подпоследовательностью как S1, так и S2, называется их общей подпоследовательностью. В качестве дополнительного требования Z должен состоять из строго возрастающей последовательности индексов множеств S1 и S2.
Индексы выбранных элементов в Z должны строго возрастать, чтобы образовалась возрастающая последовательность.
№ 2. Алгоритм Флойда-Уоршалла
Поиск кратчайшего пути между каждой парой вершин во взвешенном графе является целью алгоритма Флойда-Уоршалла. Этот метод обрабатывает диаграммы с весами в обоих направлениях. С другой стороны, это не так для циклов, в которых сумма ребер отрицательна.
Алгоритм Флойда, алгоритм Роя-Флойда, алгоритм Роя-Уоршелла и алгоритм WFI — все это названия алгоритма Флойда-Уоршалла.
Этот алгоритм использует метод динамического программирования для поиска оптимальных путей.
Как алгоритм динамического программирования решает задачи LCS быстрее, чем рекурсивный метод?
Динамическое программирование снижает накладные расходы на вызов функции. Он запоминает результат каждого вызова функции, чтобы последующие вызовы могли использовать сохраненные данные, не повторяя ту же работу.
Каждый раз, когда элемент X сравнивается с элементом Y, результаты записываются в таблицу, чтобы их можно было использовать в последующих вычислениях в вышеупомянутом динамическом процессе.
Таким образом, время выполнения динамического метода равно времени, необходимому для заполнения таблицы (O(mn)). Напротив, сложность рекурсивного алгоритма равна 2max(m, n). Также читайте Как выбрать правильный тип алгоритма шифрования для нужд вашего бизнеса
Каковы проблемы динамического программирования в Python
Используя динамическое программирование, можно найти наиболее подходящее решение для любого количества различных условий задачи. Далее мы рассмотрим некоторые из наиболее часто запрашиваемых известных формулировок задач и предоставим краткое объяснение вместе с соответствующим кодом Python.
№1. Рюкзак (0-1) Ограниченный
В этой ситуации вам даны цены и вес N товаров и поставлена задача поместить их в рюкзак вместимостью W; цель состоит в том, чтобы свести к минимуму количество выбранных предметов, но при этом все поместиться в рюкзаке.
Большинство технических собеседований в торговых организациях требуют от кандидатов решения задачи о рюкзаке, что является классическим примером техники динамического программирования.
Постановка задачи Предположим, что у вас есть сумка вместимостью W и список вещей, каждая из которых имеет вес и соответствующую прибыль. Цель состоит в том, чтобы максимизировать прибыль за счет эффективного плохого заполнения.
Ответ заключается в том, чтобы создать таблицу со столбцами для каждого мыслимого веса от 1 до W и строками для фактически выбранных вами весов. Эта таблица будет называться dp[][]. Если «j» — это вместимость рюкзака и включены первые «i» элементов в массиве веса/предмета, то состояние /cell dp[i][j] в таблице указывает на максимально возможную прибыль.
В результате значение в последней ячейке будет означать решение. Важно упаковать только то, что не превышает ограничения по весу рюкзака. Есть две альтернативы критерию «вес>wt[i-1]», где все столбцы могут быть заполнены.
№ 2. 0/1 Ранцевая ограниченная мемоизация
Наполните мешок предметами известного веса и прибыли, размер K. Ваша цель — максимизировать свой заработок. Здесь мы будем использовать запоминание вместо табуляции, чтобы посмотреть, сможем ли мы решить проблему.
В приведенной выше задаче о рюкзаке 0/1 использовалась восходящая стратегия для поиска решения, тогда как в этой задаче для получения решения используется нисходящий подход, основанный на запоминании.
Динамическое программирование использует запоминание, чтобы уменьшить необходимость многократного решения одних и тех же частей задачи. Это избавляет от необходимости постоянно решать подзадачи и упрощает процесс генерирования выходных данных.
Постановка задачи Предположим, что у вас есть сумка вместимостью W и список вещей, каждая из которых имеет вес и соответствующую прибыль. Если мешок наполнен с максимально возможной эффективностью, можно получить наивысший потенциальный уровень прибыли.
Решение состоит в том, чтобы сначала построить двумерный массив для хранения окончательных ответов на отдельные подзадачи. В столбцах таблицы будут перечислены все потенциальные веса от 1 до W, разделенные на столько разделов, а в строках будут показаны веса, которые вы выбираете в каждый момент времени.
Мы используем массив dp для отслеживания каждой решенной подзадачи. Вместо того, чтобы решать ранее решенную подзадачу, мы просто возвращаем ее ответ.
№3. Проблема равного подмножества
Найдите такой раздел данного набора, чтобы общее количество элементов в обоих подмножествах было одинаковым, используя динамическое программирование для решения проблемы с равными подмножествами. В дополнение к своим другим названиям проблема равных подмножеств (или проблема разделения) является яркой иллюстрацией силы динамического программирования.
Поставленная задача требует, чтобы мы разделили массив arr пополам, чтобы каждое из полученных подмножеств имело одинаковый общий размер.
В качестве решения нам нужно построить двумерный массив размерами (сумма/2+1)*(цель+1). Здесь результаты разбиения исходного массива могут быть сохранены для каждого подмножества и каждой суммы, а затем извлечены. Первое измерение массива будет представлять различные подмножества, которые можно создать, а второе измерение массива будет представлять различные суммы, которые можно вычислить путем объединения подмножеств.
Преимущества динамического программирования
Вот некоторые из преимуществ динамического программирования.
№1. Эффективное средство
Динамическое программирование — мощный инструмент для поиска оптимальных решений проблем с оптимальной подструктурой и перекрывающимися подзадачами. Разбивая их на управляемые части, эти проблемы легче решать с помощью этого метода. Динамическое программирование позволяет создать оптимальное решение, избегая повторяющихся вычислений и повторно используя ответы на подзадачи.
№ 2. Облегчает поиск проблем
Решение сложной проблемы может быть проще, если сначала разбить ее на более простые части. Это упрощает решение сложных проблем, разбивая их на более управляемые части. Этот метод упрощает решение и делает задачу более доступной.
№ 3. Эффективный
Устраняя ненужные вычисления и повторяя ранее решенные подзадачи, динамическое программирование может значительно сократить время, необходимое для решения задачи. Когда подпроблемы пересекаются, метод может помочь, уменьшив общее количество мер, необходимых для решения проблемы.
№ 4. Эффективен, когда у проблемы есть несколько решений
Динамическое программирование может помочь определить, какое из нескольких возможных объяснений более вероятно. Когда есть несколько жизнеспособных вариантов решения проблемы, этот метод может помочь нам выбрать лучший из них.
Каковы недостатки динамического программирования?
Вот некоторые из недостатков динамического программирования.
№1. Подпроблемы, которые продолжают повторяться
Динамическое программирование работает лучше всего, когда проблема имеет перекрывающиеся подзадачи, что может быть не всегда. Это не сработает и, вероятно, не даст вам наилучшего решения, если отдельные проблемы не пересекаются.
№ 2. Сложность во времени и пространстве
Если проблема большая, для динамического программирования может потребоваться много памяти и места для хранения, что увеличивает временную и пространственную сложность решения. Используя память, этот подход сохраняет промежуточные результаты в таблице или таблице запоминания.
№3. Структура проблемы
Хотя динамическое программирование эффективно для определенных проблемных структур, оно не всегда является лучшим выбором. Этот метод лучше всего работает, когда проблема имеет перекрывающиеся подзадачи, поэтому он может быть неприменим к другим ситуациям.
№ 4. Трудно применить на практике
Динамическое программирование требует глубоких знаний алгоритмов и структур данных, что затрудняет его реализацию для начинающих. Этот метод требует предварительного обдумывания и глубокого знакомства с рассматриваемой проблемой.
Заключение
В заключение, динамическое программирование — эффективный метод поиска ответов, хотя другие подходы предпочтительнее. Крайне важно знать все за и против и выбрать правильный метод в зависимости от проблемы. Для задач с оптимальной структурой и перекрывающимися подзадачами динамическое программирование может дать оптимальное решение; однако этот метод не всегда применим.
Хотя его сложно разработать и он требует много памяти, его способность оптимизировать процесс решения задач и сокращать время вычислений делает его важным ресурсом для ученых-компьютерщиков и математиков.
Часто задаваемые вопросы по динамическому программированию
В чем разница между линейным программированием и динамическим программированием?
Для задач линейной оптимизации у нас есть алгоритм линейного программирования (ЛП), а для общих задач нелинейной оптимизации с невыпуклыми ограничениями у нас есть динамическое программирование (ДП), которое гарантирует глобальную оптимальность решения.
Насколько сложно научиться динамическому программированию?
Общеизвестно, что динамическое программирование — сложный предмет, особенно для новичков в области компьютерных наук. Тем не менее, динамическое программирование можно легко освоить при твердом понимании основных принципов и достаточной практике.
Сложно ли динамическое программирование?
Они жесткие! Начнем с того, что идея методов динамического программирования может быть трудной для понимания. Любой опытный программист подтвердит, что овладение DP требует значительных временных затрат. Также необходим навык разложения проблемы на составные части и повторной сборки ее в работоспособное целое.
похожие статьи
- УПРАВЛЕНИЕ ВРЕМЕНЕМ ПРОЕКТА: процессы, инструменты и программное обеспечение для эффективного управления
- AMAZON SEO: как оптимизировать ваши продукты, чтобы лучше ранжироваться
- САМЫЕ ПОПУЛЯРНЫЕ ЯЗЫКИ ПРОГРАММИРОВАНИЯ: руководство 2023 года
- ЧТО ТАКОЕ КОМПЬЮТЕРНОЕ ПРОГРАММИРОВАНИЕ: примеры, типы, курсы и программное обеспечение
- Завещания онлайн: лучшие онлайн-создатели завещаний.
Справка
