Динамическое программирование — это концепция, разработанная Ричардом Беллманом, математиком и экономистом.
В то время Беллман искал способ решения сложных задач оптимизации. Задачи оптимизации требуют от вас выбора наилучшего решения из набора вариантов.
Примером задачи оптимизации является задача о коммивояжере. Цель состоит в том, чтобы найти кратчайший маршрут, позволяющий продавцу посетить каждый город ровно один раз и вернуться в начальный город.
Подход Беллмана к этим проблемам заключался в том, чтобы разбить их на более мелкие подзадачи и решить подзадачи от самой маленькой до самой большой. Затем он сохранял результаты подзадач и повторно использовал их для решения более крупных подзадач. Это основная идея динамического программирования.
Оглавление
Что такое динамическое программирование?
Динамическое программирование решает проблемы оптимизации, разбивая их на более мелкие подзадачи, решая каждую подзадачу один раз и сохраняя их решения, чтобы их можно было повторно использовать и комбинировать для решения более крупной проблемы. Проблемы решаются от самой маленькой до самой большой, что позволяет повторно использовать решения.
Как работает динамическое программирование?
Решение задачи с помощью динамического программирования включает в себя следующие шаги:
Чтобы увидеть это в действии, мы вычислим 6-е число Фибоначчи, F(6), используя этот процесс.
Сначала определите подзадачи, которые необходимо решить.
F(n) = F(n-1) + F(n-2) для n > 1
Следовательно: F(6) = F(5) + F(4)
Ф(5) = Ф(4) + Ф(3)
Ф(4) = Ф(3) + Ф(2)
Ф(3) = Ф(2) + Ф(1)
Ф(2) = Ф(1) + Ф(0)
F(1) = 1
Ф(0) = 0
Второй шаг включает в себя решение каждой подзадачи с использованием рекурсивной функции или итеративного процесса. Мы решаем подзадачи от самой маленькой до самой большой, повторно используя результаты более мелких подзадач. Это дает нам следующее:
Ф(0) = 0
F(1) = 1
F(2) = F(1) + F(0) = 1 + 0 = 1
F(3) = F(2) + F(1) = 1 + 1 = 2
F(4) = F(3) + F(2) = 2 + 1 = 3
F(5) = F(4) + F(3) = 3 + 2 = 5
F(6) = F(5) + F(4) = 5 + 3 = 8
Когда мы решаем каждую из подзадач, мы сохраняем решения в массиве или таблице, чтобы их можно было повторно использовать при решении более крупных подзадач, например:
Как только все подзадачи решены, мы используем решения для построения решения исходной задачи.
В этом случае решением исходной проблемы является 6-е число Фибоначчи, которое находится путем суммирования результатов F (5) и F (4), подзадач, определенных из самой большой проблемы. Результат дает нам 8.
Где и почему используется динамическое программирование?
Динамическое программирование используется в тех областях, где у нас есть проблемы, которые можно разделить на более мелкие подзадачи, а их решения используются для решения более крупных проблем.
Эти области включают информатику, экономику, математику и инженерию. В информатике он используется для решения задач, связанных с последовательностями, графами и целочисленными значениями, а также в соревновательном программировании.
В экономике он используется для решения задач оптимизации финансов, производства и распределения ресурсов. В математике динамическое программирование используется в теории игр, статистике и вероятности, где оно используется для решения задач оптимизации.
В инженерии он используется для решения проблем распределения ресурсов, планирования, производства, связи и систем управления.
Использование динамического программирования для решения задач оптимизации имеет несколько преимуществ:
Когда дело доходит до решения задач оптимизации, динамическое программирование является очень полезным инструментом для обеспечения эффективности решений.
Подходы, используемые в динамическом программировании
В динамическом программировании для решения задач оптимизации используются два подхода. Это подход «сверху вниз» и подход «снизу вверх».
Нисходящий подход
Этот подход также известен как мемоизация. Мемоизация — это метод оптимизации, который в основном используется для ускорения работы компьютерных программ за счет сохранения результатов вызовов функций в кэше и возврата кэшированных результатов в следующий раз, когда они потребуются, а не путем их повторного вычисления.
Нисходящий подход включает рекурсию и кэширование. Рекурсия включает в себя функцию, вызывающую саму себя с более простыми версиями проблемы в качестве аргумента. Рекурсия используется для разбиения проблемы на более мелкие подзадачи и решения подзадач.
Как только подзадача решена, ее результат кэшируется и повторно используется всякий раз, когда возникает аналогичная проблема. Метод «сверху вниз» прост для понимания и реализации и решает подзадачу только один раз. Однако недостатком этого является то, что он занимает много памяти из-за рекурсии. Это может привести к ошибке переполнения стека.
Подход «снизу вверх
Восходящий подход, также известный как табулирование, устраняет рекурсию, заменяя ее итерацией, что позволяет избежать ошибок переполнения стека.
В этом подходе большая проблема разбивается на более мелкие подзадачи, а решения подзадач используются для решения более крупной проблемы.
Меньшие подзадачи сначала решаются от наибольшей к наименьшей, а их результаты сохраняются в матрице, массиве или таблице, отсюда и название табуляция.
Сохраненные результаты решают более крупные проблемы, которые зависят от подзадач. Затем результат исходной задачи находится путем решения самой большой подзадачи с использованием ранее вычисленных значений.
Преимущество этого подхода в том, что он экономит память и время за счет отказа от рекурсии.
Примеры задач, которые можно решить с помощью динамического программирования
Ниже приведены некоторые проблемы программирования, которые можно решить с помощью динамического программирования:
№1. Проблема с рюкзаком
Источник: Википедия
Рюкзак — это сумка из холста, нейлона или кожи, обычно пристегивающаяся на спине и используемая солдатами и туристами для переноски припасов.
В задаче о рюкзаке вам предоставляется рюкзак, и, учитывая его грузоподъемность, вы должны выбрать предметы, каждый из которых имеет свою ценность. Ваш выбор должен быть таким, чтобы вы получили максимальную общую стоимость выбранных предметов, а вес предметов был меньше или равен вместимости рюкзака.
Пример задачи о рюкзаке приведен ниже:
Представьте, что вы собираетесь в поход и у вас есть рюкзак вместимостью 15 килограммов. У вас есть список предметов, которые вы можете взять с собой, а также их стоимость и вес, как показано в таблице ниже:
ПредметЗначениеВесПалатка2003Спальный мешок1502Плита501Еда1002Бутылка с водой100,5Аптечка251
Выберите подмножество предметов, которые нужно взять с собой, так, чтобы общая стоимость предметов была максимальной, а общий вес был меньше или равен вместимости рюкзака, которая составляет 15 килограммов.
Реальные приложения проблемы рюкзака включают в себя выбор ценных бумаг для добавления в портфель, чтобы минимизировать риск и максимизировать прибыль, а также поиск наименее расточительных способов сокращения сырья.
№ 2. Проблема планирования
Задача планирования — это задача оптимизации, целью которой является оптимальное распределение задач по набору ресурсов. Ресурсами могут быть машины, персонал или другие ресурсы, используемые для выполнения задач.
Ниже приведен пример задачи планирования:
Представьте, что вы руководитель проекта, ответственный за планирование набора задач, которые должны быть выполнены командой сотрудников. У каждой задачи есть время начала, время окончания и список сотрудников, которые имеют право ее выполнять.
Вот таблица, в которой описаны задачи и их характеристики:
ЗадачаВремя началаВремя окончанияКвалифицированные сотрудникиT1911A, B, CT21012A, CT31113B, CT41214A, B
Назначьте каждую задачу сотруднику, чтобы минимизировать общее время выполнения.
Проблема планирования может возникнуть в обрабатывающей промышленности при попытке оптимизировать распределение ресурсов, таких как машины, материалы, инструменты и рабочая сила.
С ним также можно столкнуться в здравоохранении при оптимизации использования коек, персонала и предметов медицинского назначения. Другими отраслями, в которых может возникнуть эта проблема, являются управление проектами, управление цепочками поставок и образование.
№3. Задача коммивояжера
Источник: Википедия
Это одна из наиболее изученных задач оптимизации, которую можно решить с помощью динамического программирования.
Задача коммивояжера содержит список городов и расстояния между каждой парой городов. Вам необходимо найти кратчайший маршрут, который проходит через каждый город ровно один раз и возвращается в исходный город.
Пример задачи коммивояжера приведен ниже:
Представьте, что вы продавец, которому нужно посетить множество городов в кратчайшие сроки. У вас есть список городов, которые вам нужно посетить, и расстояния между каждой парой городов, как показано в таблице ниже:
ГородABCDEA010152030B100352515C153503020D202530010E301520100
С проблемой коммивояжера можно столкнуться в индустрии досуга при планировании маршрутов для туристов, в логистике при планировании отгрузки товаров, в транспорте при планировании автобусных маршрутов, в сфере продаж и т.д.
Ясно, что динамическое программирование имеет много реальных применений, что помогает узнать о нем больше.
Рассмотрите следующие ресурсы, чтобы расширить свои знания о динамическом программировании.
Ресурсы
Динамическое программирование Ричарда Беллмана
«Динамическое программирование» — книга Ричарда Беллмана, который придумал динамическое программирование и разработал его на ранних стадиях.
Книга написана простым для понимания языком, для понимания текста требуются лишь базовые знания математики и исчисления. В книге Беллман представляет математическую теорию многоэтапного процесса принятия решений, которая является ключевой в динамическом программировании.
Затем в книге рассматриваются проблемы узких мест в многостадийных производственных процессах, теоремы существования и единственности, а также уравнение оптимального запаса.
Лучшее в книге то, что Беллман предлагает примеры многих сложных проблем в таких областях, как логистика, теория планирования, теория связи, математическая экономика и процессы управления, и показывает, как динамическое программирование может решить эти проблемы.
Книга доступна в версиях для Kindle, в твердом переплете и в мягкой обложке.
Мастер-курс по алгоритмам динамического программирования
Этот мастер-курс по алгоритмам динамического программирования от Udemy предлагают Апаар Камаль, инженер-программист в Google, и Пратик Наранг, который также работал с Google.
Курс оптимизирован, чтобы помочь учащимся преуспеть в соревнованиях по программированию, в которых много задач, требующих динамического программирования.
Помимо конкурентов по программированию, курс идеально подходит для программистов, желающих улучшить свое понимание алгоритмов, и людей, готовящихся к собеседованиям по программированию и онлайн-раундам кодирования.
Курс продолжительностью более 40 часов подробно описывает динамическое программирование. Курс сначала предлагает освежить в памяти такие понятия, как рекурсия и поиск с возвратом.
Затем он охватывает динамическое программирование в теории игр, строки, деревья и графы, возведение матриц в степень, битовые маски, комбинаторику и подпоследовательности, проблемы разделения и многомерное динамическое программирование, а также многие другие концепции.
Основы конкурентного программирования, мастер-алгоритмы
Udemy предлагает курс по основам конкурентного программирования от Пратика Наранга и Амала Камаара, который охватывает динамическое программирование, математику, теорию чисел и сложные структуры данных и алгоритмы таким образом, чтобы это было полезно и актуально для конкурентоспособных программистов.
Курс предлагает освежить знания о структурах данных и алгоритмах, прежде чем погрузиться в более сложные алгоритмы и методы, которые пригодятся в соревновательном программировании.
Курс охватывает динамическое программирование, математику, теорию игр, сопоставление с образцом, битмаскирование и множество передовых алгоритмов, используемых и протестированных на соревнованиях по программированию.
Курс Udemy разделен на 10 модулей и 42 раздела и предлагает множество практических вопросов после каждого раздела. Этот курс-бестселлер является обязательным для всех, кто интересуется соревновательным программированием.
Заключительные слова
Динамическое программирование — это полезный навык для любого программиста, который может научиться улучшать решение реальных задач. Поэтому программистам следует рассмотреть возможность использования предложенных ресурсов, чтобы добавить этот важный инструмент в свой набор инструментов.
Затем вы можете проверить языки программирования для использования в науке о данных.