Введение

Метод оптимизации задач. Динамическое программирование — это как математический метод оптимизации, так и алгоритмическая парадигма. Метод был разработан Ричардом Беллманом в 1950-х годах и нашёл применение в многочисленных областях, от аэрокосмической инженерии до экономики. В обоих случаях он заключается в упрощении сложной задачи путём её разбиения на более простые подзадачи рекурсивным способом. Хотя некоторые задачи принятия решений нельзя разбить таким образом, решения, охватывающие несколько моментов времени, часто могут быть рекурсивно разделены на подзадачи. Аналогично, в информатике, если задачу можно оптимально решить, разбивая её на подзадачи и затем рекурсивно находя оптимальные решения этих подзадач, то говорят, что она обладает оптимальной подструктурой. Если подзадачи могут быть рекурсивно вложены в более крупные задачи, что делает применимыми методы динамического программирования, то существует связь между значением исходной задачи и значениями подзадач. В литературе по оптимизации это соотношение называется уравнением Беллмана.

Математическая оптимизация

В терминах математической оптимизации динамическое программирование обычно подразумевает упрощение процесса принятия решения путем его разбиения на последовательность шагов принятия решений во времени. Это достигается путем определения последовательности функций ценности V1, V2, …, Vn, принимающих y в качестве аргумента, представляющего состояние системы в моменты времени i от 1 до n.

Определение Vn(y) – это ценность, полученная в состоянии y в последний момент времени n.

Значения Vi для более ранних моментов времени i = n–1, n–2, …, 2, 1 можно найти, двигаясь в обратном направлении, используя рекурсивное соотношение, называемое уравнением Беллмана. Для i = 2, …, n, Vi–1 в любом состоянии y вычисляется из Vi путем максимизации простой функции (обычно суммы) выигрыша от решения в момент времени i–1 и функции Vi в новом состоянии системы, если это решение принято. Поскольку Vi уже вычислено для необходимых состояний, указанная операция дает Vi–1 для этих состояний. Наконец, V1 в начальном состоянии системы представляет собой ценность оптимального решения. Оптимальные значения переменных решения могут быть восстановлены последовательно, отслеживая уже выполненные вычисления.

Информатика

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

Биоинформатика

Динамическое программирование широко используется в биоинформатике для решения таких задач, как выравнивание последовательностей, сворачивание белка, предсказание структуры РНК и связывание белка с ДНК. Первые алгоритмы динамического программирования для анализа связывания белка с ДНК были разработаны в 1970-х годах независимо друг от друга Чарльзом ДеЛизи в США и Георгием Гурским и Александром Заседателевым в СССР. В последнее время эти алгоритмы приобрели большую популярность в биоинформатике и вычислительной биологии, особенно в исследованиях позиционирования нуклеосом и связывания факторов транскрипции.

Выровнение последовательности

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

Более быстрый DP-решение с использованием другой параметризации

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

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

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

Тогда задача эквивалентна нахождению минимального такого, что .

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

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