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

Итак, описанная процедура дает второй эффективный алгоритм решения задачи взвешенного интервального планирования. Разумеется, на концептуальном уровне между двумя решениями существует много общего, поскольку оба решения обусловлены информацией, содержащейся в рекуррентном отношении (6.1).

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

Но в каждом из рассматриваемых случаев существует эквивалентная формулировка алгоритма с мемоизированной рекурсией.

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

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

  • Количество подзадач ограничено полиномиальной зависимостью.
  • Решение исходной задачи легко вычисляется по решениям подзадач. (Например, исходная задача может быть одной из подзадач.)
  • Существует естественное упорядочение подзадач от «меньшей» к «большей» в совокупности с легко вычисляемой рекуррентностью (как в (6.1) и (6.2)), которая позволяет определить решение подзадачи по решениям некоторого количества меньших подзадач.

Естественно, это всего лишь неформальные ориентиры. В частности, понятие «меньшего» из части (iii) зависит от типа рекуррентности.

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

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

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

Узнай цену консультации

"Да забей ты на эти дипломы и экзамены!” (дворник Кузьмич)