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

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

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

(i) Количество подзадач ограничено полиномиальной зависимостью.

(ii) Решение исходной задачи легко вычисляется по решениям подзадач. (На- пример, исходная задача может быть одной из подзадач.)

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

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

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

6.3.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

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

  1. Основной курс (Программирование)
  2. Программирования основные понятия
  3. СТЕРЕОТИП ДИНАМИЧЕСКИЙ
  4. ПСИХОЛОГИЯ ДИНАМИЧЕСКАЯ
  5. Иванова Г.С. Основы программирования, 2002
  6. ПСИХИКА: ПОНИМАНИЕ ДИНАМИЧЕСКОЕ
  7. В динамических методах
  8. АНАЛИЗ КАУЗАЛЬНО-ДИНАМИЧЕСКИЙ
  9. Динамическая медитация
  10. Динамический смысл аспектов
  11. О. Л. Голицына, Т. Л. Партыка, И. И. Попов. ЯЗЫКИ ПРОГРАММИРОВАНИЯ, 2008